Raft Consensus¶

Why a storage engineer needs it¶

A single-node engine survives crashes; it does not survive the machine dying. Distributed databases — TiKV, CockroachDB, etcd, YugabyteDB, Kafka (KRaft), Consul — replicate each piece of data to several nodes and use a consensus algorithm so that all replicas agree on the same sequence of writes, even when nodes crash and networks partition. Raft (Ongaro & Ousterhout, 2014) is the one used almost everywhere today, chosen specifically for being understandable. Each node still runs a local storage engine underneath — usually RocksDB or Pebble — so storage roles at distributed-database companies expect you to understand both layers.

Read Replication and CAP Theorem first.

The core idea: a replicated log¶

Every node holds a log of commands and a state machine (the key-value store) that applies committed commands in log order. If all nodes apply the same commands in the same order, they end in the same state. Raft's job is only to make the logs agree. This is the WAL idea generalized to several machines.

Terms and roles¶

Time is divided into numbered terms. Each term has at most one leader; every other node is a follower (or, during an election, a candidate). The term number acts as a logical clock: any message with an older term is rejected, and a node seeing a newer term steps down to follower.

Leader election¶

1. Followers expect periodic heartbeats from the leader. If none arrives within a randomized election timeout (e.g. 150–300 ms), a follower becomes a candidate, increments the term, votes for itself, and requests votes from everyone.
2. Each node grants at most one vote per term, and only to a candidate whose log is at least as up-to-date as its own (compare last entry's term, then log length).
3. A candidate with votes from a majority becomes leader and starts sending heartbeats.

The randomized timeout makes split votes rare: usually one node times out first and wins before others start. The up-to-date check is what guarantees a new leader already has every committed entry.

Log replication and commitment¶

1. The leader appends the command to its log and sends AppendEntries(term, prevLogIndex, prevLogTerm, entries, leaderCommit) to all followers.
2. A follower accepts only if its log contains an entry at prevLogIndex with prevLogTerm. If not, it rejects, and the leader retries with an earlier index until the logs match, then overwrites the follower's conflicting suffix. This log matching check keeps all logs consistent.
3. Once an entry from the leader's current term is stored on a majority, it is committed; the leader applies it, replies to the client, and tells followers the new commit index.

With 3 nodes, a write needs 2 copies (tolerates 1 failure); with 5, needs 3 (tolerates 2). Commit latency = one round trip to the fastest majority plus each node's durable log append.

Where the storage engine comes in¶

Every Raft node must make its log entry durable before acknowledging it — otherwise a crash-and-restart could "forget" an entry the leader counted toward a majority, breaking safety. So each replication step costs an fsync (Durability and fsync), and practical systems batch many entries per fsync, pipeline AppendEntries, and write the Raft log itself into an LSM engine or a dedicated log store (TiKV's Raft Engine). The applied state machine is a separate key space in the same or another engine.

Snapshots: the log cannot grow forever. Periodically, a node snapshots its state machine, records the last included index, and discards the log before it. A follower that falls too far behind receives the snapshot instead of the missing entries. For an LSM engine, a snapshot can be the set of SSTable files at a sequence number — cheap to create because SSTables are immutable (RocksDB checkpoints hard-link them).

Scaling out: Multi-Raft¶

One Raft group means one leader handling all writes. Systems like TiKV and CockroachDB split the key space into ranges/regions (e.g. 96 MB each), each with its own Raft group of 3 replicas spread over the cluster. Thousands of groups share one storage engine per node. Ranges split when they grow and move between nodes for balance — see Partitioning vs. Sharding.

Reads¶

A leader cannot simply answer reads from its state: it might have been deposed by a partition without knowing it, and serve stale data. Safe options:

• ReadIndex: record the current commit index, confirm leadership with a heartbeat round to a majority, wait until applied up to that index, then read.
• Lease reads: the leader assumes leadership for a lease period shorter than the election timeout and reads locally — fast, but correct only if clocks drift less than the margin.
• Follower reads: with a ReadIndex obtained from the leader, or at a timestamp known to be safe.

Failure scenarios to reason through¶

Common pitfall¶

Counting an entry as committed once a majority has it, even if it is from an earlier term. Raft's commit rule only commits entries from the leader's current term by counting replicas; earlier-term entries become committed indirectly, when a current-term entry after them commits. The paper's Figure 8 shows how the naive rule lets a "committed" entry be overwritten after a leader change. It is the subtlest rule in Raft, and, together with the follower-fsync rule above, the one most often gotten wrong in implementations.