Skip to content

Systems

Consensus is not the hard part: retries, compaction and partition moves

Consensus only replicates a log. Retried requests, log compaction and moving partitions between groups are what break in production.

Computing America. Applications, integrations, data analysis and AI/ML engineering.

Send the path
5 min readComputing America
Railway tracks splitting and rejoining in a switch yard, one switch mid-throw.

In short

  • Consensus algorithms replicate a log. Everything a usable system needs on top of that log, request deduplication and log compaction included, is application code you still have to write correctly.
  • A retried client request is indistinguishable from a new one unless the request carries an identity. Tag every operation with a client id and a sequence number, and answer anything at or below the highest sequence already applied with the saved reply instead of applying it again.
  • The deduplication table is data, not bookkeeping. If it stays behind when a partition moves, an acknowledged write gets applied a second time at its new home.
  • Partition-move handlers must be idempotent and keyed on the configuration number, because a leader can fail mid-handoff and its successor, unsure whether the step finished, will propose it again, so the same transition is committed twice.
  • Deleting the old copy of a moved partition before the new group has committed the install is how a crash turns into data loss. Wait for that commit and an acknowledgment to the old group.

What breaks in production is the part consensus leaves to your application: retried requests, log compaction, and partitions moving between groups as nodes join and leave.

You'll meet that part under other names:

  • Two stores must stay in agreement during a migration.
  • A retry from a phone on a bad connection mustn't duplicate the transaction.
  • A tenant has to move between shards without a maintenance window.

We keep a sharded, replicated key/value store as an internal reference implementation, with several consensus groups, a partitioned keyspace and partitions that migrate as groups join and leave. It's how we keep straight which problems an algorithm solves and which an engineer solves at two in the morning. It isn't a product, it has no monitoring, backpressure, tenant isolation or operational tooling, and we don't deploy it.

Crash the leader below and watch the term advance and a new one get elected. Keep crashing until fewer than three of the five are up, and watch what a minority can no longer do.

Interactive · Distributed state

A five-node consensus cluster, running

Live · 5-node Raft KV (single group)
Real elections, AppendEntries with prevLogIndex/prevLogTerm, commit + apply, dedup, InstallSnapshot. Click a node to inspect or kill it. Submit ops by hand from the client controls.
N0T0 · followerlog 0 · commit 0N1T0 · followerlog 0 · commit 0N2T0 · followerlog 0 · commit 0N3T0 · followerlog 0 · commit 0N4T0 · followerlog 0 · commit 0
Cluster
leader-
term0
alive5/5 · quorum
commit-
pending0
Counters
no leader
Legend
leader / append-ok
candidate / vote req
follower / append
installSnapshot
vote denied
dead node
Replicated log · indices 1–14
solid = committed · dashed = uncommitted · ░ = in snapshot
N0
N1
N2
N3
N4
Client requests
0 pending
waiting for first commit…
Protocol trace
…
Linearizability oracle
holds
kv[k] = total applied inc(k), checked every tick on the leader
get(k) results never decrease per key
Buggy mode
Submit opinjected as a fresh client request, routed to the current leader
What this isA browser model of the protocol our Go implementation follows: real terms, real vote counting, real commit rules, with the network simulated and message latency dialed down to something a human can watch. Crash the leader and a new term starts; revive it and it rejoins. There is no partition control. Restart recovery is modeled: Figure 2 lists currentTerm, votedFor and log[] as persistent state, so a revived node restores them and replays from its last snapshot rather than coming back empty.

What consensus gives you

The Raft paper (opens in a new tab) describes a protocol whose entire output is a replicated log: the same commands in the same order on every replica, surviving the failure of a minority of them. The application applies those entries, in sequence, to a state machine, which for a key/value store is a hash map.

One safety property inside the protocol is easy to skip. A majority of replicas holding an entry isn't enough for the leader to call it committed. The entry must also come from the leader's current term. Skip that condition and entries from an earlier term can be counted as committed and then overwritten. Nothing crashes, and the store is silently wrong.

Two things it does not give you

Retried requests look like new ones

A client sends a write. The leader replicates and applies it, then dies before the acknowledgment arrives. The client retries, and the new leader can't tell it's the same write, so it applies it twice. For an increment, a payment or an inventory decrement, that's corrupted state through a path the consensus layer counts as success.

Give each request an identity: a client id and a monotonically increasing sequence number. Keep the highest sequence applied per client, with the response it produced, alongside the data. This assumes each client has one request outstanding at a time. At apply time, a command at or below that sequence isn't re-executed; the saved response goes back to the client, because the retry is waiting for an answer. The Raft paper describes the same table (it tracks “the latest serial number processed for each client, along with the associated response”). The same pattern is the answer in any system that retries over an unreliable boundary.

The log grows forever

