Consistency and Consensus

Fullscreen

---

Linearizability

Linearizability means making a replicated system appear as if there is only one copy of the data and all operations on it are atomic. It's a recency guarantee, as soon as one client's write completes, every reader must see it (no stale cache/replica). Aka atomic consistency, strong consistency, immediate/external consistency. The nonlinearizable sports site: Aaliyah refreshes and sees the final score, tells Bryce, but Bryce's reload hits a lagging replica showing the game still in progress, a violation, because his read began after hers and returned older data.

What makes a system linearizable

Operations on a register x: Read(x)⇒v, Write(x,v)⇒r, CAS(x, vold, vnew)⇒r. Because of network delays, an operation takes effect at some point between its request and response.

Fullscreen

Reads concurrent with a write may return old or new, but once a value has been read, the value can't "flip back." Each operation appears to take effect atomically at a point, and those points must move forward in time only. (Linearizability is the strongest common consistency model; weaker ones include read-your-writes, monotonic reads, and consistent prefix from Ch. 6.)

Linearizability vs serializability

Fullscreen

They sound alike but differ: serializability is a transaction isolation level (multi-object, some serial order, no recency requirement); linearizability is single-object recency (no multi-object protection like write skew). Combining them is strict serializability (Spanner, FoundationDB offer it; CockroachDB gives serializability + some recency but not strict, to avoid expensive coordination). Single-node DBs are typically linearizable.

Relying on linearizability

• Locking and leader election, electing a single leader via a lease must be linearizable (no two leaders). ZooKeeper/etcd provide this via consensus; Curator adds higher-level recipes; fencing still matters (Ch. 9).
• Uniqueness constraints, a hard unique username/email/filename, a non-negative balance, no overselling stock, no double-booked seat, all need a single up-to-date value all nodes agree on (like a CAS / lock). Loosely-enforced constraints (overbook then compensate) may not.
• Cross-channel timing dependencies, the Aaliyah-Bryce voice channel is a second communication path. Same shape in systems: a web server writes a video to file storage, then queues a transcode job; if storage isn't linearizable, the (fast) queue message can beat the (slow) replication, so the transcoder reads an old/missing file → permanent inconsistency. Push-notification-then-fetch has the same race.

Implementing linearizable systems

Fullscreen

Quorums don't guarantee linearizability: even with w + r > n, variable delays let reader A (begun earlier) see the new value while reader B (begun later) sees the old value. Dynamo-style quorums can be made linearizable with synchronous read repair and read-before-write to bump timestamps, at a performance cost, but a linearizable CAS needs consensus regardless. Assume leaderless ≠ linearizable.

Linearizability and the CAP theorem

Fullscreen

Any linearizable system faces this: during a partition, pick consistency or availability. This is the CAP theorem (better phrased "either Consistent or Available when Partitioned"). The popular "pick two of three" framing is misleading, partitions aren't optional. CAP is narrow (only linearizability, only partitions, <8% of incidents per Google) and now mostly of historical interest (superseded; see also PACELC: even without a partition you may trade latency vs consistency).

Linearizability is slow even without faults. Modern multi-core CPU memory isn't linearizable (caches/store buffers), dropped for performance, not fault tolerance. Attiya-Welch proves linearizable read/write response time is at least proportional to network-delay uncertainty, so on variable networks it's inevitably high. No faster algorithm exists; weaker models can be much faster.

---

ID Generators and Logical Clocks

A single-node autoincrementing counter (atomic fetch-and-add) is linearizable and orders records by creation. But it's a single point of failure, slow cross-region, and a throughput bottleneck. Distributed alternatives trade away ordering:

Fullscreen

Wall-clock-based IDs are at best approximately ordered (clock skew/jumps); not linearizable.

Logical clocks

A logical clock counts events, not time: compact, unique, totally ordered, and consistent with causality (if A happened-before B, then A's timestamp < B's).

Fullscreen

• Lamport timestamps = (counter, node-ID); bump the local counter on every event and to match any higher counter seen. Total order consistent with causality, but not linearizable (only orders events a node has seen).
• Hybrid logical clocks (HLC) combine physical time with Lamport ordering: counts microseconds but moves forward to match higher timestamps seen and increments to stay monotonic. Looks like a wall clock but is causally consistent; needs only roughly-synced clocks, no special hardware (CockroachDB).
• Vector clocks (vs Lamport/HLC): keep a counter per node so you can detect concurrency (Lamport/HLC order concurrent events arbitrarily). Cost: much more space.

