Day 10 · System Design
Distributed Consensus Protocols (Raft & Replicated State Machines)
How a cluster of unreliable servers agrees on one ordered sequence of events, using leader election and a replicated log.
01Overview & core concept
In a distributed cluster where nodes can crash and networks can partition, how do multiple independent servers reliably agree on a single shared state or sequence of events? Distributed consensus ensures that a cluster of N machines agrees on values or state transitions even if up to F nodes fail or become unreachable, provided a quorum majority is alive.
Quorum majority
Quorum = floor(N/2) + 1, and failures tolerated F < N/2. A 5-node cluster tolerates 2 simultaneous failures and keeps making progress.
Why majorities work
Any majority (3 or more of 5 nodes) is guaranteed to overlap with any previously formed majority, so committed data is never lost.
02Architecture & request flow
┌────────────────────────────────────────────────────────┐
│ Client │
└───────────────────────────┬────────────────────────────┘
│ 1. Write Command
▼
┌────────────────────────────────────────────────────────┐
│ Leader Node │
│ ┌─────────────────┐ ┌─────────────┐ ┌──────────┐ │
│ │ Consensus Module├──►│ Append-Only ├──►│ State │ │
│ │ (Raft / Paxos) │ │ Raft Log │ │ Machine │ │
│ └────────┬────────┘ └─────────────┘ └──────────┘ │
└───────────┼────────────────────────────────────────────┘
│ 2. AppendEntries RPC (Replicate Log)
┌──────┴─────────────────────────┐
▼ ▼
┌─────────────────────────┐ ┌─────────────────────────┐
│ Follower Node 1 │ │ Follower Node 2 │
│ ┌──────────┐ ┌────────┐ │ │ ┌──────────┐ ┌────────┐ │
│ │ Raft Log │─┤ State │ │ │ │ Raft Log │─┤ State │ │
│ │ │ │ Machine│ │ │ │ │ │ Machine│ │
│ └──────────┘ └────────┘ │ │ └──────────┘ └────────┘ │
└─────────────────────────┘ └─────────────────────────┘
3. Followers acknowledge -> Leader commits entry -> Applies to State MachineConsensus engines use the Replicated State Machine (RSM) model: if identical, deterministic state machines execute the exact same ordered sequence of log entries, they compute the exact same final state.
Core mechanics of Raft
1. Leader Election
Nodes are a Leader, Follower, or Candidate. Followers expect periodic heartbeats; on a timeout a follower increments its Term Number, becomes a Candidate, and starts an election (RequestVote RPC). Randomized election timeouts (150–300ms) prevent split-vote ties when multiple nodes time out at once.
2. Log Replication
All client writes go to the Leader. It appends the entry to its local log and broadcasts AppendEntries RPC to followers. Once a majority acknowledge writing the entry to disk, the leader marks it Committed and applies it to its local state machine.
3. Safety & Election Restriction
A voter rejects a candidate whose log is less up-to-date than its own (measured by lastTerm and lastIndex). This guarantees a newly elected leader already contains all previously committed entries.
03Real-world example: Kubernetes & etcd / Kafka KRaft
Kubernetes Control Plane
etcd is a distributed key-value store powered by Raft. All cluster state (Pods, Services, Secrets, Ingress rules) is written to etcd. As a CP system, Kubernetes avoids split-brain scheduling even during network splits.
Kafka Metadata Quorum (KRaft)
Modern Apache Kafka replaces external ZooKeeper with an internal Raft quorum (KRaft), managing partition leadership and topic metadata with sub-second metadata failovers.
Multi-Raft in CockroachDB / TiKV
Instead of one Raft group for the whole database (which bottlenecks write throughput), the storage layer is sliced into small ranges (e.g., 64MB chunks). Each range runs its own independent Raft group across physical nodes.
04Architectural trade-offs
| Dimension | Consensus Cluster (Raft / Paxos) | Primary-Replica (Async Replication) |
|---|---|---|
| Consistency Guarantee | Strict linearizability; zero data loss on node crashes. | Eventual consistency; risk of data loss on primary failover. |
| Write Latency | Higher; requires a network round-trip with at least floor(N/2) + 1 nodes. | Minimal; the primary commits locally and returns immediately. |
| Availability | Requires more than 50% healthy nodes. If 3 of 5 nodes die, writes freeze. | High; writes continue on the primary as long as it is alive. |
| Throughput Scaling | Adding more nodes decreases write throughput (more round-trips for quorum). | Adding read replicas scales read throughput linearly. |
Failure modes & mitigations
ReadIndex / LeaseRead Optimization
To serve linearizable reads without a full Raft log entry per read, the leader uses time-bounded Leader Leases, or checks its commit index against a heartbeat quorum before returning results.
Log Compaction & Snapshots
Unbounded log growth consumes disk space. Raft periodically writes a point-in-time state snapshot to disk and truncates older log entries.
05Interview question & approach
How would you design a distributed lock and configuration coordination service (similar to etcd or Consul) that guarantees strong consistency, supports watch notifications on keys, and safely expires dead client locks?
Consensus Core
Build the storage engine on a 3- or 5-node Raft consensus group to guarantee linearizable writes and automatic leader election.
Lease Management & Heartbeats
Implement ephemeral leases with a TTL. Clients periodically send keep-alive heartbeats over a gRPC stream. If a client crashes or disconnects, its lease expires and the service deletes associated keys, releasing locks.
MVCC & Watch Mechanism
Store every key update with a monotonically increasing 64-bit revision number (mod_revision). Clients open HTTP/2 or gRPC streams with a start_revision, and the server streams historical and real-time mutations in order, without polling.
Atomic Compare-And-Swap (Transactions)
Support atomic conditional transactions: IF (key.version == X) THEN (SET key = Y) ELSE (FAIL), executed strictly through the Raft log to prevent races across competing clients.