Consistency and Consensus, Designing Data-Intensive Applications Notes

9.1Chapter Thesis

Consensus is what a group of machines needs whenever exactly one outcome must be chosen among several possibilities - which node is the leader, whether a transaction committed, what the next entry in a shared log is - and every machine has to end up agreeing on that one outcome despite the network and clocks lying to them, per the previous chapter. It is provably impossible to solve in full generality with guaranteed termination on an asynchronous network where nodes can fail - which is exactly why every real consensus protocol makes a specific, named compromise with that impossibility.

9.2First Principles

Linearizability is the strongest single-copy illusion

A linearizable system behaves as if there were only one copy of the data and every operation took effect atomically at some instant between its start and end. It is the strongest common consistency guarantee and the most expensive to provide, because it effectively rules out serving reads from a stale replica without additional coordination.

Total order broadcast turns consensus into message ordering

If every node in a system delivers the same sequence of messages in the same order, replicated state machines can be built trivially: apply the messages in that order, and every node ends up in the same state. This reframes "reach consensus" as "agree on one global order for a stream of messages," which is a more tractable, more general formulation of the same underlying problem.

Quorums make availability and consistency both partial

Requiring a write to succeed on w out of n replicas, and a read to check r out of n replicas, guarantees at least one overlapping replica between any write quorum and any read quorum whenever w + r > n. That overlap is what lets a quorum read see the most recent write - but it only holds for the single most recent write; concurrent writes without additional coordination can still leave replicas disagreeing about which one "won."

9.3Mechanism

The simplest possible total order broadcast has a single, designated sequencer node: every message is sent to it first, it assigns the next sequence number, and broadcasts the numbered message to everyone. Every recipient applies messages strictly in sequence-number order. This trivially satisfies total order - at the cost of making the sequencer both a throughput bottleneck and a single point of failure, which is precisely the tradeoff real consensus protocols (Raft, Paxos, Zab) exist to remove by making the "sequencer" role itself fault-tolerant via leader election and quorum-based replication of the sequence.

9.4Build It Yourself

single-sequencer-broadcast.ts

class Sequencer {
  private seq = 0;
  private subscribers: ((n: number, msg: string) => void)[] = [];

  subscribe(fn: (n: number, msg: string) => void): void {
    this.subscribers.push(fn);
  }

  // every subscriber sees every message with the same
  // number, in the same order - that's total order broadcast.
  broadcast(msg: string): void {
    const n = this.seq++;
    for (const fn of this.subscribers) fn(n, msg);
  }
}

// quorum read/write: overlap guaranteed when w + r > n
quorumWrite(
  replicas: Map<string, string>[],
  key: string,
  value: string,
  w: number
): void {
  replicas.slice(0, w).forEach((r) => r.set(key, value));
}

quorumRead(
  replicas: Map<string, string>[],
  key: string,
  r: number
): (string | undefined)[] {
  return replicas.slice(0, r).map((rep) => rep.get(key));
}

9.5Failure Modes

Condition	Resulting state
The sequencer crashes	Total order broadcast halts entirely until a new sequencer is chosen - the single-sequencer design has no fault tolerance of its own; that has to be added via leader election, which reintroduces the consensus problem this mechanism was trying to simplify.
Quorum reads without read-repair after a partial write failure	A quorum read can return two different values from two of its r replicas if the write only reached some of the w replicas before failing - the client sees an ambiguous result and must resolve it, usually by picking the value with the highest version.
w + r ≤ n	No guaranteed overlap between write and read quorums; a read can return a value older than the most recent successful write with no way to detect that it's stale.

9.6Tradeoffs

Approach	Benefit	Cost	When it makes sense
Single sequencer	Simple, trivially correct total ordering	No fault tolerance; a bottleneck at scale	Small systems, prototypes, or as a building block inside a larger fault-tolerant protocol
Quorum-based (w + r > n)	Tolerates node failures without halting; tunable latency/consistency balance	Concurrent writes can still conflict; requires conflict resolution logic	Systems prioritizing availability during partial failures over strict ordering
Full consensus protocol (Raft/Paxos)	Fault-tolerant total order with formally proven safety	Significant implementation and operational complexity	Systems where correctness under node failure is non-negotiable (config stores, leader election services)

9.7Production Perspective

Systems like etcd and ZooKeeper implement full consensus protocols specifically so that other distributed systems can outsource their leader-election and configuration-agreement problems to a single, well-tested implementation rather than each reinventing a fault-tolerant sequencer - which is why so many unrelated systems (Kafka, Kubernetes) depend on one of these two underneath.

Consistency and Consensus