Replication: Keeping Copies Honest

The write path can't have all three

When a write arrives, the leader faces one question: how many copies must hold this before I tell the client “done”? Answer “just me” (asynchronous) and the ack is fast and survives a dead follower — but if the leader dies before replicating, the acknowledged write is gone. Answer “me and every follower” (synchronous) and no acked write is ever lost — but one slow or dead follower stalls or blocks every write. Answer “a majority” (quorum) and you get the balanced middle. Three modes, one trilemma.

The clearest way to feel it: an asynchronous ack is a promise the system can’t yet keep. Here’s the policy knob from the reference implementation — the only difference between “safe” and “fast” is how many holders you count before acking.

1func (c *Cluster) Durable(index int, mode AckMode) bool {
2  switch mode {
3  case Async:
4    return c.Leader.LastIndex() >= index // the leader alone is "enough"
5  case Quorum:
6    holders := 0
7    if c.Leader.LastIndex() >= index {
8      holders++
9    }
10    for _, f := range c.Followers {
11      if f.LastIndex() >= index {
12        holders++
13      }
14    }
15    return holders > (len(c.Followers)+1)/2 // a majority must hold it
16  }
17  return false
18}

The Lag Budget: which reads may touch a replica

The double-transfer bug isn’t fixed by “turn off replicas.” It’s fixed by deciding, per read path, how stale a value is allowed to be — and routing accordingly. That decision is the Lag Budget: every read in your system gets an explicit maximum tolerable staleness, and only reads whose budget exceeds a replica’s current lag are allowed to use it.

What this sounds like in an interview

Exercises

1func (c *Cluster) Failover() *Node {
2  // leader is presumed dead; promote whoever is most caught up
3  newLeader := c.PromoteMostCaughtUp()
4 
5  // immediately start accepting writes on the new leader
6  for _, f := range c.Followers {
7    if f != newLeader {
8      // ...point each remaining follower at newLeader and keep streaming
9      f.ReplicateFrom(newLeader, newLeader.LastIndex())
10    }
11  }
12  return newLeader
13}