Building Software
Sections

Contents Section 5, State

Distributed Systems and Partial Failure

When work spans machines, any step can fail, stall or happen twice, and the design has to assume it will.

Section 5 of 9, subsection 4 of 4. Depth: do. Core 13 of 25. A 10-minute read.

Mistakes to catch in review

  1. Retries without idempotency that charge a customer twice when the first attempt had actually succeeded.

  2. Missing timeouts, so one slow dependency ties up every request that touches it.

  3. Immediate retries without backoff or jitter that turn a brief outage into a retry storm.

  4. Events ordered by wall-clock timestamps taken on different machines.

The Call That Might Have Worked

An agent builds your checkout. It calls the payment provider, waits up to ten seconds, and if no answer comes back it shows the customer "Payment failed, please try again." The customer clicks the button again. Two days later they email support: their card was charged twice.

Nothing crashed. The first charge went through. The provider's response was slow, or it was lost on the way back, and your code treated "I did not hear back" as "it did not happen." Those are two different facts, and many distributed-systems bugs come from confusing them.

The third outcome

Inside one process, a function call ends with a return or a throw, and if the process dies the caller dies with it, so nobody is left wondering. A call to another machine adds a third outcome, where the caller survives but loses contact: you do not know.

The request may never have arrived. It may have arrived and failed. It may have arrived, succeeded, and the response was lost or delayed past your timeout. From the caller's side, those cases look identical: silence.

The caller, on the left, sends a request that can end three ways, shown as three boxes in a column: never arrived, request lost; arrived and failed; succeeded, response lost or late. Dashed arrows run from all three boxes to one box on the right labelled silence, all the caller sees. A note reads: identical from the caller's side.
The request may never have arrived, may have failed, or may have succeeded with the response lost; the caller sees silence in all three.

When the provider's acknowledgment of completion does reach you, the call is settled. The trouble is the call where none arrives: without one, you cannot tell a lost request from a lost response. Making the acknowledgment itself reliable takes another acknowledgment, which can be lost too, and so on without end. This is the two generals problem, and it is why a sender over an unreliable network cannot be certain in every case that the other side acted on its message.

So every remote call forces a choice. You can send once and never retry, which means some messages are lost (at-most-once). Or you can retry until you get an answer, which means some messages are delivered more than once (at-least-once).

Exactly-once delivery would require the sender to know something it cannot know. What real systems do is deliver at-least-once and make the receiver handle duplicates so that processing a message twice has the same effect as processing it once. That property is called idempotency, and the combination is often called effectively-once processing.

Idempotency keys

Here is how to build a payment endpoint that is safe to retry. The client creates a random ID for each logical purchase, before the first attempt, and sends the same ID on every retry of that purchase. The server stores the result for each ID and returns the stored result when it sees the ID again.

SQL
CREATE TABLE idempotency_keys (
  key          text PRIMARY KEY,
  request_hash text NOT NULL,
  status       text NOT NULL CHECK (status IN ('pending', 'done')),
  response     jsonb
);
TypeScript
async function charge(key: string, req: ChargeRequest): Promise<ChargeResponse> {
  const hash = sha256(JSON.stringify(req));
  const inserted = await db.query(
    `INSERT INTO idempotency_keys (key, request_hash, status)
     VALUES ($1, $2, 'pending') ON CONFLICT (key) DO NOTHING`,
    [key, hash],
  );

  if (inserted.rowCount === 0) {
    const { rows } = await db.query(
      "SELECT request_hash, status, response FROM idempotency_keys WHERE key = $1", [key]);
    if (rows[0].request_hash !== hash) throw new ConflictError("key reused with different request");
    if (rows[0].status === "pending") throw new ConflictError("original request still in progress");
    return rows[0].response;
  }

  const result = await paymentProvider.charge(req, { idempotencyKey: key });
  await db.query(
    "UPDATE idempotency_keys SET status = 'done', response = $2 WHERE key = $1",
    [key, result],
  );
  return result;
}

Walk through the retry. The client sends key k1. The server inserts k1 as pending, charges the card, stores the response, and replies. The reply is lost.

The client times out and retries with k1. The insert hits the primary key and changes nothing, so the server reads the stored row, sees done, and returns the original response. The card was charged once, and the client got its answer.

Each line guards a specific case. The primary key makes the claim on k1 atomic, so two retries arriving at the same moment cannot both charge. The pending state tells the second one that the first is still running. The hash catches a client bug that reuses one key for two different purchases.

