System Design · Module 6

Consensus and Coordination: Paxos, Raft, Leases, and ZooKeeper/etcd

Module 3 showed that a leased primary or a quorum needs somewhere to agree on who holds the lease or how many replicas actually answered. This module builds that "somewhere": the consensus problem itself, Raft's leader-election/log-replication/safety decomposition, the Paxos state machines running inside Chubby (under Bigtable) and Spanner's spanservers, leases as consensus's cheap time-bounded cousin, and ZooKeeper's znode-and-watch coordination kernel. After it you can explain why a five-node cluster tolerates exactly two failures, what a lease buys you that a lock doesn't, and which of these four systems you would actually reach for.

Course 40 min read 6 sources As of 2026-09-17 Prerequisite: Module 3
One agreement problem, three production answers Consensus: N unreliable servers agree on one value despite crashes and network delay Raft agrees on: leader + log entries leader election log replication safety etcd, Consul, CockroachDB RAMCloud coordinator Paxos agrees on: master / tablet log entry 5-replica Chubby cell one Paxos group per tablet Chubby under Bigtable Spanner spanservers Zab agrees on: znode writes leader-based atomic broadcast Kafka, HBase service discovery all three tolerate ⌊(N−1)/2⌋ failures out of N replicas
Figure 1. The same agreement problem, answered three ways in production: Raft's leader-election/log-replication/safety decomposition1; Paxos state machines inside Chubby (behind Bigtable) and Spanner's spanservers34; and Zab, ZooKeeper's leader-based atomic broadcast protocol2. Sections 2–9 derive each column.

1. The consensus problem

Every mechanism in Module 3 quietly assumed something this module has not yet justified. A leased primary chunkserver in GFS needs a master to grant exactly one lease per chunk, never two at once, even if the master itself can crash and restart. A quorum write in Dynamo needs replicas to eventually agree on which of several concurrent versions of a key is current. Underneath both is the same unsolved problem: how do several machines, connected by a network that can lose, delay, duplicate, or reorder messages, agree on a single value — a leader, a log entry, a lock holder — when any one of them might also crash at an inconvenient moment?

This is the problem the distributed-systems literature calls consensus, and it is usually posed in the context of a replicated state machine: a collection of servers compute identical copies of the same state and can keep functioning even if some of them are down1. Each server holds a log of commands; if every server's log contains the same commands in the same order, and each server is a deterministic state machine, then every server ends up in the same state and produces the same outputs. The entire difficulty of consensus reduces to keeping the logs identical despite failures — which is why Raft's own paper defines a consensus algorithm as the thing whose job is exactly that1.

