Distributed consensus without the hand-waving

Distributed consensus is often treated as academic cryptography or a mythical property granted automatically by deploying etcd or ZooKeeper. At its core, consensus is straightforward: ensuring a cluster of independent, fault-prone nodes agree on an append-only ordered sequence of state machine transitions.

The difficulty lies not in the happy path—which is simple quorum voting—but in how the protocol guarantees safety during partial network partitions, asynchronous clock drift, and concurrent leader elections.

The replicated log abstraction

Whether you implement Raft, Multi-Paxos, or Viewstamped Replication, the fundamental model is a Replicated State Machine (RSM). If two deterministic state machines start in the identical initial state and apply the exact same sequence of log entries in the identical order, they will produce the identical terminal state.

// Go snippet: Raft Log Entry and AppendEntries RPC validation
type LogEntry struct {
    Index uint64
    Term  uint64
    Data  []byte
}

type AppendEntriesRequest struct {
    Term         uint64
    LeaderID     string
    PrevLogIndex uint64
    PrevLogTerm  uint64
    Entries      []LogEntry
    LeaderCommit uint64
}

func (n *RaftNode) HandleAppendEntries(req *AppendEntriesRequest) bool {
    n.mu.Lock()
    defer n.mu.Unlock()
    
    // 1. Reply false if term < currentTerm
    if req.Term < n.currentTerm {
        return false
    }
    // 2. Reply false if log doesn't contain entry at PrevLogIndex matching PrevLogTerm
    if !n.hasMatchingEntry(req.PrevLogIndex, req.PrevLogTerm) {
        return false
    }
    // 3. Insert new entries, overwriting conflicting uncommitted entries
    n.appendEntries(req.Entries)
    return true
}

Consensus protocols do not prevent split-brain states; they make split-brain states unobservable to clients by requiring strict majorities \(\lfloor \frac{N}{2} \rfloor + 1\) for log commit.

The subtlety of linearizable reads

Writing to a consensus cluster requires a round-trip to a majority quorum before acknowledging success. Serving read requests, however, presents a subtle danger: if a partitioned leader serves reads from its local state without checking with peers, it might return stale data if a new leader has already been elected in the majority partition (phantom reads).

To achieve linearizable reads without paying the overhead of writing dummy log entries:

• Read-Index verification: The leader records its current commitIndex, broadcasts a zero-entry heartbeat to a majority to confirm it is still the legitimate leader, and returns data once its state machine applies up to that index.
• Leader leases: The leader assumes authority for a bounded time window smaller than election timeouts. This requires monotonic hardware clocks and bounded clock skew.

Compaction and snapshotting

An append-only log cannot grow unbounded without exhausting disk space and causing endless restart recovery times. Production systems periodically snapshot the in-memory state machine (writing a point-in-time image to disk) and truncate committed log entries preceding the snapshot index.

Building consensus engines or debugging raft state machines in production? Get in touch.