Distributed consensus, replication, and fault tolerance / personal lessonsLesson 12 of 17
Distributed systems · Lesson 12

Retries and the boundary of exactly once

Separate delivery attempts, command application, and external side effects.

By the end: Design a retry contract that handles lost replies without duplicating business actions.

A network acknowledgment is not a business transaction

A client sends Transfer(10). The service commits it and crashes before replying. The client retries. Consensus can agree that both messages occupy log positions; that does not tell the application whether they represent one intended transfer or two. The client needs a stable operation identity that survives retry and service failover.

At-most-once processing can avoid duplicates but allow loss if work is abandoned after uncertainty. At-least-once delivery retries until sufficient confirmation under its progress assumptions, but can deliver duplicates. Claims of exactly-once effects need a specified boundary: which state change, which identities, which retained records, and which failures. They do not mean the network delivers a packet exactly once.

Retry identity belongs to the intended operation

A request has at least two identities worth separating. A transport attempt identifies one send, while an operation identity identifies the business action that several sends may represent. A new connection, server, or message number can change the attempt without changing the operation. If a client intends one transfer, its timeout retry must retain that transfer's operation identity. If it intends a second transfer of the same amount to the same recipient, that is new work and needs another identity. Comparing request bodies cannot reliably distinguish these intentions.

Use a separate paper case with an initial balance of 70. The client creates operation K to debit 12. The service commits the debit, leaving 58, but the success reply is lost. If the client retries as K, a correct deduplication protocol returns the original result and leaves 58. If it retries as J, the server has no basis for treating J as the same intended action and may debit again, leaving 46. Both requests can be correctly replicated. The error would be in the client's operation naming contract, not consensus on log order.

The client must retain K through the failures it expects to retry across. Generating a key only in memory does not help after a client crash if restart generates a different key for the same outstanding action. A client can durably record the intended operation before sending it, or use another documented recovery mechanism that retrieves its identity. Distinct clients also need noncolliding namespaces. A key scoped to one authenticated account may be valid, but the server must use that same scope when looking up results. The string K alone is not globally meaningful.

At-most-once and at-least-once describe different risks. Never retrying an uncertain action can avoid a second attempt while leaving a lost request unperformed. Retrying until confirmation can overcome temporary losses under eventual communication assumptions, but creates duplicates when confirmations disappear. Exactly-once business effects combine retrying with a receiver that recognizes repeated intent and applies one relevant mutation. The network may still deliver many messages. This guarantee must name its durable state boundary, key-retention period, and assumed failures rather than claim that uncertainty no longer exists.

A timeout should therefore leave a client state such as pending or outcome unknown, not silently convert it into confirmed failure. A definitive application rejection is different because it reports a known result for that operation. Even a status query can race with an in-flight request. If a query returns no record while the original request is still delayed, that request may arrive afterward. Treating absence as proof that sending new work is safe requires a cancellation, expiration, or ordering contract that actually prevents the old request from executing.

Deduplicate atomically with the effect

Attach an idempotency key to one logical operation. The service atomically checks whether that key was processed, performs the mutation if new, and stores its result under the key. A repeated key with the same request returns the recorded result without repeating the mutation. Reject reuse of the same key for different parameters rather than silently treating different work as identical.

The deduplication record belongs in replicated and recovered state alongside the effect. If the effect commits but the key record does not, a retry can repeat it. If the record commits but the effect does not, a retry may falsely claim completion. Retention matters too: after the service forgets a key, a very late retry can appear new. Session sequence numbers require a policy for concurrent requests and out-of-order retries; “remember only the last number” is not automatically sufficient for arbitrary parallel clients.

One durable transition must include the result record

An atomic deduplication transition checks the operation identity, validates the associated request, performs the business change if needed, and stores the result. These steps must behave as one indivisible durable state change for the promised failures. Two requests carrying K can arrive at different servers concurrently. If each separately checks that K is absent before either inserts it, both may perform the debit. A unique key constraint can help establish exclusivity, but the application must couple the winning key insertion to the effect and handle the losing request without repeating the mutation.