A practical consensus algorithm has to guarantee two classes of property. Safety means it never returns an incorrect result under any non-Byzantine condition — network delays, partitions, packet loss, duplication, and reordering must never cause two servers to disagree about a committed value, no matter how badly the network behaves. Liveness (the paper's word is availability) means the system stays fully functional as long as a majority of servers can reach each other and the client, and does not depend on timing to guarantee that: faulty clocks and extreme message delays can, at worst, cause an availability problem, never a safety one1.

The majority requirement is the load-bearing arithmetic of every algorithm in this module. If a cluster has N servers and a value is only considered agreed once a strict majority of them have accepted it, then any two majorities out of the same N servers must overlap in at least one server — which is exactly the mechanism that prevents two conflicting values from ever both being "committed." Writing N = 2f + 1, a cluster tolerates the simultaneous failure of any f = (N − 1) / 2 servers while still being able to form a majority among the survivors. A cluster of five servers (f = 2) tolerates the failure of any two1; three servers tolerate one failure; seven tolerate three. Adding a sixth server to a cluster of five buys nothing — six still only tolerates two failures, because a majority of six is four, the same fault tolerance as a majority of three out of five, while consuming an extra machine's worth of state and messages on every write. This is why every production system in this module runs an odd number of replicas: five for Chubby4, five as Raft's own "typical" number1, an odd count for ZooKeeper ensembles2.

Consensus algorithms that predate Raft are almost all descendants of, or explicit alternatives to, Leslie Lamport's Paxos protocol, which has "dominated the discussion of consensus algorithms over the last decade" and underlies most production implementations even where its details differ substantially from the original description1. The rest of this module follows two parallel tracks: Sections 2–5 derive Raft's mechanism in enough detail that you can read its safety proof sketch and believe it; Sections 6–7 look at what Paxos actually looks like once it is running inside two systems you already have a stake in — Bigtable's Chubby lock service and Spanner's spanservers. Section 8 pulls out leases as the cheap, time-bounded shortcut that both GFS (Module 3) and Chubby use instead of full consensus on every operation. Section 9 covers ZooKeeper, which packages a Paxos-family protocol (Zab) behind an API deliberately shaped like a filesystem so that applications, not the coordination service, decide what "lock" or "leader" means.

2. Raft: leader election

Raft's answer to consensus starts from a deliberately narrow decomposition: solve leader election, log replication, and safety as three relatively independent subproblems instead of one dense protocol1. This section covers the first piece.

2.1 Terms, three states, and RequestVote

A Raft server is always in exactly one of three states: leader, follower, or candidate. In normal operation there is exactly one leader, and every other server is a follower — passive, issuing no requests of its own, simply responding to RPCs from leaders and candidates1. Time is divided into terms, numbered with consecutive integers; each term begins with an election, and if a candidate wins it serves as leader for the rest of that term. Terms act as a logical clock: every RPC carries the sender's current term, and any server that sees a higher term than its own immediately updates itself and, if it was a leader or candidate, reverts to follower1. A stale leader that has been partitioned away and comes back will discover a higher term from the first RPC it receives or sends and step down — the term number, not a global clock, is what makes an old leader recognize its own obsolescence.

Raft servers communicate with only two RPC types. RequestVote is issued by a candidate to every other server to gather votes; a server grants its vote at most once per term, on a first-come-first-served basis, and only if the candidate's log is at least as up to date as its own (the safety-critical restriction covered in Section 4.1)1. AppendEntries is issued by a leader both to replicate log entries and, sent with an empty entry list, as a heartbeat that tells followers a leader is still alive1.

Raft server states: follower, candidate, leader, with randomized election timeouts Follower Candidate Leader times out, starts election wins majority of votes split vote: times out, new term discovers leader or higher term discovers server with higher term (rare) election timeout: random in [150, 300] ms sends heartbeats every idle period to prevent timeouts
Figure 2. Raft's three server states. A follower that hears no AppendEntries or vote request within a randomized election timeout — chosen uniformly from 150–300 ms in the reference implementation — becomes a candidate and starts an election; it becomes leader only on receiving votes from a majority of the full cluster1. The randomization is what keeps split votes rare, as Section 2.2 derives.

2.2 Randomized timeouts and why they prevent repeated split votes

A naive leader-election scheme — every follower starts an election the instant it stops hearing from a leader — fails badly: if two or more followers time out within the same narrow window, they all become candidates simultaneously, votes split with no one reaching a majority, and the term ends with no leader elected at all. Without a fix, this can repeat indefinitely.

Raft's fix is to choose each server's election timeout randomly, independently, from a fixed interval, e.g. 150–300 ms1. Because the timeouts are spread out, in most cases only a single server times out first; it starts an election, wins it, and sends heartbeats to the rest of the cluster before any other server's timeout can even elapse. The same randomization resolves split votes when they do occur, since each candidate restarts its own randomized timer at the start of every new election, making a second simultaneous timeout increasingly unlikely with each retry1.

The paper measured this directly. With no randomization at all, leader election consistently took over 10 seconds in their tests due to repeated split votes. Adding just 5 ms of randomness dropped the median downtime to 287 ms; with 50 ms of randomness the worst observed completion time across more than 1,000 trials was 513 ms — the measurements were taken on a 5-server cluster with a broadcast time of roughly 15 ms1. Section 5 turns this broadcast-time number into the general timing inequality that governs how aggressive an election timeout can safely be.

3. Raft: log replication and commit

3.1 AppendEntries and the log matching property

Once elected, the leader services every client request. It appends the command to its own log as a new entry, then issues AppendEntries RPCs in parallel to every other server to replicate that entry1. Each log entry stores a state-machine command plus the term in which the leader received it, and an index identifying its position. The leader maintains, for every follower, a nextIndex — the index of the next entry to send that follower — and retries indefinitely if a follower is slow or a packet is lost, even after it has already responded to the client1.

Consistency between logs is enforced by a single check built into AppendEntries: the leader includes the index and term of the entry immediately preceding the new ones, and a follower refuses the request if its own log doesn't contain an entry with that exact index and term. This one check, applied inductively from the initial empty state of every log, guarantees the Log Matching Property: if two logs contain an entry with the same index and term, every entry up through that index is identical in both logs1. When a follower's log has fallen out of sync with the leader's — because it missed entries during a period of unavailability, or because it holds entries a former leader never finished committing — the leader simply forces the follower to overwrite its log with the leader's own, working backward from nextIndex until the consistency check succeeds1. Raft never has to reconcile diverging histories with a merge; it always resolves them by having the follower discard and copy, because the Leader Append-Only property guarantees a leader never overwrites or deletes entries in its own log, only appends to it1.

3.2 Majority commit: a minority of slow servers cannot slow the system down

An entry is committed once the leader that created it has replicated it on a majority of the servers1 — not all of them. This single design choice is what gives Raft (and every majority-quorum protocol in this module) its central performance property: "a command can complete as soon as a majority of the cluster has responded to a single round of remote procedure calls; a minority of slow servers need not impact overall system performance"1. A five-server cluster commits as soon as the leader plus any two followers have the entry durably in their logs — the remaining two followers can be arbitrarily slow, briefly partitioned, or simply behind, and the client still gets an answer at the latency of the third-fastest round trip, not the fifth.

Once a follower learns an entry is committed — the leader tracks the highest committed index and piggybacks it on future AppendEntries calls, including heartbeats — it applies that entry to its own local state machine in log order1. Committing an entry also, as a consequence of the Log Matching Property, commits every entry that precedes it in the leader's log, including entries created by previous leaders.

Leader replicates a log entry to a majority; a minority straggler does not block the commit S1 (leader) 5 6 7 S2 (follower) 5 6 7 acked S3 (follower) 5 6 7 acked S4 (follower) 5 unreachable — behind, not yet contacted S5 (follower) 5 6 slow — round trip still in flight entries 5–6 already committed Entry 7: leader (S1) + S2 + S3 = 3 of 5 → majority → committed S4, S5 do not need to ack for entry 7 to commit
Figure 3. Leader S1 replicates entry 7 to S2 and S3; together with the leader that is 3 of 5 servers, a majority, so entry 7 commits and the leader applies it and answers the client — S4 (unreachable) and S5 (mid-round-trip) never need to respond1.

4. Raft: safety and cluster membership changes

4.1 The election restriction and the no-op entry

Leader election and log replication alone are not sufficient for correctness. A follower might be unavailable while the leader commits several entries, then get elected leader itself and overwrite those committed entries with different ones — which would let different state machines execute different command sequences, violating the entire point of replication1. Raft closes this gap with a restriction on who is allowed to win an election: a candidate can only be elected if its log is at least as up to date as a majority of the cluster's, which RequestVote enforces by having voters compare the index and term of each log's last entry and refuse a vote to any candidate whose log looks less current1. Because every committed entry is, by definition, present on a majority of servers, and a candidate must contact a majority to win, this guarantees at least one voter in that majority already holds every committed entry — so any candidate whose log is at least as up to date as that voter's must also hold everything committed. This is the Leader Completeness Property: a leader for any term contains all entries committed in previous terms1.

There's a subtler wrinkle. A leader cannot always tell, just by counting replicas, whether an entry from an earlier term is safely committed — a majority might hold it today, yet a future leader elected without ever seeing that specific entry replicated at the moment of its own election could still overwrite it, because Raft's commitment rule only counts replicas while the entry's original leader is still in charge. Raft's fix is conservative rather than clever: it never commits a log entry from a previous term by counting replicas alone. Only entries from the leader's current term are committed by direct replica count; because of the Log Matching Property, committing a current-term entry indirectly commits every entry that precedes it, previous terms included1. In practice this means every new leader appends a blank no-op entry to its log at the start of its term and waits for that entry to commit before answering any client request that depends on the state of prior entries — once its own term has one committed entry, everything before it is safely committed too1. The same mechanism underwrites linearizable reads: a leader that has just been elected may not yet know which entries are actually committed, so before answering a read-only request it must confirm its own leadership is still current by exchanging heartbeats with a majority of the cluster1.

4.2 Joint consensus for membership changes

Raft's cluster configuration — the set of servers participating — is not fixed forever; replacing a failed machine or changing the replication factor requires changing it live, without taking the cluster offline1. The obvious approach, switching every server directly from the old configuration to the new one, is unsafe: because servers cannot all switch at the same instant, there is necessarily a window during which some servers are still using the old configuration and others are already using the new one, and it becomes possible for the cluster to elect two leaders for the same term — one voted in by a majority of the old configuration, another by a majority of the new one, each unaware of the other1.

Raft avoids this by routing every membership change through an intermediate joint consensus configuration that combines both the old and new server sets. While the cluster is in the joint configuration, log entries are replicated to servers in both configurations, and agreement for elections and entry commitment separately requires a majority of the old configuration and a majority of the new configuration1. Because any majority-of-old and any majority-of-new configuration are guaranteed to overlap during the joint phase (that overlap is the entire point of the design), there is never a moment when two disjoint majorities can both elect a leader for the same term. The joint configuration is itself just a log entry — the leader commits Cold,new the same way it commits any other entry, and only once that has committed does it create and commit a further entry for the new configuration Cnew alone. If the leader is not part of Cnew, it steps down to follower the moment Cnew commits, since that is the first point at which the new configuration can safely operate independently1.

5. Timing requirements: deriving the 150–300 ms election timeout

Raft's safety never depends on timing — an unusually slow network cannot make it produce a wrong answer, only a slow one1. Availability is a different story: if a leader crashes, the cluster is unavailable until a new one is elected, and how quickly that happens is governed entirely by clock behavior. Raft states this as a single timing requirement:

$$\text{broadcastTime} \ll \text{electionTimeout} \ll \text{MTBF}$$

where broadcastTime is the average time for a server to send RPCs in parallel to every other server in the cluster and receive their responses, electionTimeout is the randomized timeout from Section 2.2, and MTBF is the mean time between failures for a single server1. Both inequalities are load-bearing and asymmetric for different reasons.

The left inequality — broadcast time an order of magnitude below election timeout — exists so that a healthy leader can reliably get a heartbeat out to every follower well before any follower's timer expires; if the two were close, ordinary network jitter would trigger unnecessary elections even with no actual failure. The right inequality — election timeout a few orders of magnitude below MTBF — exists so the system spends only a small fraction of its uptime unavailable: when a leader does crash, the cluster is down for roughly one election timeout while a new leader is chosen, and that downtime should be a rounding error against how often a server fails at all1.

Raft's own numbers make the inequality concrete rather than aspirational. Because Raft's RPCs typically require the recipient to persist information to stable storage before responding, broadcast time is set mostly by the storage medium and ranges from about 0.5 ms to 20 ms depending on the technology; this pushes the election timeout into the 10–500 ms range, and Raft's authors settle on 150–300 ms as the recommendation that will "unlikely cause unnecessary leader changes and will still provide good availability"1. On the other side of the inequality, typical server MTBFs run to several months or more, which "easily satisfies the timing requirement" against an election timeout measured in hundreds of milliseconds — the ratio between the two is on the order of 108 or higher1. The cluster used for the split-vote measurements in Section 2.2 had a measured broadcast time of roughly 15 ms1, comfortably inside the 0.5–20 ms band the paper describes, which is exactly why 150–300 ms — ten to twenty broadcast times — produced the sub-second recovery times reported there.

6. Paxos in production: Chubby under Bigtable

Raft's own paper is candid about why Paxos was worth replacing as a teaching tool: "Paxos is quite difficult to understand, in spite of numerous attempts to make it more approachable," its formulation as single-decree consensus composed into multi-decree Paxos leaves "no widely agreed-upon algorithm," and systems that implement it, including Chubby, have historically not published their details — to the point that Raft quotes Chubby's own implementers describing "significant gaps between the description of the Paxos algorithm and the needs of a real-world system," such that their final system ended up "based on an unproven protocol"1. None of that stopped Paxos from becoming the consensus protocol underneath two of the most consequential storage systems Google has published: Bigtable, via the Chubby lock service, and Spanner, directly in every spanserver (Section 7).

6.1 Chubby's own consensus: master election, master lease, and session lease

Chubby is a lock service, not a consensus library: Google chose to expose a small set of servers behind a lock-file API rather than ship every application team a Paxos library to link against, on the reasoning that a lock service reduces the number of servers a client system needs to run to make progress reliably — even a single client process using a lock service can obtain a lock and proceed safely, whereas a library-based approach still needs each application to run and keep alive its own quorum of consensus participants6. A Chubby cell typically consists of five servers called replicas, placed to reduce the likelihood of correlated failure (different racks, for example)6. The replicas run a distributed consensus protocol — Paxos63 — to elect one of themselves master; the master must win votes from a majority of the replicas, plus a promise that those replicas will not elect a different master for an interval of a few seconds known as the master lease, periodically renewed as long as the master keeps winning a majority of the vote6. Read requests are answered by the master alone, which is safe exactly as long as the master lease has not expired, since no other master can exist during that interval; write requests are propagated via the consensus protocol to all replicas and acknowledged once a majority has the update6. Master elections are typically fast — two recent elections observed took 6 s and 4 s — though values as high as 30 s have been seen6.

Above the master-election layer, Chubby exposes a second, client-facing lease: each client holds a session with the cell, kept alive by periodic KeepAlive handshakes. The master extends a session's lease timeout by a default of 12 seconds on each successful KeepAlive (an overloaded master may extend by more, to reduce how often it must process them), and a client that goes idle for a minute with no open handles has its session ended6. If a master fails over, clients do not immediately lose their sessions: they enter a grace period, 45 seconds by default, during which the client library blocks the application while it tries to reach a newly elected master and reconstruct the session before treating it as truly expired6. These are three distinct timers at three distinct layers — master lease (replica-to-replica), session lease (master-to-client), and grace period (client's tolerance for a slow failover) — and conflating them is the most common way to misread the paper.

