CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 5 of 7 · 2 min read

Which systems can be linearizable

Leaders can, consensus does, multi-leader does not, quorums usually do not.

Think of a single librarian who keeps the master card catalogue. Anyone who asks the librarian gets the latest answer. Photocopies of the catalogue in side rooms may be a day behind.

The books go through the replication styles of Level 4.

Replication style Linearizable? Why
Single leader, reads from the leader or a synchronous follower Potentially One primary copy. But a node may wrongly believe it is the leader, and asynchronous failover can lose writes
Consensus algorithms (ZooKeeper, etcd) Yes They have measures against split brain and stale replicas
Multi-leader No Writes run on several nodes and are copied later, causing conflicts
Leaderless (Dynamo style) Probably not See below

The Understanding Distributed Systems book adds a point: a node that thinks it is the leader must first contact a majority of replicas to confirm it still is, before answering a read. This makes reads slower.

The quorum trap. In leaderless stores, people claim that reading and writing quorums (w + r > n, Level 4) gives strong consistency. The DDIA book shows a counter-example. There are n = 3 replicas, the write goes to all three (w = 3), and readers use r = 2. While the write is in progress, it has reached node 1 only. Client A reads nodes 1 and 2, and sees the new value 1 on node 1. After A finishes, client B reads nodes 2 and 3 and sees only the old value 0. The quorum rule held (3 + 2 > 3), yet B read an older value than A had already seen. It is not linearizable.

It can be repaired at a cost: readers perform read repair before replying, and writers read the latest state first. Riak does not do this because of the performance penalty. Cassandra waits for read repair, but with last write wins it loses linearizability for concurrent writes to one key. The book's conclusion is to assume that Dynamo-style systems do not give linearizability. Last write wins based on clocks (module 4) is almost certainly not linearizable, and sloppy quorums remove any chance.

Common mistake

Believing that "w + r > n" means strong consistency. It means a read overlaps the latest completed write set, but concurrent timing can still show the new value and then the old one.

The price of linearizability. The book gives the key trade-off. Suppose two data centres lose the link between them.

  • With multi-leader replication, each side keeps working and exchanges writes later. Not linearizable, but available.
  • With single-leader replication, clients in the data centre without the leader cannot write, and cannot do linearizable reads. They may read stale data from a local follower, or get an error. Linearizability costs availability.

The DDIA book notes that this holds for any linearizable database on an unreliable network, not only across data centres. Module 7 gives it a name.

Check yourself:

  • Why can a multi-leader database not be linearizable?
  • In the quorum counter-example, what did B read and what should B have read?