In a replicated state machine, this decision can occur during ordered command application. Two log entries carrying K may both be committed, yet the first creates K's effect and result while the second returns that stored result. There is no requirement that the log contain K only once. There is a requirement that the application transition recognize it and that all replicas make the same decision from the same preceding state. Any snapshots and recovery paths must preserve the deduplication state needed by that contract, as well as the visible business balance.

Storing the result matters because returning the current balance is not necessarily returning the original operation result. Continue the earlier paper case. K debits 12 and records balance-after 58. Another legitimate operation L then debits 8, leaving 50. A retry of K should return the saved result appropriate to K's API, not pretend K just changed 70 to 50. Depending on the contract, that result may include a transfer identifier and status rather than a balance. The point is to preserve K's outcome despite intervening work.

Request equivalence also needs a definition. If K was used for debit 12 to Ada, reusing K for debit 15 to Bo must not silently return Ada's result. Store enough request information to compare relevant parameters, or a suitable canonical request digest under a specified design. The comparison should include fields that change the business meaning and the authorized identity scope. Incidental transport fields need not make a retry different. Authentication establishes which client may ask about K, but it does not by itself enforce that client's honest reuse of K.

Think through three crash positions on paper. Before the atomic transition commits, recovery must expose neither a completed debit nor a completed result record for K. After it commits but before the reply, recovery must expose both. After the reply, the same durable state supports subsequent retries. There must be no recoverable middle state with only one half. A local transaction or deterministic replicated transition can provide the needed boundary when correctly integrated with durable storage. Separately flushing two files eventually does not establish that boundary. The displayed table below assumes it already exists.

Work through the model

AttemptDurable key recordBalance changeResponse
First request KStore K → resultDebit 10 onceLost
Retry KFound existing resultNo new debitReturn saved result
New request JNew identityAnother debit possibleSeparate operation

Stage 1 of 3. All stages remain visible for comparison.

Step 0 / 2
The key record and balance change must share one atomic commit boundary.

Retention and request ordering change the retry contract

The displayed first request and retry represent one logical operation under key K. The row for J is deliberately different. It shows that two identical-looking debits can be legitimate separate work if their identities differ. The table does not model concurrent requests or disk failures. To extend it on paper, add an operation L between K and its retry, then verify that the retry still returns K's recorded result without undoing L or recomputing K. This distinguishes replaying a response from repeating a state transition.

Deduplication records cannot be deleted without considering delayed requests. Suppose K completes on Monday and its record is removed Tuesday. A delayed Monday retry reaches the service Wednesday. If the service accepts K as new, the one-effect promise no longer holds for that retry. A retention window is therefore part of the API, not only a storage optimization. The service may instead reject expired identities or close a client session under a rule that prevents old requests from executing. Whatever the choice, it must distinguish forgotten work from genuinely new work safely.

A client-supplied creation timestamp alone does not settle expiration. Clients may have inaccurate clocks, and delayed requests can arrive after the service's retention boundary. A design needs an authoritative admission rule and documented clock assumptions if time determines whether old work can run. Rejecting a very old request can preserve duplicate-effect safety while sacrificing its eventual completion. Accepting every request forever while forgetting all old keys cannot preserve arbitrary-late retry deduplication. The limitation follows from missing identity evidence, not from a shortage of retries.

Sequence numbers can reduce record storage for a restricted client protocol. If one client sends operation 1, waits for its result, then sends 2, the service can use the ordering contract to manage old results. Parallel requests within one client's sequence are different. Let request 11 arrive before request 10, with both intended as new work. Remembering only maximum sequence 11 and treating every lower number as already processed would incorrectly suppress 10. Conversely, remembering only the latest result cannot answer a retry of an earlier completed request accurately. Out-of-order operation admission and result retention need explicit rules.

Failover and restart test whether the retention promise is real. A service that deduplicates using a process-local cache works only until that cache disappears or another server handles the retry. A restored snapshot that retains the debit but loses K creates the same failure. Durable deduplication means the effect and the evidence required to recognize its repeats survive together under the specified recovery procedures. This is why later recovery work includes application metadata rather than treating snapshots as copies of the most visible business tables alone.

Crossing into another system

