System Design Fundamentals
Consensus algorithms
Imagine an Uber-scale matching shard deciding which driver won a ride, or a Kubernetes control plane writing cluster config. Several replicas hear the request. Only one ordered history can become truth, even if a node dies mid-write.
is how those machines agree. It is the foundation of leaders, locks, and replicated metadata. Skip it on the hot path for every user click; use it where would break the product.
Safe write journey
Client talks to the current leader.
Followers store the same command.
Only then is the write committed.
State machines advance together.
Try it: replicate one log entry to a majority
Raft-style consensus in miniature: one leader appends to its log, followers copy the entry, and commitment waits for a majority of acks for the same index.
- Leader
- R1
- Term
- 1
- Acks for latest
- 5/5
- Committed
- No
R1
ackedLog tail
bootstrap
R2
ackedLog tail
bootstrap
R3
ackedLog tail
bootstrap
R4
ackedLog tail
bootstrap
R5
ackedLog tail
bootstrap
Propose a command as leader, replicate to followers, then collect acknowledgements. A majority must ack before the entry is treated as committed in this toy Raft step.
Connect to quorums. The majority here is the same overlap idea as W and R in Dynamo-style stores, but Raft ties it to a single ordered log and leader-driven replication.
What actually happens
A replicated write needs both enough durable copies and election rules that protect those copies. In Raft, the leader can advance commitment by counting a majority for an entry from its current term; committing that entry also commits the preceding log prefix. A future leader must have a sufficiently up-to-date log to win votes. Majority overlap is the foundation, but these additional protocol rules explain why a stale candidate cannot simply overwrite committed history.
Leader-based protocols like , , and elect one writer per , then run . Followers can serve stale reads if the caller accepts staleness; linearizable reads need leader checks or forwarding.
That is why consensus appears in interviews: you pay coordination latency and stall when no majority is reachable, but you prevent two different committed values for the same log index.
How to choose when to use consensus
1. Must there be one authoritative order? Leaders, cluster config, lock ownership, and shard metadata usually yes. User timeline fan-out often no.
2. Can you tolerate write stalls during partitions? Strong consensus prefers safety over availability when a majority is unreachable.
3. Do you trust your own nodes? Crash-fault algorithms with 2f+1 nodes cover most internal systems. is for multi-party distrust, not typical microservices.
Simple rule of thumb
Use consensus for small amounts of critical state, not for every request. Prefer mature stores (etcd, ZooKeeper, Spanner-style groups) over hand-rolling . Run many independent consensus groups (one per shard) for parallelism at scale.
In simple terms: consensus buys one truth; eventual replication buys speed. Pick based on what a wrong second truth would cost.
Leader write flow: why majority matters
Safety, liveness, and cost show up together: two committed values must never exist for one index; progress needs a reachable majority and a stable leader; every strong write pays quorum latency.
Read the diagram definition
sequenceDiagram
participant Client
participant Leader
participant F1 as Follower 1
participant F2 as Follower 2
participant State as State machine
Client->>Leader: write command
Leader->>Leader: append uncommitted log entry
Leader->>F1: AppendEntries(term, entry)
Leader->>F2: AppendEntries(term, entry)
F1-->>Leader: ack
F2-->>Leader: ack
Leader->>Leader: majority reached, mark committed
Leader->>State: apply in log order
Leader-->>Client: success
Leader->>F1: commit index update
Leader->>F2: commit index updateSafety
Two different committed values cannot exist for the same log index.
Liveness
Progress needs a reachable majority and a stable leader long enough to replicate.
Cost
Every strong write pays coordination latency and tail latency from the slowest quorum member.
5-node log replication trace
Majority quorum is safer than "the leader wrote it locally" because any future leader must win votes from a majority that overlaps the committed set.
| Step | Term | Log state | Commit index | Why it is safe |
|---|---|---|---|---|
| Leader L appends x at index 8 | 4 | L has x; F1–F4 do not yet | 7 | Uncommitted; leader crash can still lose x. |
| F1 and F2 acknowledge | 4 | L, F1, F2 store x | 8 | 3 of 5 is a majority; future majorities overlap this set. |
| Leader crashes after reply | 4 | F3, F4 may lag | 8 on nodes that heard commit | Election rules prefer candidates with the latest log. |
| F1 wins term 5 | 5 | F1 contains x and repairs laggards | 8 | The committed prefix survives failover. |
Safe follower reads
A follower may serve its applied state when the caller accepts staleness. A linearizable read needs evidence that it is reading after the relevant committed operations and that leadership is still valid. A read-index protocol confirms leadership with a quorum and waits for the local state machine to apply through the resulting index; forwarding to a leader still requires that leader to perform the necessary checks. Lease-based reads additionally depend on the implementation’s timing assumptions.
What to test
Kill leaders before and after majority ack, partition 2/5 from 3/5, and assert there is one leader per term and no committed log entry disappears.
Leader-based consensus internals
State machine roles: Follower → Candidate → Leader. Expand each step for election, replication, compaction, and membership.
Leader election
- Follower timeout (150–300ms, randomized) → become Candidate
- Increment term, vote for self, request votes from all peers
- Majority votes → become Leader
- Leader sends heartbeats (empty AppendEntries) every 50–150ms
- If no heartbeat received → follower triggers new election
Log replication
Suppose a three-node group receives a command to set x to 5. The leader appends the entry with its term and index, then sends AppendEntries to followers. Each follower checks the preceding entry’s term and index before accepting the new suffix. Once the current-term entry meets the durable majority rule, the leader commits it, applies it in order, and replies.
A lost reply does not undo a committed command. Retrying an increment could execute it twice unless the replicated state includes a client request identifier and cached result. Consensus orders accepted commands; it does not automatically recognize two network requests as the same business intent.
Log compaction (snapshotting)
A snapshot records the state machine after an applied log prefix together with the included index and term. Once the snapshot is durably established, older entries can be compacted because recovery can load the snapshot and replay the remaining suffix. A lagging follower may receive the snapshot instead of every historical entry. Keep enough metadata for log matching and request deduplication; copying just application rows can lose protocol state needed after restart.
Cluster membership changes
Membership changes alter what counts as a majority, so they must use the implementation’s supported consensus transition. Raft’s joint-consensus approach requires majorities of both old and new configurations during the transition. Some mature implementations instead permit carefully constrained single-voter changes. Add a new node as a non-voting learner where supported, let it catch up, and then promote it through the protocol. Editing each node’s peer list independently can create disjoint voting groups.
Multi-Paxos and related algorithms
Basic agrees on one value per round (slow). Multi-Paxos elects a stable leader so Phase 1 can be skipped: about one round trip per consensus instead of two.
Used by globally consistent stores and lock services: often Multi-Paxos per tablet, with cross-shard 2PC over Paxos groups.
(ZooKeeper)
- Leader processes writes, broadcasts to followers (majority ack)
- Reads can go to any node (sequential consistency)
- Recovery: new leader reconciles divergent logs
- Uses epoch (like Raft term) for leader uniqueness
ZooKeeper has historically coordinated systems such as HBase, Solr, and Kafka. Kafka also has a Raft-based metadata mode called KRaft; the actual migration path depends on the deployed Kafka release. The architectural lesson is to identify which system owns metadata consensus rather than assuming that every service using a leader implements the same election and replication protocol.
Comparing consensus algorithms
| Algorithm | Leader | Complexity | Latency | Production use |
|---|---|---|---|---|
| Paxos | Implicit | Hard | 2 RTT (basic) | Foundational; rarely used raw |
| Multi-Paxos | Stable | Hard | 1 RTT (leader) | Globally consistent store tablets |
| Raft | Explicit | Moderate | 1 RTT (leader) | etcd, Consul, CockroachDB, TiKV |
| ZAB | Explicit | Moderate | 1 RTT (leader) | ZooKeeper |
| PBFT | Rotating | Very hard | 3 RTT | Hyperledger, blockchain |
| EPaxos | Leaderless | Hard | 1 RTT (fast path) | Research; some DB evaluations |
What consensus is for
Leader election
Exactly one leader per term. Used by Kafka partition leaders, Elasticsearch masters, Redis Sentinel.
Configuration / metadata
Cluster config, service registry, feature flags: all nodes must see the same truth. Kubernetes stores cluster state in etcd.
Same log + same initial state = same final state. Used by CockroachDB, TiKV (per-range Raft), Spanner-style Paxos groups.
Byzantine fault tolerance
Crash-fault tolerance
Assumes nodes crash cleanly (stop, do not lie). Tolerates f failures with 2f+1 nodes. 3 nodes → 1 failure; 5 nodes → 2 failures.
(PBFT)
Byzantine fault tolerance considers replicas that may send conflicting or malicious messages. Classic PBFT uses 3f+1 replicas to tolerate f Byzantine faults under its model, with pre-prepare, prepare, and commit stages. These stages are not simply three universal client round trips: message paths and the normal-case fast path matter. Authentication, quorum intersections, and view-change rules carry more complexity than a crash-fault protocol, so choose BFT only when its threat model fits.
When not to use BFT
Internal microservices where you trust your own code and operators.
When BFT can make sense
Multi-organization systems, blockchain validators, or safety-critical systems with external adversaries.
and practical implications
In a purely asynchronous system with even one faulty process, no deterministic algorithm can guarantee consensus termination. You cannot distinguish a slow node from a dead one without timing assumptions.
Timeouts (partial synchrony)
Assume the network is eventually timely. Leader consensus uses timeouts for election. Progress may pause during a partition, then resume after healing.
Randomization
Random delays reduce livelock. Raft uses randomized election timeouts (150–300ms).
Failure detectors
Eventually accurate failure detectors (Ω) make consensus solvable under weaker models.
In practice, leader consensus terminates in reasonable time on real networks. FLP is a theoretical limit, not a reason to skip timeouts.
Production systems using consensus
| System | Algorithm | Scale notes | Use |
|---|---|---|---|
| etcd | Raft | ~10K writes/sec | Kubernetes cluster state |
| CockroachDB | Raft | 50K+ writes/sec/range | Distributed SQL |
| TiKV | Raft | Millions of Raft groups | Distributed KV |
| Spanner-style store | Multi-Paxos | Global, 5+ replicas | Globally consistent DB |
| ZooKeeper | ZAB | ~10K writes/sec | Coordination |
| Consul | Raft | Multi-DC | Service discovery + KV |
| FoundationDB | Active Disk Paxos | Millions ops/sec | iCloud-scale backends |
| Kafka (KRaft) | Raft | Replacing ZooKeeper | Metadata management |
Paxos phase-by-phase
Basic Paxos: single-value agreement.
Phase 1a: PREPARE
Proposer → Acceptors: Prepare(n). n is a unique, monotonically increasing proposal number: "I want to propose with number n; what have you accepted?"
Phase 1b: PROMISE
If n > highest_seen: promise to reject proposals < n and return any previously accepted value. If n ≤ highest_seen: REJECT.
Phase 2a: ACCEPT
After obtaining promises from a majority, the Paxos proposer examines the accepted proposals those acceptors returned. If any exist, it must choose the value associated with the highest accepted proposal number among those replies; otherwise it may choose its own value. It then sends Accept with its new proposal number. This selection rule preserves a value that may already have been chosen by an earlier majority, even when the new proposer did not witness that decision.
Phase 2b: ACCEPTED
If n ≥ highest_promised: accept and persist. Consensus is reached when a majority accepts the same (n, value).
Dueling proposers (livelock)
Competing Prepare/Accept rounds can starve each other. Fix with random backoff or a stable leader (Multi-Paxos / Raft).
Viewstamped Replication and EPaxos
Viewstamped Replication (VR)
Predates Paxos (1988). Primary processes requests and replicates to backups. View changes when the primary fails. Similar power to Multi-Paxos; influenced Raft's leader-based design.
EPaxos
Leaderless: any replica can propose. Non-conflicting commands commit in one RTT (fast path); conflicts take a slow path. Better geo latency than a single Raft leader, but harder to implement.
Choosing and explaining consensus algorithms
A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.
Explain the core idea
Use consensus only for state that must have one authoritative order: leaders, metadata, locks, or replicated logs.
Leader consensus protocols tolerate crash faults with 2f+1 nodes; they do not tolerate Byzantine behavior.
The main product cost is write latency and reduced availability when no majority is reachable.
When it belongs
A design needs exactly one leader or scheduler.
Configuration changes must not split brain.
A database shard must survive node loss without losing committed writes.
How it fails
Network partition leaves minority replicas unavailable for writes.
Election timeouts are too aggressive and cause leader flapping.
Unbounded logs or slow snapshots make recovery take too long.
Trade-offs to weigh
Strong ordering versus lower latency eventual replication.
Small clusters are cheap but tolerate fewer failures.
Cross-region consensus improves durability but adds wide-area p99 latency.
Common misunderstandings
Saying consensus is needed for every request path.
Confusing quorum reads/writes with a replicated log consensus protocol.
Ignoring membership changes, snapshotting, and operational recovery.
Going deeper
Consensus algorithms
The mechanism and its boundary
Consensus lets a group of nodes agree on one ordered log even when some nodes fail. The key interview move is to distinguish consensus from replication alone: consensus decides which value wins and in what order.
Majority decision flow
Leader proposes
Majority accepts
Commit index moves
Followers apply
Work through the sizing assumptions
When it belongs
The system needs one leader, one lock owner, or one ordered metadata log. Split brain would corrupt state. A replicated control plane needs linearizable decisions.
Assumptions that matter
Small voter groups are preferred; large clusters shard consensus groups. Read-only followers may lag unless reads go through the leader or a lease. Clock assumptions must be explicit when leases are used.
Easy mistakes
Requiring a global consensus decision for every unrelated data write can serialize work that separate groups or a metadata-only consensus path could handle independently. Without snapshots, log compaction, and a recovery path for lagging followers, the retained log and catch-up work can grow until they threaten the active group. Voters placed across distant regions improve geographic resilience only at the cost of the network and durable-write latency required by the chosen quorum.
How it fails
Leader loses quorum and must stop accepting writes. Network partitions cause repeated elections and availability loss. Disk stalls on the leader delay the entire group.
Trade-offs to name
Waiting for a quorum gives the log a single agreed order, but every committed write pays for the required durable acknowledgements, which becomes especially visible across regions. More voters can tolerate more failures, but also increase replication work and change which acknowledgements are needed; benchmark the actual placement rather than assuming a larger group is automatically better. A leader simplifies ordering and recovery, but concentrates sequencing and write traffic on one node, so large systems often partition data into multiple consensus groups.
Wrap-up
You have walked leader logs, majorities, and when not to use consensus. Keep these sources handy when you need the original proofs and production caveats.
Primary sources
- Ongaro & Ousterhout: Raft (ATC 2014) : understandable consensus.
- Lamport: Paxos Made Simple : classic consensus.
- etcd Docs: why etcd / Raft notes : leases, elections, production caveats.
Key takeaway
Consensus is how distributed systems keep one truth. Prefer leader-based designs you can reason about, compact logs with , change membership one node at a time, and reserve BFT for untrusted parties. At billion-user scale, run thousands of independent consensus groups: one per partition, instead of one global bottle neck.
Practice and further reading
Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.
Focus for this lesson: Separate safety from liveness and compare Raft/Paxos terms, quorums, log agreement, linearizable reads, snapshots, and membership changes.
Explain the decision
Can consensus remain available without a majority?
Read the reasoning
Not while preserving its safety model; a minority cannot distinguish partition from a competing majority and must stop committing.
Apply it to a production scenario
A follower with a stale log wins votes after a partition. Which rule failed?
Read one approach
Voters must reject candidates whose last log term/index is less up-to-date, preserving leader completeness.
Work through the numbers
A seven-node group tolerates how many failures while retaining majority?
Read the worked calculation
Three; majority is four. More replicas increase fault tolerance but also quorum latency and operational cost.
Reason through a failure
What is the replicated-log invariant?
Read the recovery reasoning
Committed entries remain in the same order in every future leader and are applied exactly once per state-machine position.
Sources and further study
Continue with Quorum Consensus.