Locks in Chubby are advisory, not mandatory: holding a lock on file F is neither necessary nor sufficient to access F, so a client that ignores the lock protocol can still corrupt shared state, which Google's own developers accepted in exchange for not having to force every application to shut down cleanly for administrative purposes6. To guard against a paused or delayed client acting on a lock it no longer holds, Chubby attaches a monotonically increasing sequencer to each lock acquisition, which a lock holder can pass to a server it talks to so that server can reject a stale request without needing its own session with Chubby6. The most common recipe built on top of this primitive is primary election: every candidate process opens the same lock file and calls Acquire(); exactly one succeeds and becomes primary, and the rest become replicas that discover the primary by reading the file the winner writes its identity into6.

6.2 What Bigtable actually asks Chubby to do

Bigtable relies on Chubby for a specific, narrow list of jobs rather than as a general-purpose database: to ensure there is at most one active Bigtable master at any time; to store the bootstrap location of Bigtable data (the root tablet, in the three-level tablet-location hierarchy); to discover live tablet servers and finalize the death of one that has lost its lock; to store Bigtable's schema information (the column-family list for each table); and to store access control lists3. Each tablet server, on starting, creates and acquires an exclusive lock on a uniquely named file in a Chubby directory Bigtable calls the servers directory; it stops serving the moment it loses that lock — for example because a network partition dropped its Chubby session — and Chubby provides an efficient mechanism for a tablet server to check whether it still holds the lock without incurring network traffic on every check3. The Bigtable master periodically asks each tablet server for the status of its lock, and if the master cannot reach a server or the server reports losing its lock, the master itself attempts to acquire that server's lock file; succeeding proves the tablet server is truly gone (Chubby is live and the file is still lockable), so the master deletes the file, which guarantees the old server can never serve again, and reassigns its tablets3. If Bigtable cannot be sure a network problem is between it and Chubby rather than between it and its tablet servers, the master simply kills itself when its own Chubby session expires — a direct application of the same principle GFS's leases use in Module 3, pushed one layer up.

