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

Reasoning through a distributed-system incident

Combine guarantees, failure evidence, recovery choices, and design tradeoffs.

By the end: Audit an expert design claim and diagnose a failure without mistaking missing evidence for failure of the protocol.

Start with promises and failure domains

Consider a reservation service with a three-node Raft group A,B,C, durable logs, an atomic Reserve command, and replicated request-key results. The service promises one owner per seat and linearizable confirmation reads. Search results use a separate stale cache. Email confirmations go through an outbox and an idempotent consumer. Those are deliberately different contracts for different operations.

Ask which failure each mechanism handles. A majority can preserve decision progress with one unavailable member under stable conditions, but a common software error can affect all members. The outbox protects a delivery intent, not the email provider’s availability. Backups protect selected recovery history, not zero data loss for every disaster. State recovery-point objectives, acceptable data loss, separately from recovery-time objectives, the acceptable time to restore service.

Turn each service promise into evidence requirements

Begin an incident record by separating an operation's specification from the evidence currently available. A reservation success promises an authoritative conditional state change. A search response may promise only a recently cached description. An email reports an event through another delivery path. If these observations disagree, the disagreement is a lead to investigate, not yet a contradiction in one object's contract. A stale search display and a correct reservation rejection can be the expected result of two deliberately different interfaces.

Give each observation an identity and a boundary. For a request, record its stable operation key and parameters, the invoked endpoint, and the actual response or timeout. For replicated state, record the configuration, leader election term, entry index and entry term, and any evidence of commitment and application. An election term names a leadership attempt; an entry term records when an entry originated. Treating both as one version number can conceal whether a new leader inherited an older command or appended a new command of its own.

Consider a separate paper case with three replicas in which request M reserves seat 27 for Inez. The leader records M at index 40 in term 8. A follower stores the prefix and returns an acknowledgment. The leader establishes commitment under the term-8 rules, then applies index 40 and stores M's result atomically with the reservation. Its response packet disappears. The client reports a timeout, but the state transition has already happened. Each sentence supplies a distinct premise. Removing the application step, for example, prevents us from inferring that a state-machine read already contains the reservation.

Continue the case with a leader election in term 9. A replacement containing index 40 may initially lack an exact known commit boundary. Its successful election does not alone certify a current confirmation read. It establishes the required current-term boundary under Raft's rules, confirms current authority through the chosen read protocol, and waits until its state machine has applied through the read index. Only then can that read answer under the promised linearizable contract. The new term does not change the entry term of M, and it does not turn application lag into missing committed history.

Use this paper case to annotate an incident timeline with two kinds of statement. Mark observed facts such as a captured response or a persisted record separately from conclusions that depend on the protocol assumptions. A log line saying commit may be evidence about what a process believed, not independent proof that disks honored durability. A success recorded by the client establishes the client-visible promise even if some server logs are missing. Keeping those categories separate prevents an investigator from assuming the very storage or implementation behavior that the incident calls into question.

Trace the incident before diagnosing it

A logs request K to reserve seat 12 for Ada. B persists it and acknowledges; A commits and applies it. The reply to Ada is lost. A then becomes isolated from B and C. B, whose log includes K, wins the next term with C under the normal rules and establishes its current-term committed boundary. Ada retries K at B. B must return the saved result without reserving a second time. A stale search cache may still show the seat as empty, but an authoritative reservation by Bo must reject.

An old worker attached to A may still believe it owns an external resource. Fencing must be checked at that resource. A stale local read from A must not be presented as a linearizable confirmation. If B and C later cannot communicate with each other, lack of a majority can stop new decisions while the old committed seat assignment remains safe. No successful response is not the same as lost committed data. Conversely, forcing service by erasing history or bypassing quorum rules can create the loss you were trying to avoid.

Test competing explanations against the same observations

The incident above supplies a specified history with known premises. A real investigation usually begins with less information. Suppose a customer reports a timeout and later sees an empty seat in search. At least three explanations remain possible. The original request may never have reached the service. It may have committed while search still lags. Or the authoritative path may have violated its contract. These explanations require different evidence, so restarting everything before collecting records can destroy the distinctions needed to choose among them.

An operation-status lookup should use the original key and the documented authority, rather than issuing a new reservation as a diagnostic probe. If the status read itself is stale, an absent key does not settle the original outcome. If the API cannot distinguish absent from unknown during recovery, report that uncertainty. A new request identity creates new work and changes the system being investigated. Preserving the original identity lets the deduplication mechanism answer the original business question without deliberately introducing another effect.

