Linearizable Reads

Linearizable means: once a write is acknowledged, every later read — from any client — sees it (or something newer). Time never runs backwards. Raft's write path gives writes this for free: they are committed through one ordered log. Reads are where implementations quietly cheat.

The stale-leader read

The tempting shortcut: reads change nothing, so let the leader answer straight from its local state machine — no log entry, no network, fast. And wrong:

L1 is leader in term 3. A partition cuts it off from the other 4 nodes.
Those 4 elect L2 (term 4). A client acquires a lock: L2 commits lock1=held-by-B.
Another client asks L1: "who holds lock1?"  L1 answers from local state: "nobody".
Two clients now both believe they own lock1.

L1 is not lying — it simply has not heard about term 4 yet, and nothing in its local memory can reveal that. Only the cluster can. Every correct read strategy is a way of asking the cluster, at some price:

Option 0 — read through the log. Commit a no-op read entry, answer when it applies. Fully linearizable; costs an fsync plus a replication round per read. Nobody scales reads this way.

Option 1 — ReadIndex (etcd's default for linearizable reads). Four steps, each load-bearing:

1. read_index = commit_index           # snapshot the commit frontier
2. heartbeat round; majority acks      # proves: still leader as of step 1
3. wait until last_applied >= read_index
4. answer from the state machine

Step 2 without any log write is what makes it cheap — one network round, no fsync. Step 3 is the one people skip: proof of leadership is not enough; the state machine must have applied everything committed at read time, or you serve a value older than an acknowledged write. One extra guard from the thesis: a freshly elected leader does not yet know the commit frontier of prior-term entries, so it must first commit its own term's no-op before serving ReadIndex reads.

Option 2 — lease reads. Skip even the heartbeat: after a successful quorum round at time T, the leader assumes no rival can be elected before the election timeout expires (minus a clock-drift bound), and serves purely local reads inside that lease. Near-zero-cost reads bought with a clock assumption — and a paused VM, GC stall, or clock jump can leave two nodes both "holding" the lease, silently serving stale data. TiKV ships this; know what you are betting on.

Option 3 — follower reads. Serve from followers, accepting bounded staleness — right for analytics, dashboards, caches. (Followers can even serve linearizable reads by first fetching a ReadIndex from the leader: one extra hop, and read throughput scales with cluster size.)

The menu your exercise encodes: mutations always go through the log; strict reads pay for ReadIndex; latency-critical session/token checks ride leases; staleness-tolerant traffic goes to followers.

Your exercise

Classify each scenario line. The grader-caught mistake is keying on the word "linearizable": Linearizable read after a prior commit is a READ and must print READ_INDEX — printing LINEARIZABLE_WRITE because the adjective matched is exactly what the hidden test catches. Mutations hide behind nouns: Banking ledger update must print LINEARIZABLE_WRITE. And Session check on leader lease prints LEASE, while Cached metrics dashboard prints FOLLOWER_READ.