19. Consensus, Coordination & Time

19.1 Why consensus

Leader election, distributed locks, configuration, membership, and strongly consistent replication all reduce to getting a group of nodes to agree on one ordered log despite crashes and partitions. Raft and Paxos do this with a majority quorum: 2f+1 nodes tolerate f failures (3 nodes tolerate 1, 5 tolerate 2).

19.2 Raft in five lines

1. Nodes are followers, candidates, or the leader. Each term has at most one leader.
2. A follower that hears no heartbeat before a randomized timeout becomes a candidate and requests votes. It wins with a majority.
3. The leader appends client commands to its log and replicates them. An entry is committed once a majority has stored it.
4. A node votes only for candidates whose log is at least as up-to-date as its own, so committed entries survive leader changes.
5. Every write pays at least one round trip to a majority, which is why consensus systems hold metadata and coordination state, not bulk data (etcd, ZooKeeper, Chubby). Bulk-data systems shard into many independent consensus groups (Spanner, CockroachDB, TiKV).

19.3 Leases, locks, and fencing tokens

A distributed lock cannot by itself guarantee mutual exclusion. A client can pause (GC, VM migration) past its lease, wake up, and still believe it holds the lock.

Client A gets lock (token=33) ── long GC pause ──────────────▶ writes with token 33 ✗ rejected
Lease expires; Client B gets lock (token=34) ── writes with token 34 ✓
Storage rejects any token lower than the highest it has seen.

The fix is fencing tokens: monotonically increasing numbers issued with each lock grant and checked by the resource itself. Redis-based locks (Redlock) are fine for efficiency (avoiding duplicate work) and not safe for correctness without fencing. This is a classic Staff+ probe.

19.4 Time

• Physical clocks drift. NTP keeps them within milliseconds normally, and much worse when misconfigured. Never use wall-clock timestamps to order events across machines for correctness.
• Lamport clocks: a logical counter that gives an order consistent with causality.
• Vector clocks: detect concurrency (which is what Dynamo-style conflict detection needs).
• Hybrid logical clocks (HLC): physical time plus a logical counter, close to wall-clock but causally safe (CockroachDB, YugabyteDB).
• TrueTime (Spanner): an API that returns an interval [earliest, latest] backed by GPS and atomic clocks. Spanner waits out the uncertainty (commit wait, a few ms) before acknowledging a commit, and in exchange gets globally ordered, externally consistent transactions.

19.5 Coordination services, and when to use them

Use etcd, ZooKeeper, or a cloud equivalent for leader election, service discovery, configuration, distributed locks (with fencing), and shard assignment. Don't use them as a general database or a message queue, and don't put them on the per-request data path.

19.6 🏗️ Flow: Raft leader election and log replication

 Term 7: Leader L (n1), followers n2..n5
   client write X ─▶ L appends X @ index 42 (term 7)
   L ─AppendEntries(42)─▶ n2 ✓ n3 ✓ n4 ✗(slow) n5 ✗(down)
   majority (L,n2,n3 = 3/5) stored → index 42 COMMITTED → apply to state machine → reply client

 n1 crashes. n2's election timeout (random 150-300 ms) fires first:
   n2 → term 8, RequestVote(lastLogTerm=7, lastLogIndex=42)
   n3 votes yes (n2's log ≥ its own); n4 (lagging, index 40) votes yes; → n2 has 3/5 → LEADER term 8
   n4 would NOT win: voters reject candidates with less up-to-date logs → committed entry 42 survives

19.7 Deeper: Raft and Paxos details that come up at Staff+

• Linearizable reads: a leader can't simply answer reads from local state, because it might have been deposed without knowing. Options are ReadIndex (confirm leadership with a heartbeat round, then read), lease reads (assume leadership for a lease period, which depends on bounded clock drift), or writing the read through the log (slow).
• Pre-vote: a node coming back from a partition with a higher term can disrupt a healthy leader. Pre-vote checks that it could win before incrementing its term.
• Membership changes: adding or removing nodes safely needs joint consensus or one-at-a-time changes. Going from 3 to 5 nodes directly can create two disjoint majorities.
• fsync is part of correctness: acknowledging a vote or entry before it's durable breaks safety after a crash. That makes consensus latency disk latency bound. etcd on slow disks causes leader flapping, and so do Kubernetes control-plane outages.
• Snapshots and log compaction: without them, a restarted node replays months of log. With them, a lagging follower must receive a large snapshot, which needs to be throttled.

19.8 🌍 In production

• Google Chubby (2006): a coarse-grained lock and naming service on Paxos. Its paper is candid that most users used it for leader election and naming, not fine-grained locking.
• etcd is the brain of every Kubernetes cluster (Raft). Its performance and disk health define control-plane stability. See the K8s guide.
• Kafka KRaft: Kafka replaced its ZooKeeper dependency with a built-in Raft quorum for metadata, which removes an external system and speeds up failover for clusters with many partitions.
• CockroachDB: hybrid logical clocks plus a configured maximum clock offset (default 500 ms). A node that detects its clock is too far off shuts itself down rather than risk violating consistency.
• Cloudflare, "A Byzantine failure in the real world" (2020): a partial network failure, where some nodes could reach each other and others couldn't, caused an etcd cluster to elect leaders repeatedly, which degraded systems that depended on it. Real partitions are rarely clean.
• Cloudflare 2017 leap second: code assumed time never goes backwards. A leap second made a duration negative, which crashed part of their DNS. Use monotonic clocks for durations.

19.9 ⚠️ Corner cases & deep details

• Partial partitions: A can reach B, B can reach C, A can't reach C. Leader election may thrash. Pre-vote and check-quorum help, but monitoring must also detect asymmetric reachability.
• GC pauses and lease expiry: a leader pauses for 10 s and resumes, believing it's still leader. Fencing tokens (§19.3) protect the downstream resource, and the leader must check its lease before every side effect.
• Clock jumps: NTP stepping the clock backwards breaks wall-clock lease logic. Use monotonic clocks for timers and slew (don't step) in production.
• Even-sized clusters: 4 nodes tolerate 1 failure, the same as 3, but with more write latency. Use odd sizes.
• Cross-region consensus: a 5-node group spread over 3 regions has commit latency of about one cross-region round trip. Put the leader where the writes are, or partition so each region leads its own groups.