The measured cost of this dependency is small but not zero. Across 14 Bigtable clusters spanning 11 Chubby instances, Chubby unavailability accounted for an average of 0.0047% of Bigtable server-hours where some stored data was unreachable, with the single worst-affected cluster at 0.0326%3 — three or four nines of Chubby-attributable availability even in Bigtable's own worst case, which is why "if Chubby becomes unavailable for an extended period of time, Bigtable becomes unavailable" is stated as an accepted, bounded cost rather than a design flaw3.

Five Chubby replicas elect a Paxos master; Bigtable's master and tablet servers depend on that master's lock files Chubby cell — 5 replicas, Paxos-elected master R R master R R master lease renewed by majority vote Bigtable master holds unique lock file → only one master exists servers directory one exclusive lock file per live tablet server schema, ACLs, root tablet location stored as small Chubby files measured: 0.0047% of Bigtable server-hours affected by Chubby unavailability (14 clusters)
Figure 4. Chubby's own Paxos-based master election runs inside the dashed cell; Bigtable then layers three uses on top of the resulting single, lease-holding master: exclusive master election for itself, tablet-server liveness via the servers directory, and small-file storage for schema/ACL/bootstrap data36.
Table 1. Chubby production numbers, as measured and documented by Google63.
QuantityValueSource
Replicas per cell5typical, placed to reduce correlated failure
Master lease (replica-to-replica)a few secondsinterval a master's majority promises not to re-elect within
Session lease default extension12 sper successful KeepAlive; raised under heavy load
Idle-session timeout60 sno open handles, no calls for a minute
Grace period (client-observed failover tolerance)45 sdefault; client blocks application calls during it
Observed master election time4–30 stwo elections at 6 s and 4 s typical; up to 30 s seen
Direct clients per master, no proxy90,000seen handled by one 2-CPU 2.6 GHz Xeon master
Write share of RPC traffic<1%KeepAlives dominate at 93% of RPC rate in a snapshot cell
Bigtable server-hours affected by Chubby unavailability0.0047%average across 14 clusters / 11 Chubby instances