Check the atomic boundary rather than merely searching for both records somewhere. A recovered seat owner and a recovered request result must represent the same committed transition if the retry contract depends on them. Two independently persisted records can appear correct after a clean shutdown while failing between writes. A snapshot that preserves the seat but omits a retained key can create the same problem after restoration. The relevant evidence includes transaction boundaries and snapshot metadata, not only the final business row. A durable deduplication result with different request parameters is also a contract error, not a valid retry match.

For guided exploration, construct two paper timelines that give the client the same timeout. In the first, stop before the server appends anything. In the second, stop after atomic application but before the reply arrives. Ask what a correct status protocol can eventually reveal after recovery. Then add an outbox event to the second timeline and let the relay crash after the receiver accepts it but before the relay records delivery. The business mutation remains single, while delivery may repeat. Receiver-side durable deduplication must protect any non-idempotent effect it promises to perform once.

These paper timelines are not additional controls in the worked model below. Its rows present the authored reservation incident and preserve all stages for comparison. They do not execute alternative leaders, snapshot installation, status queries, or an email service. Read the rows by asking which premise licenses the next conclusion. In particular, committed at A and B assumes the normal current-term commitment rules, and retry returns the result assumes replicated, recovered, atomic request-key state. Without those premises, the same row labels would not prove the claimed client behavior.

Work through the model

EventDurable/authoritative stateClient observation
K stored at A and BK committed under term rulesWaiting
Success response lostSeat belongs to Ada; K result storedTimeout
B takes over with CCommitted history preservedRetry can reach B
Retry same KReturn original resultOne reservation confirmed
Bo sees stale cacheCache is not the authorityFinal Reserve must reject

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

Step 0 / 4
This is a specified incident, not a measured production trace. Each conclusion follows from the stated protocol and API contracts.

Reconstruct a history without inventing real-time order

The worked model's ordering is part of its stated example. Production records do not automatically provide that ordering. Wall clocks on separate hosts can disagree, and a log collector can receive old records after new ones. Sorting timestamps can therefore place a response before its cause or make two overlapping operations appear strictly ordered. Begin with local program order, request identifiers, and message dependencies. Add cross-host physical-time constraints only when the measurement system supplies justified uncertainty bounds.

Suppose a response timestamp on one host estimates its actual time as between 100 and 104 milliseconds on an agreed reference scale. A later request's timestamp on another host estimates between 103 and 107. These intervals overlap. Timestamp evidence alone cannot prove the response completed before the request began. If the second request instead has an invocation interval between 106 and 110, the first response's latest possible time precedes the second invocation's earliest possible time. Under those stated bounds, the real-time precedence is supported. The numbers are constructed examples, not claimed clock measurements.

A complete client trace can establish order without synchronized server clocks. If one client waits for a successful reservation response and only then invokes a confirmation read, its program order supplies the required precedence. A read returning empty with no intervening release would contradict the stated reservation contract. If the read overlaps the reservation, that same return may be legal. If the reservation timed out, the trace contains an incomplete operation whose possible effect must be considered. A timeout cannot simply be rewritten as a completed rejection to make history analysis easier.

The earlier register widget is deliberately narrower than this investigation. It searches orders for at most eight complete operations on one register initially zero. A reservation object's conditional success and rejection rules differ from register replacement, and this incident includes incomplete requests and external effects. Passing a simplified register history to that checker would not validate the reservation service. On paper, write the actual sequential rule first, including how occupied seats reject and how repeated keys return saved results. Then check whether each proposed order obeys that rule and every established real-time constraint.

Absence of a counterexample in captured traffic has a limited meaning. Missing response records can hide completed operations, and inspecting one server can miss a leader change elsewhere. Conversely, a single genuine forbidden history can refute a universal safety claim under its assumptions. Preserve the raw observations and mark any inferred completion, omitted interval, or uncertain clock relationship. This lets another investigator challenge the reconstruction rather than debate a timestamp sort as though it were the execution itself. The useful result is either a supported violation or a precise account of which missing evidence prevents a conclusion.

Evaluate tradeoffs and test the contract

Coordination has costs even without failures. A leader and its durable quorum need communication and storage work; a remote member on the critical acknowledgment path can add wide-area latency. Batching can amortize work but add waiting. Pipelining can increase throughput without reducing the latency of an individual required round. More read replicas can scale suitable reads; they do not automatically increase one log’s write throughput. Partitioning creates more independent logs but introduces cross-partition coordination when invariants span them.

