Chapter 05

Distributed Systems Essentials

Partial failure, CAP and PACELC, consistency models, quorums, clocks, consensus, distributed transactions, idempotency and CRDTs: the ideas behind every "what happens when this node dies?" question, each with a small model you can run.

9 topics

Parts marked Advanced are extra depth. Skip them on a first read or a quick revision.

#Why distributed systems are hard

Added

A distributed system is any system where the work is split across machines that talk over a network: a web server and its database, three replicas of a key-value store, twenty microservices. The moment two machines cooperate, you inherit three problems a single process never has. Partial failure: one part can fail while the rest keeps running, and the rest may not even know. Unreliable networks: messages can be lost, delayed, duplicated or reordered, and from the sender's side all of those look the same. Unreliable clocks: each machine has its own clock, they drift apart, and they can jump backwards.

On one machine, a function call either returns or throws. Across a network there is a third outcome: you don't know. You sent "charge the card" and heard nothing back within your timeout. Maybe the request never arrived. Maybe the server charged the card and the reply was lost. Maybe the server is slow and the reply is still on its way. Your code has to do something sensible without being able to tell which.

A mental model that sticks: you're coordinating with friends by post, with no phone. Letters can get lost or arrive weeks late, a friend might have moved away without telling you, and every friend's watch shows a slightly different time. "Did Sam get my letter?" can only be answered by another letter, which can also be lost. Every technique in this chapter (timeouts, retries, idempotency keys, quorums, logical clocks, consensus) is a way to get useful work done by post.

Three different failures, one symptom: the client sees a timeout and cannot tell which one happened.

The model below charges 10,000 cards over a network that loses 5% of requests, loses 5% of replies, and is too slow 5% of the time. The client does what most HTTP clients do: on a timeout it retries, up to three attempts in total. It runs twice: once against a server that just charges, and once against a server that remembers an idempotency key (the payment id) and treats a repeat as a no-op. The randomness is a seeded PRNG (mulberry32), so it prints the same numbers every run.

timeout-ambiguity.mjs