7. Paxos in production: Spanner's spanservers

Spanner takes Paxos a layer deeper than Bigtable does: instead of using a Chubby cell as an external lock service that a small number of masters depend on, every spanserver implements a Paxos state machine directly, one per tablet4. A zone in a Spanner universe has one zonemaster and between one hundred and several thousand spanservers, each of which is responsible for 100 to 1,000 of these tablets4. The set of replicas for a given tablet, spread across different zones (Spanner's rough analog of a Bigtable/GFS deployment, usually one per datacenter), is called a Paxos group4. Writes must go through the group's elected leader; reads can be served by any replica sufficiently up to date, which is the same read/write asymmetry Chubby's lock service exhibits at a coarser grain — a single elected authority handles writes, while reads can be spread across replicas once staleness is bounded.

Spanner's Paxos implementation supports long-lived leaders through time-based leader leases, defaulting to 10 seconds, explicitly justified by the same argument Module 3 made for GFS's chunk lease and Section 6.1 made for Chubby's session lease: Spanner is designed for long-lived transactions — a report-generation query might run for minutes — and those perform poorly under optimistic concurrency control if the underlying leader keeps churning4. Every Paxos write is currently logged twice, once in the tablet's own log and once in the Paxos log, a choice the paper calls "expedient" rather than fundamental and expects to fix4.

At each replica that is the group's leader, the spanserver additionally runs a transaction manager and a lock table: the lock table implements two-phase locking by mapping ranges of keys to lock states, and the transaction manager implements a participant leader when a transaction spans more than one Paxos group. If a transaction touches only one group — the common case — it bypasses the transaction manager entirely, since the group's own Paxos-replicated lock table is sufficient; if it spans multiple groups, those groups' leaders coordinate two-phase commit, with one group's leader designated coordinator leader and the others' participant slaves4. This is the concrete instantiation of what Module 4 covered abstractly as two-phase commit over Paxos-replicated groups: Paxos gives each group internal consensus on its own log; 2PC gives multiple such groups an all-or-nothing outcome across the group boundary.

Data placement moves in units called directories — buckets of contiguous keys sharing a prefix — which can be relocated between Paxos groups by a background task (movedir) to shed load, colocate frequently co-accessed data, or move data closer to where it's accessed; a 50 MB directory can typically move between groups in a few seconds4. Movement is deliberately not implemented as a single atomic transaction, since that would block ongoing reads and writes on a data range mid-move; instead movedir moves most of the data in the background and only wraps the final, nominal remainder in an atomic step4. Spanner's authors are explicit about why they were willing to pay the cost of running 2PC over Paxos groups at all, given the availability problems 2PC has historically caused: Bigtable's total lack of cross-row transactions "led to frequent complaints" from application teams, and the alternative — pushing every performance problem onto developers to work around, one bespoke case at a time — was judged worse than paying the latency and availability cost of general transactions up front4. Module 5's PACELC framing gives this choice a name: Spanner pays a latency-for-consistency cost even absent a partition, deliberately, because Bigtable's alternative left that cost on every application team's desk instead.

8. Leases: a time-bounded alternative to indefinite locks

A recurring pattern cuts across every system in this module: instead of running full consensus on every single operation, hand out a time-bounded promise — a lease — and only fall back to consensus to grant, renew, or reassign that promise. A lease is a lock with a clock attached, and the clock is what makes it administratively cheap: whoever grants it never has to wait for an explicit release message from a holder that might have crashed, partitioned away, or simply gone silent, because the promise self-expires2.

Module 3 already derived this pattern once, for GFS: the master grants a 60-second chunk lease to one replica, the primary, which then orders every mutation to that chunk without consulting the master again until the lease needs renewing, and renewal is piggybacked on the heartbeat messages the master and every chunkserver already exchange5. This module has now derived the identical pattern twice more, at two different layers of two different systems. Chubby uses it internally, among its own five replicas, to decide which one gets to be master without re-running an election on every read (Section 6.1); Spanner uses it inside every spanserver's Paxos group, so a leader can serve reads and coordinate long transactions for up to 10 seconds without a fresh round of voting (Section 7). All three leases solve the same problem — bound the blast radius of a slow or failed holder without paying for a fresh consensus round on every operation — at costs and durations tuned to a completely different layer of the stack: file-chunk mutation ordering, cell-wide master election, and per-tablet transaction leadership, respectively.

Table 2. The same time-bounded-promise pattern at three layers, with each system's stated default duration.
SystemWhat the lease decidesDefault durationRenewal path
GFS chunk leasewhich chunkserver orders mutations to one 64 MB chunk60 spiggybacked on master↔chunkserver HeartBeat RPCs5
Chubby master leasewhich of 5 replicas is the cell's single mastera few secondsrenewed while the master keeps winning a majority vote6
Chubby session leasewhether a client's handles/locks/cache remain valid12 sextended on each successful client KeepAlive6
Spanner Paxos leader leasewhich spanserver replica leads one tablet's Paxos group10 stime-based renewal while the leader stays reachable4

The general lesson is not the specific numbers — 60 s, "a few seconds," 12 s, and 10 s are tuned to each system's own failure-detection budget and blast radius, not to a shared constant — but the shape of the trade-off each duration encodes. A short lease detects a failed holder quickly and hands its role to someone else sooner, at the cost of more frequent renewal traffic and a tighter bound on how much clock skew the system can tolerate between the granter and the holder. A long lease amortizes renewal cost and tolerates more clock drift, at the cost of a longer window during which a genuinely failed holder is still, as far as everyone else is concerned, alive. Chubby's own authors made the trade-off explicit when they let an overloaded master extend session leases beyond the 12-second default specifically to reduce how often it has to process KeepAlive calls, accepting slower failure detection in exchange for lower server load6.

9. ZooKeeper: a coordination kernel

Chubby and the Paxos groups inside Spanner both expose locks as the primitive applications build on. ZooKeeper, built at Yahoo! and described in a 2010 USENIX paper, takes a different position: rather than fix a lock as the primitive, it exposes a smaller, wait-free set of operations — file-like data nodes and change notifications — and lets applications build locks, leader election, group membership, and configuration distribution themselves, entirely at the client, on top of that kernel2. The paper's own comparison to Chubby is direct: "looking at just the API signatures, ZooKeeper seems to be Chubby without the lock methods, open, and close"2 — the data model is nearly identical; what differs is that ZooKeeper refuses to bless any particular recipe as the one true coordination primitive.

9.1 Znodes, ephemeral nodes, and watches

ZooKeeper organizes data as znodes in a hierarchical namespace that looks like a filesystem — /app1/p_1 names a data node the same way a UNIX path does2. Every znode holds data and can have children, except ephemeral znodes, which cannot. A znode can be one of two lifetime types: regular znodes exist until a client explicitly deletes them; ephemeral znodes are automatically removed the instant the client session that created them ends, whether that end is a deliberate disconnect or an unannounced crash2. A znode can additionally be created with a sequential flag, which appends a monotonically increasing counter to its name — the value of that counter for a new node is never smaller than the sequence value already given to any prior sibling, which is precisely the property a fair queue needs2.

Clients avoid polling for changes through watches: a read operation issued with a watch flag set completes normally, but the server additionally promises to send the client a one-time notification the next time the data it just read changes. Watches are one-shot — they are unregistered the instant they fire or the session closes — and they tell the client only that something changed, not what the new value is, so a client that wants the new state has to issue a fresh read2.

9.2 Zab, and why reads don't need it

ZooKeeper offers exactly two ordering guarantees: all requests that update state are linearizable and respect precedence (linearizable writes), and all requests from one client are executed in the order that client sent them (FIFO client order)2. To guarantee the first, ZooKeeper implements a leader-based atomic broadcast protocol called Zab2 — a Paxos-family protocol in the same sense Raft is: a distinguished leader orders every state-changing operation before it is applied anywhere.

What Zab deliberately does not do is order reads. ZooKeeper's target workloads run at read-to-write ratios from 2:1 up to 100:1, so the paper's whole performance argument rests on serving reads locally, from whichever server a client happens to be connected to, without running them through Zab or contacting a majority at all2. This makes a ZooKeeper read fast — a local lookup, not a quorum round trip — at the cost of possibly returning slightly stale data if the server a client is talking to has not yet applied the latest write. For an application that cannot tolerate that staleness for a specific read, ZooKeeper provides sync(): it waits for all writes already pending at the server the client is connected to before that read is issued, converting one read into what the paper calls a slow read without requiring every read to pay that cost2. This read/write asymmetry is the same shape as Chubby's — a single authority (a leader, or a lease-holding master) orders writes, while reads are allowed to be cheaper and more local — implemented with a named protocol instead of a lease.

9.3 Building a lock without the herd effect

ZooKeeper ships no lock primitive; it ships the pieces to build one, and its own paper works through the construction as a worked example2. A naive lock — every client creates the same fixed-name ephemeral node, and whoever's create call succeeds holds the lock — works, but has a herd effect: every waiting client is watching the same node, so when the lock is released, every one of them wakes up and retries the create simultaneously even though only one can win2. That thundering-herd retry storm, once you already understand it as a general failure mode, is a special case of Module 11's cascading-failure material one layer up the stack.

ZooKeeper's own lock recipe avoids the herd effect by having each client create an ephemeral, sequential node under a shared lock path, then only watch the one sibling immediately before it in sequence order, rather than watching the lock path itself2. Because each waiting client watches exactly one other node, a release wakes up exactly one client, not all of them.

ZooKeeper lock recipe: ephemeral sequential znodes and a watch on the predecessor /lock lock-000000001 client A creates (ephemeral, sequential) lock-000000002 client B creates B checks: lowest sequence? no B watches lock-000000001 (not the lock path) lock-000000001 A's session ends — node auto-deleted watch fires on B: NodeDeleted B re-lists children: lock-000000002 is now lowest lock-000000002 — HOLDS LOCK
Figure 5. ZooKeeper's ephemeral-sequential lock recipe: each waiting client watches only the sibling znode directly ahead of it, so a lock release or a crashed holder's session timeout wakes exactly one client instead of every client waiting on the lock2.
  1. Create. Client A calls create("/lock/lock-", EPHEMERAL|SEQUENTIAL); ZooKeeper assigns it sequence 1. A lists /lock's children, sees its own node has the lowest sequence number, and holds the lock immediately2.
  2. A second client arrives. Client B creates its own ephemeral sequential node, gets sequence 2, lists the children, and finds it is not lowest — so it does not hold the lock.
  3. Watch the predecessor, not the lock. B sets a watch on exactly the sibling with the sequence number immediately below its own (node 1) — never on the shared lock path itself, which is what avoids waking every waiting client on a release2.
  4. Holder disappears. Client A's session ends — cleanly, or because it crashed — and ZooKeeper deletes A's ephemeral node automatically as part of ending the session2.
  5. Exactly one watch fires. Only B, which was watching node 1, receives the notification. B re-lists the children, finds its own node is now lowest, and acquires the lock — every other waiting client (had there been one behind B) is still asleep, watching its own predecessor.

The same two primitives — ephemeral nodes as liveness markers, watches as one-shot change notification — are what the ZooKeeper paper uses to build group membership (each live process holds one ephemeral child of a group znode; listing the group's children lists who's alive) and leader election (the lowest-sequence ephemeral node among a set of candidates is the leader, exactly as in the lock recipe, with the leader's identity plus contact information written into the winning node's data)2. This is what "coordination kernel" means in practice: ZooKeeper does not know it is being used to elect a leader or take a lock — it only knows a client created and watched some znodes — and that ignorance is precisely what lets a single small service support locks, leader election, membership, and configuration distribution without shipping bespoke server-side code for each.

Where experts disagree

Every mechanism in this module is well specified; the live disagreement is about the field's own recommendation. Raft was published explicitly to replace Paxos as the default choice for new systems, backed by a controlled comparison. The systems Aman is most likely to actually run into at Google's own scale — Chubby underneath Bigtable, and every spanserver inside Spanner — are Paxos, not Raft, and neither shows signs of migrating. Both facts are true at once, and the interesting question is what that tension is actually evidence of.

Raft's understandability advantage is real and decisive for new systems

Ongaro and Ousterhout, based on a controlled user study1

Raft's authors designed the comparison deliberately: 43 students at Stanford and Berkeley watched an equal-quality lecture on each algorithm (the Paxos lecture was actually 14% longer, biasing the comparison in Paxos's favor) and took a matched quiz on each. The mean Raft score was 25.7 out of 60 versus a mean Paxos score of 20.8; a paired t-test found, with 95% confidence, that the true Raft-score distribution exceeds the true Paxos-score distribution by at least 2.5 points1. Self-reported preference was even more lopsided: 33 of 41 respondents on each question said Raft would be easier to implement, and separately easier to explain, than Paxos1. The mechanism behind the result is structural, not incidental: Raft's strong-leader design means log entries flow in exactly one direction, membership changes reuse the ordinary log-replication path via joint consensus instead of a separate protocol, and Raft uses only 4 RPC message types where Viewstamped Replication and ZooKeeper's implementation each use 101.

  • Directly measured, not asserted — a matched-quiz study with a statistically significant result, biased if anything toward Paxos.
  • New consensus-based systems overwhelmingly choose Raft: etcd, Consul, and CockroachDB all build on it1.
  • Fewer message types and one fewer independently-varying mechanism (leader election is not separable from the rest, unlike in Paxos) means less state space for an implementer to get wrong.
  • The study measures learnability and short-term implementation confidence, not measured production reliability, throughput, or latency under real workloads at scale.
  • Raft's performance is explicitly "similar to other consensus algorithms such as Paxos" by its own authors' account1 — understandability was never claimed as a performance advantage.

