To understand linearizability better, let’s look at more examples. Figure 10-2 shows three clients concurrently reading and writing the same object x in a linearizable database. In distributed systems theory, x is called a register—in practice, it could be one key in a key-value store, one row in a relational database, or one document in a document database, for example.
Diagram showing Client C writing to a register, while Clients A and B alternate in reading the register. Reads that overlap in time with the write may or may not return the written value, but reads that begin after the write is complete return the new value.
Figure 10-2. If a read request is concurrent with a write request, it may return either the old or the new value.
For simplicity, Figure 10-2 shows only the requests from the clients’ point of view, not the internals of the database. Each bar is a request made by a client. The start of the bar is the time when the request was sent, and the end of the bar is when the response was received by the client. Because of variable network delays, a client doesn’t know exactly when the database processed its request. It knows only that it must have happened sometime between the client sending the request and receiving the response.
In this example, the register has two types of operations:
-
Read(x) ⇒ v means the client requested to read the value of register x, and the database returned the value v.
-
Write(x, v) ⇒ r means the client requested to set the register x to value v, and the database returned response r (which could be OK or Error).
In Figure 10-2, the value of x is initially 0, and client C performs a write request to set it to 1. While this is happening, clients A and B are repeatedly polling the database to read the latest value. What are the possible responses that A and B might get for their read requests?
Let’s break it down:
-
The first read operation by client A completes before the write begins, so it must return the old value, 0.
-
The last read by client A begins after the write has completed, so if the database is linearizable, it must return the new value, 1, because the read must be processed after the write.
-
Any read operations that overlap in time with the write operation might return either 0 or 1, because we don’t know whether the write has taken effect at the time when the read operation is processed. These operations are concurrent with the write.
However, this is not yet sufficient to fully describe linearizability. If reads that are concurrent with a write can return either the old or the new value, then readers could see a value flip back and forth between the old and the new value several times while a write is going on. That is not what we expect of a system that emulates “a single copy of the data.”
To make the system linearizable, we need to add another constraint, illustrated in Figure 10-3.
Same as the previous diagram, but with an additional restriction: once Client A has read the new value, the subsequent read by Client B must also return that value.
Figure 10-3. After any one read has returned the new value, all following reads (on the same or other clients) must also return the new value.
In a linearizable system, we imagine that there must be some point in time (between the start and end of the write operation) at which the value of x atomically flips from 0 to 1. Thus, if one client’s read returns the new value 1, all subsequent reads must also return the new value, even if the write operation has not yet completed.
This timing dependency is illustrated with an arrow in Figure 10-3. Client A is the first to read the new value, 1. Just after A’s read returns, B begins a new read. Since B’s read occurs strictly after A’s read, it must also return 1, even though the write by C is still ongoing. (It’s the same situation as with Aaliyah and Bryce in Figure 10-1: after Aaliyah has read the new value, Bryce also expects to read the new value.)
We can further refine this timing diagram to visualize each operation taking effect atomically at some point in time, as in the more complex example shown in Figure 10-4. In this example, we add a third type of operation besides read and write:
CAS(x, vold, vnew) ⇒ r means the client requested an atomic CAS operation (see “Conditional writes (compare-and-set)”). If the current value of the register x equals vold, it should be atomically set to vnew. If the value of x is different from vold, then the operation should leave the register unchanged and return an error. r is the database’s response (OK or Error).
Each operation in Figure 10-4 is marked with a vertical line (inside the bar for each operation) at the time when we think the operation was executed. Those markers are joined up in a sequential order, and the result must be a valid sequence of reads and writes for a register (every read must return the value set by the most recent write).
The requirement of linearizability is that the lines joining up the operation markers always move forward in time (from left to right), never backward. This requirement ensures the recency guarantee we discussed earlier: once a new value has been written or read, all subsequent reads see the value that was written, until it is overwritten again.
Diagram illustrating client operations over time to show linearizability, with a highlighted point where read by Client B is not linearizable.
Figure 10-4. Visualizing the points in time at which the reads and writes appear to have taken effect—the final read by B is not linearizable
There are a few interesting details to point out in Figure 10-4:
-
First client B sent a request to read x, then client D sent a request to set x to 0, and then client A sent a request to set x to 1. Nevertheless, the value returned to B’s read is 1 (the value written by A). This is OK: it means that the database first processed D’s write, then A’s write, and finally B’s read. Although this is not the order in which the requests were sent, it’s an acceptable order, because the three requests are concurrent. Perhaps B’s read request was slightly delayed in the network, so it reached the database only after the two writes.
-
Client B’s read returned 1 before client A received its response from the database saying that the write of the value 1 was successful. This is also OK, because it just means the OK response from the database to client A was slightly delayed in the network.
-
This model doesn’t assume any transaction isolation; another client may change a value at any time. For example, C first reads 1 and then reads 2, because the value was changed by B between the two reads. An atomic CAS operation can be used to check that the value hasn’t been concurrently changed by another client: B and C’s CAS requests succeed, but D’s CAS request fails (by the time the database processes it, the value of x is no longer 0).
-
The final read by client B (in a shaded bar) is not linearizable. The operation is concurrent with C’s CAS write, which updates x from 2 to 4. In the absence of other requests, it would be OK for B’s read to return 2. However, client A had already read the new value (4) before B’s read started, so B is not allowed to read an older value than A. Again, it’s the same situation as with Aaliyah and Bryce in Figure 10-1.
That is the intuition behind linearizability; the formal definition describes it more precisely. It is possible (though computationally expensive) to test whether a system’s behavior is linearizable by recording the timings of all requests and responses and checking whether they can be arranged into a valid sequential order.
Just as there are various weaker isolation levels for transactions besides serializability (see “Weak Isolation Levels”), there are various weaker consistency models for replicated systems besides linearizability. The guarantees of read-after-write consistency, monotonic reads, and consistent prefix reads that we saw in “Problems with Replication Lag” are examples of these. Linearizability includes all these guarantees and more; it the strongest consistency model in common use.