// A client charges a card over a lossy network and retries on timeout. Seeded, so every run is identical.
function mulberry32(seed) {
  return () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const rand = mulberry32(42);

// One attempt: what actually happened, and what the client saw.
function attempt(server, paymentId, useKey) {
  const r = rand();
  if (r < 0.05) return "timeout";                 // request lost: server never saw it
  server.charge(paymentId, useKey);               // the server did the work...
  if (r < 0.10) return "timeout";                 // ...but the reply was lost
  if (r < 0.15) return "timeout";                 // ...or arrived after the client gave up
  return "ok";
}

function run(useKey) {
  const charges = new Map();                      // paymentId -> times the card was charged
  const seenKeys = new Set();
  const server = {
    charge(id, useKey) {
      if (useKey && seenKeys.has(id)) return;     // idempotency key: repeat = no-op
      seenKeys.add(id);
      charges.set(id, (charges.get(id) ?? 0) + 1);
    },
  };
  const outcome = { ok: 0, gaveUp: 0, doubleCharged: 0, chargedButToldFailed: 0 };
  for (let id = 0; id < 10_000; id++) {
    let result = "timeout";
    for (let tries = 0; tries < 3 && result === "timeout"; tries++) result = attempt(server, id, useKey);
    const n = charges.get(id) ?? 0;
    if (result === "ok") outcome.ok++;
    else outcome.gaveUp++;
    if (n > 1) outcome.doubleCharged++;
    if (result !== "ok" && n > 0) outcome.chargedButToldFailed++;
  }
  return outcome;
}

console.log("retry, no key :", run(false));
console.log("retry + key   :", run(true));

Result

retry, no key : { ok: 9958, gaveUp: 42, doubleCharged: 1064, chargedButToldFailed: 41 }
retry + key   : { ok: 9957, gaveUp: 43, doubleCharged: 0, chargedButToldFailed: 41 }

What’s happening

Each attempt draws one random number. Below 0.05 the request is lost and the server never runs charge. Between 0.05 and 0.15 the server does run charge, and then the reply is lost or too late. Only above 0.15 does the client get "ok". Three of the four outcomes look the same to the client: "timeout".
Without a key, every retry after cases 2 and 3 charges the card again: 1,064 of 10,000 customers were charged more than once. The retry that was meant to make the system reliable is what caused the damage, because the client retried work that had already happened.
gaveUp: 42 are payments where all three attempts timed out, so the client reported a failure. But chargedButToldFailed: 41: in 41 of those 42 the card was charged. "The request failed" really meant "I don't know". On a single machine you'd never confuse the two.
With the key, server.charge checks seenKeys first, so a retry of work already done changes nothing: doubleCharged: 0. The client can now retry freely, because the operation is idempotent (doing it twice has the same effect as once).
The key doesn't fix the 41 "told failed, actually charged" cases on its own. What it gives you is the right recovery: retry later with the same key (or ask "what happened to payment 123?"), and the answer comes back without a second charge. That's the shape of Idempotency and exactly-once and of payment APIs.

AdvancedThe eight fallacies of distributed computing

L. Peter Deutsch at Sun Microsystems wrote down seven false assumptions in 1994, building on earlier work by Bill Joy and Dave Lyon, and James Gosling added the eighth around 1997 (Wikipedia, checked October 2026). Every one of them still turns up in design reviews, so it helps to know what each one costs you in a design:

Fallacy	What breaks when you believe it	What the design does instead
The network is reliable	calls hang, retries duplicate work	timeouts on every call, retries with backoff, idempotent operations
Latency is zero	chatty APIs: 50 calls × 2 ms is 100 ms	batch, cache, keep data near the code that uses it
Bandwidth is infinite	big payloads, full-object syncs saturate links	pagination, compression, deltas instead of snapshots
The network is secure	plain-text traffic inside the data centre	TLS everywhere (mTLS between services), least privilege
Topology doesn't change	hard-coded IPs, caches of "who is the leader"	service discovery, health checks, re-resolve on failure
There is one administrator	one team's config change breaks another	clear ownership, versioned contracts, staged rollouts
Transport cost is zero	serialisation CPU and cross-zone traffic bills	measure it; keep hot paths in one zone where possible
The network is homogeneous	one slow or old hop drags everything	timeouts per hop, tolerate mixed versions and protocols

How often does the network actually fail? A Microsoft Research study of a year of network logs from tens of its data centres (Gill, Jain and Nagappan, SIGCOMM 2011) found that load balancers caused the most failures and that network redundancy was only about 40% effective at reducing the median impact of a failure. Redundancy helps, but it doesn't make the first fallacy true.

AdvancedClocks lie in two different ways

Two facts about time on a server. A wall clock (Date.now(), System.currentTimeMillis()) tells you the date and time, and NTP can move it forwards or backwards to correct drift. A monotonic clock (performance.now() and process.hrtime.bigint() in Node) only ever moves forwards, but its value means nothing across machines; it's only good for measuring durations on one machine. And different machines' wall clocks disagree: NTP usually keeps clocks within tens of milliseconds over the public internet and under a millisecond on a good LAN, but asymmetric routes and congestion can cause errors of 100 ms or more (Wikipedia's NTP article, October 2026).

clocks-lie.mjs

// Two things wall clocks get wrong, with fake clocks so the output is exact.

// 1. Measuring a duration with the wall clock while NTP steps it back by 1.2 s.
let trueMs = 1_000_000;           // real time, never jumps
let wallOffset = 0;               // what NTP adds or removes
const wall = () => trueMs + wallOffset;
const monotonic = () => trueMs;   // like performance.now(): only goes forward

const w0 = wall(), m0 = monotonic();
trueMs += 300;                    // the upstream call really takes 300 ms...
wallOffset -= 1200;               // ...and meanwhile NTP corrects a fast clock
console.log("wall-clock duration :", wall() - w0, "ms");
console.log("monotonic duration  :", monotonic() - m0, "ms");

// 2. Ordering writes on two servers by their own wall clocks.
const servers = {
  A: { skewMs: 0 },               // accurate
  B: { skewMs: -80 },             // 80 ms behind
};
const stamp = (server, realMs) => realMs + servers[server].skewMs;

const writes = [
  { value: "email=old@x.com", server: "A", realMs: 5_000 },
  { value: "email=new@x.com", server: "B", realMs: 5_030 }, // really happened 30 ms later
];
for (const w of writes) w.ts = stamp(w.server, w.realMs);
const winner = writes.reduce((a, b) => (b.ts > a.ts ? b : a)); // last-write-wins by timestamp
console.log(writes.map((w) => `${w.value} @${w.server} ts=${w.ts}`).join(" | "));
console.log("LWW keeps:", winner.value, "(the user's latest change is silently lost)");

Result

wall-clock duration : -900 ms
monotonic duration  : 300 ms
email=old@x.com @A ts=5000 | email=new@x.com @B ts=4950
LWW keeps: email=old@x.com (the user's latest change is silently lost)

What’s happening

Part 1 measures a 300 ms call with both clocks while NTP steps the wall clock back by 1.2 seconds (it does that when it finds the clock running fast). The wall clock says the call took −900 ms. The monotonic clock says 300 ms, the truth, because nothing ever adjusts it.
A negative duration isn't just a funny log line. On 1 January 2017 a leap second made a duration in Cloudflare's Go DNS server negative; it was passed to rand.Int63n, which panics on a negative argument, and a small share of DNS queries failed (The Register's report, 2017). Go 1.9 later added a monotonic reading to time.Now (Go 1.9 release notes). Rule: measure durations with a monotonic clock.
Part 2 orders two writes by the timestamps the servers stamped on them. Server B's clock is 80 ms behind, so the edit made on B 30 ms after the edit on A gets timestamp 4950, which is earlier than A's 5000.
Last-write-wins compares timestamps, keeps old@x.com and throws the newer email away, with no error anywhere. Any design that orders events across machines by wall-clock time has this bug whenever the skew is bigger than the gap between writes.
That's why the rest of the chapter avoids comparing wall clocks between machines: Lamport and vector clocks order events by causality instead, consensus orders them through a leader's log, and CRDTs make the order not matter.

AdvancedProcess pauses and stale leases

Process pauses: the node that doesn't know it's been asleep

A process can stop for a long time without crashing: a stop-the-world garbage collection, a VM being live-migrated, a laptop lid closing, a container being throttled. When it resumes, it carries on from the next line as if no time had passed. If it was holding a lease ("I'm the leader for 10 more seconds"), it may still believe it holds it, while the rest of the cluster has already picked someone else. Code can't check "am I still leader?" and then act, because the pause can happen between the check and the action. This is the real reason distributed locks need fencing tokens, and it's modelled in Leader election and consensus.

AdvancedInterview: naming partial failure per arrow

What to say in the interview

When you add a network hop to a design, say what happens when it fails. For each arrow on your diagram, the useful questions are: what's the timeout, is the call retried, is it safe to retry (idempotent), and what does the caller do if it never gets an answer? Naming partial failure early ("the payment service might charge the card and then time out on us, so the call carries an idempotency key") is one of the clearest signals of distributed-systems experience an interviewer looks for.

What can go wrong when service A calls service B over the network?

"Three kinds of thing. The request or the reply can be lost or delayed, and from A's side a lost request, a lost reply and a slow server all look like the same timeout, so A doesn't know whether B did the work. B can be partly down: up but slow, or up for some requests and not others. And their clocks disagree, so A and B can't order events by timestamp. So I'd give every call a timeout, retry only with backoff and jitter and only if the operation is idempotent (an idempotency key if it isn't naturally), put a circuit breaker in front of B so a slow B doesn't take A down, and never rely on comparing A's and B's wall clocks. Where the outcome is unknown, I'd design a way to find out, like querying the payment status by its key, instead of guessing."

The retry that charged twice

A checkout calls the payment service with a 2-second timeout and retries once. The payment service is healthy but takes 2.5 seconds for a slow card network. No idempotency key is sent. What does the customer see, and what happens to their card?

Show answer

The checkout shows an error, or a success after the retry, and the card is charged twice.

What’s happening

Attempt 1 reaches the payment service, which starts the charge. At 2 seconds the checkout's timeout fires; it doesn't know the charge is in progress.
The checkout retries. Attempt 2 is a brand-new request to the payment service, which has no way to know it's a repeat, so it starts a second charge.
At 2.5 seconds attempt 1 completes: card charged. Its reply arrives at a client that has stopped listening.
Attempt 2 either completes in time (the user sees "success", with two charges) or times out as well (the user sees an error, with two charges, and probably tries again).
The fix is not a longer timeout (some call will always be slower). It's an idempotency key generated once per checkout and sent on every attempt, so the payment service returns the first result for the repeat.

#CAP and PACELC in a design discussion

Added

CAP is about one moment: a replicated system whose copies can't reach each other (a partition). A node that receives a request on the cut-off side has two options. It can answer from what it has, which keeps it available but may return stale data or accept a write that conflicts with the other side. Or it can refuse until it can coordinate, which keeps the data consistent (every read sees the latest write, as if there were one copy) but makes that node unavailable. Partitions aren't optional in a real network, so the theorem is really "during a partition, choose C or A". The Databases course shows this on a real Redis primary and replica cut off by a Docker network partition; here the point is how to use it in a design.

PACELC (Daniel Abadi, 2010) adds the half CAP leaves out, and it's the half you live with every day: Else, when there is no partition, you trade Latency against Consistency, because a write that waits for replicas in other zones or regions is slower than one that doesn't. A system is described by both choices, such as PC/EC (stop on partition, wait for replicas otherwise) or PA/EL (keep going, don't wait).

The mental model: two shops sharing one stock book by phone. If the phone line is cut, each shop either stops selling until the line is back (C) or keeps selling and sorts it out later, risking selling the last item twice (A). Even with the phone working, ringing the other shop before every sale makes every sale slower (the ELC part). The useful interview move is to make that choice per operation, not per system: the same app can stop selling the last ticket during a partition and still let people browse and like posts.

The partition forces the choice only on the side that can't reach a majority: answer anyway (A) or refuse (C).

The model plays that picture out. Six customers try to buy the last three tickets, spread across both sides of the partition, once with the CP rule (a side may sell only if it can reach 2 of the 3 replicas) and once with the AP rule (every side sells from its own copy).

partition.mjs

// Last 3 concert tickets, stored on 3 replicas (EU-1, EU-2, US). The link to US is cut.
// CP mode: a side may only sell if it can reach a majority (2 of 3). AP mode: every side keeps selling.
function cluster(mode) {
  const replicas = { "EU-1": 3, "EU-2": 3, US: 3 };                  // tickets left, per copy
  const groups = [["EU-1", "EU-2"], ["US"]];                           // the partition
  const log = [];
  function buy(customer, at) {
    const side = groups.find((g) => g.includes(at));
    if (mode === "CP" && side.length < 2) {
      log.push(`${customer}@${at}: ERROR no quorum (try later)`);
      return;
    }
    if (replicas[at] === 0) return log.push(`${customer}@${at}: sold out`);
    for (const r of side) replicas[r]--;                                // replicate within the side
    log.push(`${customer}@${at}: OK, ${replicas[at]} left here`);
  }
  for (const [c, at] of [["ana", "EU-1"], ["ben", "US"], ["caro", "US"], ["dev", "EU-2"], ["eli", "US"], ["fay", "EU-1"]]) buy(c, at);
  const sold = log.filter((l) => l.includes("OK")).length;
  // Heal: the copies disagree; the business has to reconcile them.
  return { log, sold, oversold: Math.max(0, sold - 3), copies: replicas };
}

for (const mode of ["CP", "AP"]) {
  const r = cluster(mode);
  console.log(`--- ${mode} ---`);
  for (const line of r.log) console.log(line);
  console.log(`sold ${r.sold} of 3, oversold ${r.oversold}, copies after:`, r.copies);
}

Result

--- CP ---
ana@EU-1: OK, 2 left here
ben@US: ERROR no quorum (try later)
caro@US: ERROR no quorum (try later)
dev@EU-2: OK, 1 left here
eli@US: ERROR no quorum (try later)
fay@EU-1: OK, 0 left here
sold 3 of 3, oversold 0, copies after: { 'EU-1': 0, 'EU-2': 0, US: 3 }
--- AP ---
ana@EU-1: OK, 2 left here
ben@US: OK, 2 left here
caro@US: OK, 1 left here
dev@EU-2: OK, 1 left here
eli@US: OK, 0 left here
fay@EU-1: OK, 0 left here
sold 6 of 3, oversold 3, copies after: { 'EU-1': 0, 'EU-2': 0, US: 0 }

What’s happening

groups is the partition: EU-1 and EU-2 can still talk, US is alone. A sale decrements every copy on the same side (for (const r of side) replicas[r]--), which is replication that works only within a side.
CP: ana, dev and fay buy on the EU side, which has 2 of 3 replicas, so each sale is allowed and the count goes 3 → 2 → 1 → 0. ben, caro and eli are on the US side, which can't reach a majority, so they get ERROR no quorum. Exactly 3 tickets sold, zero oversold, and US users saw errors for as long as the partition lasted.
AP: every side sells from its own copy. The EU side sells 3 and the US side sells another 3 from a copy that still says 3. Everyone got an answer (available), and the venue has sold 6 seats for 3 places.
The final copies show the difference after healing. CP: EU is at 0 and US still says 3 but sold nothing, so the US copy is simply behind and catches up from the majority. AP: all copies say 0, but that hides the real problem: 3 extra sales that now need a business decision (refunds, upgrades, an apology email).
Neither run is wrong. For concert seats you'd choose CP and show "try again in a moment"; for a shopping cart, a like count or a feed, AP's "always answer, reconcile later" is the better product, as Amazon's Dynamo paper argued for carts in 2007.

AdvancedChoosing per operation, out loud

The same product usually needs both. Make the choice per operation and give the reason in business terms:

Operation	During a partition	Why
Sell the last seat, book a slot, claim a username	CP: refuse on the minority side	a double booking costs more than a short error
Move money, place a trade	CP	correctness is the product; errors are retried
Add to cart, like, follow	AP: accept, merge later	a lost or duplicate like is cheap; an error is not
Read a feed, a product page, a profile	AP: serve possibly stale data	slightly old is better than nothing
Change a password, revoke a session	CP for the write, and invalidate caches	an old password still working is a security bug
Collect metrics, logs, clicks	AP	the totals are approximate anyway

AdvancedPACELC: the latency cost of consistency

The "else": how much consistency costs without a partition

PACELC's second half is a latency bill you can calculate. If the leader waits for followers before saying "ok", every write pays the round trip to them. The model below uses Microsoft's published median round-trip times between Azure regions (the 30 days to 30 July 2026, measured from East US) and Microsoft's target of under about 2 ms between availability zones in one region (Azure availability zones overview, October 2026).

pacelc-latency.mjs

// "Else" branch of PACELC: what a synchronous (EC) write costs for different replica placements.
// RTTs from Azure's published P50 round-trip table (30 days to 30 July 2026); inter-zone is Azure's "< ~2 ms" target.
const rttFromEastUS = {
  "East US zone 2": 2, "East US zone 3": 2,
  "East US 2": 8, "West US": 69, "West Europe": 83, "Japan East": 162,
};

// The leader is in East US. A write is acknowledged once `acks` replicas (including the leader) have it.
// The leader's own copy is free; each follower costs one round trip; they run in parallel,
// so the wait is the (acks - 1)-th fastest follower RTT.
function writeLatency(followers, acks) {
  const rtts = followers.map((f) => rttFromEastUS[f]).sort((a, b) => a - b);
  return acks <= 1 ? 0 : rtts[acks - 2];
}

const placements = [
  ["3 zones, one region", ["East US zone 2", "East US zone 3"]],
  ["2 nearby regions + 1", ["East US 2", "West US"]],
  ["US + Europe + Asia", ["West Europe", "Japan East"]],
];

console.log("extra wait per write:".padEnd(22), "async(EL)  majority(EC)  all(EC)");
for (const [name, followers] of placements) {
  const n = followers.length + 1;
  const majority = Math.floor(n / 2) + 1;
  console.log(
    name.padEnd(22),
    `${writeLatency(followers, 1)} ms`.padEnd(10),
    `${writeLatency(followers, majority)} ms`.padEnd(13),
    `${writeLatency(followers, n)} ms`,
  );
}

Result

extra wait per write:  async(EL)  majority(EC)  all(EC)
3 zones, one region    0 ms       2 ms          2 ms
2 nearby regions + 1   0 ms       8 ms          69 ms
US + Europe + Asia     0 ms       83 ms         162 ms

What’s happening

writeLatency assumes the leader sends to all followers in parallel and waits for acks - 1 of them (the leader's own copy is free). So the wait is the RTT of the (acks - 1)-th fastest follower, which is why the RTTs are sorted.
Async (EL) adds nothing: the leader says "ok" before any follower has the write. That's fast, and it's also why a leader crash can lose the last few acknowledged writes.
Majority (EC) with three zones in one region costs about 2 ms per write. That's the sweet spot most managed databases default to: survive a zone failure with no data loss, for a cost users never notice.
With followers in East US 2 and West US, the majority write waits for the nearest follower only: 8 ms. Waiting for all of them costs 69 ms, because the slowest follower sets the pace. Majority quorums are popular partly because they ignore the slowest replica.
Spread across US, Europe and Asia, even the majority write waits 83 ms, and every write waits that long. That's the EC price of surviving a whole region failing with no data loss. Cosmos DB's documentation puts the write latency of a strongly consistent account with more than one region at two times the RTT between the two farthest regions, plus 10 ms at the 99th percentile (Microsoft Learn, 2026), and blocks strong consistency by default for accounts whose regions span more than 8,000 km.

AdvancedInterview: CAP choices in business terms

What to say in the interview

Mention CAP when the design replicates data, and immediately make it concrete: which operations would rather fail than be wrong, which would rather be stale than fail, and what the user sees in each case. Then mention the PACELC cost of the consistent choice in milliseconds, because that's what drives the replica placement. "Payments go through a single-region primary with synchronous replication to two zones, about 2 ms per write; the product catalogue is read from regional replicas that may be a few seconds behind" is a much stronger answer than "we pick CP".

Who gets errors?

A store runs 5 replicas with majority writes and reads: 3 in Frankfurt, 2 in Dublin. The link between the cities fails for ten minutes. Which users can still write, and which can still read the latest data?

Show answer

Users routed to Frankfurt can read and write normally. Users routed to Dublin get errors for consistent reads and all writes until the link heals (or until they're rerouted to Frankfurt).

What’s happening

A majority of 5 is 3. Frankfurt has 3 replicas, so it can still form a write quorum and a read quorum by itself.
Dublin has 2 replicas, which is not a majority. If it accepted a write, Frankfurt could accept a conflicting one at the same time, which is exactly what majority quorums exist to prevent.
So Dublin must refuse writes and consistent reads: that's the CP choice, made by the quorum rule automatically.
If the product allows it, Dublin could still serve stale reads from its local copies, clearly marked or for non-critical pages. That's choosing A for those reads only.
If the leader was in Dublin when the link broke, Frankfurt elects a new one; the old leader in Dublin can't reach a majority and stops accepting writes. That's the subject of Leader election and consensus.

#Consistency models

Added

A consistency model is a contract between a replicated store and its users about which values a read is allowed to return. With one copy of the data the question never comes up: a read returns the last write. With several copies that update at different moments, a read might hit a copy that hasn't caught up, and the model says how far behind it may be and in what ways. Stronger models are easier to program against and cost more coordination (latency, and availability during partitions); weaker models are cheaper and push the problems into your application.

Doug Terry's well-known explanation ("Replicated Data Consistency Explained Through Baseball", Communications of the ACM, 2013) uses a baseball scoreboard. The umpire deciding in the ninth inning whether the game is over needs the current score (strong). The official scorekeeper is the only person who writes the score, so read-my-writes is enough to give him the current score. A radio reporter who reads the score every 30 minutes can be behind, but must never announce a score that never existed or one that goes backwards (consistent prefix plus monotonic reads). A sportswriter who has dinner for an hour after the game can ask for staleness bounded at one hour and be sure of the final score. A fan checking season statistics once a day is fine with eventual consistency. Same data, different readers, different guarantees, and every one weaker than strong is cheaper.

From strongest to weakest, the ones worth naming in an interview:

Model	What a reader is guaranteed	Example anomaly it forbids
Linearizable (strong)	behaves like one copy: once a write completes, every later read sees it or something newer	reading the old balance a second after the transfer said "done"
Sequential	everyone sees all writes in the same order, possibly behind real time	two users seeing two edits in opposite orders
Causal	if one write could have influenced another, everyone sees them in that order; unrelated writes may differ	a reply showing before the comment it answers
Read-your-writes (session)	you always see your own earlier writes	saving your profile and seeing the old one on refresh
Monotonic reads (session)	your reads never go back in time	a comment count going 12, 14, 13
Consistent prefix	you see writes in order, maybe not the latest ones	seeing the third update of a document without the second
Eventual	if writes stop, all copies converge; nothing about meanwhile	none; anything can be stale for a while

Each step to the right removes a guarantee and some coordination. Most product features need something in the middle, not either end.

The session guarantees are the ones you'll design for most often, because they're what a single user notices. The model below has a leader and two followers that lag 3 and 12 ticks behind. Ana edits her profile now and then (on the leader); Ana and Bob read it every tick. It counts two kinds of anomaly, read-your-writes violations (Ana doesn't see an edit she already saved) and monotonic-read violations (someone sees an older version than they saw before), under four routing strategies. The routing randomness is seeded.

session-guarantees.mjs

// Ana edits her profile; Ana and Bob keep reading it. One leader, two followers that lag behind.
// Seeded PRNG so every run prints the same numbers.
function mulberry32(seed) {
  return () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const TICKS = 5000;
const lag = { leader: 0, f1: 3, f2: 12 };               // how many ticks behind each copy is
const names = Object.keys(lag);

const strategies = {
  "any replica": (user, rand) => names[Math.floor(rand() * 3)],
  "leader after own write": (user, rand, t) =>
    user.name === "ana" && t - user.lastWriteTick < 15 ? "leader" : names[Math.floor(rand() * 3)],
  "sticky replica": (user) => (user.name === "ana" ? "f1" : "f2"),
  "version token": (user, rand) => names[Math.floor(rand() * 3)], // checked against the token below
};

for (const [label, route] of Object.entries(strategies)) {
  const rand = mulberry32(7);
  const versionAt = [];                                  // leader's version at each tick
  let version = 0;
  const users = ["ana", "bob"].map((name) => ({ name, lastWriteTick: -1e9, wrote: 0, seen: 0 }));
  const bad = { readYourWrites: 0, monotonic: 0 };
  let leaderReads = 0;
  for (let t = 0; t < TICKS; t++) {
    if (rand() < 0.02) {                                 // Ana saves an edit on the leader
      version++;
      Object.assign(users[0], { lastWriteTick: t, wrote: version });
    }
    versionAt[t] = version;
    for (const user of users) {
      let replica = route(user, rand, t);
      const token = Math.max(user.wrote, user.seen);
      if (label === "version token" && versionAt[Math.max(0, t - lag[replica])] < token) replica = "leader";
      if (replica === "leader") leaderReads++;
      const v = versionAt[Math.max(0, t - lag[replica])];
      if (v < user.wrote) bad.readYourWrites++;          // didn't see my own saved edit
      if (v < user.seen) bad.monotonic++;                // went back in time
      user.seen = Math.max(user.seen, v);
    }
  }
  const pct = ((100 * leaderReads) / (TICKS * 2)).toFixed(0);
  console.log(`${label.padEnd(23)} RYW violations ${String(bad.readYourWrites).padStart(4)}   ` +
    `monotonic violations ${String(bad.monotonic).padStart(4)}   reads on leader ${pct}%`);
}

Result

any replica             RYW violations  495   monotonic violations  688   reads on leader 33%
leader after own write  RYW violations    0   monotonic violations  299   reads on leader 42%
sticky replica          RYW violations  312   monotonic violations    0   reads on leader 0%
version token           RYW violations    0   monotonic violations    0   reads on leader 42%

What’s happening

versionAt[t] is the leader's version at tick t, and a replica with lag L returns versionAt[t - L]. Each tick Ana saves an edit with probability 0.02, and both users read once. user.wrote is the version Ana last saved; user.seen is the highest version that user has read so far.
Any replica (random routing, the default for a naive read-replica setup): 495 times Ana didn't see her own saved edit, and 688 times someone's view went backwards: a read served by f1 followed by one served by f2, which is 9 ticks further behind, can show an older version than the one before it.
Leader after own write sends Ana to the leader for 15 ticks after each save, longer than the worst lag (12). Her read-your-writes problem goes to 0, but monotonic reads still break 299 times (all of them Bob's, counted per user in a variant of this script: he still bounces between replicas), and 42% of reads now hit the leader instead of 33%.
Sticky replica pins each user to one replica (Ana on f1, Bob on f2). A single replica never goes backwards, so monotonic violations are 0 and the leader serves nothing, but Ana still misses her own edits 312 times because f1 is 3 ticks behind.
Version token: the client remembers the highest version it has written or seen and sends it with each read; a replica that's behind that version can't serve it, and the read goes to the leader. Both counts are 0, and leader reads are 42%, the same as strategy 3. This is how Cosmos DB's Session consistency works: every write returns a session token, the client sends it on reads, and if the replica it asked doesn't have that token's data, the client retries on another replica in the region, then in other regions (Microsoft Learn, 2026).
The lesson: the two session guarantees fail for different reasons and have different fixes. Name the one the feature needs. "After saving, the user sees their change" is read-your-writes; "the counter never jumps backwards" is monotonic reads.

AdvancedCausal consistency: effects after their causes

Session guarantees are about one client. Causality is about writes from different clients that depend on each other. Ana posts "Who wants pizza?"; Bob reads it and replies "Me!". If a third user's replica receives Bob's reply before Ana's post, they see an answer to a question that doesn't exist yet. Causal consistency forbids that: anything Bob had seen when he wrote must be visible before his write is. Writes nobody saw (two people posting in different threads) can show up in any order.

Causal consistency is attractive because it's the strongest model that can stay available during a partition: each side can keep accepting writes, as long as it delays showing a write until the writes it depends on have arrived. One precise caveat: that holds when each client keeps talking to the same replica (Bailis et al. call this "sticky availability"); a client that switches to a replica that hasn't seen its earlier writes has to wait. Tracking "depends on" is what vector clocks do. MongoDB offers it as causally consistent sessions, and many chat and comment systems get it more cheaply by keeping a thread's messages on one partition, where a single log gives them an order.

AdvancedLinearizable: when you really need one copy

Some operations need the full guarantee, because a stale read breaks a rule rather than just looking odd: "only one user gets this username", "this lock is held by exactly one client", "the leader is node 3", "the balance can't go below zero". Those go through a single leader with majority replication or a consensus system such as etcd, ZooKeeper or Spanner. Everything else should ask whether a weaker model is enough, because linearizable reads are also the most expensive ones: in Cosmos DB, strong and bounded-staleness reads are made from two replicas and cost twice the request units of the weaker levels; in DynamoDB a strongly consistent read of up to 4 KB costs one read unit and an eventually consistent one costs half (both from the vendors' docs, October 2026).

Product	Its knobs, strongest to weakest
Azure Cosmos DB	Strong, Bounded staleness, Session, Consistent prefix, Eventual (per account, weaker per request)
DynamoDB	`ConsistentRead: true` (strong, leader) or default eventually consistent reads
MongoDB	read concern `linearizable` / `majority` / `local`, write concern `majority` / `1`, causally consistent sessions
Cassandra	per-query `ALL`, `QUORUM`, `LOCAL_QUORUM`, `ONE` (see Quorums)

AdvancedInterview: naming the model per feature

What to say in the interview

State the model per feature, in user terms, then the mechanism: "profile edits need read-your-writes, so after a save the client sends its last write version and replicas that are behind forward the read to the leader; the feed only needs eventual consistency and monotonic reads, so feed reads are pinned to one replica per session". That shows you know the models are a menu, not a single dial.

Which guarantee broke?

A video's comment count, read by one user over a few seconds, shows 12, then 14, then 13. Nobody deleted a comment. Which consistency guarantee was violated, and what's a cheap fix?

Show answer

Monotonic reads. The cheap fix is to pin the user's reads to one replica (sticky routing) for the session, or to send the highest version seen and refuse to go below it.

What’s happening

Every value the user saw was a real value at some point: 12, then 13, then 14 comments were really written. So nothing was invented and no write was lost.
The user's second read hit a replica that had reached 14, and the third hit a replica that was only at 13. Each replica on its own moves forward; switching between replicas with different lag is what makes the view go backwards.
That is exactly what monotonic reads forbids: once you've seen a value, you never see an older one.
Read-your-writes isn't involved, because the user didn't write anything. Linearizability would also prevent it, but at a much higher cost than needed for a counter.
Pinning a session to one replica (or carrying a "seen at least version 14" token) fixes it, as the sticky and token strategies in the model above showed with 0 monotonic violations.

#Quorums: R + W > N

Added

In a leaderless store (Dynamo, Cassandra, Riak, ScyllaDB), any replica can take a write. Each key lives on N replicas. A write is sent to all N and counts as successful once W of them confirm. A read asks replicas and waits for R answers, then returns the value with the newest version. N, R and W are knobs: the system doesn't decide consistency for you, the numbers do.

The rule that makes it work is plain counting. If R + W > N, every set of R replicas you read from must share at least one replica with every set of W replicas a successful write reached, because there aren't enough replicas for the two sets to miss each other. So at least one of the R answers has the latest acknowledged write, and "pick the newest version" finds it. If R + W ≤ N, a read can land entirely on replicas the write hasn't reached yet.

The mental model: three notebooks in three rooms. To record a decision you must write it in at least two of them. To look it up, you must check at least two. With only three notebooks, any two you check include at least one of the two that were written in. Write in one and check one, and you might open the one notebook nobody wrote in.

With R + W > N, any read set overlaps any acknowledged write set, so the newest version is always among the answers.

The simulation below has N = 3. Each write is sent to all three replicas; each replica usually applies it after 1 ms, but 20% of the time it's slow and takes up to 50 ms. The write is acknowledged when the W-th replica has applied it, and the client immediately reads from R replicas picked at random and keeps the highest version. It counts stale reads and the average wait for writes and reads, over 10,000 rounds with a seeded PRNG, then checks which settings survive one replica being down.

quorum.mjs

// N = 3 replicas. Each write is sent to all three; it's acknowledged once W have applied it.
// A read asks R random replicas and keeps the highest version. Seeded, so the output is stable.
function mulberry32(seed) {
  return () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const N = 3;

function trial(W, R, rounds = 10_000) {
  const rand = mulberry32(2026);
  let stale = 0, writeWait = 0, readWait = 0;
  const delay = () => (rand() < 0.2 ? 1 + Math.floor(rand() * 50) : 1); // usually 1 ms, a slow replica up to 50
  for (let version = 1; version <= rounds; version++) {
    const applyAt = Array.from({ length: N }, delay);          // when each replica has applied this write
    const ackAt = [...applyAt].sort((a, b) => a - b)[W - 1];   // the W-th replica to apply it
    writeWait += ackAt;
    // The client reads immediately after the ack. Pick R distinct replicas at random.
    const picked = [0, 1, 2].sort(() => rand() - 0.5).slice(0, R);
    const seen = Math.max(...picked.map((i) => (applyAt[i] <= ackAt ? version : version - 1)));
    if (seen < version) stale++;
    readWait += Math.max(...picked.map(delay));                  // a read waits for all R replies
  }
  const ms = (total) => (total / rounds).toFixed(1).padStart(4);
  return { stale: ((100 * stale) / rounds).toFixed(1).padStart(4) + "%", write: ms(writeWait), read: ms(readWait) };
}

for (const [W, R] of [[1, 1], [1, 2], [2, 1], [2, 2], [3, 1], [1, 3]]) {
  const { stale, write, read } = trial(W, R);
  const overlap = R + W > N ? "R+W>N " : "R+W<=N";
  console.log(`W=${W} R=${R}  ${overlap}  stale ${stale}   avg write ${write} ms   avg read ${read} ms`);
}

// One replica is down: which (W, R) can still serve both writes and reads?
for (const [W, R] of [[2, 2], [3, 1], [1, 3]]) {
  const up = N - 1;
  console.log(`replica down, W=${W} R=${R}: writes ${W <= up ? "ok" : "FAIL"}, reads ${R <= up ? "ok" : "FAIL"}`);
}

Result

W=1 R=1  R+W<=N  stale 18.8%   avg write  1.1 ms   avg read  5.9 ms
W=1 R=2  R+W<=N  stale  3.5%   avg write  1.1 ms   avg read 10.0 ms
W=2 R=1  R+W<=N  stale 15.5%   avg write  2.7 ms   avg read  5.9 ms
W=2 R=2  R+W>N   stale  0.0%   avg write  2.7 ms   avg read 10.0 ms
W=3 R=1  R+W>N   stale  0.0%   avg write 13.7 ms   avg read  5.9 ms
W=1 R=3  R+W>N   stale  0.0%   avg write  1.1 ms   avg read 13.7 ms
replica down, W=2 R=2: writes ok, reads ok
replica down, W=3 R=1: writes FAIL, reads ok
replica down, W=1 R=3: writes ok, reads FAIL

What’s happening

applyAt holds when each replica applies the write; sorting it and taking index W - 1 gives the moment the W-th replica has it, which is when the client hears "ok". A replica has the new version at read time if applyAt[i] <= ackAt. Each read waits for the slowest of its R replies.
W=1, R=1: the write is acknowledged by the fastest replica, and the read asks one random replica. 18.8% of reads were stale: roughly the 20% chance that the replica you happened to ask is a slow one. Fast both ways, and wrong one time in five.
R+W ≤ N stays unsafe whatever the split: W=1, R=2 cut staleness to 3.5% and W=2, R=1 to 15.5%, but neither reached zero. More replicas make a stale read less likely; only overlap makes it impossible.
Every R + W > N row is 0.0% stale: W=2, R=2, and the two extremes W=3, R=1 and W=1, R=3. What differs is who pays. W=3 makes every write wait for the slowest replica (13.7 ms on average against 2.7 ms for W=2), and R=3 does the same to every read. W=2, R=2 pays a little on both: its writes never wait for the slowest replica. (The model's reads ask two random replicas and wait for both; a real coordinator usually sends the read to all three and takes the first two replies, so its reads skip the slowest replica too.)
The last three lines are about availability. With one replica down, W=2, R=2 still serves reads and writes; W=3 can't write at all, and R=3 can't read. That's why majority quorums (W = R = ⌊N/2⌋ + 1) are the usual default: consistent overlap and tolerance of a minority of failures.

AdvancedHow much availability a quorum buys

Whether a quorum can be formed is a probability you can calculate. The estimate below assumes each replica is up independently 99% of the time. That's a rule-of-thumb number, and the independence is optimistic (replicas in one rack or zone fail together), but it shows the shape.

quorum-availability.mjs

// Chance that at least q of n replicas are up, if each is up independently with probability p.
// Assumption: p = 0.99 per replica (a rule-of-thumb number for one node; real failures are often correlated).
const choose = (n, k) => (k === 0 ? 1 : (n * choose(n - 1, k - 1)) / k);
const atLeast = (n, q, p) => {
  let sum = 0;
  for (let k = q; k <= n; k++) sum += choose(n, k) * p ** k * (1 - p) ** (n - k);
  return sum;
};
const minutesDownPerYear = (a) => ((1 - a) * 365 * 24 * 60).toFixed(1);

const p = 0.99;
for (const n of [3, 5]) {
  for (let q = 1; q <= n; q++) {
    const a = atLeast(n, q, p);
    console.log(`N=${n}, need ${q} up: ${(a * 100).toFixed(6)}%   no quorum ~${minutesDownPerYear(a).padStart(7)} min/year`);
  }
}

Result

N=3, need 1 up: 99.999900%   no quorum ~    0.5 min/year
N=3, need 2 up: 99.970200%   no quorum ~  156.6 min/year
N=3, need 3 up: 97.029900%   no quorum ~15610.8 min/year
N=5, need 1 up: 100.000000%   no quorum ~    0.0 min/year
N=5, need 2 up: 99.999995%   no quorum ~    0.0 min/year
N=5, need 3 up: 99.999015%   no quorum ~    5.2 min/year
N=5, need 4 up: 99.901985%   no quorum ~  515.2 min/year
N=5, need 5 up: 95.099005%   no quorum ~25759.6 min/year

What’s happening

atLeast(n, q, p) sums the binomial probabilities that exactly k of n replicas are up, for every k from q to n.
With N=3 and a majority (need 2), you lose quorum about 157 minutes a year, against about 15,600 minutes (11 days) if you need all 3. Requiring every replica is far worse than a single replica (which is down 1% of the time, about 5,256 minutes): more replicas only help if you need fewer than all of them.
With N=5 and a majority (need 3), it's about 5 minutes a year. Going from 3 to 5 replicas buys roughly 30 times fewer quorum outages for the cost of two more copies; the 100.000000% for "need 1" is a rounding of a number with ten nines.
"Need 4 of 5" (515 minutes) is worse than "need 2 of 3", which is why you choose the quorum as well as N: a write quorum of 4 out of 5 gives up most of what the extra replicas bought.
In a real design the independence assumption is the weak point. Put the replicas in different availability zones so that one zone failing takes out one replica, not a quorum.

AdvancedRead repair, hinted handoff and sloppy quorums

What real systems add on top

Mechanism	What it does	Cost or catch
Read repair	the read coordinator sees a stale answer (C's `v6`) and writes `v7` back to C	only fixes keys that get read
Anti-entropy	replicas compare their data in the background, usually with Merkle trees, and copy what's missing	background I/O; repairs lag behind
Sloppy quorum	if some of a key's N home replicas are unreachable, the write goes to other healthy nodes instead	the R and W sets may no longer overlap, so R + W > N no longer guarantees fresh reads
Hinted handoff	the stand-in node keeps a "hint" and hands the write to the home replica when it's back	hints can be lost if the stand-in dies
Local quorum	Cassandra's `LOCAL_QUORUM` counts only replicas in the client's data centre	fast and still consistent within a region; another region can lag

Amazon's Dynamo paper (2007) is the classic description of these: it states that "the common (N,R,W) configuration used by several instances of Dynamo is (3,2,2)", calls R + W > N "a quorum-like system", and uses a sloppy quorum with hinted handoff so the shopping cart always accepts writes. The same paper reports that over 24 hours, 99.94% of requests to the cart service saw exactly one version of the data, so conflicting versions were rare in practice.

AdvancedInterview: justifying N, R and W

What to say in the interview

When you design a replicated store, name N, R and W with a reason: "N=3 across three zones, W=2 and R=2 so reads overlap writes and either side survives one zone being down; for the analytics counters we'd use W=1, R=1 because a slightly stale count is fine and we want the lowest latency". Then say what happens to a slow or dead replica (hinted handoff, read repair, anti-entropy). The full case is Design a distributed key-value store.

Five replicas, read-heavy

A store has N = 5 and serves 50 reads for every write. Reads must see the latest acknowledged write, and the system must keep working, both reads and writes, with any two replicas down. Which R and W do you pick?

Show answer

W = 3, R = 3 (majorities). No other pair meets both requirements.

What’s happening

Freshness needs R + W > 5, so R + W must be at least 6.
Writes must work with two replicas down, so W can be at most 3 (only 3 replicas are up). Reads likewise need R ≤ 3.
With W ≤ 3 and R ≤ 3, the only way to get R + W ≥ 6 is W = 3 and R = 3.
The read-heavy mix tempts you towards a small R such as R = 1 with W = 5, which makes reads cheap but makes any single replica failure block all writes, failing the second requirement.
If the availability requirement were relaxed to one replica down, W = 4, R = 2 would become possible: cheaper reads, more expensive writes. The requirements pick the numbers, which is the point to make out loud.

#Time and ordering: Lamport and vector clocks

Added

Wall clocks can't order events across machines (see Why distributed systems are hard), but often you don't need the real time at all. You need to know whether one event could have caused another. Leslie Lamport defined this in 1978 as happened-before (written a → b): a happened before b if they're on the same machine and a came first, or a is the sending of a message and b is its receipt, or there's a chain of those from a to b. If neither a → b nor b → a, the events are concurrent: neither could have known about the other, whatever the wall clocks said.

Logical clocks track happened-before with counters instead of time. A Lamport clock is a single number per machine: tick it on every event, attach it to every message, and on receipt jump to past the number in the message. It guarantees that if a → b then L(a) < L(b), which gives every machine the same total order without talking. A vector clock keeps one counter per machine and can answer the reverse question too: from two vectors alone it can tell you whether one event happened before the other or whether they were concurrent.

The mental model: a Lamport clock is a ticket dispenser that you always wind forward past any ticket number you see on an incoming letter, so replies always get a later number than what they reply to. A vector clock is a row of page numbers, one per friend's diary: "I've read up to page 4 of Ana's diary, page 3 of Ben's, and page 3 of mine". Comparing two such rows tells you whether one writer had read everything the other had (cause and effect) or whether each had read something the other hadn't (concurrent).

Arrows are messages. An event happened before another only if you can follow the lines and arrows forwards from one to the other.

The trace in the picture, with Lamport clocks. Each event is local work, a send or a receive, listed in an order that really happened.

lamport.mjs

// Three servers A, B, C. Each event is local work, a send, or a receive (in an order that really happened).
const trace = [
  ["a1", "A", "local"],
  ["c1", "C", "local"],
  ["a2", "A", "send", "m1"],
  ["b1", "B", "local"],
  ["b2", "B", "recv", "m1"],
  ["b3", "B", "send", "m2"],
  ["a3", "A", "local"],
  ["c2", "C", "recv", "m2"],
  ["c3", "C", "send", "m3"],
  ["a4", "A", "recv", "m3"],
];

const clock = { A: 0, B: 0, C: 0 };
const inFlight = {};                       // message -> timestamp it carries
const L = {};
for (const [id, node, kind, msg] of trace) {
  if (kind === "recv") clock[node] = Math.max(clock[node], inFlight[msg]) + 1; // jump past the sender
  else clock[node] += 1;                                                       // local or send: tick
  if (kind === "send") inFlight[msg] = clock[node];
  L[id] = clock[node];
  console.log(`${id} on ${node}  ${kind.padEnd(5)} ${msg ?? "  "}  L=${L[id]}`);
}

// Total order: sort by (L, node name). Every server computes the same order without talking.
const order = Object.keys(L).sort((x, y) => L[x] - L[y] || x[0].localeCompare(y[0]));
console.log("total order:", order.join(" < "));
console.log(`L(c1)=${L.c1} < L(a2)=${L.a2}, yet c1 and a2 never communicated`);

Result

a1 on A  local     L=1
c1 on C  local     L=1
a2 on A  send  m1  L=2
b1 on B  local     L=1
b2 on B  recv  m1  L=3
b3 on B  send  m2  L=4
a3 on A  local     L=3
c2 on C  recv  m2  L=5
c3 on C  send  m3  L=6
a4 on A  recv  m3  L=7
total order: a1 < b1 < c1 < a2 < a3 < b2 < b3 < c2 < c3 < a4
L(c1)=1 < L(a2)=2, yet c1 and a2 never communicated

What’s happening

Local and send events tick: clock[node] += 1. A's first event a1 gets 1, and a2 (sending m1) gets 2; m1 carries the number 2. B and C start at 0 too, so b1 and c1 both get 1: Lamport numbers aren't unique, which is why the total order breaks ties by server name.
Receives jump: when b2 receives m1, B's clock is 1 and the message says 2, so B takes max(1, 2) + 1 = 3. A receive always gets a bigger number than the send it pairs with, so causes always get smaller numbers than their effects. c2 receives m2 (4) and gets 5; a4 receives m3 (6) and gets 7, even though A's own clock was only at 3.
The total order sorts by (L, server): a1 < b1 < c1 < a2 < …. Every server can compute it from the numbers alone, which is what Lamport clocks are used for: a single agreed order for things like totally ordered broadcast, or tie-breaking between operations.
The last line is the limitation. L(c1) = 1 < L(a2) = 2, but c1 and a2 never exchanged anything: they're concurrent. A Lamport clock says "if a caused b, then L(a) < L(b)", not the reverse, so a smaller number doesn't mean "happened before". To detect concurrency you need vector clocks.

AdvancedVector clocks: detecting concurrency

Same trace, but each server keeps a vector with one counter per server. It ticks its own slot on every event; on receive it first takes the element-wise maximum with the vector in the message. Then x → y exactly when every entry of V(x) is ≤ the matching entry of V(y) and they're not equal. If neither vector is ≤ the other, the events are concurrent.

vector-clocks.mjs

// Same trace as the Lamport example, now with one counter per server.
const trace = [
  ["a1", "A", "local"], ["c1", "C", "local"], ["a2", "A", "send", "m1"], ["b1", "B", "local"],
  ["b2", "B", "recv", "m1"], ["b3", "B", "send", "m2"], ["a3", "A", "local"], ["c2", "C", "recv", "m2"],
  ["c3", "C", "send", "m3"], ["a4", "A", "recv", "m3"],
];
const nodes = ["A", "B", "C"];
const vc = { A: [0, 0, 0], B: [0, 0, 0], C: [0, 0, 0] };
const inFlight = {};
const V = {};
for (const [id, node, kind, msg] of trace) {
  const i = nodes.indexOf(node);
  if (kind === "recv") vc[node] = vc[node].map((x, k) => Math.max(x, inFlight[msg][k])); // merge
  vc[node][i] += 1;                                                                     // then tick own slot
  if (kind === "send") inFlight[msg] = [...vc[node]];
  V[id] = [...vc[node]];
}
console.log(Object.entries(V).map(([id, v]) => `${id}=[${v}]`).join("  "));

const leq = (x, y) => x.every((n, k) => n <= y[k]);
function compare(x, y) {
  if (leq(V[x], V[y]) && !leq(V[y], V[x])) return `${x} -> ${y}`;   // x happened before y
  if (leq(V[y], V[x]) && !leq(V[x], V[y])) return `${y} -> ${x}`;
  return `${x} || ${y}`;                                             // concurrent
}
for (const [x, y] of [["a2", "c2"], ["c1", "a2"], ["a3", "b3"], ["b1", "a4"], ["a3", "c3"]]) console.log(compare(x, y));

const ids = Object.keys(V);
const concurrent = [];
for (let i = 0; i < ids.length; i++)
  for (let j = i + 1; j < ids.length; j++) if (compare(ids[i], ids[j]).includes("||")) concurrent.push(`${ids[i]}||${ids[j]}`);
console.log(`${concurrent.length} concurrent pairs of ${(ids.length * (ids.length - 1)) / 2}:`, concurrent.join(" "));

Result

a1=[1,0,0]  c1=[0,0,1]  a2=[2,0,0]  b1=[0,1,0]  b2=[2,2,0]  b3=[2,3,0]  a3=[3,0,0]  c2=[2,3,2]  c3=[2,3,3]  a4=[4,3,3]
a2 -> c2
c1 || a2
a3 || b3
b1 -> a4
a3 || c3
13 concurrent pairs of 45: a1||c1 a1||b1 c1||a2 c1||b1 c1||b2 c1||b3 c1||a3 a2||b1 b1||a3 b2||a3 b3||a3 a3||c2 a3||c3

What’s happening

b2 merges B's [0,1,0] with the [2,0,0] carried by m1, giving [2,1,0], then ticks B's own slot: [2,2,0]. The vector now says "B has seen two of A's events and two of its own", which is exactly what B could know at that moment.
a2 -> c2: [2,0,0] is ≤ [2,3,2] in every slot, so a2 happened before c2. That's the chain a2 → m1 → b2 → b3 → m2 → c2, found from the vectors alone.
c1 || a2: [0,0,1] has more in C's slot, [2,0,0] more in A's. Neither dominates, so they're concurrent. This is the pair the Lamport numbers made look ordered (1 < 2).
a3 || b3 and a3 || c3: A's a3 is [3,0,0]; B and C never heard about A's third event, and A hadn't heard from them yet, so those are concurrent. b1 -> a4: a4 = [4,3,3] includes B's first event through the chain b1 → b2 → b3 → m2 → c2 → c3 → m3 → a4.
Out of 45 pairs of events, 13 are concurrent. Those are the pairs where a system that cares about conflicts (two writes to the same key) has to merge or ask the user, rather than letting the later one win. The cost is size: a vector has one entry per server (or per writer), and it travels with every message and is stored with every value.

AdvancedVersion vectors in a Dynamo-style store

Stores like Dynamo and Riak use the same idea per key: each stored value carries a version vector, and a write carries the version the client read (its "context"). If the new write's vector descends from a stored one, it replaces it. If not, both are kept as siblings and the next read gets all of them. The model shows two devices editing the same cart.

version-vectors.mjs

// Dynamo-style versions for one key (a shopping cart). Each write carries the version it was based on;
// the replica that takes it increments its own slot. Versions that don't descend from each other are siblings.
const descends = (a, b) => Object.keys(b).every((k) => (a[k] ?? 0) >= b[k]);   // a has seen everything b has
const store = [];                                                            // current versions (siblings)

function put(replica, value, context) {
  const version = { ...context, [replica]: (context[replica] ?? 0) + 1 };
  // Every version the writer had seen is now superseded; anything it hadn't seen stays as a sibling.
  for (const s of store) if (descends(context, s.version)) s.obsolete = true;
  store.splice(0, store.length, ...store.filter((s) => !s.obsolete), { value, version });
  console.log(`put ${JSON.stringify(value)} via ${replica} -> ${JSON.stringify(version)}; siblings: ${store.length}`);
}
const get = () => ({ values: store.map((s) => s.value), context: store.reduce((m, s) => mergeMax(m, s.version), {}) });
const mergeMax = (a, b) => {
  const out = { ...a };
  for (const [k, n] of Object.entries(b)) out[k] = Math.max(out[k] ?? 0, n);
  return out;
};

put("X", ["milk"], {});                                   // first write
const seen = get().context;                              // phone and laptop both read {X:1}
put("Y", ["milk", "eggs"], seen);                        // phone adds eggs via replica Y
put("Z", ["milk", "bread"], seen);                       // laptop adds bread via Z, not having seen eggs
const { values, context } = get();
console.log("read returns siblings:", JSON.stringify(values), "context", JSON.stringify(context));
const merged = [...new Set(values.flat())];              // the app's merge rule for carts: union
put("X", merged, context);                               // writing with the merged context replaces both

Result

put ["milk"] via X -> {"X":1}; siblings: 1
put ["milk","eggs"] via Y -> {"X":1,"Y":1}; siblings: 1
put ["milk","bread"] via Z -> {"X":1,"Z":1}; siblings: 2
read returns siblings: [["milk","eggs"],["milk","bread"]] context {"X":1,"Y":1,"Z":1}
put ["milk","eggs","bread"] via X -> {"X":2,"Y":1,"Z":1}; siblings: 1

What’s happening

The first put via replica X creates {"X":1}. Both devices then read the cart and get the context {"X":1}.
The phone adds eggs through replica Y, based on {"X":1}: the new version {"X":1,"Y":1} descends from the stored one, so it replaces it. Still one version.
The laptop adds bread through Z, also based on {"X":1}, because it never saw the eggs. Its version {"X":1,"Z":1} supersedes {"X":1}, which was already gone, but not {"X":1,"Y":1}: neither of those two descends from the other. The store keeps both: siblings: 2.
The next read returns both siblings and a merged context {"X":1,"Y":1,"Z":1}. The store doesn't know how to merge carts; the application does, here by union, giving milk, eggs and bread.
Writing the merged cart with the merged context produces {"X":2,"Y":1,"Z":1}, which descends from both siblings and replaces them. Union merges never lose an added item, which is the trade-off the Dynamo paper describes: an "add to cart" is never lost, "however, deleted items can resurface" (a removal on one device is undone by the other device's sibling).

AdvancedPhysical time: HLC, TrueTime, better clocks

Physical time, done carefully

Sometimes you do want real time: "show messages in the order they were sent", or snapshot reads "as of 10:00:00". Two designs make physical time usable:

Hybrid logical clocks (HLC), used by CockroachDB and others, combine the wall clock with a Lamport-style counter: timestamps stay close to real time but still respect causality when clocks are slightly off.
TrueTime in Google Spanner exposes the clock's uncertainty as an interval. A transaction picks a commit timestamp and then waits out the uncertainty before it becomes visible (commit wait), so no later transaction anywhere can get a smaller timestamp. Google's Spanner Omni documentation (2026) says commit latency doesn't grow while the uncertainty stays below the Paxos round-trip time; the 2012 Spanner paper (OSDI) reports that, with GPS and atomic-clock time masters, the uncertainty is typically a sawtooth from about 1 to 7 ms, so about 4 ms most of the time.
On ordinary cloud machines, the clocks are better than they used to be: AWS says its Time Sync Service gives clock accuracy in the low double-digit microseconds on supported EC2 instances (AWS, 2023, extended to more instance types in 2024 and 2026), with ClockBound to report the error bound. Better clocks shrink the problem; they don't let you skip reasoning about it.

AdvancedInterview: when logical clocks are needed

What to say in the interview

Bring logical clocks in when the design must detect conflicting concurrent updates (a multi-leader or leaderless store, offline editing) or must order events across machines without trusting their clocks. Say what you'd use: "a Lamport timestamp is enough for a total order and tie-breaks; to detect concurrent writes I need version vectors, and then a merge rule (union for a cart, a CRDT for a counter, or ask the user)".

Before, after, or concurrent?

Three replicas tag versions of the same key with version vectors in the order [A, B, C]. Version P is [2, 1, 0], version Q is [2, 2, 0] and version R is [1, 1, 3]. What's the relationship between P and Q, Q and R, and P and R?

Show answer

P → Q (Q supersedes P). Q and R are concurrent, and so are P and R. A read must return Q and R as siblings, or merge them.

What’s happening

Compare P [2,1,0] with Q [2,2,0] slot by slot: 2 ≤ 2, 1 ≤ 2, 0 ≤ 0, and they're not equal. So every write P had seen, Q had seen too, plus one more on B: P happened before Q and Q can replace it.
Q [2,2,0] against R [1,1,3]: Q is bigger in A's and B's slots, R is bigger in C's. Neither is ≤ the other in every slot, so they're concurrent.
P [2,1,0] against R [1,1,3]: P is bigger in A, R is bigger in C, so they're concurrent too.
The store therefore keeps Q and R (P is obsolete) and hands both to the next reader with a merged context [2,2,3]. Writing a merged value with that context, via replica A, gives [3,2,3], which descends from both.

#Leader election and consensus

Added

Many designs quietly assume that the machines agree on something: who the leader is, which node holds a lock, what the current configuration is, the order of writes in a replicated log. Consensus is the problem of getting several machines to agree on a value, or a sequence of values, even when some of them crash and messages are delayed, and of never letting two of them decide differently. Without it you get split brain: two nodes both think they're the leader, both accept writes, and the data diverges.

Consensus algorithms (Paxos, Raft, Zab) all rest on the same two ideas. Majorities: a decision needs a majority of the nodes, and any two majorities overlap in at least one node, so two conflicting decisions can't both get one. Epochs, called terms in Raft: every leadership period has a number that only goes up, and nodes reject anything from an older term, so a deposed leader that wakes up after a pause can't do damage. There's a famous theoretical limit (the FLP result, 1985): in a fully asynchronous network, no algorithm can guarantee it always reaches agreement if even one node may crash. Real systems get around it with timeouts: they're always safe (never two decisions), and they make progress whenever the network behaves well enough for long enough.

The mental model: a committee with numbered meetings. Each meeting (term) has at most one chair, elected by a majority of members, and each member votes once per meeting. Decisions only count once a majority has written them in their minutes. A member who slept through meetings 7 and 8 and shows up claiming to chair meeting 6 is simply ignored.

Every transition is driven by a timeout or a term number. Nothing depends on comparing clocks between servers.

Raft in brief

Raft (Ongaro and Ousterhout, 2014) was designed to be easier to understand than Paxos, and it's what etcd, CockroachDB and Kafka's KRaft metadata layer use (MongoDB's replica sets use a Raft-like protocol). The parts worth being able to explain:

Terms: time is divided into numbered terms. Every message carries the sender's term; a node that sees a higher term adopts it and becomes a follower; a message with a lower term is rejected.
Election: a follower that hears no heartbeat before its election timeout becomes a candidate, increments the term, votes for itself and asks the others. Each node grants one vote per term, and only to a candidate whose log is at least as up to date as its own. A majority of votes makes it leader.
Randomized timeouts: each node picks its timeout at random from a range (typically 150 to 300 ms, per Wikipedia's summary of the Raft paper, checked October 2026), so usually one node times out first and wins before the others start. The paper's timing rule, as quoted there, is broadcast time ≪ election timeout ≪ mean time between failures.
Log replication: clients send writes to the leader, which appends them to its log and sends them to followers (heartbeats are empty appends). An entry is committed once a majority stores it (counted for entries from the leader's current term; see the commit rule below); only then is it applied and acknowledged to the client.

The model below runs only the election part, on five servers in 1 ms steps with a 5 ms one-way message delay. The leader sends heartbeats every 50 ms and crashes at 1,000 ms. It runs twice: with randomized timeouts (seeded) and with every server using the same fixed 150 ms timeout.

raft-election.mjs

// Raft leader election only (no log), 5 servers, 1 ms steps, 5 ms one-way message delay. Seeded timeouts.
function mulberry32(seed) {
  return () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function simulate(label, timeout, { verbose = false, crashLeaderAt = 1000, until = 2500 } = {}) {
  console.log(`--- ${label} ---`);
  const rand = mulberry32(11);
  const nodes = [1, 2, 3, 4, 5].map((id) => ({ id, role: "follower", term: 0, votedFor: null, votes: 0, up: true }));
  const resetTimer = (n, now) => (n.deadline = now + timeout(rand));
  nodes.forEach((n) => resetTimer(n, 0));
  let inbox = [];
  const send = (now, from, to, msg) => inbox.push({ at: now + 5, from, to, ...msg });
  const leaderTerms = [];
  let mostVotes = 0;
  for (let now = 0; now <= until; now++) {
    for (const m of inbox.filter((m) => m.at === now)) {
      const n = nodes[m.to - 1];
      if (!n.up) continue;
      if (m.term > n.term) Object.assign(n, { term: m.term, role: "follower", votedFor: null }); // newer term wins
      if (m.type === "vote?") {
        const grant = m.term === n.term && (n.votedFor === null || n.votedFor === m.from);
        if (grant) { n.votedFor = m.from; resetTimer(n, now); }
        send(now, n.id, m.from, { type: "vote", term: n.term, granted: grant });
      } else if (m.type === "vote" && n.role === "candidate" && m.term === n.term && m.granted) {
        mostVotes = Math.max(mostVotes, ++n.votes);
        if (n.votes === 3) {                                     // majority of 5
          n.role = "leader";
          leaderTerms.push(`t=${now} ms: n${n.id} is leader of term ${n.term}`);
          console.log(leaderTerms.at(-1));
        }
      } else if (m.type === "heartbeat" && m.term === n.term) { n.role = "follower"; resetTimer(n, now); }
    }
    inbox = inbox.filter((m) => m.at > now);
    for (const n of nodes.filter((n) => n.up)) {
      if (n.role === "leader") {
        if (now === crashLeaderAt) { n.up = false; console.log(`t=${now} ms: n${n.id} crashes`); continue; }
        if (now % 50 === 0) nodes.forEach((o) => o !== n && send(now, n.id, o.id, { type: "heartbeat", term: n.term }));
      } else if (now >= n.deadline) {                             // heard nothing: start an election
        Object.assign(n, { role: "candidate", term: n.term + 1, votedFor: n.id, votes: 1 });
        resetTimer(n, now);
        if (verbose) console.log(`t=${now} ms: n${n.id} times out, becomes candidate for term ${n.term}`);
        nodes.forEach((o) => o !== n && send(now, n.id, o.id, { type: "vote?", term: n.term }));
      }
    }
  }
  const maxTerm = Math.max(...nodes.map((n) => n.term));
  console.log(`leaders elected: ${leaderTerms.length}, highest term: ${maxTerm}, best candidate had ${Math.max(mostVotes, 1)} of 5 votes`);
}

simulate("randomized timeouts, 150-300 ms", (rand) => 150 + Math.floor(rand() * 150), { verbose: true });
simulate("same fixed timeout, 150 ms", () => 150);

Result

--- randomized timeouts, 150-300 ms ---
t=226 ms: n1 times out, becomes candidate for term 1
t=229 ms: n2 times out, becomes candidate for term 1
t=236 ms: n1 is leader of term 1
t=1000 ms: n1 crashes
t=1150 ms: n2 times out, becomes candidate for term 2
t=1160 ms: n2 is leader of term 2
leaders elected: 2, highest term: 2, best candidate had 3 of 5 votes
--- same fixed timeout, 150 ms ---
leaders elected: 0, highest term: 16, best candidate had 1 of 5 votes

What’s happening

At the start nobody is leader, so every server's election timer runs out eventually. With random timeouts, n1's fires first, at 226 ms: it becomes a candidate for term 1, votes for itself and sends vote? to the other four.
n2's timer fires 3 ms later, before n1's request (5 ms in flight) has reached it, so n2 also becomes a candidate for term 1 and votes for itself: a near split. But n1's requests reach n3, n4 and n5 first, each grants its single term-1 vote to n1, and at 236 ms n1 has 3 of 5: leader of term 1. n2 gets no votes, and when n1's heartbeat arrives with term 1 it goes back to being a follower.
At 1,000 ms n1 crashes. Its last heartbeat went out at 950 ms; n2's timer, reset by that heartbeat, fires at 1,150 ms. n2 starts term 2, the others haven't timed out yet and grant their votes, and at 1,160 ms n2 is leader. Failover took 160 ms, most of it waiting for the timeout to be sure the leader was really gone.
With the same fixed timeout, all five servers time out at exactly the same moment, each votes for itself, and every vote request reaches servers that have already voted in that term. The best any candidate gets is 1 of 5 votes. They all time out again together, move to the next term, and repeat: after 2.5 seconds, 16 terms and no leader.
That's why the randomness isn't an optimisation but part of the algorithm's liveness. Safety never depended on it (one vote per term means at most one leader per term even in the fixed run); randomness is what makes an election finish. Real networks have jitter, so the fixed case wouldn't be quite this perfect, but split votes would still repeat far more often.

AdvancedThe commit rule: majority, and nothing less

The leader tracks how far each follower's log matches its own (matchIndex). An entry is committed when a majority of servers, counting the leader, store it. One subtlety interviewers sometimes probe: a leader only counts replicas this way for entries from its own term. An entry left over from an earlier term becomes committed only when a current-term entry after it reaches a majority, because the Raft paper's Figure 8 shows an old-term entry stored on a majority being overwritten by a later leader. The second model computes the counting rule for a few situations in one term.

raft-commit.mjs

// Raft log replication, the commit rule only. The leader knows how far each follower's log matches its own.
// An entry is committed once a majority of servers store it; only then is it applied and the client told "ok".
function commitIndex(matchIndex) {
  const sorted = [...matchIndex].sort((a, b) => b - a);  // highest first
  return sorted[Math.floor(matchIndex.length / 2)];      // the value a majority has reached
}

const leaderLog = ["x=1", "y=2", "x=3", "z=9", "y=7", "x=4", "z=0"]; // entries 1..7 in the leader's log
const cases = {
  "healthy":               [7, 7, 6, 7, 5],   // leader first, then the four followers
  "two followers behind":  [7, 7, 5, 3, 3],
  "partitioned leader":    [7, 2, 2, 2, 2],   // leader appended 5 entries nobody else has
};
for (const [label, match] of Object.entries(cases)) {
  const c = commitIndex(match);
  console.log(`${label.padEnd(21)} match ${JSON.stringify(match)} -> committed up to ${c} (${leaderLog.slice(0, c).join(", ")})`);
}

// What happens to entries 3..7 of the partitioned leader: a new leader is elected on the majority side
// with a log of length 2, and its later entries overwrite them. The clients for 3..7 were never told "ok".
console.log("uncommitted on the old leader, discarded after it rejoins:", leaderLog.slice(2).join(", "));

Result

healthy               match [7,7,6,7,5] -> committed up to 7 (x=1, y=2, x=3, z=9, y=7, x=4, z=0)
two followers behind  match [7,7,5,3,3] -> committed up to 5 (x=1, y=2, x=3, z=9, y=7)
partitioned leader    match [7,2,2,2,2] -> committed up to 2 (x=1, y=2)
uncommitted on the old leader, discarded after it rejoins: x=3, z=9, y=7, x=4, z=0

What’s happening

commitIndex sorts the match positions from highest to lowest and takes the one at position ⌊5 / 2⌋ = 2, the third-highest: by definition, three servers (a majority of five) have at least that many entries.
Healthy: positions [7,7,6,7,5] sort to [7,7,7,6,5], so all seven entries are committed. The follower at 5 is behind but doesn't hold anything up, because a majority already has everything.
Two followers behind: [7,7,5,3,3] sorts to [7,7,5,3,3], so entries up to 5 are committed. Entries 6 and 7 are on only two servers; the clients that sent them are still waiting for "ok".
Partitioned leader: the old leader appended five entries that no follower has, so only entries 1 and 2 are committed. Meanwhile the four followers elect a new leader in a higher term, and when the old leader rejoins it sees the higher term, steps down, and its uncommitted entries 3 to 7 are overwritten by the new leader's log.
Nothing acknowledged is lost, because nothing was acknowledged before reaching a majority. This is the real meaning of "consensus-based replication": once the leader has an entry from its own term on a majority, the entry is durable and any future leader must have it, because winning an election needs votes from a majority, and that majority includes at least one server with the entry (which refuses to vote for a candidate whose log is less up to date than its own).

AdvancedHow big should the cluster be?

A cluster of N tolerates ⌊(N − 1) / 2⌋ failed nodes, because the rest must still be a majority:

Nodes	Majority	Failures tolerated	Note
1	1	0	no fault tolerance
3	2	1	the usual minimum
4	3	1	no better than 3, and one more node to fail
5	3	2	common for important clusters
7	4	3	rarely worth it: every write waits for 4 nodes

Even sizes don't help, and bigger isn't faster: every committed write needs a majority to respond, so a consensus cluster is kept small (3 or 5 nodes) and is used for small, critical data (who is leader, configuration, locks, metadata), not as the main database for high-volume traffic.

AdvancedUse etcd or ZooKeeper; don't write your own

In a design you almost never implement consensus. You use a coordination service built on it: etcd (Raft, the store behind Kubernetes) or ZooKeeper (Zab, a Paxos-like protocol), or a database that has it built in. Typical uses:

Leader election for your own service: each instance tries to create a key with a lease (etcd) or an ephemeral node (ZooKeeper); the one that succeeds is leader, and if it dies its lease expires and another instance takes over.
Service configuration and feature flags that must be identical everywhere, with watches so instances hear about changes.
Distributed locks with leases, which need fencing tokens (below).
Membership: which nodes are alive and which shards each one owns.

Timings are tunable and they're the trade-off: etcd's defaults are a 100 ms heartbeat interval and a 1,000 ms election timeout, and its tuning guide says the election timeout should be at least ten times the round-trip time between members and the heartbeat around 0.5 to 1.5 times it (etcd v3.6 documentation, October 2026). A shorter timeout fails over faster but triggers needless elections whenever the network hiccups.

AdvancedLeases and fencing tokens

A lease is a lock with an expiry: "you hold it for 10 seconds unless you renew". It solves the "lock holder crashed and never released it" problem. It creates a new one: a holder that pauses (GC, VM migration) for longer than the lease wakes up still believing it holds the lock, while someone else has been granted it. The fix is a fencing token: the lock service hands out a number that increases with every grant, the holder sends it with every write, and the storage rejects any write with a token lower than one it has already seen.

fencing.mjs

// A lock with a lease, and a client that pauses (GC, VM migration) while it thinks it still holds the lock.
// The lock service hands out a fencing token that goes up by one with every grant.
function lockService(leaseMs) {
  let holder = null, expires = 0, token = 33;
  return {
    acquire(client, now) {
      if (holder && now < expires) return null;               // someone else holds a live lease
      holder = client; expires = now + leaseMs; token++;
      return token;
    },
  };
}

function storage(checkTokens) {
  let highest = 0;
  const writes = [];
  return {
    write(client, token, data) {
      if (checkTokens && token < highest) return `REJECTED ${client} (token ${token} < ${highest})`;
      highest = Math.max(highest, token);
      writes.push(data);
      return `ok ${client} (token ${token})`;
    },
    get file() { return writes.join(" + "); },
  };
}

for (const checkTokens of [false, true]) {
  const locks = lockService(10_000);
  const disk = storage(checkTokens);
  const t1 = locks.acquire("client-1", 0);                   // t=0 s: client 1 gets the lock
  // client 1 now freezes for 15 s; its lease runs out at t=10 s
  const t2 = locks.acquire("client-2", 12_000);              // t=12 s: client 2 gets the lock
  const log = [disk.write("client-2", t2, "B's update")];    // t=13 s
  log.push(disk.write("client-1", t1, "A's stale update"));  // t=15 s: client 1 wakes, still "holding" it
  console.log(`${checkTokens ? "with fencing   " : "without fencing"}: ${log.join(", ")} -> file = ${disk.file}`);
}

Result

without fencing: ok client-2 (token 35), ok client-1 (token 34) -> file = B's update + A's stale update
with fencing   : ok client-2 (token 35), REJECTED client-1 (token 34 < 35) -> file = B's update

What’s happening

client-1 acquires the lock at t = 0 with a 10-second lease and gets token 34 (the counter started at 33). Then it freezes for 15 seconds without knowing it.
At t = 12 s the lease has expired, so the lock service grants it to client-2 with token 35. client-2 writes its update with token 35.
At t = 15 s client-1 wakes up and carries on from where it was: it writes, still believing it holds the lock. It never had a chance to check, because the pause could have happened between any check and the write.
Without fencing the storage accepts both, and the file ends up as B's update + A's stale update: two "exclusive" holders wrote, which is exactly what the lock was meant to prevent.
With fencing the storage remembers the highest token it has seen (35) and rejects token 34: REJECTED client-1. The protection sits in the resource, not in the client's belief about the lock, which is the only place it can't be fooled by a pause. etcd exposes such a number as the key's revision; ZooKeeper as the node's version or zxid.

AdvancedInterview: leader election without split brain

What to say in the interview

When a design has "one leader" or "one worker owns this shard", say how the one is chosen and what stops two: "the scheduler instances elect a leader through an etcd lease; the leader includes the lease's revision as a fencing token on every job it dispatches, and the job store rejects a lower one, so a paused ex-leader can't double-dispatch". And keep consensus off the hot path: etcd decides who's in charge; it doesn't store the jobs.

How do you elect a leader and avoid split brain?

"I'd use a consensus-backed coordination service such as etcd or ZooKeeper rather than building it. The instances race to take a lease on a key; the winner is leader and keeps renewing; if it dies or is partitioned away, the lease expires and another instance wins. Underneath, etcd's Raft only lets a node become leader with votes from a majority, and terms stop an old leader's messages from counting. Split brain can still happen at the application level if the old leader is paused and doesn't notice its lease has expired, so every action it takes carries a fencing token, the lease revision, and the downstream system rejects tokens older than the newest it has seen. Cluster size: three or five etcd nodes across zones, so it survives one or two failures."

Four nodes or three?

To be "safer", a team runs its etcd cluster with 4 nodes instead of 3. How many node failures does each cluster survive, and what did the fourth node change?

Show answer

Both survive one failure. The fourth node added cost and one more machine that can fail, and made every write wait for 3 acknowledgements instead of 2.

What’s happening

A cluster of 3 needs a majority of 2. With one node down, the other 2 are still a majority; with two down, 1 is not. So it tolerates 1.
A cluster of 4 needs a majority of 3 (more than half of 4). With one down, 3 remain, a majority; with two down, 2 is exactly half, not a majority. So it also tolerates 1.
A network split into 2 + 2 is worse with 4 nodes: neither half has a majority, so the whole cluster stops. A 3-node cluster split 2 + 1 keeps working on the side with 2.
Writes need the third-fastest of four acknowledgements instead of the second-fastest of three, so they're slightly slower too.
To survive two failures, go to 5 nodes (majority 3).

#Distributed transactions: two-phase commit, sagas and the outbox

Added

Placing an order touches the orders database, the payments service and the stock service. Inside one database you'd wrap it in a transaction and get all-or-nothing for free. Across services and databases there's no shared transaction, so you have to choose how much "all-or-nothing" you need and what you'll pay for it. Three patterns cover almost every interview answer:

Two-phase commit (2PC): a coordinator asks every participant to prepare, then tells all of them to commit or all to abort. Atomic, but participants hold locks while they wait, and a coordinator failure at the wrong moment leaves them blocked.
Saga: a sequence of local transactions, one per service, each with a compensating action that semantically undoes it. If a step fails, the completed steps are compensated in reverse order. No locks across services and no blocking, but other users can see the in-between states.
Transactional outbox: not a transaction protocol but the piece that makes sagas and events reliable: write the business change and the event to publish in the same local transaction, and let a separate relay publish the event.

Two mental models. 2PC is a wedding: the officiant asks each person "do you?", and only when both say "I do" does the officiant pronounce them married. Once you've said "I do" you can't walk out, and if the officiant faints before pronouncing, everyone stands at the altar waiting. A saga is booking a trip yourself: book the flight, then the hotel, then the car; if no car is available, you cancel the hotel and the flight. Cancelling isn't the same as never having booked (there may be a fee, and the airline did send you a confirmation email), and that difference is what makes sagas harder than they look.

Two round trips and a durable decision in between. From its YES until the commit arrives, a participant holds its locks; if the coordinator dies before the decision reaches them (before logging it, or after logging but before sending), every participant is stuck in doubt.

The model runs 2PC across three participants three times: everyone votes yes, one participant votes no, and the coordinator crashes after collecting the votes but before logging a decision.

two-phase-commit.mjs

// Two-phase commit across three databases. The coordinator writes its decision to its own log before phase 2.
function participant(name, { voteNo = false } = {}) {
  return {
    name, state: "idle", locks: false,
    prepare() {                                   // phase 1: do the work, hold locks, promise you can commit
      if (voteNo) { this.state = "aborted"; return "NO"; }
      this.state = "prepared"; this.locks = true; // a prepared participant may NOT decide on its own any more
      return "YES";
    },
    finish(decision) { this.state = decision === "COMMIT" ? "committed" : "aborted"; this.locks = false; },
  };
}

function run(label, parts, { crashAfterVotes = false } = {}) {
  const coordLog = [];
  const votes = parts.map((p) => [p.name, p.prepare()]);
  const decision = votes.every(([, v]) => v === "YES") ? "COMMIT" : "ABORT";
  console.log(`--- ${label} ---`);
  console.log("phase 1 votes:", votes.map(([n, v]) => `${n}=${v}`).join(" "));
  if (crashAfterVotes) {
    console.log("coordinator crashes before logging or sending the decision");
    console.log("participants:", parts.map((p) => `${p.name}=${p.state}${p.locks ? " (locks held)" : ""}`).join(" "));
    return { parts, coordLog };
  }
  coordLog.push(decision);                        // durable decision: the commit point
  for (const p of parts) if (p.state === "prepared") p.finish(decision);
  console.log(`phase 2: ${decision} ->`, parts.map((p) => `${p.name}=${p.state}`).join(" "));
}

run("happy path", [participant("orders"), participant("payments"), participant("stock")]);
run("stock votes no", [participant("orders"), participant("payments"), participant("stock", { voteNo: true })]);
const { parts, coordLog } = run("coordinator crash", [participant("orders"), participant("payments"), participant("stock")], { crashAfterVotes: true });

// While the coordinator is down, can the participants work it out among themselves?
const others = parts.slice(1).map((p) => `${p.name}=${p.state}`).join(", ");
console.log(`orders asks the others: ${others} -> nobody knows the decision, locks stay held`);
const recovered = coordLog.at(-1) ?? "ABORT";      // recovery rule: no decision logged -> presumed abort
for (const p of parts) p.finish(recovered);
console.log(`coordinator recovers, log has no decision -> ${recovered}:`, parts.map((p) => `${p.name}=${p.state}`).join(" "));

Result

--- happy path ---
phase 1 votes: orders=YES payments=YES stock=YES
phase 2: COMMIT -> orders=committed payments=committed stock=committed
--- stock votes no ---
phase 1 votes: orders=YES payments=YES stock=NO
phase 2: ABORT -> orders=aborted payments=aborted stock=aborted
--- coordinator crash ---
phase 1 votes: orders=YES payments=YES stock=YES
coordinator crashes before logging or sending the decision
participants: orders=prepared (locks held) payments=prepared (locks held) stock=prepared (locks held)
orders asks the others: payments=prepared, stock=prepared -> nobody knows the decision, locks stay held
coordinator recovers, log has no decision -> ABORT: orders=aborted payments=aborted stock=aborted

What’s happening

Phase 1: prepare() makes each participant do the work, hold its locks, and promise it can commit: once it has said YES, it is no longer allowed to decide on its own. That promise is what makes the protocol atomic, and it's also its weakness.
Happy path: all three vote YES, the coordinator writes COMMIT to its own durable log (the commit point: from now on the answer is commit, even if it crashes), and phase 2 tells everyone. All three end committed.
One NO: stock can't reserve the item, so the decision is ABORT, and orders and payments, which had prepared and were holding locks, roll back. One participant can veto the whole transaction, which is the all-or-nothing you wanted.
Coordinator crash after the votes: all three are prepared (locks held). When orders asks the others, they're prepared too: none of them knows whether the coordinator logged COMMIT (and maybe already told someone) or never decided. Committing could break atomicity, aborting could too, so they wait, holding locks, which blocks every other transaction that touches those rows.
When the coordinator comes back, its log has no decision, so by the usual presumed-abort rule the answer is ABORT and everyone rolls back. The blocking lasted as long as the coordinator was down. That's why 2PC is used inside one system with a highly available coordinator, and avoided between independently owned services.

AdvancedWhere 2PC is still used

2PC isn't dead; it moved inside databases, where the coordinator itself is replicated so it can't simply disappear. Spanner and CockroachDB run 2PC across shards whose participants and coordinator are each a Paxos or Raft group, so "the coordinator crashed" means a new leader of its group picks up the log. Within one cloud service you get the same effect as a product feature: DynamoDB's TransactWriteItems groups up to 100 actions across tables in one account and region, up to 4 MB in total (AWS documentation, October 2026). Classic XA transactions between different databases and message brokers exist too, but they couple the systems' availability and are rarely what an interviewer wants to hear for microservices.

AdvancedSagas: local transactions plus compensations

A saga splits the operation into steps, each a local transaction in one service. If a step fails, the saga runs the compensations of the steps already done, in reverse order. There's no global lock and no blocking; the price is that the system is visibly in between for a while, and that every compensation must itself succeed eventually.

Compensations run in reverse order and undo the business effect, not the history: the refund is a new ledger entry, and the cancelled order still exists.

An orchestrated saga for that order, run once where everything works and once where booking the courier fails:

saga.mjs

// An orchestrated saga: each step is a local transaction in one service, with a compensating action.
const state = { order: "none", stock: 10, charged: 0, shipment: "none" };

const steps = [
  { name: "create order",  run: () => (state.order = "PENDING"),   undo: () => (state.order = "CANCELLED") },
  { name: "reserve stock", run: () => (state.stock -= 1),          undo: () => (state.stock += 1) },
  { name: "charge card",   run: () => (state.charged += 25),       undo: () => (state.charged -= 25) }, // a refund, not a delete
  { name: "book courier",  run: (fail) => { if (fail) throw new Error("no courier in area"); state.shipment = "BOOKED"; } },
  { name: "confirm order", run: () => (state.order = "CONFIRMED") },
];

function runSaga(failAt) {
  const done = [];
  for (const step of steps) {
    try {
      step.run(step.name === failAt);
      done.push(step);
      console.log(`  ok    ${step.name.padEnd(14)} ${JSON.stringify(state)}`);
    } catch (err) {
      console.log(`  FAIL  ${step.name.padEnd(14)} ${err.message}`);
      for (const prev of done.reverse()) {             // compensate in reverse order
        prev.undo?.();
        console.log(`  undo  ${prev.name.padEnd(14)} ${JSON.stringify(state)}`);
      }
      return "compensated";
    }
  }
  return "completed";
}

console.log("saga 1: everything works");
console.log("  ->", runSaga(null));
Object.assign(state, { order: "none", stock: 10, charged: 0, shipment: "none" });
console.log("saga 2: the courier step fails");
console.log("  ->", runSaga("book courier"));

Result

saga 1: everything works
  ok    create order   {"order":"PENDING","stock":10,"charged":0,"shipment":"none"}
  ok    reserve stock  {"order":"PENDING","stock":9,"charged":0,"shipment":"none"}
  ok    charge card    {"order":"PENDING","stock":9,"charged":25,"shipment":"none"}
  ok    book courier   {"order":"PENDING","stock":9,"charged":25,"shipment":"BOOKED"}
  ok    confirm order  {"order":"CONFIRMED","stock":9,"charged":25,"shipment":"BOOKED"}
  -> completed
saga 2: the courier step fails
  ok    create order   {"order":"PENDING","stock":10,"charged":0,"shipment":"none"}
  ok    reserve stock  {"order":"PENDING","stock":9,"charged":0,"shipment":"none"}
  ok    charge card    {"order":"PENDING","stock":9,"charged":25,"shipment":"none"}
  FAIL  book courier   no courier in area
  undo  charge card    {"order":"PENDING","stock":9,"charged":0,"shipment":"none"}
  undo  reserve stock  {"order":"PENDING","stock":10,"charged":0,"shipment":"none"}
  undo  create order   {"order":"CANCELLED","stock":10,"charged":0,"shipment":"none"}
  -> compensated

What’s happening

steps pairs each forward action with its compensation. book courier and confirm order have none: the first is the step that may fail, and the last runs only when everything before it worked. The orchestrator remembers each completed step in done.
Saga 1 runs all five steps. After each one the state is visible to the rest of the system: for four steps the order is PENDING, and for the last two of them the stock is already reserved and the card already charged. That's the lack of isolation; other readers see these intermediate states.
Saga 2: book courier throws no courier in area. The orchestrator walks done backwards: refund the card (charged 25 → 0), release the stock (9 → 10), cancel the order.
The end state is consistent again (stock 10, nothing charged), but it isn't "as if nothing happened": the order exists with status CANCELLED, and in a real payment system the charge and the refund are two ledger entries the customer can see. A compensation is a new business action, not a database rollback.
In production the orchestrator's progress lives in a durable store (or a workflow engine such as Temporal or AWS Step Functions), so a crash mid-saga resumes where it stopped. That means a step or a compensation can run twice, so each must be idempotent, and compensations must be retried until they succeed: "refund failed" can't be the end of the story.

	Orchestration	Choreography
How	a coordinator service tells each service what to do next	each service reacts to the previous service's event
Good at	complex flows, visibility ("where is order 42?"), timeouts	few steps, loose coupling, no central component
Watch out for	the orchestrator becoming a god service	the flow being spread over many services; cyclic event chains
Typical	payments, travel bookings, onboarding flows	"order placed → send email, update analytics"

AdvancedMaking sagas safe in practice

Order the steps by how hard they are to undo. Put the steps most likely to fail first (validation, reservations), and the hard-to-reverse ones last (charging a card, sending an email, shipping). The step after which the saga can only go forward is called the pivot.
Use semantic locks for isolation: the PENDING status tells everyone else the order isn't final, so the UI shows "processing" and other workflows don't act on it yet.
Reserve, don't take: stock is held with a reservation that expires, payments are authorised before they're captured, so a failed saga has less to undo.
Make every step idempotent with a saga id plus step name as the key, because the orchestrator will retry after timeouts (see Idempotency and exactly-once).

AdvancedTransactional outbox versus the dual write

The outbox: publishing an event without the dual write

Sagas and event-driven designs depend on "save the change and publish the event". Doing those as two separate operations is the dual-write problem: if the process dies between the database commit and the publish, the order exists but nobody hears about it; publish first and the database commit can fail, and you've announced an order that doesn't exist. The transactional outbox writes the event as a row in an outbox table in the same transaction as the business change. A relay (a poller, or change data capture such as Debezium reading the database log) publishes outbox rows and marks them sent.

The database transaction makes "order saved" and "event recorded" one fact; the relay turns that into "event delivered at least once".

The model saves 1,000 orders both ways, with a seeded 3% chance of a crash at each crash point:

outbox.mjs

// 1,000 orders. Each must end up as a row in the orders DB AND an "OrderPlaced" event on the broker.
// Crashes are injected at random points (seeded), then we count what went wrong.
function mulberry32(seed) {
  return () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const crash = (rand) => rand() < 0.03;          // 3% chance of dying at any given point

function dualWrite(rand) {
  const db = new Set(), broker = [];
  for (let id = 1; id <= 1000; id++) {
    db.add(id);                                  // COMMIT the order
    if (crash(rand)) continue;                   // process dies here: the event is never sent
    broker.push(id);                             // publish
  }
  return { db, broker };
}

function outbox(rand) {
  const db = new Set(), outboxTable = new Map(), broker = [];
  for (let id = 1; id <= 1000; id++) {
    db.add(id); outboxTable.set(id, "NEW");       // one transaction: order row + outbox row, or neither
  }
  // The relay polls the outbox. It can die after publishing but before marking the row SENT.
  while ([...outboxTable.values()].includes("NEW")) {
    for (const [id, status] of outboxTable) {
      if (status !== "NEW") continue;
      broker.push(id);                           // publish
      if (crash(rand)) break;                    // relay restarts; this row is still NEW -> sent again
      outboxTable.set(id, "SENT");
    }
  }
  return { db, broker };
}

function report(label, { db, broker }) {
  const delivered = new Set(broker);
  const lost = [...db].filter((id) => !delivered.has(id)).length;
  const duplicates = broker.length - delivered.size;
  console.log(`${label.padEnd(11)} orders ${db.size}  events ${String(broker.length).padStart(4)}  lost ${String(lost).padStart(2)}  duplicates ${duplicates}`);
}
report("dual write", dualWrite(mulberry32(5)));
const result = outbox(mulberry32(5));
report("outbox", result);
const processed = new Set();                     // consumer side: dedup by event id
let applied = 0;
for (const id of result.broker) if (!processed.has(id)) { processed.add(id); applied++; }
console.log(`consumer with dedup applies ${applied} events, once each`);

Result

dual write  orders 1000  events  964  lost 36  duplicates 0
outbox      orders 1000  events 1038  lost  0  duplicates 38
consumer with dedup applies 1000 events, once each

What’s happening

Dual write: the order is committed, then the process may die (3%) before broker.push. 36 of 1,000 orders were saved with no event, so the stock service, the email and the analytics never heard of them. Nothing retries, because nothing remembers the event was owed.
Outbox: the order row and the outbox row go into one transaction, so they exist together or not at all. Every order has a NEW outbox row the relay will eventually publish: 0 lost.
The relay can die after publishing and before marking the row SENT (3% again). On restart the row is still NEW, so it's published again: 38 duplicates. The outbox trades "maybe never" for "at least once", which is the right trade, because duplicates can be detected and lost events can't.
The consumer keeps the ids it has processed and skips repeats, so it applies 1,000 events, once each. Outbox on the producer side plus an idempotent consumer is the standard way to get effectively-once processing between services. The Node.js course implements the same pattern with Kafka in depth; at the design level, the picture above is what to draw.

AdvancedInterview: saga, outbox and why not 2PC

What to say in the interview

For any operation that spans services, state the pattern and why: "the order flow is an orchestrated saga: reserve stock, authorise payment, create shipment, then capture payment; each step is a local transaction with an idempotent compensation, the orchestrator's state is durable so it resumes after a crash, and each service publishes its events through an outbox". Mention 2PC to say why you're not using it (blocking, couples availability) unless the data lives in one database that offers it. The payment flow is worked through in Design a payment system.

How do you keep an order, its payment and its stock consistent across three services?

"Not with a distributed lock or 2PC between the services: 2PC blocks everyone if the coordinator dies after the votes, and it ties the availability of all three services together. I'd use a saga. The order service creates the order as PENDING, then an orchestrator asks stock to reserve, payments to authorise, and finally captures the payment and marks the order CONFIRMED. If any step fails, it runs the compensations backwards: void the authorisation, release the reservation, cancel the order. Each step is idempotent, keyed by the order id and step, because the orchestrator retries. Each service publishes its events with a transactional outbox so a crash can't lose them, and consumers dedupe by event id. The trade-off is isolation: other parts of the system can see the PENDING order, so the UI shows it as processing."

Which step goes last?

A saga for a hotel booking has four steps: send the confirmation email, charge the card, hold the room (expires in 15 minutes), and check the guest's loyalty status. In what order would you run them, and why?

Show answer

Check loyalty status → hold the room → charge the card → send the email. Order the steps from "most likely to fail and easiest to undo" to "hardest to undo".

What’s happening

Checking loyalty status is a read: it changes nothing, needs no compensation, and might reject the booking (wrong rate), so it goes first.
Holding the room can fail (sold out) and is cheap to undo: release the hold, or simply let it expire after 15 minutes if the compensation itself fails.
Charging the card is the pivot: once it succeeds, the saga should only go forward. Its compensation (a refund) works but is visible to the customer and may cost a fee, so it comes after everything that's likely to fail.
The email can't be undone at all, so it goes last, after the booking is certain. Sent first, a later failure would need an embarrassing "please ignore our confirmation" email.
If the charge fails, the only compensation needed is releasing the room hold, which is the cheapest possible failure path. The order of steps is a design decision in its own right, and saying why is part of the answer.

#Idempotency and exactly-once

Added

Every message or request between machines is delivered under one of three promises. At-most-once: send it and don't retry; nothing is duplicated, but some messages are lost. At-least-once: retry until acknowledged; nothing is lost, but some messages arrive twice, because an ack can be lost after the work was done. Exactly-once delivery would be the dream, and over an unreliable network it isn't achievable in general: the sender can never be sure whether the receiver acted on a message whose ack it didn't get (this is the "two generals" problem). What real systems deliver is effectively-once processing: at-least-once delivery plus a receiver that makes duplicates harmless.

A receiver makes duplicates harmless by being idempotent: applying the same message twice has the same effect as applying it once. Some operations are naturally idempotent ("set the email to x", "delete order 42"); others aren't ("add $10", "send an email", "create an order") and need a deduplication key: a unique id for the intent, recorded when the effect is applied, so a repeat is recognised and skipped.

The mental model: a lift call button. Pressing it five times doesn't summon five lifts; the button records "a lift is coming" and further presses change nothing. A "toggle the light" button is the opposite: press it twice and you're back in the dark. Your job in a design is to turn every toggle-style operation that can be retried into a lift-button one.

The model below delivers 10,000 "credit this account" messages at least once: each processing attempt may crash before doing anything (4%), crash after its first step (4%), or finish but lose its ack (4%), and every one of those causes a redelivery. Four consumers handle the same seeded sequence of failures.

idempotent-consumer.mjs

// 10,000 "credit account" messages, delivered at least once: if the consumer crashes or its ack is lost,
// the broker delivers the message again. Crash points are seeded, so every run is identical.
function mulberry32(seed) {
  return () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

// Each consumer is a list of steps. A crash can happen after any step, or the ack can be lost at the end.
const consumers = {
  "naive":                ["apply"],
  "apply, then record id": ["apply", "record"],
  "record id, then apply": ["record", "apply"],
  "apply + record in 1 tx": ["apply+record"],
};

for (const [label, steps] of Object.entries(consumers)) {
  const rand = mulberry32(99);
  const appliedCount = new Map();               // message id -> times its credit was applied
  const processed = new Set();                  // the dedup table
  let deliveries = 0;
  for (let id = 1; id <= 10_000; id++) {
    let acked = false;
    while (!acked) {
      deliveries++;
      if (label !== "naive" && processed.has(id)) { acked = true; break; } // duplicate: skip, just ack
      const r = rand();
      const crashAfter = r < 0.04 ? 0 : r < 0.08 ? 1 : r < 0.12 ? steps.length : Infinity; // 0 = before step 1
      for (let s = 0; s < steps.length && s < crashAfter; s++) {
        if (steps[s].includes("apply")) appliedCount.set(id, (appliedCount.get(id) ?? 0) + 1);
        if (steps[s].includes("record")) processed.add(id);
      }
      acked = crashAfter === Infinity;          // only a clean run gets its ack through
    }
  }
  const counts = [...Array(10_000).keys()].map((i) => appliedCount.get(i + 1) ?? 0);
  const twice = counts.filter((c) => c > 1).length, never = counts.filter((c) => c === 0).length;
  console.log(`${label.padEnd(23)} deliveries ${deliveries}  applied twice+ ${String(twice).padStart(4)}  never ${String(never).padStart(3)}`);
}

Result

naive                   deliveries 11423  applied twice+  876  never   0
apply, then record id   deliveries 11349  applied twice+  438  never   0
record id, then apply   deliveries 11291  applied twice+    0  never 430
apply + record in 1 tx  deliveries 11291  applied twice+    0  never   0

What’s happening

All four need between 11,291 and 11,423 deliveries for 10,000 messages: the 12% failure rate per attempt, plus failures on the retries. (The deduplicating consumers need slightly fewer because a duplicate that's skipped is acknowledged without another chance to crash.) That's normal at-least-once behaviour; the question is only what each consumer does with the repeats.
Naive just applies the credit. Every time the work was done but the ack didn't get through, the redelivery applies it again: 876 accounts credited twice or more. That's real money.
Apply, then record the id: duplicates that arrive after the id was recorded are skipped, but a crash between applying the credit and recording the id leaves no trace that it was applied, so the redelivery applies it again: 438 doubles, half the naive number.
Record the id, then apply: now a crash between the two steps leaves an id that says "done" for a credit that never happened. The redelivery is skipped as a duplicate: 430 credits lost. Ordering the steps only chooses which way you're wrong.
Apply and record in one transaction: the credit and the dedup row are committed together or not at all, so there's no in-between state for a crash to expose. 0 doubles, 0 lost. This is the whole technique: the dedup record must be stored atomically with the effect, in the same database transaction (or as a conditional write on the same item).

AdvancedWays to make an operation idempotent

Operation	Idempotent as is?	How to make it safe to retry
`SET email = 'x'` / `PUT /users/7` with the full resource	yes	nothing to do (but watch out for an old retry arriving after a newer write: add a version check)
`DELETE /orders/42`	yes, for the state (the second call may return 404)	treat "already gone" as success
`balance += 10`	no	store the message id with the change in one transaction; or turn it into an event row with a unique id
`POST /orders` (create)	no	the client sends an `Idempotency-Key`; the server stores key → result and replays the result
Insert a ledger entry	no	a unique constraint on (transaction id), and treat the duplicate-key error as "already done"
Send an email or push	no	check for a "sent for event X" record, send, then write the record (a crash between sending and recording gives a rare duplicate); or use the provider's idempotency key
Conditional update	yes	`UPDATE … SET status='PAID' WHERE id=42 AND status='PENDING'`: the second time it matches nothing

The API side of this, with a full idempotency-key middleware, is in Idempotency keys for APIs; the messaging side in Delivery guarantees and ordering.

AdvancedSizing the dedup window

How long to remember, and what it costs

A dedup table only has to remember a key for as long as a duplicate can still arrive. Real systems pick very different windows: Amazon SQS FIFO queues drop a message with the same deduplication id sent within a 5-minute interval (SQS documentation, October 2026); Stripe may prune an idempotency key once it's at least 24 hours old, after which reusing it creates a new request (Stripe API docs, 2026); a Kafka consumer that can be rewound may see any message still on the topic, and Kafka's default retention is 168 hours, 7 days (log.retention.hours). The size follows directly.

dedup-window.mjs

// How big is the dedup table? Assumptions (state them out loud in the interview):
const msgsPerSecond = 2_000;       // average consumed rate
const bytesPerKey = 16 + 8 + 40;   // 16-byte UUID + 8-byte timestamp + ~40 bytes index/row overhead (rule of thumb)
const windows = { "5 minutes (SQS FIFO-style)": 300, "24 hours (Stripe-style keys)": 86_400, "7 days (Kafka default retention)": 604_800 };

for (const [label, seconds] of Object.entries(windows)) {
  const keys = msgsPerSecond * seconds;
  const gb = (keys * bytesPerKey) / 1e9;
  console.log(`${label.padEnd(32)} ${keys.toLocaleString("en-US").padStart(13)} keys  ${gb.toFixed(gb < 1 ? 3 : 1).padStart(6)} GB`);
}

Result

5 minutes (SQS FIFO-style)             600,000 keys   0.038 GB
24 hours (Stripe-style keys)       172,800,000 keys    11.1 GB
7 days (Kafka default retention) 1,209,600,000 keys    77.4 GB

What’s happening

The assumptions are written as constants: 2,000 messages per second, and 64 bytes per remembered key (a 16-byte UUID, an 8-byte timestamp, and about 40 bytes of index and row overhead, a rule of thumb rather than a measurement for a particular database).
A 5-minute window is 600,000 keys, about 38 MB: fits in memory, in Redis or even in the process.
A 24-hour window is 172.8 million keys, about 11 GB: a database table with a TTL index or a Redis cluster, and a cleanup job.
A 7-day window is 1.2 billion keys and about 77 GB, which is why consumers that can replay a whole topic usually dedupe with a business key that the target table already has a unique index on (the order id, the payment id), instead of a separate table of message ids.
The design rule: choose the window from the longest time a duplicate can arrive (retry policy, redelivery timeout, replay), then size the store. Say both numbers out loud.

AdvancedWhat "exactly-once" means in products

Kafka: the idempotent producer (the default since Kafka 3.0, with acks=all, per KIP-679 and the 3.0 upgrade notes; a bug left it off in 3.0.0 and 3.1.0 unless set explicitly) stops a producer retry from writing a duplicate to a partition. Kafka transactions extend that to read-process-write: consume, produce results and commit offsets atomically, all within Kafka. Once your consumer writes to a database, sends an email or calls an API, you're back to needing an idempotent effect.
SQS: standard queues are at-least-once; FIFO queues add deduplication within the 5-minute interval and ordering within a message group. A FIFO queue doesn't make your consumer's database write atomic with its delete of the message, so the consumer still has to be idempotent.
Stream processors (Flink, Kafka Streams) give exactly-once state updates through checkpoints and transactions; their sinks must be transactional or idempotent for the guarantee to reach the outside world.

AdvancedInterview: explaining the dedup key

What to say in the interview

When a design has a queue or a retried call, say "at-least-once delivery, idempotent consumers" and then say exactly how: which key, where it's stored, that it's written in the same transaction as the effect, and how long it's kept. That's the difference between naming the pattern and understanding it.

How do you guarantee each payment event is processed exactly once?

"Exactly-once delivery isn't achievable over a network, so I'd design for at-least-once delivery and make processing idempotent. Each event carries an event id generated once by the producer, written in its outbox row. The consumer, in a single database transaction, inserts that id into a processed-events table with a unique constraint and applies the ledger entry. If the event comes again, the insert hits the constraint, so the consumer skips the work and acknowledges. Checking the id and applying the effect in separate steps isn't enough: a crash between them either double-applies or loses the event. I'd keep the ids at least as long as the broker can redeliver or we might replay, or dedupe on the payment id that the ledger already has a unique index on."

Safe to retry?

Which of these can be retried blindly after a timeout: (a) PUT /users/7 with the full user, (b) POST /transfers moving $50, (c) UPDATE stock SET qty = qty - 1 WHERE sku = 'A', (d) UPDATE orders SET status = 'SHIPPED' WHERE id = 9 AND status = 'PACKED'?

Show answer

(a) and (d) are safe to retry. (b) and (c) are not; they need a dedup key or a rewrite.

What’s happening

(a) PUT with the full resource sets the same final state however many times it runs, so it's idempotent. The only catch is an old retry overwriting a newer change, which a version check (If-Match) prevents.
(b) Each POST /transfers creates a new transfer, so a retry after a lost reply moves another $50. It needs an Idempotency-Key that the server stores with the transfer and checks first.
(c) qty = qty - 1 subtracts again on every run, so two runs reserve two units. Rewrite it as a reservation row with a unique id (or carry a dedup key), so the second run is recognised.
(d) The condition status = 'PACKED' is true only the first time; the retry matches zero rows and changes nothing. Conditional updates are one of the cheapest ways to get idempotency, and the "0 rows updated" can be treated as "already done".

#Conflict resolution: last-write-wins and CRDTs

Added

When more than one replica accepts writes for the same data (multi-leader replication across regions, a leaderless store, a phone editing offline), two replicas can change the same thing at the same time without knowing about each other. When they sync, something has to decide the result. There are three broad answers: last-write-wins (keep the write with the highest timestamp and drop the other), keep both and let the application or user merge (the siblings in version vectors), or use a data type whose merge can't lose anything: a CRDT.

A CRDT (conflict-free replicated data type) is a data structure designed so that replicas can update independently and then merge in any order, any number of times, and always end up identical. The merge function has to be commutative (A merge B = B merge A), associative (grouping doesn't matter) and idempotent (merging the same state twice changes nothing). Those three properties are exactly what an unreliable network needs: messages arrive out of order, in different groupings, and more than once. (That describes state-based CRDTs, which ship their whole state or deltas of it, as in the model below. The other family, operation-based CRDTs, ships individual operations instead and needs the transport to deliver each one exactly once, in causal order.)

The mental model for the simplest one, the G-counter (grow-only counter): a tally sheet with one column per region. Each region only ever adds marks in its own column. To merge two copies of the sheet, take the larger number in each column (a column only grows, so the larger one includes everything the smaller one had). The total is the sum of the columns. No mark is counted twice, and none is lost, whatever order the sheets meet in.

Last-write-wins is the default in many stores (Cassandra resolves concurrent writes to a cell by timestamp, for instance) because it's simple and needs no extra metadata. It's correct when the new value replaces the old one and losing a concurrent write is acceptable, like a display name or a "last seen" time. It's wrong for anything that accumulates, and it inherits every clock problem from Why distributed systems are hard.

The model counts likes on one post in three regions that can't talk to each other, with a PN-counter (two G-counters, one for likes and one for unlikes), then delivers the three regions' states to a fresh replica in every possible order, and once with duplicates.

crdt-counters.mjs

// G-counter: one slot per replica, each replica only increments its own slot. Merge = max per slot.
const gInc = (g, replica, n = 1) => ({ ...g, [replica]: (g[replica] ?? 0) + n });
const gMerge = (a, b) => {
  const out = { ...a };
  for (const [r, n] of Object.entries(b)) out[r] = Math.max(out[r] ?? 0, n);
  return out;
};
const gValue = (g) => Object.values(g).reduce((s, n) => s + n, 0);

// PN-counter: two G-counters, one for increments (P) and one for decrements (N). Value = P - N.
const pn = () => ({ P: {}, N: {} });
const pnAdd = (c, replica, n) => (n >= 0 ? { ...c, P: gInc(c.P, replica, n) } : { ...c, N: gInc(c.N, replica, -n) });
const pnMerge = (a, b) => ({ P: gMerge(a.P, b.P), N: gMerge(a.N, b.N) });
const pnValue = (c) => gValue(c.P) - gValue(c.N);

// Likes on one post, counted in three regions while they can't talk to each other.
let us = pn(), eu = pn(), asia = pn();
us = pnAdd(pnAdd(us, "us", 5), "us", -1);   // 5 likes, 1 unlike
eu = pnAdd(eu, "eu", 3);                    // 3 likes
asia = pnAdd(pnAdd(asia, "asia", 2), "asia", -2);
console.log("local values:", pnValue(us), pnValue(eu), pnValue(asia));

// Deliver the three states to a fresh replica in every possible order, and once with a duplicate.
const states = { us, eu, asia };
const orders = [["us", "eu", "asia"], ["us", "asia", "eu"], ["eu", "us", "asia"], ["eu", "asia", "us"],
  ["asia", "us", "eu"], ["asia", "eu", "us"], ["eu", "us", "eu", "asia", "us"]];
for (const order of orders) {
  const merged = order.reduce((acc, name) => pnMerge(acc, states[name]), pn());
  console.log(order.join(" + ").padEnd(26), "->", pnValue(merged), JSON.stringify(merged));
}

// A naive merge that adds the other side's total is not idempotent: a repeated message counts twice.
const naive = (order) => order.reduce((sum, name) => sum + pnValue(states[name]), 0);
console.log("naive sum, each once:", naive(["us", "eu", "asia"]), "  with duplicates:", naive(orders.at(-1)));

Result

local values: 4 3 0
us + eu + asia             -> 7 {"P":{"us":5,"eu":3,"asia":2},"N":{"us":1,"asia":2}}
us + asia + eu             -> 7 {"P":{"us":5,"asia":2,"eu":3},"N":{"us":1,"asia":2}}
eu + us + asia             -> 7 {"P":{"eu":3,"us":5,"asia":2},"N":{"us":1,"asia":2}}
eu + asia + us             -> 7 {"P":{"eu":3,"asia":2,"us":5},"N":{"asia":2,"us":1}}
asia + us + eu             -> 7 {"P":{"asia":2,"us":5,"eu":3},"N":{"asia":2,"us":1}}
asia + eu + us             -> 7 {"P":{"asia":2,"eu":3,"us":5},"N":{"asia":2,"us":1}}
eu + us + eu + asia + us   -> 7 {"P":{"eu":3,"us":5,"asia":2},"N":{"us":1,"asia":2}}
naive sum, each once: 7   with duplicates: 14

What’s happening

Each region only touches its own slot: us adds 5 to P.us and 1 to N.us (5 likes, 1 unlike), eu adds 3 to P.eu, asia adds 2 to both P.asia and N.asia. Their local values are 4, 3 and 0: each region sees only its own activity.
pnMerge merges the P maps and the N maps separately with gMerge, which takes the maximum per slot. Every slot is written by one region only and only grows, so the maximum is always that region's latest count.
All six orders give 7 (10 likes − 3 unlikes) and the same P and N maps: the key order in the printed JSON differs, but the contents are identical. That's commutativity and associativity in practice.
The last row merges eu and us twice. Taking the max of 3 and 3 is still 3, so the result is still 7: merging is idempotent, so redelivered sync messages are harmless and no dedup table is needed.
The naive merge that adds each received total gets 7 when every state arrives exactly once, and 14 when two arrive twice. That's why CRDT merges use max over per-replica slots rather than sums of totals: the network will deliver duplicates.
Decrements need the separate N counter because max-merge only works for values that grow. A single slot that went 5 → 4 would lose to a stale copy still saying 5. Keeping unlikes as their own grow-only count turns a decrement into an increment of something else.

AdvancedThe same likes under last-write-wins

For contrast, the three regions store the count as a plain number: each reads the current value (10), adds its own likes, and writes the new total with its own timestamp.

lww-counter.mjs

// The same likes, but stored as a plain number under last-write-wins (a timestamp per write).
// Each region reads the current value, adds its likes, and writes the new total with its own clock.
const lwwMerge = (a, b) => (b.ts > a.ts || (b.ts === a.ts && b.region > a.region) ? b : a); // tie: region name

const start = { value: 10, ts: 100, region: "-" };
const us   = { value: start.value + 4, ts: 205, region: "us" };   // +5 likes -1 unlike, written at t=205
const eu   = { value: start.value + 3, ts: 207, region: "eu" };   // +3 likes, written at t=207
const asia = { value: start.value + 0, ts: 209, region: "asia" }; // +2 -2, written at t=209

const merged = [us, eu, asia].reduce(lwwMerge, start);
console.log("LWW keeps:", merged, "-> value", merged.value, "but 10 + 4 + 3 + 0 =", 10 + 4 + 3 + 0);

// Where LWW is fine: a field whose new value replaces the old one, like a display name.
const names = [{ value: "Rohit", ts: 300, region: "us" }, { value: "Rohit V.", ts: 301, region: "eu" }];
console.log("display name:", names.reduce(lwwMerge).value);

Result

LWW keeps: { value: 10, ts: 209, region: 'asia' } -> value 10 but 10 + 4 + 3 + 0 = 17
display name: Rohit V.

What’s happening

All three regions started from 10 and wrote 14, 13 and 10 respectively, each with its own timestamp. Each write is a full replacement of the value.
lwwMerge keeps the highest timestamp, so Asia's write at t=209 wins and the count is 10. The US's and Europe's 7 net likes are silently gone; the correct total is 17.
Nothing errored, and every replica agrees on 10 after merging. LWW converges; it just converges on a value that throws away concurrent work. Convergence alone isn't correctness.
With clock skew it's worse: if Asia's clock were a few milliseconds behind, a different region's value would win, so the answer depends on which machine's clock was off.
For the display name, LWW is right: "Rohit V." replaces "Rohit", and if two devices rename at once, keeping one is the expected behaviour. Choose the conflict rule per field, the same way you chose CP or AP per operation.

AdvancedA catalogue of common CRDTs

A small catalogue

CRDT	State	Merge	Good for
G-counter	one count per replica	max per replica	views, likes without unlikes
PN-counter	two G-counters	merge both	likes with unlikes, votes, stock deltas (no floor, see below)
LWW register	value + timestamp	keep the higher timestamp	names, settings, "last seen"
Multi-value register	all concurrent values	keep the ones not dominated (version vectors)	carts, documents where the user picks
G-set / 2P-set	added (and removed) elements	union	tags; 2P-set elements can't be re-added after removal
OR-set (add-wins)	elements tagged with unique add ids	union of adds minus observed removes	carts, membership, where add and remove may race
Sequence CRDTs (RGA, Yjs, Automerge)	characters with unique ids and positions	interleave by id	collaborative text and offline-first apps

Where you'll meet them: Redis Software's Active-Active databases use CRDTs so the same Redis data types and commands work while concurrent writes to a key in different regions are resolved automatically (Redis documentation, 2026; it's an enterprise feature, not open-source Redis). Riak exposes counters, sets and maps as data types. Yjs and Automerge power collaborative editors and local-first apps; that case is in Design a collaborative document editor.

AdvancedInterview: conflict rules per data type

What to say in the interview

Bring CRDTs up when a design writes in several regions at once or works offline, and pair each data type with its conflict rule: "likes are a PN-counter per post, merged per region; profile fields are last-write-wins with hybrid logical clock timestamps; the cart is an add-wins set; and stock is not a CRDT, it goes through the home region's primary because it has to stay non-negative". That shows you know where the free lunch ends.

We run active-active in three regions. How do we count likes on a post?

"Each region accepts likes locally so users get low latency and likes keep working during a partition. I'd store the count as a PN-counter: per post, one increment slot and one decrement slot per region. A region only updates its own slots, regions ship their state or deltas to each other asynchronously, and merging takes the max per slot, so it doesn't matter in what order or how many times updates arrive. The displayed count is the sum, which can be a few seconds behind across regions, and that's fine for likes. I wouldn't use last-write-wins on a plain number: concurrent increments would overwrite each other. And to stop someone liking twice, the like itself is a set membership keyed by user and post, an add-wins set or simply a unique row in the user's home region, with the counter derived from it."

Why max and not sum?

Two replicas of a G-counter hold { A: 4, B: 2 } and { A: 3, B: 5 }. What does merging them give, and why would adding the slots together be wrong?

Show answer

The merge is { A: 4, B: 5 }, value 9. Adding slots would give { A: 7, B: 7 } = 14, double-counting increments both replicas had already seen.

What’s happening

Slot A is only ever incremented by replica A. The first copy says A has counted 4; the second copy has an older view of A's slot, 3. Both are reports of the same, single tally at different times.
The newest report of a grow-only number is the largest, so max(4, 3) = 4 is A's real count. Adding them would count A's first 3 increments twice.
The same for B: max(2, 5) = 5.
The value is 4 + 5 = 9. Merging this result with either input again gives 9 again (idempotent), and merging in the other order also gives 9 (commutative), which is what makes it safe over a network that duplicates and reorders messages.