Production-hardened Paxos implementations are not being replaced, and that is the more informative data point

Observable from Google's own published systems346

Chubby was built and deployed years before Raft's 2014 publication, has run continuously underneath Bigtable with measured unavailability of 0.0047% of Bigtable server-hours across 14 production clusters3, and Google has not published any account of replacing its Paxos core with Raft. Spanner, published two years before Raft, runs one Paxos state machine per tablet on every spanserver, at a scale of hundreds to several thousand spanservers per zone4, and again shows no published migration. The Chubby paper's own account of building the system supports why: Chubby's authors state plainly that the difficulty they were solving was not "research" but engineering — getting an already-understood but gap-ridden protocol description into a system that survives real failures, ACL misuse, Java interop, and abusive clients over a decade of operation6. Once that engineering investment is sunk and the system has years of production battle-scars behind it, a pedagogical advantage in a controlled study is a weak reason to re-litigate a proven implementation.

  • Directly observable: two of the highest-scale storage systems ever published still run Paxos, years after Raft existed as an alternative.
  • Operational maturity — the accumulated fixes for the "rich source of interesting bugs" that fail-over code turns out to be6 — is real and does not transfer to a rewrite for free.
  • Neither Chubby nor Spanner's spanservers are bottlenecked on developer understanding of Paxos; they are maintained by teams that already paid that cost once.
  • Inertia is not the same claim as "Paxos is operationally superior" — the absence of a migration is also fully consistent with "rewriting a load-bearing consensus core is expensive and risky regardless of which algorithm wins on paper," which says nothing about Raft's merits.
  • Neither Chubby nor Spanner's papers make an explicit case for Paxos over Raft on any performance axis — they simply predate Raft and were never revisited in print.
