The Two Generals and Exactly Once
Two armies camp on two hills with a valley between them. If they attack at the same moment they win, and if either attacks alone it is defeated. Their only way to agree is to send messengers across the valley, where some are captured. However many confirmations the generals exchange, neither can ever be certain the other will attack.
This puzzle is more than fifty years old, and it is the reason no network protocol can deliver a message exactly once. Every reliable system you use delivers at least once instead, and makes the second delivery harmless. This topic gives the argument in plain words, then the two promises a system can honestly make and the third it cannot, and the one combination that gives the effect people mean when they say "exactly once".
The Puzzle
General A sends "attack at dawn". General B will not attack unless sure that A knows the message arrived, because otherwise A might hold back, so B sends an acknowledgement. Now A is in B's old position: A will not commit unless sure the acknowledgement arrived, so A acknowledges the acknowledgement. Whoever sends the latest message is always the one left unsure, and the chain never ends.
E. A. Akkoyunlu, K. Ekanadham and R. V. Huber published the problem in 1975, in a paper on the design of network communications, with two groups of gangsters in place of armies. Jim Gray gave it its generals in 1978, in his "Notes on Data Base Operating Systems", and his version is the one that stuck.
Why No Protocol Solves It
Suppose some protocol claims to end in certain agreement. Look at its last message. The protocol must work whether or not that message arrives, because it can be lost and its sender would never know. So neither general can depend on it, and it can be removed from the protocol without changing anything. Now the second-to-last message is the last one, and the same reasoning removes it too.
Repeat until nothing is left. A protocol of zero messages cannot produce agreement, so the original protocol could not either. The argument takes four sentences and applies to every channel that can lose messages, which includes every network your services talk over. Fixing it would need a channel that cannot lose anything, and no such channel exists between two machines.
Three Delivery Promises
A system that moves messages over a lossy link can make one of two honest promises. At-most-once means send once and never retry: no duplicates, and some messages lost. At-least-once means retry until acknowledged, the mechanism of the acknowledgements topic in this chapter: nothing lost as long as the sender keeps running, and some messages delivered twice, because an acknowledgement can be lost after its message arrived.
Exactly-once delivery between endpoints that can crash, over a link that can lose, is what the generals rule out. The sender cannot know whether its last message arrived, so it must either risk a loss or risk a repeat. A system that advertises exactly-once delivery means at-least-once delivery plus a receiver that recognizes the repeat.
Idempotence
An operation is idempotent when applying it twice has the same effect as applying it once. "Set copies on shelf to 2" is idempotent: repeat it and the shelf count is still 2. "One copy was checked out" is not: repeat it and the count drops by two. Everything the feed needs to survive duplicates comes down to making its operations behave like the first kind.
The feed has two ways to get there. It can send absolute state with a version: "branch 7, record 1048576: 2 on shelf, as of message 118". Lantern applies the newest version it has seen, and a repeat changes nothing. Or it can keep sending changes and have Lantern remember each branch's last applied sequence number and ignore anything older, which is the receiver from the acknowledgements topic. Both turn the duplicates that at-least-once delivery guarantees into no-ops.
Exactly-Once Effect
Put the two together: deliver at least once, and make the effect happen once, by deduplication or by idempotent operations. The detail that makes it work is where the record of what was applied lives. Lantern must write "applied message 118 from branch 7" in the same transaction as the shelf-count change. If the two are written separately, a crash between them either repeats the change or loses the record of it, and the duplicate gets through.
This is the idea behind payment idempotency keys and the transactional outbox. The practice, with keys, stored responses and relay processes, belongs to Backend Deep Dive: its "Failure by Design" chapter covers idempotency keys and the outbox pattern, and its "Background Work" chapter covers at-least-once and idempotent jobs.
Where This Book Stops
The generals are two parties and one link. Getting many machines to agree on one value while some of them crash is a harder problem, called consensus, with its own impossibility results and its own algorithms, and it belongs to the System Design course on the roadmap. This book stops at one machine and one link on purpose.
What carries over is the habit this chapter built. For every message a system sends, ask what happens if it is lost, what happens if it arrives twice, and what happens if it arrives late, and make each answer boring. The cost of the habit is a sequence number and a transaction per message. The cost of skipping it is a count that drifts for years.
The Two Generals problem is about an unreliable channel between honest parties: messages can be lost, nobody lies, and certain agreement is impossible. It explains why exactly-once delivery cannot exist.
The Byzantine Generals problem, published by Leslie Lamport, Robert Shostak and Marshall Pease in 1982, is about unreliable parties: messages arrive, but some participants lie or fail in arbitrary ways. It concerns fault-tolerant agreement among many machines and belongs to System Design.
- "One more acknowledgement would settle it." Each confirmation moves the uncertainty to the next message. The last message of any protocol can be lost, and its sender can never know whether it was.
- "Our message broker delivers exactly once, so the handler does not need to be idempotent." A broker's exactly-once features cover its own log and transactions. The email the handler sends, the card it charges and the row it writes in another database lie outside them, and a redelivery after a crash repeats all three.
- "Retrying until it succeeds gives exactly-once." It gives at-least-once. Every retry after a lost acknowledgement is a duplicate that the receiver has to recognize.
- "At-most-once is the safe choice." It is safe from duplicates by accepting losses. For a shelf count it means a number that drifts until someone counts the shelf by hand.
- "Deduplicating by message content is enough." Two genuine checkouts of two copies of The Dispossessed at the same branch produce identical content. Deduplication needs an identity the sender assigns, not a hash of the payload.
- Assume at-least-once delivery on every path and make every handler idempotent. Duplicates are not a rare fault; they are the price of not losing messages.
- Give every message a sender-assigned identity, and record it together with its effect in one transaction. Written separately, a crash between the two lets the duplicate through.
- Prefer messages that state absolute values with a version over messages that state changes. A repeated "is 2" is harmless; a repeated "one fewer" is not.
- Take the operational side from the practice books. Timeouts, retries, idempotency keys and the outbox are Backend Deep Dive's "Failure by Design" chapter.
Knowledge Check
Which retelling of the Two Generals argument is right?
- The generals fail because messengers are slow, so replies come too late
- The last message may be lost, so it cannot matter; drop it from the protocol, and repeat
- The generals fail because one of them may lie about the attack time
- The generals could agree with enough messages, but it would take too long
Which of these operations on the feed is idempotent?
- Set copies on shelf for record 1048576 at branch 7 to 2
- Subtract one from the copies on shelf for record 1048576
- Append a checkout event to record 1048576's history list
- Add one to the searches-today counter for branch 7
A worker reads jobs from a queue, processes each and then acknowledges it. If it crashes before acknowledging, the job is redelivered. What does this design give?
- At-most-once: a job is never processed more than once
- Exactly-once: the acknowledgement guarantees a single run
- At-least-once: no job is lost, but some may run twice
- No guarantee at all, since a crash can lose any job
Lantern deduplicates feed messages by a hash of their content. What goes wrong?
- Hashing every incoming message is too slow for 30 branches at once
- Two different feed messages could collide on the very same hash value
- Resent messages get new hashes, so the duplicates slip straight through
- Two real checkouts of two copies look identical and one is lost
Where does "exactly once" actually live in a system that works?
- In the transport, which can be configured never to duplicate
- In the broker, whose exactly-once setting covers the handler's effects too
- In the effect: at-least-once delivery plus a deduplicated update
- In the sender, which stops retrying once it has sent twice
You got correct