CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 4 of 7 · 2 min read

When linearizability is needed

Locks, uniqueness and cross-channel timing.

Think of a single ticket window for the last concert seat. If there were two windows with separate lists, both might sell the last seat. For some jobs, there must be one agreed answer.

The book lists the cases where linearizability is important.

Locking and leader election. A system with a single leader must be sure there is only one leader (the book calls two leaders "split brain"). If the leader is chosen by a lock, then all nodes must agree who owns the lock, so the lock must be linearizable. ZooKeeper and etcd are used for this. They use consensus (module 8) to make operations linearizable. The book adds a detail: their writes are linearizable but reads may be stale unless you ask for a linearizable read.

Uniqueness and constraints. A user name must be unique, a bank balance must not go negative, stock must not be oversold, two people must not book the same seat. These are like a compare-and-set on a single up-to-date value that all nodes agree on. A hard uniqueness rule needs linearizability. The book says many real systems treat such constraints loosely, as when an overbooked flight is fixed by compensation. In that case linearizability may not be needed. Foreign keys and attribute checks can be enforced without it.

Cross-channel timing. The book's example: a user uploads a photo. The web server stores it in a file service and then puts a "resize this" message on a queue. If the file store is not linearizable, the resizer might read the file before the new version is visible, find the old or missing one, and produce a bad thumbnail. There are two channels (the queue and the file store), and the system only works if the second sees what the first promised. Linearizability makes causality hold across channels without extra work.

A worked example. Two people register the name "sam" at the same moment through different replicas.

Design Result
Each replica checks its own copy Both see "free", both create "sam". Two users, one name
One linearizable store with compare-and-set (set name=sam if absent) The store orders the two requests. The first wins, the second gets an error

Check yourself:

  • Why must a leader lock be linearizable?
  • Which constraints can be enforced without linearizability?