And the key is passed on to the provider, because the same problem exists one hop further down: if the server crashes after charging but before recording done, the key stays pending, and whatever process cleans up pending keys needs to be able to ask the provider what happened to k1 rather than charging again. Payment APIs such as Stripe accept an idempotency key for exactly this reason: because the provider deduplicates on the key, retrying the provider call with k1 returns the first charge instead of making a second one.

Two rows. The top row is attempt 1: the client sends key k1, the server inserts k1 with status pending, the card is charged with k1 passed to the provider, the server stores the response with status done, and the reply is lost, marked with a cross. The bottom row is the retry: the client retries with the same key k1, the insert hits the primary key and changes nothing, the server reads the row and sees done, linked by a dashed line to the stored row above, and the client gets the original response, highlighted. A note reads: charged once.
The first attempt charges the card and stores done, but its reply is lost; the retry with the same k1 hits the primary key, reads done, and gets the original response.

Keys do not last forever. Stripe, for example, may remove a key once it is at least 24 hours old, and your own table should expire old rows too. Retry within that window. After it, a retry with the same key can become a second charge, so look up the original payment at the provider and reconcile before charging again.

A real version of this endpoint also records definite failures, such as a declined card, so the key does not stay pending forever. Only an unknown outcome should leave it pending for the cleanup process to resolve.

The client side matters as much. The key must be generated once per purchase and reused across retries. A key generated inside the retry loop gives each attempt a fresh key, and the server correctly treats each one as a new purchase.

This block runs both clients against a server that stores one response per key and loses the reply to the first attempt.

TypeScriptRuns in your browser
// A stand-in for the server above: it stores one response per key,
// and the reply to the first attempt is lost on the way back.
let charges = 0;
let replyLost = true;
const stored = new Map<string, string>();

async function chargeEndpoint(key: string, cents: number): Promise<string> {
  const earlier = stored.get(key);
  if (earlier) return earlier;
  charges += 1;
  const response = `charge #${charges} for ${cents} cents`;
  stored.set(key, response);
  if (replyLost) {
    replyLost = false;
    throw new Error("timeout");
  }
  return response;
}

let keysMade = 0;
const newKey = () => `key-${++keysMade}`;

async function payWithRetries(cents: number, keyFor: () => string) {
  for (let attempt = 1; attempt <= 3; attempt++) {
    try {
      return await chargeEndpoint(keyFor(), cents);
    } catch {
      // timed out: try again
    }
  }
  throw new Error("gave up");
}

const fresh = await payWithRetries(2500, newKey); // new key on every attempt
console.log("key made inside the loop:", fresh, "| charges:", charges);

charges = 0;
replyLost = true;
const purchaseKey = newKey(); // made once, before the first attempt
const reused = await payWithRetries(2500, () => purchaseKey);
console.log("key made once per purchase:", reused, "| charges:", charges);

The same reasoning applies when a service changes its database and also publishes a message to a queue. If it commits and then crashes before publishing, the message is lost. If it publishes first and the commit fails, the message describes something that never happened.

The outbox pattern writes the message into an outbox table in the same transaction as the change, and a separate process publishes rows from that table, retrying until the queue accepts them. Delivery is then at-least-once, so consumers deduplicate, usually by a message ID.

Every wait needs a limit

Now the other half of the checkout problem. Suppose the payment provider does not fail. It just gets slow, taking 30 seconds to answer instead of 300 milliseconds, and your code has no timeout at all.

Little's law says the number of requests in progress equals the arrival rate times the time each one takes. At 50 checkouts per second and 0.3 seconds each, about 15 are in progress at once. At 30 seconds each, 1,500 are.

Checkouts, 1,500 in progress, point to the payment provider, which takes 30 s per call, with an arrow labelled waits. Checkouts also point to the database pool, all 20 connections held, with an arrow labelled holds a connection. The product page, which cannot get a connection, has a dashed arrow to the pool. A note reads: unrelated features fail.
Checkouts stuck waiting on the slow provider hold all 20 pool connections, so the product page, which never calls the provider, cannot get one.

Each of those holds a connection, some memory, and often a slot in a database connection pool that other pages also need. If the pool has 20 connections, the product page, which never talks to the payment provider, starts failing too, because it cannot get a connection. One slow dependency has taken down unrelated features.

A timeout turns "slow" into "failed" at a point you choose. Set it from what the dependency normally does, and choose the rate of false timeouts you can live with, since any timeout also cuts off some slow calls that would have succeeded. If 99.9% of payment calls finish within two seconds, a three-second timeout cuts off the stuck ones and a small fraction of the slow successes, and each of those needs the idempotent retry above. Every network call, every database query and every lock acquisition needs one. Library defaults are often infinite or measured in minutes, so read what yours are.