A database transaction cannot by itself atomically update its own row and send an irreversible email or charge through an unrelated API. The transactional outbox pattern stores the business change and an event in one local transaction. A relay reads committed outbox events and retries delivery. A consumer deduplicates by event identity or performs an idempotent transition. The relay can still send twice if it crashes after delivery but before recording its acknowledgment.

Idempotence means repeating the operation has the same relevant effect as doing it once. Setting a field to a specified value can be idempotent, while incrementing it usually is not; even setting a value may overwrite a newer concurrent update unless version checks protect it. State exactly what “same effect” covers. External providers need their own idempotency or transaction support; an internal consensus log cannot create that guarantee on their behalf.

An outbox preserves intent but still permits duplicate delivery

Consider a separate order service whose database owns an order row and an outbox row. One local transaction changes order O to confirmed and inserts event E saying that O was confirmed. If the transaction aborts, neither change appears. If it commits and the process immediately crashes, the event remains available for a restarted relay. This closes the gap where an order commits but the process dies before recording that any notification must be sent. The outbox provides durable delivery intent within the database boundary, not proof of external delivery.

The relay cannot solve its acknowledgment uncertainty by choosing a different write order. If it marks E delivered before sending, a crash between those steps can lose the notification. If it sends first and marks afterward, a crash between those steps can cause a duplicate send after restart. Waiting longer for a reply changes neither logical case. A receiver that atomically records E with its own effect can make repeated delivery safe within that receiver's boundary. The relay should preserve E's identity across attempts rather than minting a new event identity each time.

For a paper receiver, let E create one shipping task. On the first delivery, a transaction stores the task and records E's result together. Lose the reply. On the second delivery, the receiver finds E and returns its recorded task identifier instead of creating another task. If its transaction stores E but sends a physical parcel through an unrelated mechanism, the same boundary problem appears again at that next mechanism. Guarantees do not automatically extend through every downstream system. Each irreversible effect needs its own supported protocol or a weaker stated contract.

Idempotent updates also need concurrency analysis. Setting address to X twice has the same final address as setting it once if nothing intervenes. But if a legitimate later operation sets address to Y, a delayed repeat of set-X can restore an obsolete address. A version-conditional update or operation deduplication can prevent that overwrite under the intended contract. Algebraic idempotence of one function does not mean replay is harmless among arbitrary other functions. Likewise, fencing can reject old authority epochs while allowing duplicate actions within the current epoch. These mechanisms protect different conditions.

Finally, delivery progress remains conditional. An outbox event can persist safely while a receiver is unreachable indefinitely. Retrying forever does not make the receiver available, and duplicate suppression does not establish that every intended event has been delivered. Monitoring pending intent and recovering failed relays concern progress; preserving atomic records concerns safety. The next lesson examines how recovery and membership changes retain these obligations. A trustworthy restoration must preserve enough state to know both which business effects already happened and which delivery intents still require action.

Exercises

Key and effect in separate commits

A service debits an account, commits, then stores the request key in another transaction. What crash window remains?

Hint

Stop execution between the two commits.

Worked answer
Persistent state after crashRetry interpretationRisk
Debit exists; key absentNew operationSecond debit
Writing the key eventually is not enough.

A crash after the debit but before the key record leaves a completed effect with no deduplication evidence. A retry can debit again. Put both mutations in one atomic transaction or use another protocol that proves the equivalent boundary.

An outbox relay crashes

A relay delivers event E and crashes before marking it delivered. What must the receiver tolerate?

Hint

The sender cannot distinguish a lost delivery from a lost acknowledgment.

Worked answer
Relay restartReceiver without deduplicationReceiver with durable E record
Sends E againMay repeat effectReturns prior result or skips duplicate effect
Exactly-once business effects require a receiver-side contract too.

A later relay attempt may deliver E again. The receiver must deduplicate E atomically with its own effect, or make that effect safely idempotent. The outbox prevents a committed business change from lacking a durable delivery intent; it does not guarantee one physical delivery.

Sources and further reading

The explanations and worked answers above stand alone. These references provide the original algorithms, assumptions, and deeper proofs; they are not required downloads.