Consensus and Raft, intuitively

The problem: one shard map, three copies, no disagreement

Snip's shard router (05.01 Sharding: range, hash, directory) reads a map: logical shard 41 is on Postgres 9. During a rebalance (05.04 Rebalancing without downtime) the map changes. If one router believes shard 41 moved and another doesn't, writes for the same links go to two machines. The map must be stored on several machines so it survives failures, and yet every reader must see the same sequence of changes, as if there were one copy.

That's the consensus problem: several machines agreeing on a value, or a sequence of values, while some of them crash and messages are delayed or lost. Snip doesn't build it; it stores the map in etcd, which runs Raft. But knowing how Raft works explains what these systems can and can't do.

Majorities

Raft, like other consensus algorithms, makes progress whenever a majority of its servers is available. Any two majorities of the same group share at least one member, so two decisions made by two different majorities can't both go unnoticed: someone was in both.

A fourth server adds no tolerance over three, which is why clusters have odd sizes. etcd's guidance is 3 or 5 members, and probably no more than 7, since every write must reach a majority and more members means more waiting.

Terms and leaders

Raft divides time into terms, numbered 1, 2, 3 … Each term has at most one leader. The leader handles every request and tells the others what to do; followers just follow. This makes Raft much simpler to reason about than designs where anyone can propose.

Leader election. Followers expect regular heartbeats from the leader. If one hears nothing for its election timeout, chosen at random from a range such as 150–300 ms, it becomes a candidate: it starts a new term, votes for itself and asks the others for votes. A server grants at most one vote per term, and wins with a majority. The randomness makes it likely that one server times out first and wins before others start competing.

Log replication

Clients send commands to the leader ("move shard 41 to Postgres 9"). The leader appends each to its log, sends it to the followers, and once a majority have stored it, the entry is committed: it will never be lost or changed, and the leader applies it and answers the client. Followers apply committed entries in the same order, so every copy of the shard map goes through the same states.

The two rules that make it safe

Most of Raft's safety comes down to two checks, sketched here:

type Entry = { term: number; command: string };
type Node = { currentTerm: number; votedFor: string | null; log: Entry[] };

const lastTerm = (log: Entry[]) => (log.length ? log[log.length - 1].term : 0);

/** RequestVote: grant at most one vote per term, and only to a candidate whose log is at least as up to date. */
export function handleRequestVote(me: Node, term: number, candidate: string, candLastIndex: number, candLastTerm: number) {
  if (term < me.currentTerm) return false;
  if (term > me.currentTerm) {
    me.currentTerm = term;
    me.votedFor = null;
  }
  const upToDate =
    candLastTerm > lastTerm(me.log) || (candLastTerm === lastTerm(me.log) && candLastIndex >= me.log.length);
  if ((me.votedFor === null || me.votedFor === candidate) && upToDate) {
    me.votedFor = candidate;
    return true;
  }
  return false;
}

/** AppendEntries: accept only if our log has the leader's previous entry; then overwrite anything that conflicts. */
export function handleAppendEntries(me: Node, term: number, prevIndex: number, prevTerm: number, entries: Entry[]) {
  if (term < me.currentTerm) return false;
  me.currentTerm = term;
  if (prevIndex > 0 && (me.log.length < prevIndex || me.log[prevIndex - 1].term !== prevTerm)) return false;
  me.log = [...me.log.slice(0, prevIndex), ...entries];
  return true;
}

1. Only up-to-date candidates win. A server refuses its vote to a candidate whose log is behind its own (an older last term, or the same term but shorter). Since a committed entry is on a majority, and a winner needs a majority's votes, any new leader must already have every committed entry. Tested: a voter with a term-3 entry refused a candidate whose last entry was from term 2, even though that candidate's log was longer.
2. Logs must match before appending. The leader sends the index and term of the entry just before the new ones. A follower whose log doesn't have that entry rejects the request, and the leader retries further back until they match; then the follower overwrites its conflicting tail. Tested: a follower with stale term-2 entries rejected a mismatched append, then accepted one from the matching point and ended with the leader's log.

Real Raft also persists currentTerm, votedFor and the log to disk before answering, handles membership changes, and compacts the log with snapshots. Use a tested implementation; these sketches are for understanding.

What consensus costs

• A majority round trip per write. Spread a 5-node cluster over three regions and every write waits for a cross-region acknowledgement.
• No progress without a majority. A 3-node cluster with 2 nodes down is read-only at best. That's the C choice in CAP (08.03 CAP and PACELC, without the myths), made deliberately.
• Small data, not big. Consensus systems such as etcd, ZooKeeper and Consul hold configuration, leader leases and locks, not your main data. Systems that need consensus over big data (CockroachDB, Spanner) split it into many small replicated groups.

Recap

Interview questions