Retrying without making it worse

Once calls can time out, you will want to retry the ones that fail, and a careless retry policy makes outages worse.

Take a service that retries every failed call to its inventory backend three times, immediately. When the backend is healthy, that is harmless. When the backend is struggling, every failing request becomes four requests in quick succession.

If you normally send 1,000 requests per second and they all start failing, you are now sending up to 4,000 per second to a service that was already failing at 1,000. Every other client of that backend with the same policy does the same. The backend cannot recover while the load is four times higher than the load that broke it. This is a retry storm.

The fix has three parts. Wait between attempts, and double the wait each time (exponential backoff): 100 ms, 200 ms, 400 ms, capped at a few seconds. Add randomness to each wait (jitter), because if a thousand clients failed at the same moment and all wait exactly 200 ms, they all retry at the same moment again. And stop after a small number of attempts.

TypeScript
async function withRetry<T>(fn: () => Promise<T>, attempts = 3): Promise<T> {
  if (!Number.isInteger(attempts) || attempts < 1) throw new RangeError("attempts must be a positive integer");
  for (let i = 0; ; i++) {
    try {
      return await fn();
    } catch (err) {
      if (i === attempts - 1 || !isRetryable(err)) throw err;
      const ceiling = Math.min(5_000, 100 * 2 ** i);
      await sleep(Math.random() * ceiling); // full jitter
    }
  }
}

isRetryable matters. Retry timeouts, connection errors and responses that mean "try later" (503, 429). Do not retry a 400 that says the card number is invalid; it will be invalid every time. And only retry operations that are idempotent, or that carry an idempotency key.

This block counts where 1,000 simultaneous retries land with each kind of wait:

TypeScriptRuns in your browser
// 1,000 clients fail at the same moment and each waits before retrying.
// Count how many retries land in the busiest 10 ms slice of time.
function busiestWindow(retryTimes: number[], windowMs = 10): number {
  const counts = new Map<number, number>();
  for (const t of retryTimes) {
    const w = Math.floor(t / windowMs);
    counts.set(w, (counts.get(w) ?? 0) + 1);
  }
  return Math.max(...counts.values());
}

const clients = 1000;
const fixedWait = Array.from({ length: clients }, () => 200);
const fullJitter = Array.from({ length: clients }, () => Math.random() * 200);

console.log("fixed 200 ms wait:", busiestWindow(fixedWait), "retries in the busiest 10 ms");
console.log("random wait up to 200 ms:", busiestWindow(fullJitter), "retries in the busiest 10 ms");

With a fixed wait, all 1,000 retries arrive in the same window. With full jitter, the busiest window holds around 60, and the numbers change a little on each run.

Timeouts in a chain

Retries and timeouts interact when calls are nested. Say service A calls B, and B calls C. B gives each call to C a one-second timeout and makes up to three attempts, with backoff waits of up to 100 ms and 200 ms between them. B's worst case is 3 × 1 s + 0.3 s = 3.3 seconds before it gives up.

If A calls B with a two-second timeout, A abandons the request while B is still retrying. B keeps working on a response A will never read, and A, if it also retries, starts a new request that makes B try C three more times. With three attempts at each of two layers, one user action can hit C nine times. Add a third retrying layer and it is 27.

Two rules keep this under control. If B may use its full retry budget, A's timeout on B has to exceed B's worst case of 3.3 seconds plus B's own processing, so say four. If A cannot wait that long, pass A's deadline down with the request so B stops retrying when A stops waiting. And retry at one layer, usually the one closest to the failing dependency, while the layers above treat a failure as final.

Clocks disagree

Distributed systems also go wrong over time itself. An agent builds an audit log where each service writes events with Date.now(), and a report sorts them by timestamp to show what happened in what order.

Every machine has its own clock, and no two agree exactly. Clocks drift, and NTP, the protocol that corrects them, adjusts them in small steps and sometimes large jumps, including backward. Two servers can easily disagree by several milliseconds, and far more when one has lost contact with its time source.

If server 1 records "order placed" at 12:00:00.005 and server 2 records "payment captured" for that order at 12:00:00.003, the log says the payment came first. Sorting by wall-clock time from different machines gives an order that did not happen.

Top row: order placed on server 1, stamped 12:00:00.005, then an arrow labelled then to payment captured on server 2, stamped 12:00:00.003. Bottom row: the log sorted by timestamp. Dashed lines cross from top to bottom: payment captured lands first in the sorted log and order placed lands second. A note reads: events in an order that did not happen.
The order came first, but server 2 stamped the payment 2 ms before the order's timestamp, so sorting by timestamp lists the payment first.