To test a design, record operation identities, invocation/response intervals, outputs, terms, log positions, and relevant failure events. Inject message loss, long pauses, retries, crashes before and after persistence, and restore from snapshots. Account for clock uncertainty when reconstructing cross-client real-time order; wall-clock sorting alone can invent violations. Check safety in recorded histories and progress only under stated recovery conditions. Passing tests is evidence, not a proof over all schedules. You should now be able to ask an expert: What is the object contract? Which quorum remembers what? Where is the atomic boundary? Which assumptions protect safety, and which are needed only for progress? Full protocol proofs, production implementation, performance tuning, and specialized Byzantine protocols remain deeper work.

Match recovery experiments to the failure being claimed

A fault-injection plan should name the fact each experiment tries to distinguish. Crash after a durable append but before acknowledgment to test recovery of stored evidence without leader knowledge. Crash after atomic application but before the client reply to test retry results. Delay state-machine application after commitment to test read barriers. Restore a snapshot and replay a retained operation key to test whether recovery preserves the advertised deduplication window. These experiments target different boundaries; repeating an ordinary process kill at random times may never reach the one that matters.

State the storage contract beside every crash experiment. A process restart with its durable disk intact tests a different assumption from permanent disk loss. Three logs on three processes are not independent protection if all reside on one failed volume. Conversely, a process that stops before flushing a write does not prove that a correctly acknowledged durable write was lost. Record when the implementation claims persistence and which failure the test introduces. Without that pairing, a test can accidentally assume stronger durability than the implementation advertises or excuse a loss that its contract forbids.

Correlated failures need an allocation argument. In a separate planning example, five voting replicas require three votes. Place three replicas in one power domain and two in another. Losing the three-replica domain leaves two votes and stops normal decisions, despite having five machines in total. A placement of two, two, and one across three independent domains retains at least three votes after any single domain loss. That arithmetic still assumes surviving members can communicate, storage remains usable, and leadership stabilizes. The placement does not certify progress during a failure that isolates all three domains from one another.

Recovery objectives constrain the allowed response to such outages. A zero acknowledged-data-loss objective rules out restoring an older backup and silently claiming the old success history remains intact. A short restoration-time objective may conflict with waiting for unavailable evidence. The decision must state whether service remains unavailable, whether operators accept an explicit recovery-point loss, and how the old authority is fenced before a replacement becomes authoritative. Declaring a survivor the whole cluster changes the protocol assumptions. It is not an ordinary timeout adjustment or a harmless way to lower the quorum temporarily.

Finally, test progress only after specifying the recovery conditions. If the network remains partitioned below quorum, a correct service may reject or wait while preserving prior decisions. That is a loss of successful service for affected operations, not satisfaction of CAP's formal availability through error responses, and not necessarily data loss. Once the test restores the required communication and functioning storage, measure whether useful requests resume under the implementation's stated assumptions. Keep the safety history and the progress observation as separate results. Neither bounded schedules nor the preserved lesson models establish a full Raft implementation proof, a database validator, or protection against arbitrary Byzantine behavior.

Exercises

Audit the incident

A team claims the timeout proves K failed, the stale cache proves Raft lost data, and retrying with a new key is safest. Assess all three claims.

Hint

Keep client knowledge, cache freshness, and operation identity separate.

Worked answer
ClaimMissing distinctionCorrect investigation
Timeout means failureUnknown outcome vs rejectionQuery/retry K
Stale cache means lost logCache vs authoritative stateRead committed reservation
New key is safestRetry vs new operationPreserve logical operation identity
An incident diagnosis must identify which layer violated which promise.

All three claims are unsupported. The timeout can be a lost success reply. The cache has a weaker contract and does not establish a divergent committed log. A new key represents new work and defeats deduplication; retry K through the documented status/retry protocol. Investigate authoritative history before diagnosing data loss.

Design a regional outage policy

A,B are in one region; C is in another. The first region is unreachable. Can C alone continue majority decisions without changing the safety argument? Suggest a better planned design if surviving either region is required.

Hint

Count surviving votes, then consider common failure domains rather than machine count.

Worked answer
Placement and outageSurviving votesNormal progress
2+1; two-node region lost1 of 3No
1+1+1; one region lost2 of 3Possible with stable communication
Two disconnected sides each forced authoritativeCompeting membershipsSafety argument broken
Placement changes which correlated failure the quorum can tolerate.

C has one of three votes and cannot continue normal majority decisions. Simply declaring it a new cluster risks conflict with A+B and missing history. A planned three-region placement with one member per region can retain two votes after any one region fails, provided the surviving pair can communicate and other assumptions hold. It adds coordination latency and still does not survive every multi-region failure. Two regions alone cannot both independently retain exclusive majority authority during a partition.

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.