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
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
prevLogIndex/prevLogTerm, commit + apply, dedup, InstallSnapshot. Click a node to inspect or kill it. Submit ops by hand from the client controls.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.The controller publishes a new assignment describing which group owns which partition.
- 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.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.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.The new owner acknowledges to the old owner, which then deletes its frozen copy through its own log.
step
1 Assignment published
2 Old owner freezes
2–4 Neither owner serves
2–5 Old copy still held
3 New owner pulls
4 Install committed
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
Three bugs our reference implementation's harness found¶
| The bug | What it looks like | What fixes it |
|---|---|---|
| Stale read from a lagging replica | A 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 twice | The 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 early | The 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. |
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.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.
- Phone
- (214) 723-2510
- 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.
$199/month
Billed monthly
$182.42/month
Billed yearly
$499/month
Billed monthly
$457.42/month
Billed yearly
- Scammers stopped from sending email as you
- Your website and systems scanned every week
- Your email settings checked every week
- Everything in the 1 to 10 plan
- Covers up to 50 people
$199/month
after a one-time setup fee
- A site planned, designed and built for you
- Hosting and updates every month
$499/month
Billed monthly
$457.42/month
Billed yearly
$999/month
Billed monthly
$915.75/month
Billed yearly
- Your Google profile, fully set up
- A Google post every week
- 2 social posts a week
- Everything in Get found
- 4 social posts a week
- Your top 10 Google searches tracked
from$500/month
after a one-time setup fee
- Your data gathered from the tools you use
- A first analysis that answers your questions
- New findings every month
Related reading
Engineering3 min readLegacy software modernization: why rewrites get canceled, and a safer bet
A big-bang rewrite is a bad bet, not a bad pitch. Replacing the system one slice at a time changes the bet and gives the budget review something it can approve.
Engineering3 min readOffline-first apps: the product decision to make in week one
A field app that treats offline as an error state fails where the work happens. Three questions settled in week one decide whether yours will.
Engineering5 min readSemaphores explained: the count is the contract
Locks, caps and signals are one primitive with different starting counts. This article covers how semaphore code fails: deadlock, laps and a wrong starting count.