Some rules follow. To measure how long something took on one machine, use a monotonic clock (performance.now() in JavaScript, time.monotonic() in Python), which only moves forward and is unaffected by clock corrections. To order events, use something that captures causality, which means a logical clock carried in the messages. A database sequence does not do this: it orders the handing out of IDs, and a service that writes its log entry late gets a later number than an event it caused.

A Lamport clock is a counter each process increments on every event and attaches to every message; a receiver sets its counter above the highest value it has seen. If event X caused event Y, X gets the smaller number. The reverse does not hold, because two unrelated events also get numbers, so a smaller number alone does not show cause.

Here is the audit log case with a 4 ms skew between the two servers:

TypeScriptRuns in your browser
// Server 2's clock runs 4 ms behind server 1's. Only this simulation knows the true time.
let trueTime = 1_000;
const skew = { s1: 0, s2: -4 };
const wallClock = (server: "s1" | "s2") => trueTime + skew[server];

const lamport = { s1: 0, s2: 0 };
const log: Array<{ what: string; wall: number; lamport: number }> = [];

// Server 1 places the order and sends a message carrying its counter.
trueTime += 1;
lamport.s1 += 1;
log.push({ what: "order placed", wall: wallClock("s1"), lamport: lamport.s1 });
const message = { orderId: 7, lamport: lamport.s1 };

// Two milliseconds later, server 2 receives it and captures the payment.
trueTime += 2;
lamport.s2 = Math.max(lamport.s2, message.lamport) + 1;
log.push({ what: "payment captured", wall: wallClock("s2"), lamport: lamport.s2 });

const order = (key: "wall" | "lamport") =>
  [...log].sort((a, b) => a[key] - b[key]).map((e) => `${e.what} (${e[key]})`);
console.log("by wall clock:", order("wall"));
console.log("by Lamport clock:", order("lamport"));

The payment really happened 2 ms after the order, but server 2 stamped it 2 ms before. The Lamport counter puts them in the order the message forced.

Agreeing on anything

The hardest version of these problems is getting several machines to agree, for example on which one is the leader allowed to accept writes. The standard approach is a quorum: a decision counts once a majority has accepted it. With five nodes, three must agree, so the system survives two failures, and two different majorities always share at least one node. That shared node stops two nodes from both being elected leader for the same term, provided each node durably records its vote and grants at most one vote per term; a node that forgot its vote after a restart could vote twice.

When the network splits, the side without a majority has to stop accepting writes or risk accepting ones the other side contradicts. That forced choice between staying available and staying consistent during a partition is the CAP tradeoff.

Getting these protocols right is hard enough that you should use a proven implementation: your database's own replication, or a coordination service such as etcd or ZooKeeper, instead of an agent's homemade lock built on a cache and a timestamp.

Check your understanding