An append-only log with no compaction is a disk-space countdown. The application must snapshot its state machine periodically and tell the consensus layer it may discard the prefix. In the Raft paper a snapshot holds “the entire current system state”, and the same paper puts the per-client table in the state machine. So the deduplication table belongs in every snapshot. A snapshot of the data alone restores a replica that has forgotten which retries it already answered, and the retry is applied again.

A replica too far behind to catch up by replay is sent a whole snapshot, and what it does with its own log matters. Sometimes the snapshot “describes a prefix of its log (due to retransmission or by mistake)”. The paper then says the covered entries are deleted but “entries following the snapshot are still valid and must be retained.” A follower that discards its whole log on every snapshot throws those entries away.

Then somebody adds a node

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

When the assignment changes, partitions move and every key that isn't moving must stay available. Moving keys block, redirect or fail with a hint to refetch the assignment and retry, all without violating the ordering guarantees.

  1. 1.The controller publishes a new assignment describing which group owns which partition.
  2. 2.Each group sees partitions it holds that are no longer assigned to it, freezes them at the previous configuration's version and stops serving reads and writes for them.
  3. 3.The new owner sees partitions assigned to it that it doesn't hold, and pulls them from the old owner's frozen snapshot together with the old owner's deduplication table for those keys (the highest sequence and last response per client).
  4. 4.Until the new owner has committed the install in its own log, requests for those keys get an explicit wrong-owner error, and clients refetch and retry. No client is served a stale value.
  5. 5.The new owner acknowledges to the old owner, which then deletes its frozen copy through its own log.
Fig. 1

step

  1. 1 Assignment published

  2. 2 Old owner freezes

  3. 2–4 Neither owner serves

  4. 2–5 Old copy still held

  5. 3 New owner pulls

  6. 4 Install committed

  7. 5 Acknowledged, deleted

Neither owner serves the moving keys between the freeze and the committed install, and the old copy survives until the new owner acknowledges.

SourceHandoff sequence described in this article; steps are in order, not to a clock.

Interactive · Reconfiguration

Moving a partition between consensus groups

Live · 2 Raft groups · 4 shards · controller-managed
Shard data + dedup table migrate together. Click a shard to inspect. Toggle a bug to make the linearizability oracle scream.
Controllerconfig #1
s0G0s1G0s2G1s3G1
Group G0installed config #1
Group G1installed config #1
Client requests
0 pending
…
Reconfig trace
…
Linearizability oracle
holds
per shard: counter on owner = total applied inc(shard); never lost across migrations
Buggy mode
What this isThe part of the store that has no paper written about it. Publish a new assignment and watch the old owner freeze the partition, the new owner pull it out of that frozen snapshot, and requests for those keys fail with a wrong-owner hint in between. The deduplication table travels with the partition here exactly as it does in the implementation; the panel will show you what happens when it does not.

Three bugs our reference implementation's harness found

The bugWhat it looks likeWhat fixes it
Stale read from a lagging replicaA replica serves a read before applying recent entries, returning a value that was true a second ago.Route reads through the leader. It records its commit index, confirms it is still the leader (a heartbeat round with a majority, which the Raft thesis calls ReadIndex, or a lease, which relies on bounded clock skew), and answers only after its state machine has applied entries up to that index.
Configuration change applied twiceThe leader dies mid-handoff. Its successor, unsure whether the step completed, proposes it again, so the same transition is committed twice.Make every partition-move handler idempotent and key it on the configuration number, exactly like the client dedup one layer down.
Data loss from collecting too earlyThe old owner frees its copy the moment the transfer looks complete. The new group has not committed the install, its leader dies, and the data exists nowhere.The new owner's acknowledgment, not the end of the transfer, is the permission to free the old copy.
Each bug is correct on the happy path and wrong under one specific interleaving, which is why a functional test suite passes over it. The harness, which partitions the network, kills leaders and churns the configuration continuously, found all three.

What to check in your own system

  • Identity on retried operations: does a retry carry an id the receiver checks?
  • Idempotent transitions: can a migration step run twice and leave the same result?
  • Ownership handoff: is there a moment when two owners, or none, accept writes?
  • Cleanup: can the source copy be deleted before the install is committed?
  • Snapshots: does one carry the deduplication table, and does a follower keep the entries after the prefix a snapshot covers?
  • Reads: can a replica answer before it has applied entries up to the leader's commit index?

Sources

  1. 1.In Search of an Understandable Consensus Algorithm (Raft) (opens in a new tab), Ongaro & Ousterhout, Stanford University,

Next step

Send us the retry or migration path.

A sequence diagram, a runbook or a few lines on what happens when a write is retried or a store moves. We will mark where a duplicate, a gap or an early cleanup can occur.

Reply
A person replies, not a sequence: within one business day, from someone who would be on the engagement.

Packages

Start with a package

Four packages, each with its price on the page. Pick one and buy it online.

Billing