Consensus is not the hard part. Reconfiguration is.

There is a well-worn path through distributed systems. You read the consensus paper, you implement leader election and log replication, your test suite goes green, and you conclude that you understand replicated state. You do not, yet. You understand the part that has a paper written about it.

We keep a sharded, replicated key/value store as an internal reference implementation: multiple consensus groups, a keyspace partitioned across them, and partitions that migrate as groups join and leave. It is not a product and we do not deploy it. It exists because building it is the cheapest way we know to stay honest about which distributed-systems problems are solved by an algorithm and which ones are solved by an engineer at two in the morning.

Rather than ask you to take the next two thousand words on trust, here is the protocol running. Crash the leader, partition the cluster, and watch which side is still allowed to commit.

What consensus actually gives you¶

The Raft paper describes a protocol whose entire output is a replicated log: a sequence of commands, in the same order, on every replica, surviving the failure of a minority of them. The application on top applies those entries in order to a state machine. For a key/value store the state machine is a hash map and the entries are reads and writes. That is the whole deal, and stated that way it sounds like a few hundred lines of glue.

One safety property inside that protocol is the one almost every first implementation gets wrong. It is not sufficient for a majority of replicas to have replicated an entry before the leader calls it committed. The entry must also come from the leader’s current term. Skip that condition and a deposed leader’s entries can be counted as committed and then overwritten later, which is a silent correctness failure rather than a crash. It is a two-line check, and finding out you need it by reasoning from first principles costs a week.

Two things it does not give you¶

Both of the following are application-level concerns, both are unavoidable, and both are where the uncomfortable bugs live.

Client requests are not automatically linearizable¶

A client sends a write. The leader replicates it, applies it, and dies before the acknowledgement arrives. The client, seeing no response, retries. The new leader has no way to know this is the same write, so it applies it twice. If the operation was an increment, or a payment, or an inventory decrement, you have just corrupted state through a mechanism the consensus layer considers a complete success.

The fix is to give requests an identity: tag each one with a client id and a monotonically increasing sequence number, keep the highest sequence applied per client alongside the data, and silently skip anything at or below it at apply time. It is perhaps fifteen lines. It is also the difference between a store and a hazard, and the same pattern is the correct answer in any system that retries over an unreliable boundary, which is to say every integration we have ever built.

The log grows forever¶

Replicated logs are append-only, and an append-only structure with no compaction is a disk-space countdown. The application has to snapshot its state machine periodically and tell the consensus layer it may discard the prefix. A replica that has fallen too far behind to catch up by replaying entries must instead be shipped a whole snapshot. This is routine until it interacts with the topology changing underneath it, at which point it stops being routine.

Then somebody adds a node¶

A single consensus group can only serve what one replica can handle, because every operation goes through agreement. Scaling means partitioning the keyspace across several groups, each owning some partitions, with clients routing by key. Hash modulo group count is the obvious partitioning and the wrong one, because adding a group reshuffles almost every key. An explicit partition-to-group assignment table, itself replicated, is simpler to reason about and far easier to inspect when something is wrong.

Eventually the assignment changes. Partitions have to move from old owners to new ones while the system stays available for every key that is not moving, and while the keys that are moving either block, redirect, or fail with a hint that tells the client to refetch the assignment and retry. Doing that without violating the ordering guarantees you just spent a month establishing is the actual work.

1. 1.The controller publishes a new assignment describing which group owns which partition.
2. 2.Each group notices that partitions it holds are no longer assigned to it, and freezes them at the previous configuration’s version rather than continuing to serve writes.
3. 3.The new owner notices partitions assigned to it that it does not hold, and pulls them from the old owner out of that frozen snapshot.
4. 4.Until the new owner has installed the data, requests for those keys are rejected with an explicit wrong-owner error, and clients refetch and retry rather than being served stale values.

Three bugs, and what they cost¶

All three share a shape: they are correct under the happy path and wrong under a specific interleaving that a functional test will never produce. They are found by adversarial harnesses that partition the network, kill leaders and churn the configuration continuously, not by more careful reading.

Why this shows up in commercial work¶

Almost no client asks us to build a consensus protocol, and we would push back hard on one who did. What clients ask for constantly is a system that keeps two stores in agreement during a migration, or that accepts a retry from a mobile device on a bad connection without duplicating the transaction, or that moves a tenant between shards without a maintenance window.

Those are the same four problems wearing different clothes: identity on retried operations, idempotent transitions, ownership handoff without a gap or an overlap, and cleanup that happens after confirmation rather than before it. Having built the version with no business logic in the way is what makes them recognizable when they arrive dressed as a shipping integration.

One honest limit. A reference implementation that survives a hostile test harness is not production infrastructure. It has no monitoring, no backpressure, no multi-tenant isolation and no operational tooling, and we would not claim otherwise. Knowing precisely how far it is from production is part of what the exercise teaches.