Part 3 of 7 · 3 min read
Linearizability
A recency guarantee: once a new value is seen, no one sees the old one again.
Think of a football score on a phone. Alice sees the final score and shouts it out. Bob, in the next seat, reloads and still sees "not finished". It feels wrong. Bob started his reload after Alice finished hers, so he should see at least what she saw.
That is the example the DDIA book uses, and it is the heart of linearizability.
Linearizability
Linearizability is the guarantee that the system behaves as though there were a single copy of the data and every operation took effect atomically at one moment between its start and its end. Once any read has returned a new value, all later reads must return it too.
Example: a write of x = 1 runs from time 10 to time 20. A read that starts at time 21 must return 1. A read that overlaps the write may return 0 or 1, but if one read returns 1, all reads that start after it ends must also return 1.
The books phrase the idea as follows:
- A write does not happen instantly. It takes time to reach the leader and be executed. It takes effect somewhere between its invocation and its completion.
- A read that starts after a write has completed must see that write.
- Reads that overlap a write may see the old or new value. But to look like a single copy, there must be one point at which the value flips from old to new, and after any read sees the new value, all later reads must too.
The DDIA book also adds a compare-and-set operation to the picture. Each operation can be drawn with a mark at the moment it seems to take effect. The marks must form a valid sequence of reads and writes, and the line joining them must always move forward in time, never back.
Details noted in the book: the order the database processes concurrent requests need not be the order they were sent, and a read may return a value before the writer gets its "ok" reply, since the reply can be slow.
Linearizability versus serializability. The book warns that they sound alike and are different.
| Serializability | Linearizability | |
|---|---|---|
| Kind of guarantee | Isolation of transactions | Recency of reads and writes |
| Scope | Many objects in a transaction | One object (a register) |
| Promise | Same result as some serial order, not necessarily the real order | The real-time order is respected |
| Stops write skew? | Yes | No, not by itself |
A database may offer both, called strict serializability. Implementations by 2PL or actual serial execution are typically linearizable. Serializable snapshot isolation (module 3) is not, because a snapshot by design ignores newer writes.
A worked example, with times in seconds. Write W: x from 0 to 1, runs from t = 10 to t = 20.
| Read | Start | End | Returns | Allowed? |
|---|---|---|---|---|
| R1 | 5 | 8 | 0 | Yes, entirely before W |
| R2 | 12 | 15 | 1 | Yes, overlaps W and the flip happened already |
| R3 | 16 | 18 | 0 | No. It starts after R2 ended with 1, so it must return 1 |
| R4 | 22 | 25 | 1 | Required, starts after W ended |
R3 is the Alice and Bob case.
Check yourself:
- A write runs from t = 5 to t = 9. A read starts at t = 10. What must it return?
- Why does linearizability not stop write skew?