Assessment

These two positions are not actually in conflict once the comparison is scoped correctly. For a team building a new replicated log today — the situation Raft's authors designed the study for — the understandability advantage is decisive: it is easier to get an implementation right the first time, it needs fewer message types, and the open-source ecosystem (etcd, Consul, CockroachDB) has already absorbed the cost of getting Raft production-ready, so there is no offsetting engineering-investment argument for choosing Paxos instead. For a team maintaining an existing Paxos deployment that has already amortized its correctness and operational cost over a decade — Chubby's or Spanner's position — understandability is close to irrelevant, because the hard, expensive part (proving the implementation correct and finding its bugs in production) is sunk, and a rewrite would re-incur exactly the risk Raft was designed to reduce, for a system that already works. The evidence that would actually settle whether Raft is superior in some absolute sense, rather than merely superior-for-greenfield-systems, does not exist and may never: nobody has published a head-to-head account of replacing a hardened Paxos deployment with Raft at Chubby's or Spanner's scale and reporting what changed, and the economic case for ever running that experiment on a working system is weak regardless of which algorithm would win.

References

  1. paperOngaro, D., Ousterhout, J. In Search of an Understandable Consensus Algorithm (Extended Version). Stanford University, 2014. https://raft.github.io/raft.pdf. Accessed 2026-09-17. Used for: replicated state machine model and safety/liveness properties (§2), leader/candidate/follower states and RequestVote (§5.1–5.2), randomized election timeouts and split-vote measurements (§5.2, §9.3), AppendEntries and the Log Matching Property (§5.3), majority commit (§5.3), election restriction and no-op commit of previous-term entries (§5.4, §8), joint-consensus membership changes (§6), and the broadcastTime ≪ electionTimeout ≪ MTBF timing requirement (§5.6).
  2. paperHunt, P., Konar, M., Junqueira, F. P., Reed, B. ZooKeeper: Wait-free Coordination for Internet-scale Systems. Yahoo! Research, USENIX ATC 2010. https://www.usenix.org/legacy/event/atc10/tech/full_papers/Hunt.pdf. Accessed 2026-09-17. Used for: the coordination-kernel design rationale and the "Chubby without the lock methods" comparison (§1), znode types and watches (§2.1), linearizable-writes/FIFO-client-order guarantees and Zab (§1, §2.3), the 2:1–100:1 read:write target ratio and local unlinearized reads and sync() (§1, §2.3), and the ephemeral-sequential lock and leader-election recipes (§2.4).
  3. paperChang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A., Gruber, R. E. Bigtable: A Distributed Storage System for Structured Data. Google, OSDI 2006. https://www.usenix.org/legacy/event/osdi06/tech/chang/chang.pdf. Accessed 2026-09-17. Used for: Bigtable's specific uses of Chubby — master election, tablet-server discovery via the servers directory, bootstrap/schema/ACL storage (§4, §5.1–5.2) — and the measured 0.0047%/0.0326% Chubby-attributable unavailability (§4).
  4. paperCorbett, J. C., Dean, J., Epstein, M., et al. Spanner: Google's Globally-Distributed Database. Google, OSDI 2012. https://research.google.com/archive/spanner-osdi2012.pdf. Accessed 2026-09-17. Used for: zones/spanservers/tablets scale (§2), one Paxos state machine per tablet and the 10-second default leader lease (§2, §2.1), the lock table/transaction manager/participant leader and two-phase commit across Paxos groups (§2.1), directories and movedir (§2.2), and the stated motivation for paying 2PC-over-Paxos cost given Bigtable's cross-row-transaction complaints (§2.3).
  5. paperGhemawat, S., Gobioff, H., Leung, S-T. The Google File System. Google, SOSP 2003. https://research.google.com/archive/gfs-sosp2003.pdf. Accessed 2026-09-17. Used for: the 60-second chunk lease and heartbeat-piggybacked renewal (§3.1), cited here only as one row of the cross-system lease comparison (Table 2); full GFS mechanics are Module 3's and Module 7's scope, not re-derived here.
  6. paperBurrows, M. The Chubby Lock Service for Loosely-Coupled Distributed Systems. Google, OSDI 2006. https://static.googleusercontent.com/media/research.google.com/en//archive/chubby-osdi06.pdf. Accessed 2026-09-17. Used for: Chubby's own cell/replica/master-election design and rationale for a lock service over a Paxos library (§2.1–2.2), master lease and read/write handling (§2.2), session lease default (12 s), idle-session timeout, and grace period (§2.7–2.9), advisory locks, sequencers, and the primary-election recipe (§2.4, §2.6), and the production numbers in Table 1 (§4.1) — fetched directly by the writer; not in the module's original source map.