8 questions on this lesson. Pick an answer to see whether it holds and why.

  1. 1An agent wrote this client for a payment API that supports idempotency keys. The first attempt charges the card, but its reply is lost and the call times out. What happens on the retry, and what is the fix?
    TypeScript
    async function pay(order: Order) {
      for (let attempt = 0; attempt < 3; attempt++) {
        try {
          return await api.charge(order, { idempotencyKey: crypto.randomUUID() });
        } catch (err) {
          if (!isTimeout(err)) throw err;
          await sleep(Math.random() * 100 * 2 ** attempt);
        }
      }
      throw new Error("payment unavailable");
    }
    Show the answer

    Answer C. The server deduplicates by key, and this code makes a new key on every attempt, so each retry looks like a new purchase. The backoff and jitter are fine, but waiting does not help when the first charge already succeeded: the second request still carries a key the server has never seen.

  2. 2This decides which failed calls to the payment provider get retried. What is wrong with it?
    TypeScript
    function isRetryable(err: HttpError): boolean {
      return err.status >= 400;
    }
    Show the answer

    Answer A. status >= 400 includes every 4xx client error, and a request the provider rejected as invalid will be rejected again, so retrying only adds load. 503 and 429 are both included by this check, so the problem is too many retries, not too few. A timeout or dropped connection has no status at all and needs its own branch.

  3. 3Service A calls B, and B calls C. B gives each call to C a 2-second timeout and makes up to 2 attempts, waiting up to 500 ms between them. A cannot pass a deadline down. What timeout should A use on its call to B so B can use its full retry budget?
    Show the answer

    Answer D. B's worst case is 2 + 0.5 + 2 = 4.5 seconds before it gives up, and B also spends time on its own processing, so A needs more than that. 4 seconds is the tempting number, but it forgets the backoff wait, and A would abandon requests that B is still retrying and may still answer.

  4. 4Two services write to one audit log, and a report sorts it to show what happened in order. Which change makes the order trustworthy?
    TypeScript
    // order service, machine 1
    log.write({ event: "order placed", at: Date.now() });
    await queue.send("order", { orderId });
    
    // payment service, machine 2, after it receives "order"
    log.write({ event: "payment captured", at: Date.now() });
    
    // report
    events.sort((a, b) => a.at - b.at);
    Show the answer

    Answer B. A Lamport counter travels with the message, so the payment, caused by the order message, always gets a larger number than the order. performance.now() is monotonic on one machine, but each machine counts from its own starting point, so values from two machines cannot be compared. A sequence orders when IDs were handed out, which can differ from the order the events happened.

  5. 5The process crashes right after the transaction commits and before the publish. What is the result, and what fixes it?
    TypeScript
    await db.transaction(async (tx) => {
      await tx.insert("orders", order);
    });
    await queue.publish("order-created", { orderId: order.id });
    Show the answer

    Answer A. A committed transaction stays committed, and nothing remembers that a publish was still owed. Publishing first only flips the failure: if the commit then fails, consumers act on an order that does not exist. With an outbox, the order and its message commit together, and a separate publisher retries until the queue accepts it.

  6. 6A consumer reads an order-shipped message, adds loyalty points to the customer's balance in your database, then acknowledges the message. It crashes after the database write and before the acknowledgement. What happens, and what makes it safe?
    Show the answer

    Answer C. Without the acknowledgement the queue cannot tell a crash before the write from a crash after it, so it redelivers, and the points would be added twice. Recording the message ID in the same transaction makes the second delivery a no-op. Acknowledging first turns the risk into lost points whenever the crash comes between the ack and the write.

  7. 7Checkout calls a payment provider with no timeout. The provider slows from 0.3 seconds to 20 seconds per call. Checkout handles 40 requests per second, and each one holds a connection from a 25-connection database pool while it waits. Why does the search page, which never calls the provider, start failing?
    Show the answer

    Answer B. Little's law gives 40 per second times 20 seconds, about 800 checkouts in progress, far more than 25 connections, so search waits for a connection that never frees up. An awaited network call does not block the event loop; the event loop is free, but the pool is empty.

  8. 8During a short outage, 2,000 clients fail at the same moment. Each retries with exponential backoff of exactly 100, 200 and 400 ms and no randomness. What does the provider see as it recovers?
    Show the answer

    Answer D. Every client computed the same waits from the same start, so each round of retries arrives at once. Backoff spaces out one client's attempts, but only jitter spreads different clients apart. Random waits drawn up to the same ceiling send the same total number of requests, spread over the interval instead of stacked in one instant.

You understand it when you can

Drill

An agent wrote a checkout endpoint that retries the payment call on timeout, up to five times, with no delay between attempts. Find the path that charges the customer twice and what the retries do to the payment provider during an outage, then write the test that proves the double charge.

Topics

The Fallacies of Distributed Computing
The false assumptions, such as a reliable network and zero latency, that break distributed designs.
Timeouts, Retries and Backoff
Bounding every wait, and retrying safely with exponential backoff and jitter.
Idempotency
Designing operations that give the same result when applied twice, using idempotency keys and deduplication.
Delivery Guarantees
At-most-once, at-least-once and effectively-once processing with queues and the outbox pattern.
Time and Ordering
Clock skew, monotonic clocks and logical clocks, and why wall-clock time cannot order events across machines.
Consensus and Coordination
Leader election, quorums and the CAP tradeoff, and when to rely on a proven coordination service.

Further reading

Start here

Short reads

Watch

Books

  • Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. Martin Kleppmann and Chris Riccomini, 2026, 2nd edition.

    Its chapter on the trouble with distributed systems covers unreliable networks, timeouts, unreliable clocks and process pauses, followed by consistency, consensus and exactly-once semantics.

  • Understanding Distributed Systems. Roberto Vitillo, 2022, 2nd edition.

    A practitioner's short guide to timeouts, retries with backoff, idempotency, the outbox pattern, leader election and replication, written for application developers.

  • Release It!: Design and Deploy Production-Ready Software. Michael T. Nygard, 2018, 2nd edition.

    Catalogs production failure modes such as missing timeouts, cascading failures and self-inflicted retry storms, and the stability patterns that stop them: timeouts, circuit breakers and bulkheads.

Primary sources

  • Stripe API Reference: Idempotent requests. Specification.

    The payment API's own contract for idempotency keys: the server stores the first result for a key and returns it on a retry, so a retry after a timeout never charges twice.