Linearizable ID generators

Lamport/HLC ordering is still weaker than linearizable. The photo-privacy bug: user sets account private (one DB), then uploads a photo (another DB); if the photos DB's clock lags, the upload gets a lower timestamp than the privacy change, and an MVCC reader can see the account as still public → leak. Fixes:

• Single-node oracle, one node atomically increments + persists + replicates a counter (TiDB/TiKV's "timestamp oracle," per Google Percolator). Batch IDs to avoid per-request disk/replication (some IDs skipped on crash, but never duplicated/out-of-order). Can't shard or distribute across regions, but one node handles high throughput.
• Spanner's TrueTime, wait out the clock's uncertainty interval, giving linearizable IDs without communication (even cross-region), at the cost of tight clock sync.

Logical clocks aren't enough for locks/uniqueness: you could pick the lowest timestamp as winner, but a node can't know its timestamp is lowest without hearing from every other node, which breaks under faults. For fault-tolerant locks/leases/uniqueness you need consensus.

---

Consensus

Many single-node-easy things get hard with fault tolerance: leader failover without split brain, a fault-tolerant ID counter, a fault-tolerant CAS. All are the same problem: consensus, getting nodes to agree on a value. Best-known algorithms: Viewstamped Replication, Paxos, Raft, Zab (non-Byzantine; nodes may crash/delay but don't lie). BFT variants exist (blockchains, <1/3 Byzantine) but are out of scope.

FLP impossibility: no deterministic algorithm can always reach consensus if a node may crash, but only in the asynchronous model with no clocks/timeouts. With timeouts (or randomness) consensus becomes solvable in practice.

The many faces of consensus (all equivalent)

Fullscreen

• Single-value consensus, one/more nodes propose, the algorithm decides one. Properties: uniform agreement (no two decide differently), integrity (no changing your mind), validity (a decided value was proposed), termination (every non-crashed node eventually decides, a liveness property; the other three are safety). The first three are easy with a hardcoded dictator; fault tolerance (termination despite crashes) is the hard part, and requires a majority of nodes to be up.
• CAS as consensus, propose via CAS(null → your value); decided value is whatever it's set to. CAS ⇔ consensus.
• Shared logs as consensus, a shared log (multiple appenders) with eventual-append/reliable-delivery/append-only/agreement/validity, implementable via total order broadcast (atomic broadcast). Decide the first log entry's value ⇒ consensus; run one consensus instance per log slot ⇒ a shared log. Equivalent.
• Fetch-and-add as consensus, only solves consensus for 2 nodes (the one that reads 0 wins, but if it crashes before announcing, others hang). Its consensus number is 2, vs ∞ for CAS/shared logs.
• Atomic commitment as consensus, like consensus but must abort if any participant votes abort (extra validity + nontriviality properties). 2PC's coordinator is a single point of failure; replacing it with consensus makes atomic commit fault-tolerant. Atomic commit ⇔ consensus.

Consensus in practice

Most consensus systems expose a shared log (= total order broadcast): Raft, VR, Zab do natively; Paxos gives single-value but Multi-Paxos adds a log.

Using shared logs: if each entry is a write and every replica applies entries in the same order with deterministic logic → state machine replication (the basis of event sourcing); deterministic stored-procedure entries → serializable transactions. A log also yields single-value consensus, CAS, per-item consensus (theater seats), fetch-and-add, and fencing tokens (the entry counter; ZooKeeper's zxid). (Sharded strong-consistency DBs often keep one log per shard, limiting cross-shard guarantees.)

From single-leader to consensus, the bootstrap puzzle ("need a leader for consensus, need consensus to elect a leader") is broken with epoch numbers (ballot in Paxos, view in VR, term in Raft):

Fullscreen

Two rounds of voting (elect leader; then approve each entry), with overlapping quorums so any approved proposal proves no higher epoch exists. Unlike 2PC: any node can start an election and only a quorum must respond (2PC needs the coordinator and every participant's yes).

Subtleties: a new leader must be at least as up-to-date as a majority (Raft) or bring itself up-to-date (Paxos), else it could overwrite committed entries. Linearizable reads also need a quorum round-trip to confirm leadership (etcd does this). Weakening this (Kafka's unclean leader election, async replication) trades safety for availability, "thin ice." Algorithms support reconfiguration to add/remove nodes.

Pros and cons: consensus is a breakthrough, automatic failover, no lost commits, no split brain; any auto-failover without a proven consensus algorithm is likely unsafe. But: needs a strict majority (3 to tolerate 1, 5 to tolerate 2); every op needs a quorum so adding nodes doesn't raise throughput (it slows things); a partition blocks the minority; timeout tuning is hard (too short → leader-election storms). Raft has edge cases (one bad link can bounce leadership; fixed with a pre-vote phase); EPaxos is leaderless and more robust.

Coordination services

Fullscreen

Modeled on Google's Chubby. They hold small, slow-changing data (in memory, replicated via consensus) to coordinate other systems (Kubernetes→etcd; Spark/Flink HA→ZooKeeper). Beyond consensus they add: failure detection (sessions + heartbeats; ephemeral nodes vanish when a client dies), change notifications (watches), configuration management, allocating work to nodes (leader/primary election, shard assignment, auto-recovery without humans; Curator helps), and service discovery (though that often doesn't need linearizability, caching/TTL and ZooKeeper observers, which replicate without voting, give availability and read throughput at the cost of possibly-stale reads). Outsourcing consensus to 3-5 nodes is far better than running it over thousands.

---

Real-world examples and analogies

• Linearizability, one whiteboard everyone reads. Even if there are secretly many copies, it must look like a single whiteboard: the instant someone writes a new number, anyone who looks next sees the new number, never the old one. Bryce seeing the stale score after hearing Aaliyah is like reading a whiteboard that hasn't been updated yet.
• Linearizability vs serializability, "up to date" vs "as if one at a time." Serializability promises transactions don't tangle (some valid order), but that order may be stale. Linearizability promises recency for a single value. Strict serializability is both: correct order and current.
• CAP partition, two halves of a split office. When the phone line between two offices dies, each half must choose: refuse to act until reconnected (consistent), or keep working independently and reconcile later (available). You can't have both, and the line dying wasn't your choice.
• Lamport clock, numbering emails by "highest seen + 1." You don't timestamp by wall clock; you write a counter that's always one more than the highest you've ever seen on any email. Replies always outrank what they answer, so the thread reads in causal order.
• Vector clock vs Lamport, knowing two people emailed simultaneously. A single counter can't tell "concurrent" from "one after the other"; a per-person tally can, at the cost of carrying everyone's tally.
• Consensus = single-leader done right, electing a class monitor with terms. The class can lose its monitor and elect a new one (a new "term"); if the old monitor reappears, the higher term wins, so there's never two monitors giving conflicting orders.
• Shared log / state machine replication, everyone follows the same recipe in the same order. Give every cook the identical ordered recipe and they all end up with the same dish. That's how replicas stay consistent: apply the same log of writes in the same order.
• The equivalence of consensus problems, different shapes of the same lock. A coin-flip to pick a winner (CAS), a numbered ticket queue (shared log), a turnstile counter (fetch-and-add), and a "all sign or none" contract (atomic commit) look different but are interconvertible, solve one and you've solved them all.
• Coordination service, the building's front desk. A small, trusted desk (3-5 people) hands out the single key to each room (lease), stamps each handout with a rising number (fencing token), notices when someone stops checking in (ephemeral node), and tells you when a colleague arrives or leaves (notification), so the thousands of workers don't each have to negotiate.

---

Cheat-sheet flashcards

Cover the answer and recall it.

• Two consistency philosophies? → Eventual consistency vs strong consistency.
• What is linearizability in one phrase? → A recency guarantee; behave like a single copy with atomic operations.
• Other names for linearizability? → Atomic/strong/immediate/external consistency.
• What does linearizability require once a new value is read? → All later reads must return the new value (no flipping back).
• Linearizability vs serializability? → Single-object recency vs multi-object some-serial-order (stale reads OK).
• What is strict serializability? → Both linearizability and serializability (Spanner, FoundationDB).
• Three uses that need linearizability? → Leader election/locking, uniqueness constraints, cross-channel timing.
• What is a cross-channel timing dependency? → A second communication path that exposes staleness (voice, message queue).
• Which replication methods can be linearizable? → Single-leader (potentially), consensus (likely); not multi-leader or leaderless.
• Do quorums (w + r > n) guarantee linearizability? → No, concurrent ops can still race.
• What does the CAP theorem say? → During a partition, choose consistency or availability.
• Better phrasing of CAP? → Either consistent or available when partitioned.
• Why is linearizability slow even without faults? → Response time scales with network-delay uncertainty (Attiya-Welch).
• Why isn't multi-core CPU memory linearizable? → Caches/store buffers, dropped for performance.
• Single-node autoincrement IDs, property? → Linearizable and ordered, but a SPOF/bottleneck.
• Four distributed ID schemes? → Sharded, preallocated blocks, random UUID, wall-clock-made-unique.
• Why are wall-clock IDs not linearizable? → Clock skew/jumps make ordering approximate.
• What is a logical clock? → Counts events; totally ordered and consistent with causality.
• Lamport timestamp format and rule? → (counter, node-ID); bump on each event and to match higher seen.
• Are Lamport timestamps linearizable? → No, only causal total order.
• What does a hybrid logical clock add? → Physical-time meaning + causal ordering, no special hardware.
• Lamport/HLC vs vector clock? → Can't detect concurrency vs can (at more space).
• How do you build a linearizable ID generator? → Single-node oracle (replicated) or Spanner TrueTime (commit-wait).
• Why aren't logical clocks enough for locks? → A node can't know its timestamp is lowest without hearing from all nodes.
• What is consensus? → Getting multiple nodes to agree on a value.
• Four named consensus algorithms? → Viewstamped Replication, Paxos, Raft, Zab.
• What does FLP prove (and its caveat)? → Can't always terminate; only in the async model with no timeouts.
• Four equivalent faces of consensus? → Single-value/CAS, shared log/total order broadcast, fetch-and-add, atomic commit.
• Four properties of single-value consensus? → Uniform agreement, integrity, validity, termination.
• Which consensus property is liveness? → Termination.
• Consensus number of fetch-and-add vs CAS? → 2 vs infinity.
• How does atomic commitment differ from consensus? → Must abort if any participant votes abort.
• What do most consensus systems expose? → A shared log (total order broadcast).
• What is state machine replication? → Replicas apply the same log in the same order deterministically.
• What is an epoch number, and why? → Per-election term (ballot/view/term) guaranteeing a unique leader per epoch.
• Consensus vs 2PC on voting? → Any node starts an election, quorum responds vs only coordinator, every participant.
• What is unclean leader election? → Letting a non-up-to-date replica become leader (trades safety for availability).
• Why can't you scale consensus throughput by adding nodes? → Every op needs a quorum; more nodes = slower.
• What are coordination services, and examples? → Consensus-based coordination stores: ZooKeeper, etcd, Consul (Chubby-like).
• Four coordination-service features? → Locks/leases, fencing, failure detection (ephemeral nodes), change notifications.
• What is a ZooKeeper observer? → A non-voting replica for available, higher-throughput (possibly stale) reads.

---

Common interview questions

1. What is linearizability, and how does it differ from eventual consistency? (Single-copy recency illusion vs visible replication/conflicts.)
2. Distinguish linearizability from serializability; what is strict serializability? (Single-object recency vs multi-object order; both together.)
3. When do you actually need linearizability? (Leader election/locking, uniqueness, cross-channel timing.)
4. Which replication methods can be linearizable, and why aren't quorums enough? (Single-leader/consensus yes; multi-leader/leaderless no; quorum race.)
5. Explain the CAP theorem and why the "pick two of three" framing is misleading. (Consistent-or-available-when-partitioned; partitions aren't optional.)
6. Why is linearizability inherently higher-latency? (Attiya-Welch: response time scales with delay uncertainty.)
7. Compare ways to generate distributed IDs and their ordering guarantees. (Sharded/blocks/UUID/wall-clock/logical/linearizable.)
8. What are Lamport timestamps, and how do hybrid logical and vector clocks improve on them? (Causal total order; +physical time; +concurrency detection.)
9. Why is consensus needed for fault-tolerant locks/leader election? (Logical clocks can't tolerate faults; need agreement despite crashes.)
10. Show that single-value consensus, shared logs, and atomic commit are equivalent. (Interconvertible; CAS ⇔ consensus; log slots; vote-then-propose.)
11. How do consensus algorithms elect a leader and avoid split brain? (Epoch numbers, two overlapping quorum votes, higher epoch wins.)
12. What is a coordination service, and what does it provide beyond consensus? (ZooKeeper/etcd; fencing, ephemeral nodes, notifications, work allocation, service discovery.)

---

Key terms glossary

---

Forward links (where these ideas return)

• Avoiding linearizability without sacrificing correctness → Chapter 13
• Loosely-interpreted constraints (timeliness vs integrity) → Chapter 13
• Shared logs, state machine replication, event sourcing in streaming → Chapter 12
• Fencing tokens, leases, split brain → Chapter 9
• Two-phase commit and distributed transactions → Chapter 8
• Snapshot isolation, MVCC, transaction IDs → Chapter 8