Building a distributed KV store from scratch

Distributed consensus is easy to explain at a whiteboard and difficult to preserve in a running system. The gap is filled with details: exactly when state reaches disk, which term a delayed response belongs to, and whether a restarted node can accidentally vote twice.

The useful part of Raft

Raft’s greatest feature is not that it is simple. It is that it gives the implementation a vocabulary: terms, leaders, committed prefixes, and a small collection of invariants that can be asserted continuously.

async fn replicate(&self, entry: Entry) -> Result<Index> {
    let index = self.log.append(entry).await?;
    let acknowledgements = self.broadcast(index).await;

    if acknowledgements >= self.quorum() {
        self.commit(index);
        return Ok(index);
    }

    Err(Error::QuorumUnavailable)
}

Real code is more defensive, but the shape matters: durability precedes replication, and replication precedes commitment.

Test the schedule

Most failures were not caused by an incorrect steady state. They were caused by an unfortunate ordering of individually reasonable events. The most productive test tool was therefore a deterministic simulator capable of reordering messages, advancing clocks, and replaying the exact schedule that produced a violation.

The lesson generalises beyond consensus: when concurrency is the problem, make the schedule an input.