Learnings

System design, part 4 of 12

Distributed Systems Patterns

The patterns that keep a multi-machine design correct when machines crash, messages are lost and clocks disagree. Each one is given as the problem, a diagram, how it works at interview depth, what it costs, how it fails and where it shows up. This is the area where a senior answer names the guarantee it needs and the price it pays, instead of drawing a box labelled "queue".

Map of the page

PartQuestion it answersPatterns
1. Why distributed is hardWhat can go wrong that cannot on one machine?Failure model, fallacies, partial failure, impossibility results
2. Time and orderWhich event happened first?Lamport, vector and hybrid clocks, sequence numbers
3. AgreementHow do nodes agree on one leader or one log?Leases, fencing, Raft, quorums, gossip
4. Distributed transactionsHow do two systems change together?2PC, sagas, outbox, TCC
5. Messaging correctnessWhat happens when a message arrives twice, late or never?Idempotency, inbox, DLQ, retries, deadlines
6. Staying upHow does one slow dependency not take everything down?Circuit breaker, bulkhead, shedding, backpressure, hedging
7. Coordination patternsHow does exactly one worker do a thing?Locks, work assignment, singleton jobs, counters, IDs
8. Consistency in practiceWhat may a reader see, and when?Linearizability, serializability, convergence, read-your-writes

Senior signal: for every arrow in your design, be able to answer three questions: what if this call times out, what if it runs twice, and what if the two ends disagree about the order. Most of this page is the vocabulary for those answers.

Why distributed is hard

Part 1 of 8 · the failure model you design against

On one machine a call either returns or the whole process dies. Across machines a third outcome appears: you do not know. Everything else on this page is a way of living with that.

The failure model

Why distributed is hard

State the failures you tolerate before you pick a protocol. A design is only "correct" relative to a failure model.

FailureWhat happensTypical causeStandard defence
Crash-stopNode halts and never returnsHardware loss, terminated instanceReplication, failover
Crash-recoveryNode halts, later returns with its disk state but not its memoryRestart, deploy, OOM killDurable log (fsync before ack), rejoin protocol
OmissionA message is never sent or never receivedFull queue, dropped packet, overloaded receiverTimeouts, retries, idempotency
Network partitionTwo groups of healthy nodes cannot talk to each otherSwitch or link failure, misconfiguration, zone isolationMajority quorums, fencing
Timing ("slow is the new down")Node responds, but far too late; often partially (one disk, one endpoint)GC pause, noisy neighbour, degraded disk, overloadDeadlines, circuit breakers, hedging, outlier ejection
ByzantineNode sends arbitrary or malicious messagesCompromise, bugs that corrupt messagesOut of scope here: needs 3f+1 nodes and signatures (blockchains, some aerospace)
  • Datacentre designs assume crash-recovery plus omission plus partitions, with checksums to turn data corruption into a detectable crash-like fault.
  • Slow nodes are harder than dead ones: a dead node is removed by health checks, a slow one keeps receiving traffic and holds its callers' threads.

Interview tip: say "I am assuming non-Byzantine failures: nodes may crash, pause or be partitioned, but do not lie". It shows you know the assumption exists.

The fallacies of distributed computing

Why distributed is hard

Eight assumptions (Deutsch and others at Sun) that are false in production. Each one maps to a design rule.

False assumptionDesign consequence
The network is reliableEvery remote call needs a timeout, a retry policy and an idempotent receiver
Latency is zeroCount round trips; batch, cache and co-locate chatty services; no remote calls in loops
Bandwidth is infinitePaginate, compress, send deltas, keep payloads small
The network is secureAuthenticate and encrypt between services (mTLS), not only at the edge
Topology does not changeService discovery and health checks, never hard-coded addresses
There is one administratorVersioned, backward-compatible APIs; other teams deploy on their own schedule
Transport cost is zeroSerialisation costs CPU and cross-zone or cross-region traffic costs money
The network is homogeneousStandard protocols, explicit schemas, expect mixed versions during rollouts

Partial failure and timeouts

Why distributed is hard

A timeout tells you only that no reply arrived in time. The request may never have arrived, may be still running, or may have completed with the reply lost. The caller cannot tell these apart.

Three different server states, one observation at the client. In case 3 a blind retry debits twice.
  • A timeout is an unknown outcome, not a failure. The safe reactions are: retry an idempotent operation, or query the outcome, or surface "pending" to the user.
  • A failure detector built on timeouts is necessarily imperfect: short timeouts declare healthy nodes dead (false positives, needless failovers), long ones leave dead nodes in rotation.
  • Hence the two recurring tools: idempotency, so retrying is safe, and fencing, so a node wrongly declared dead cannot do damage when it wakes.

Two generals and FLP

Why distributed is hard

Two generals. Two parties that can only talk over a link that may drop messages cannot become certain that they both agreed, however many messages they exchange. Whoever sent the last message does not know whether it arrived, and adding an acknowledgement only moves the doubt to the acknowledgement. This is why a sender can never know for sure that a receiver processed a message, and why "exactly-once delivery" is not on offer.

FLP (Fischer, Lynch, Paterson, 1985). In a fully asynchronous system, where there is no bound on message delay or process speed, no deterministic consensus protocol can guarantee that it always terminates if even one process may crash.

  • FLP is about liveness, not safety. Raft and Paxos never decide two different values; what they cannot promise is to decide within bounded time under arbitrary delays.
  • Real systems step around it by assuming partial synchrony: timeouts (with randomisation) make progress very likely once the network behaves for a while.

Senior signal: phrase guarantees as "always safe, live when a majority can communicate in a timely way". That is exactly what consensus systems provide.

Time and order

Part 2 of 8 · deciding what happened first

There is no shared clock. Ordering events across machines needs either logical clocks, which capture causality, or a single sequencer, which imposes an order.

Physical clocks

Time and order

Quartz clocks drift, typically by tens of parts per million (10 ppm is about 0.9 s per day; Google's Spanner design assumes a worst case of 200 ppm). NTP corrects this to within roughly a millisecond inside a well-run datacentre and tens of milliseconds or worse over the internet, and may step the clock backwards while doing so. All figures are order of magnitude.

The later write (x = 2) is silently discarded because the earlier one carried a larger timestamp. No error is raised anywhere.
  • Two clocks per machine: time-of-day (can jump, use only for display and coarse TTLs) and monotonic (never goes back, use for durations and timeouts, meaningless across machines).
  • Wall-clock timestamps are fine for logs, metrics and TTLs measured in seconds. They are unsafe for ordering writes, lock expiry decided by two different machines, and "newest wins" conflict resolution.
  • Process pauses (GC, VM migration) make it worse: a thread can read the clock, pause for seconds, then act on the stale reading.

Failure mode: last-write-wins with client or server timestamps loses acknowledged writes under clock skew. If you propose LWW, say what data you are prepared to lose.

Lamport clocks

Time and order

One integer per node. Increment it on every local event and send; on receive set it to max(local, received) + 1. Attach it to every message.

Timestamps rise along every message path. C's first event (L = 1) and A's send (L = 2) are unrelated, yet their numbers still compare.
Tells youDoes not tell you
If a happened before b (causally), then L(a) < L(b)L(a) < L(b) does not imply a happened before b: they may be concurrent
A total order when ties are broken by node id: (L, node)Whether two events are concurrent, or how far apart they were in real time

Cost: 8 bytes per message. Use it when you need some deterministic order consistent with causality (ordering log entries, tie-breaking); Raft terms and Paxos ballot numbers are the same idea.

Vector clocks

Time and order

One counter per node, carried as a vector. Increment your own slot on each event; on receive take the element-wise maximum, then increment your own slot.

Vectors are written as slots A B C. a1 (1 0 0) and c1 (0 0 1): neither is less than or equal in every slot, so they are concurrent. a1 is below 2 2 2 in every slot, so a1 happened before C's last event.
Tells youDoes not tell you / costs
Exactly whether a happened before b, b before a, or they are concurrentWhich concurrent write should win: that is an application merge or a sibling returned to the client
Enough to detect conflicting updates without losing eitherSize grows with the number of participants; needs pruning, which can produce false conflicts
  • Where it shows up: Dynamo-style stores track version vectors (a close relative, one entry per replica rather than per client) to detect concurrent writes to a key. The original Dynamo paper returns conflicting versions to the application to merge.
  • Trade-off: Lamport is small and gives an order but hides concurrency; vectors reveal concurrency but cost O(nodes) per value.

Hybrid clocks and TrueTime

Time and order

Hybrid logical clock (HLC). A timestamp of (physical time, logical counter) that advances like a Lamport clock but stays within the clock-skew bound of wall time, so it is fixed size, respects causality across messages, and is still meaningful to a human. Databases such as CockroachDB, YugabyteDB and MongoDB use HLC-style timestamps for versioning and snapshot reads.

TrueTime (Spanner). The clock API returns an interval [earliest, latest] that is guaranteed to contain the true time, with the width kept to a few milliseconds by GPS and atomic clock references in each datacentre. Spanner waits out that uncertainty before a commit becomes visible ("commit wait"), so if transaction T1 finishes before T2 starts, T1's timestamp is smaller: timestamp order matches real-time order.

ClockSizeRespects causalityDetects concurrencyRelated to real time
Wall clock (NTP)8 bytesNoNoApproximately, unbounded error in the worst case
Lamport8 bytesYesNoNo
VectorO(nodes)YesYesNo
HLC8 to 12 bytesYesNoYes, within the assumed skew bound
TrueTime-style interval2 timestampsYes, by waiting out uncertaintyNoYes, with an explicit error bound

Trade-off: without bounded-uncertainty clocks, an HLC database must handle the skew window some other way (for example restarting a read that hits an uncertain timestamp, or refusing to run when skew exceeds a configured maximum). Exact behaviour is implementation-dependent.

Total order vs partial order

Time and order

Partial orderTotal order
DefinitionSome pairs of events are incomparable (concurrent)Every pair is ordered, and every node sees the same order
SourceCausality: happens-before, vector clocksA single sequencer: one leader's log, one partition, a consensus log
CostNo coordination; conflicts must be mergedEvery write goes through one place; throughput and availability of that place bound the system
Use whenOperations commute or can be merged (likes, carts, presence)Order changes the outcome (ledger entries, uniqueness, state machines)
  • Delivering the same messages in the same order to all nodes (total order broadcast) is equivalent in power to consensus. If a design needs a global order, it needs a consensus-backed log or a single leader somewhere.
  • The practical compromise is total order per key: order within a partition, none across partitions. See ordering guarantees and partition keys.

Idempotent sequence numbers

Time and order

On a single stream you do not need a clock at all. The sender numbers its messages (sender id, sequence number) and the receiver remembers the highest number applied per sender. That gives order, duplicate detection and gap detection with one integer of state per sender.

A retry is recognised by its number, not by its content. A gap is visible immediately.
  • Where it shows up: TCP sequence numbers; Kafka's idempotent producer (producer id, epoch and a per-partition sequence number, with the broker rejecting duplicates and out-of-sequence batches); replication streams keyed by log offset.
  • Requirement: the receiver must store "last applied sequence" atomically with the effect, otherwise a crash between the two reintroduces the duplicate.
  • Limit: it covers one sender-receiver stream. For arbitrary clients retrying arbitrary requests, use idempotency keys.

Agreement

Part 3 of 8 · one leader, one log, one view of who is alive

Many designs reduce to "exactly one node must be in charge of X". Getting that right under partitions is consensus; getting it cheaply and approximately is gossip.

Leader election and leases

Agreement

Why a leader: a single writer gives a total order for free, removes write conflicts and makes invariants (uniqueness, balances) easy to check. The cost is that the leader is a throughput ceiling and its failure needs detection and handover.

Lease-based election: a node becomes leader by writing itself into a strongly consistent store with an expiry ("I am leader until T"). It renews well before T (for example every third of the lease). If it stops renewing, another node may take the lease only after it expires.

ChoiceShort lease (1 to 5 s)Long lease (30 s or more)
Failover timeFastSlow: the system is leaderless until expiry
False failoversMore: a GC pause or a network blip loses the leaseFewer
Load on the lease storeHigher renewal rateLower
  • A lease is a timing assumption: it is safe only if clocks advance at roughly the same rate on both sides and the holder notices expiry before acting. Holders should stop work some margin before their local view of the expiry.
  • The lease store itself must be consensus-backed (etcd, ZooKeeper, a database with a compare-and-set on a single row). A lease in an asynchronously replicated store can be granted twice after a failover.

Failure mode: the leader pauses for longer than the lease (stop-the-world GC, VM freeze, swapped-out process), a new leader is elected, then the old one resumes and carries on writing. A lease alone cannot prevent this; the next chapter does.

Fencing tokens

Agreement

Every time the lease or lock is granted, the lock service also returns a number that only ever increases. The holder sends that number with every write, and the resource rejects any write whose number is lower than the highest it has seen.

The stale leader is stopped by the storage layer, not by its own belief about the lease. Safety no longer depends on clocks or pauses.
  • Where the token comes from: a Raft term, a ZooKeeper zxid or znode version, an etcd revision, a database sequence, a leader epoch in Kafka.
  • What it costs: the protected resource must be able to compare and remember tokens, atomically with the write. A plain file system or a third-party API usually cannot, and then the lock is only best-effort.
  • The same idea under other names: epoch numbers, generation numbers, If-Match version checks, STONITH (which fences by powering the old node off instead).

Senior signal: whenever you say "we take a lock" or "the leader does X", follow it with "and the writes carry the epoch so a stale holder is rejected". Interviewers probe exactly this.

Consensus in plain terms

Agreement

Consensus lets a group of nodes agree on a value so that the decision survives crashes and is never contradicted. Run it repeatedly and you get an agreed, ordered log; feed the same log to the same deterministic state machine on every node and you get a replicated database, lock service or config store.

PropertyMeaningKind
AgreementNo two nodes decide different valuesSafety: holds always
ValidityThe decided value was proposed by some nodeSafety
IntegrityA node decides at most onceSafety
TerminationEvery non-faulty node eventually decidesLiveness: only when a majority is up and can communicate in a timely way
  • Use it for: small, critical, low-churn state: who is leader, shard maps, configuration, locks, the metadata of a larger system.
  • What you pay: every write needs a majority round trip and a durable write on each (roughly 1 to 10 ms in one region, an inter-region round trip when the group spans regions), and the group is unavailable for writes without a majority.
  • You almost never implement it. You use etcd, ZooKeeper, a Raft library or a database built on one, and you say so.

Raft: roles and terms

Agreement

Raft keeps a replicated log through a single strong leader. Every node is in one of three roles, and time is divided into numbered terms, each with at most one leader.

Any node that sees a higher term than its own adopts it and becomes a follower. That single rule retires stale leaders.
  • Term: a monotonically increasing number stored durably on each node and sent in every RPC. It is a logical clock and a fencing token: requests carrying an older term are rejected.
  • One vote per term: a node votes for at most one candidate in a given term (the vote is persisted before replying). Since winning needs a majority, two leaders in one term are impossible.
  • Followers are passive: they only answer RPCs. Clients talk to the leader; a follower redirects.
  • Two RPCs carry the whole protocol: RequestVote and AppendEntries (which doubles as the heartbeat when empty).

Raft: log replication and commit

Agreement

The client is answered after a majority (leader included) has the entry on disk. The slowest follower does not delay the write.
  • Consistency check: each AppendEntries names the index and term of the entry just before the new ones. A follower that has no matching entry refuses; the leader steps back one entry at a time (or faster with an optimisation) until they match, then overwrites the follower's conflicting suffix. The leader never rewrites its own log.
  • Commit rule: an entry is committed once it is stored on a majority and it belongs to the leader's current term. Entries from earlier terms are never committed by counting replicas; they become committed indirectly when a current-term entry after them commits.
  • Durability: nodes persist term, vote and log entries before replying, so a committed entry survives any minority of crashes.
  • Client retries: a leader can crash after committing but before replying, so commands should carry a client id and serial number and the state machine should deduplicate.
  • Reads: a leader that has been deposed without knowing it would serve stale data from local state. Linearizable reads therefore go through the log, or confirm leadership with a round of heartbeats to a majority first, or rely on a leader lease (which reintroduces a clock assumption).

Raft: leader election

Agreement

Node 3 resets its election timer when it grants the vote and again on each heartbeat, so it does not start a competing election.
  • Election timeout: each follower picks a random timeout (the paper suggests 150 to 300 ms; production systems often use around a second) and restarts it on every valid heartbeat. Randomisation makes it likely that one node times out first and wins before the others start.
  • Split vote: if no candidate reaches a majority, candidates time out, increment the term and try again with fresh random timeouts.
  • Election restriction: a voter refuses a candidate whose log is less up to date than its own (compare the term of the last entry, then the log length). Because a committed entry is on a majority and a winner needs votes from a majority, the new leader always holds every committed entry.
  • Timing requirement for liveness: broadcast time must be much smaller than the election timeout, which must be much smaller than the mean time between failures. Safety does not depend on timing.
  • Common extensions, named in one breath: pre-vote (a partitioned node does not disrupt the cluster with an inflated term when it returns) and membership change one server at a time or through joint consensus.

Raft under a partition

Agreement

Two nodes claim leadership, but in different terms, and only one side can gather a majority. Client 1's write is never acknowledged.
  • Majority side: stops hearing heartbeats, elects a leader in a higher term, keeps serving writes.
  • Minority side: the old leader still accepts requests but can never commit them, so clients time out. A local read on this side can be stale unless reads are confirmed with a majority.
  • On heal: the old leader sees term 4, steps down, and its uncommitted entries are overwritten by the new leader's log. Nothing that was acknowledged to a client is lost, because nothing on the minority side was acknowledged.
  • No majority anywhere (for example a 2 / 2 / 1 split of five): no side can elect a leader and the cluster is unavailable for writes until connectivity returns. This is the CP choice.

Interview tip: the two questions asked most are "can there be two leaders?" (yes, briefly, in different terms; only the newer can commit) and "can a committed write be lost?" (no, given durable storage and at most a minority failed).

Paxos in one paragraph

Agreement

Single-decree Paxos agrees on one value in two phases. A proposer picks a unique, increasing proposal number and asks acceptors to prepare; each acceptor promises to ignore lower numbers and reports any value it has already accepted. If a majority promises, the proposer sends accept with the value of the highest-numbered proposal reported, or its own value if none was, and the value is chosen once a majority accepts. Multi-Paxos repeats this per log slot and keeps a stable leader so the prepare phase is skipped in the common case, which makes it behave much like Raft. The honest summary: Paxos and Raft tolerate the same failures at similar cost; the original Paxos description leaves log management, leader election and membership change to the implementer, so real "Paxos" systems differ from each other, while Raft specifies those parts. In an interview, know the two phases and the majority overlap argument, and do not offer to implement either.

Quorums and why majorities

Agreement

Any two majorities of the same group share at least one node. So a new leader's voters always include someone who saw the last committed decision, and two sides of a partition can never both make progress. To survive f crash failures you need 2f + 1 nodes.

NodesMajorityFailures toleratedComment
110No fault tolerance
220Worse than 1: either node failing stops writes
321The usual minimum; one node per zone
431Same tolerance as 3, slower commits
532Survives one failure during maintenance of another
743Rare: more replicas to wait on per write
  • Even sizes add cost without adding tolerance. Use 3 or 5; scale reads with non-voting learners or followers, not with more voters.
  • Losing a majority permanently means manual recovery with possible data loss. Spread voters across at least three failure domains.
  • Dynamo-style quorums (N replicas, W write acks, R read replies, R + W > N) guarantee that a read set overlaps the latest successful write set. That is not the same as linearizability: concurrent writes, partially failed writes and sloppy quorums can still produce stale or conflicting reads. Details in Data Systems.

Split brain

Agreement

Two nodes each believe they are the leader and both accept writes. The histories diverge, and merging them afterwards is usually manual and lossy (duplicate ids, double spends, overwritten rows).

PreventionHow it worksCost / caveat
Majority quorum for promotionA node may lead only with votes from more than half of a fixed membershipNeeds 3 or more voters; a minority side stops serving writes
Witness / tiebreakerA small third voter (often in a third zone) that holds no dataOne more thing to run; still must be a real voter
Fencing token / epochStorage and followers reject the older epochEvery write path must check it
STONITHPower off or isolate the old primary before promotingNeeds a reliable out-of-band control path
Synchronous replication to a quorumAn isolated primary cannot acknowledge writesWrite latency and availability depend on replicas

Failure mode: a two-node primary and standby pair where the standby promotes itself when it "cannot see" the primary. A partition between them (with both still reachable by clients) gives two primaries. A timeout is never proof of death.

Coordination services

Agreement

ZooKeeper (Zab protocol), etcd and Consul (both Raft) are small, strongly consistent key-value stores with leases or sessions and watches. They exist so that applications do not implement consensus themselves.

Use forMechanism
Leader electionEphemeral sequential znode (lowest wins) or an etcd key bound to a lease; the creation revision or zxid is the fencing token
Locks and leasesSame primitives; holder loses the lock when its session or lease expires
Membership and discoveryEach instance registers an ephemeral key; watchers are notified on change
Configuration and metadataSmall values (shard maps, feature flags, schemas) updated with compare-and-set, pushed by watches
Do not use forWhy
Application data or large valuesDesigned for megabytes to a few gigabytes in total; etcd's default request limit is about 1.5 MiB and its default storage quota is 2 GiB
High write ratesEvery write is a majority round trip plus fsync through one leader: think thousands of writes per second, not hundreds of thousands (order of magnitude, hardware-dependent)
A queue or event busWatches are change notifications, not a durable high-volume stream
A lock on the hot path of every requestAdds a consensus round to each request and makes the service a global bottleneck
A hard runtime dependency for serving trafficCache the last known config or membership so an outage of the coordination service degrades control, not the data path

Senior signal: keep the coordination service on the control plane. Data-plane nodes read from a local cache updated by watches and keep serving if it is unreachable.

Gossip protocols

Agreement

Every node periodically (about once a second) picks a few random peers and exchanges what it knows. Information spreads like an epidemic: with fan-out k, all N nodes hear a rumour in O(log N) rounds, with no coordinator and no single point of failure.

The number of informed nodes roughly doubles or triples each round. Some messages are wasted on nodes that already know (F to B), which is the price of having no coordinator.
GainPay
Scales to thousands of nodes, constant load per nodeOnly eventual: for a few rounds nodes disagree about the state
Tolerates node loss and message loss without special handlingRedundant messages; state must be mergeable (versioned per node)
No leader, no quorum, works during partitionsCannot be used to make a decision that needs agreement (who is leader, who owns a lock)

Where it shows up: cluster membership and metadata in Dynamo-style stores and Cassandra, Redis Cluster's cluster bus, Consul's Serf layer (SWIM-based). Each entry carries a version or heartbeat counter so that the newer one wins on merge.

Failure detection and membership

Agreement

DetectorHow it decidesTrade-off
Heartbeat with fixed timeoutDead if no heartbeat for TOne number trades detection speed against false positives; wrong whenever the network gets slower than usual
Phi accrualOutputs a suspicion level computed from the observed distribution of heartbeat arrival gaps, and the caller picks a thresholdAdapts to each link; still a guess
SWIM-style probingPing a random member; on no reply ask k others to ping it indirectly; mark "suspect" before "dead"Separates "I cannot reach it" from "nobody can"; constant load per node

Membership is the list of nodes currently in the cluster. There are two ways to keep it, and choosing wrongly is a classic bug.

Gossip-based membershipConsensus-based membership
ViewEach node has its own, converging over timeOne agreed, versioned view
Available during partitionYes, each side keeps its viewOnly the majority side can change it
Good forRouting hints, load balancing, replica placement in AP storesAnything where two owners is a bug: shard ownership, leader identity, lock holders
ExamplesCassandra ring state, SerfZooKeeper ephemeral nodes, etcd leases, Kafka controller metadata
  • Detecting failure and acting on it are separate decisions. Declaring a node dead is cheap to undo for a load balancer and expensive for a database failover; use a longer confirmation for the expensive action.
  • A node can be alive but unreachable from only some peers (asymmetric partition). Majority-confirmed or indirect probing avoids one observer evicting a healthy node.

Distributed transactions

Part 4 of 8 · changing two systems together

A local ACID transaction stops at the boundary of one database. As soon as a business operation touches a second database, a broker or another service, atomicity has to be rebuilt, and each way of rebuilding it gives up something.

The dual-write problem

Distributed transactions

A service writes to its database and then to a second system (broker, cache, search index, another service) as two separate steps. Nothing makes the pair atomic, so any crash or timeout between them leaves the two permanently different.

The order is durable, the event is not. No retry will fix it, because after the crash nothing remembers that a publish was owed.
Order of the two writesFailure in between gives
DB commit, then publishLost event: downstream never hears of a real change
Publish, then DB commitPhantom event: downstream acts on a change that was rolled back
Either order, two concurrent requestsThe two systems may apply the updates in different orders and end on different values, with no failure at all

Senior signal: spot every dual write in your own diagram ("write DB, then update cache", "save, then call the email service") and name the fix: one source of truth plus a derived, replayable stream (outbox / CDC), not "we will wrap it in a try/except".

Two-phase commit

Distributed transactions

A coordinator asks every participant to prepare (do the work, write it durably, hold the locks, promise to commit if told to). If all vote yes it records the decision and tells everyone to commit; any no or timeout means abort.

The point of no return is the coordinator's durable decision record. If the coordinator dies after the yes votes and before the decision reaches a participant, that participant keeps its locks until the coordinator comes back.
PropertyDetail
GivesAtomic commit across participants: all commit or all abort
BlockingA prepared participant cannot decide alone; rows stay locked for as long as the coordinator is down
LatencyTwo round trips and several forced log writes, with locks held throughout
AvailabilityNeeds every participant and the coordinator up: availability multiplies down
Does not giveIsolation across participants by itself; that comes from each participant's locks or MVCC
  • Where it is still used: XA transactions between a database and a broker or between two databases; inside distributed SQL databases, where a transaction spanning shards is committed with 2PC and each participant (and the coordinator state) is itself a consensus group, which removes the single-coordinator blocking problem (Spanner is the documented example); Kafka transactions use a coordinator-driven protocol of the same shape.
  • Avoid across independently owned microservices: it couples their availability, needs every party to support the protocol, and holds locks across network calls.
  • Three-phase commit adds a pre-commit phase so participants can decide without the coordinator, but it assumes bounded delays and no partitions, so it is rarely deployed.

Sagas

Distributed transactions

A saga is a sequence of local transactions, one per service, each committed on its own. If a later step fails, the earlier ones are undone by compensating transactions. You get atomicity "eventually" and give up isolation.

StepServiceLocal transactionCompensationKind
1OrderCreate order as PENDINGMark order REJECTEDCompensable
2InventoryReserve stockRelease reservationCompensable
3PaymentCapture paymentNone needed if it fails; refund if a later step could failPivot: the go / no-go point
4OrderMark order CONFIRMEDNoneRetriable: must eventually succeed
5ShippingCreate shipmentNoneRetriable
  • Compensation is a new business transaction, not a rollback: a refund, a cancellation, a reversing ledger entry. The original remains visible in history.
  • Compensations and retriable steps must be idempotent and must be retried until they succeed; a compensation that can fail permanently needs a human queue.
  • Put steps that cannot be undone (charging a card with fees, sending an email, shipping) at or after the pivot, and make everything after the pivot unable to fail for business reasons.
  • Each step is "commit locally and emit a message", which is itself a dual write: build sagas on the outbox.

Trade-off: use a saga when the steps belong to different services and seconds of visible intermediate state are acceptable. Avoid it when the invariant must hold at every instant (a balance that may never go negative across two accounts): put that data in one database instead.

Saga choreography

Distributed transactions

No central controller. Each service subscribes to the others' events and reacts, including to failure events.

Events flow through a broker (not drawn). The failure path is just more subscriptions, and nobody holds the whole picture.
  • Gain: no extra component, loose coupling, each team owns its reactions.
  • Pay: the workflow is implicit, spread over subscriptions; hard to answer "where is order 981 stuck"; easy to create cyclic event dependencies; timeouts have no natural owner.
  • Reasonable for two to four steps with a linear flow. Beyond that, orchestrate.

Saga orchestration

Distributed transactions

One orchestrator owns the workflow as a persisted state machine. It sends commands, waits for replies, and on failure issues compensations in reverse order.

The orchestrator's stored state says exactly which step each saga is on, so a restarted orchestrator resumes and an operator can see stuck sagas.
  • Gain: the flow is explicit and testable, timeouts and retries live in one place, participants stay simple (command in, reply out).
  • Pay: one more service to run and scale; risk of business logic drifting into the orchestrator; its state store must be durable and its commands idempotent, since it retries after a crash.
  • Often delegated to a workflow engine (Temporal, AWS Step Functions, Camunda) rather than hand-built.

What isolation a saga loses

Distributed transactions

Each local transaction commits and is visible immediately, so other requests can observe and act on a saga that is half done or about to be compensated.

AnomalyExampleCountermeasure
Dirty readA report counts revenue from a payment that is refunded seconds laterSemantic lock: a PENDING state on the record that readers must respect
Lost updateA user edits the order while the saga is running and the saga overwrites itVersion check: each step updates with a conditional write on the record version
Acting on a reservation that disappearsStock shown as available, then taken back by a compensation, or the reverseReserve, do not decrement: hold quantities in a separate reserved bucket until confirmed
Out-of-order effectsCancel arrives before the create it cancelsCommutative updates and tombstones, so order of arrival does not change the result

Interview tip: "a saga is ACD, not ACID" is the one-line answer. The follow-up is always "so what does the user see in between?", and the answer is a named pending state.

Transactional outbox and CDC

Distributed transactions

Turn the dual write into a single local transaction: write the business row and a row describing the event into an outbox table in the same database transaction. A separate relay then publishes outbox rows to the broker.

Either both rows commit or neither does. The relay can crash and resume from its log position, so an event may be published twice but is never lost or invented.
Relay styleHowTrade-off
Polling publisherQuery unpublished outbox rows every N ms, publish, mark as sentSimple, any database; adds polling load and latency; ordering needs care with concurrent transactions
Log-based CDCTail the database's replication log (Debezium-style connectors)Low latency, commit order preserved, no polling; more infrastructure and operational knowledge
  • Guarantee: at-least-once publication, in commit order per aggregate. Consumers must deduplicate on the event id (the inbox pattern).
  • Costs: an extra write per transaction, a relay to run and monitor (lag is your new SLI), outbox cleanup, and events arrive milliseconds to seconds after commit.
  • CDC directly on business tables (no outbox) also works, but couples consumers to your schema; the outbox lets you publish a deliberate event contract.
  • Failure mode: with log-based CDC on PostgreSQL, a stalled connector holds a replication slot and the WAL grows until the disk fills. Alert on slot lag.

Try-confirm-cancel

Distributed transactions

A reservation protocol at the business level. Try reserves the resource in each service (hold funds, hold a seat) without making it final; Confirm turns every reservation into the real thing; Cancel releases them.

Like 2PC in shape, but the "prepared" state is an ordinary business record (a hold) rather than a database lock, so nothing blocks at the storage level.
  • Versus a saga: nothing is shown as done until Confirm, so there is less to compensate and better isolation; the price is that every participant must expose three idempotent operations and model holds explicitly.
  • Holds carry an expiry so an abandoned transaction frees itself. Confirm must not fail for business reasons, only be retried.
  • Failure modes to handle: a Cancel that arrives before its Try (record it and make the late Try a no-op), and duplicates of any of the three.
  • Where it shows up: payment authorise then capture, ticket and hotel holds, inventory reservations.

Avoiding the distributed transaction

Distributed transactions

The cheapest distributed transaction is the one you design away. Ask first whether the boundary that forces it is in the right place.

RedesignHow it removes the problemCost
Co-locate the dataPut rows that must change together in one database, one shard, one aggregate (same partition key)Service boundary moves; cross-shard cases remain
One source of truth, the rest derivedCommit to one store; feed search, cache, analytics and other services from its logDerived views lag
Single-entry ledger of intentsRecord "transfer T: A to B, 500" once; both balances are computed or updated from that one recordReaders must understand pending entries
Idempotent retry instead of atomicityMake each step safe to repeat and drive the operation to completion with retriesTemporary inconsistency; needs a completion driver
ReconciliationAccept rare divergence; detect and repair with a periodic compare jobDetection delay; needs a trustworthy source
A database that does it for youUse a distributed SQL database with cross-shard transactionsHigher write latency; vendor and operational weight

Senior signal: decide by invariant. "Money is neither created nor destroyed" must hold always, so it lives in one transactional store. "The search index reflects the order" may lag, so it is derived asynchronously.

Messaging correctness

Part 5 of 8 · duplicates, order, poison and retries

Asynchronous messaging moves failure handling from the caller to the consumer. The consumer must assume every message can arrive more than once, late and out of order unless the design says otherwise.

Delivery semantics

Messaging correctness

SemanticsHow you get itWhat can happenFits
At-most-onceSend without retry, or acknowledge before processingLoss, never duplicatesMetrics samples, best-effort notifications
At-least-onceRetry until acknowledged; acknowledge after processingDuplicates, never loss (while the broker is durable)The default for anything that matters
Effectively-once (exactly-once processing)At-least-once delivery plus an idempotent or deduplicating consumer, or an atomic commit of "result and progress marker" togetherMessage may be delivered and even executed twice, but the observable effect happens oncePayments, ledgers, counters
The broker cannot distinguish "not processed" from "processed, ack lost", so it must redeliver. Only the consumer can make the second delivery harmless.
  • Exactly-once delivery is impossible over an unreliable channel: it is the two generals problem. The sender either retries (duplicates possible) or does not (loss possible).
  • What products mean by "exactly-once": Kafka's exactly-once semantics combine the idempotent producer with transactions that atomically write output records and consumer offsets, which gives effectively-once for read-process-write loops that stay inside Kafka. A side effect outside it (an email, a call to another service, a row in an external database) is not covered and still needs its own idempotency.
  • Acknowledge after the effect is durable. Acknowledging first silently turns at-least-once into at-most-once.

Interview tip: never say "we use exactly-once delivery". Say "at-least-once delivery with idempotent consumers, so processing is effectively-once", then say where the dedup state lives.

Idempotency keys

Messaging correctness

An operation is idempotent if doing it twice has the same effect as doing it once. Where the operation is not naturally so (charge a card, create an order), the client attaches a unique key per logical operation and the server remembers key to outcome.

The unique constraint on the key is the lock. The retry never reaches the card processor, and the client receives the original answer.
Retry findsServer does
No rowInsert IN_PROGRESS and execute
COMPLETED, same request hashReturn the stored response without executing
IN_PROGRESS, lock not expiredReturn a conflict (commonly 409) so the client retries later; do not execute concurrently
IN_PROGRESS, lock expiredTake over: ask the downstream for the outcome using the same derived key, then finish
Same key, different request hashReject (commonly 422 or 400): the key was reused for another operation
  • Atomicity is the whole point: the key row and the business effect commit in the same local transaction. A dedup record in one store and the effect in another is a dual write.
  • Propagate: every downstream call uses a key derived from the original, so the chain is idempotent end to end.
  • Retention: keep keys longer than the longest client retry window (24 hours is a common public-API choice), then expire. Storage is one small row per write request.
  • Scope the key per tenant or user so one client cannot collide with another.
  • Prefer natural idempotency when available: PUT with a full representation, "set status = SHIPPED", an upsert on a business key, a conditional write on a version.

Failure mode: "check if the key exists, then insert" as two statements. Two concurrent retries both pass the check. Use an insert against a unique constraint, or a conditional put, as the single atomic step.

Ordering guarantees and partition keys

Messaging correctness

A partitioned log orders messages within a partition and promises nothing across partitions. You choose what is ordered by choosing the key.

All events for one account land on one partition and are read by one consumer of the group at a time, so they are processed in order. Events of different accounts have no defined order.
What breaks per-key orderGuard
Producer retries with several requests in flightIdempotent producer with sequence numbers (Kafka preserves order with idempotence on and at most 5 in-flight requests per connection)
Consumer processes a partition with a thread poolSerialise per key inside the consumer (hash key to a worker), or process sequentially
Changing the partition countKey-to-partition mapping changes: old and new events of a key sit on different partitions. Over-provision partitions up front or migrate deliberately
Retry topic or dead-letter queueThe failed message is overtaken by later ones of the same key: block the key, or make handlers tolerate reordering with versions
Rebalance during processingTwo consumers may briefly process the same partition: handlers must be idempotent
  • Key choice: the entity whose events must be ordered (account, order, device). Too coarse a key (tenant) creates hot partitions; too fine a key loses the order you needed.
  • Global order needs one partition, which caps throughput at one partition's rate and one consumer. Almost always per-entity order is what the business actually requires.
  • Belt and braces: put a per-entity version in each event so a consumer can detect and drop a stale or out-of-order update.

The inbox pattern

Messaging correctness

The consumer-side mirror of the outbox. The consumer records each message id in an inbox table in the same transaction as the state change it causes. A redelivered message hits the unique constraint and is skipped.

Dedup record and effect share one commit, so there is no window in which the effect exists without the record or the record without the effect.
  • Outbox + at-least-once broker + inbox is the standard recipe for effectively-once processing between two services with their own databases.
  • Storage: one row per message for the dedup window. The window must exceed the longest possible redelivery delay (broker retention, DLQ redrive); prune older rows.
  • If the handler's effect is not in a database (calls an API, sends an email), pass the message id on as an idempotency key instead; if the target does not support one, you are back to at-least-once and should say so.
  • Cheaper alternative when it fits: store "last processed offset or sequence per partition" with the state, as in sequence numbers.

Poison messages and dead-letter queues

Messaging correctness

A poison message fails every time it is processed (bad schema, a bug, a reference to deleted data). With naive at-least-once it is redelivered forever, and on an ordered partition it blocks everything behind it.

Transient and permanent failures take different exits. The dead-letter queue is a parking place with an owner, not a bin.
  • Classify errors: timeouts and 503s are transient (retry with backoff); validation and deserialisation errors are permanent (dead-letter at once, retrying wastes capacity).
  • Carry context: original topic, partition and offset, attempt count, error, first-failure time. Without it the message cannot be diagnosed or redriven.
  • Operate it: alert on DLQ depth and age, provide a redrive tool, and make redrive safe by keeping consumers idempotent.
  • Trade-off: dead-lettering one message lets later messages of the same key overtake it. If per-key order is a correctness requirement, either stop the partition and page someone, or park all later messages of that key too.

Retries, backoff and jitter

Messaging correctness

Retries turn transient failures into successes and turn overload into an outage. The rules exist to keep the first effect and prevent the second.

RuleWhy
Retry only idempotent operationsA timeout does not mean the first attempt failed
Retry only retryable errorsTimeouts, connection resets, 503, 429 (after Retry-After). Never 400, 401, 403, 404, 422
Exponential backoffGive a struggling dependency progressively more room
JitterClients that failed together otherwise retry together, in synchronised waves that re-create the spike at 100 ms, 200 ms, 400 ms
Retry at one layerThree attempts at each of three layers is up to 27 attempts at the bottom
Retry budgetCap retries as a fraction of normal traffic (for example 10 percent per client) so retries cannot multiply load during an outage
  • Retry storm: a dependency slows, callers time out and retry, offered load rises exactly when capacity is lowest, and the dependency cannot recover even after the original cause is gone. This self-sustaining state is called a metastable failure.
  • Retry budget mechanics: a token bucket per client refilled by successful requests; each retry spends a token; with no tokens, fail immediately. gRPC's retry throttling and service-mesh retry budgets work this way.
  • Servers help by answering overload with an explicit "do not retry" or Retry-After, and by rejecting cheaply.

Senior signal: whenever you add "with retries" to an arrow, add in the same sentence: idempotent, capped, jittered, and bounded by a budget and the request deadline.

Timeouts and deadline propagation

Messaging correctness

Every remote call needs a timeout, and a chain of calls needs a shared one. The edge sets an absolute deadline; every hop forwards the time remaining, checks it before starting work and abandons work once it has passed.

B stops working when nobody is waiting any more. Without propagation, B would finish the query and A might retry it, all for a client that left long ago.
  • Choosing a timeout: start from the dependency's measured p99 or p99.9 plus headroom, not a round number. Too long and threads pile up behind a slow dependency; too short and healthy requests fail and trigger retries.
  • Separate connect timeout (short, tens to hundreds of ms inside a datacentre) from request timeout.
  • Inner timeouts must be shorter than outer ones, otherwise the outer caller gives up first and the inner work is wasted. Deadline propagation enforces this automatically.
  • gRPC carries the deadline in request metadata and cancels downstream calls for you; with plain HTTP you pass a header and enforce it yourself.
  • Propagate cancellation as well as the deadline, so that a client disconnect stops downstream work.

Staying up

Part 6 of 8 · containing failure instead of spreading it

Outages at scale are rarely one component dying. They are one component slowing down and the rest of the system amplifying it. These patterns each cut one link of that chain.

Anatomy of a cascading failure

Staying up

Two feedback loops: retries add load to the thing that is already slow, and removing unhealthy instances concentrates load on the rest.
Link in the chainPattern that breaks it
Callers wait indefinitely on a slow dependencyTimeouts and deadlines
Callers keep sending to a failing dependencyCircuit breaker: fail fast, let it recover
One dependency's slowness consumes all threadsBulkhead: it can exhaust only its own pool
Retries multiply loadBackoff, jitter, retry budgets
Server accepts more work than it can finishLoad shedding and backpressure
The whole request fails because an optional part didGraceful degradation
Health checks eject everything at onceShallow checks, fail-open load balancing
Recovery triggers a synchronised stampedeJitter, coalescing, slow start

Senior signal: describe overload as a feedback loop and say which loop each mechanism opens. "Add a circuit breaker" with no reason is a mid-level answer.

Circuit breaker

Staying up

A client-side state machine in front of a dependency. When calls keep failing it stops making them for a while, which protects the caller's resources and gives the dependency room to recover.

Closed lets calls through and counts outcomes. Open rejects immediately. Half-open lets a few probes through to test recovery.
SettingTypical choiceWhy it matters
Trip conditionError or slow-call rate above about 50 percent over a 10 to 30 s rolling window, with a minimum request countA raw count trips on low traffic; no minimum trips on one bad call
What counts as failureTimeouts, connection errors, 5xx. Not 4xxClient errors say nothing about the dependency's health
Cool-downSeconds, often growing on repeated tripsToo short keeps hammering; too long delays recovery
ScopePer dependency, ideally per endpoint or per hostOne bad host or one bad endpoint should not cut off the healthy rest
  • When open you still need an answer: a fallback, a cached value, or a fast clear error. See graceful degradation.
  • Failure mode: breaker state is local to each client instance, so each one must discover the failure itself; and when all of them go half-open together their probes arrive at the same moment. Add jitter to the cool-down.
  • The numbers above are common starting points, not standards. Tune from measured error rates.

Bulkhead

Staying up

Partition resources so that a failure in one compartment cannot sink the others. Give each dependency, tenant or request class its own bounded pool.

Reviews is slow and its pool is full, so calls to it are rejected at once. Catalog and Payments still have their threads.
LevelIsolation unit
In processThread pool, semaphore or connection pool per dependency
Per tenant or prioritySeparate queues and concurrency limits, so one tenant's spike or a batch job cannot starve interactive traffic
DeploymentSeparate instance groups for critical and non-critical endpoints
InfrastructureCells or shards: independent copies of the whole stack, each serving a subset of customers, so the blast radius of a bad deploy or poison request is one cell

Trade-off: isolation costs utilisation. Twenty threads reserved for Payments sit idle while Catalog is saturated. Size compartments from measured peak concurrency, and reject (not queue) when one is full.

Rate limiting and load shedding

Staying up

Both reject requests. They answer different questions and belong in different places.

Rate limitingLoad shedding
QuestionIs this client within its allowance?Can this server finish more work right now?
Decided byPolicy per client, key or tenantThe server's own state: concurrency, queue time, CPU
ProtectsFairness, cost, abuse limitsThe server's ability to keep serving what it has accepted
Response429 with Retry-After503, quickly, ideally with a hint not to retry at once
WhereEdge or gateway (algorithms in Building Blocks)Every service, as early in the request as possible
  • Why shed: past saturation, queues grow, latency exceeds client timeouts, and the server spends its capacity on requests whose callers have already left. Goodput falls towards zero while CPU stays at 100 percent. Rejecting the excess keeps goodput at capacity.
  • Shed by priority: health checks and payments before search suggestions; requests already in progress before new ones; drop what has exceeded its deadline before doing any work on it.
  • Signal: limit concurrent in-flight requests or time spent queued, not CPU percentage, which reacts late. Adaptive concurrency limits adjust the cap from observed latency.
  • Rejection must be much cheaper than service, otherwise shedding does not help.

Backpressure

Staying up

When a consumer is slower than its producer, the slowness has to go somewhere. Backpressure sends it upstream as a signal to slow down, instead of letting it accumulate in a buffer.

Two forms of the same signal: a full bounded queue pushes back implicitly, a credit or window says explicitly how much the consumer can take.
MechanismExample
Bounded queue, block or reject when fullThread pool with a fixed queue and a rejection policy
Window or credit based flow controlTCP receive window, HTTP/2 flow control, Reactive Streams request(n)
Pull instead of pushKafka consumers fetch at their own pace; the durable log is the buffer and consumer lag is the signal
Explicit slow-down response429 or 503 with Retry-After
  • An unbounded queue is not a buffer, it is a latency and memory leak: it hides overload until the process runs out of memory, and everything in it is already late.
  • Backpressure only works where the source can slow down (batch jobs, internal producers, streams). A human at a browser cannot, so at the edge backpressure becomes load shedding.
  • Queues smooth bursts; they do not fix a sustained rate mismatch. If average arrival exceeds average service rate, the only fixes are more capacity or less work.

Graceful degradation and fallbacks

Staying up

Decide per dependency whether the request can still succeed without it, and what it returns instead.

FallbackExampleWatch for
Stale dataServe the last cached price list or profileBound the staleness; never for balances or permissions
Default or static responsePopular items instead of personalised recommendationsMake it obvious in metrics that defaults are being served
Drop the optional featureRender the product page without reviewsCallers must treat the field as optional
Reduced modeRead-only mode while the primary database fails overNeeds to be a designed, tested mode
DeferAccept the order, queue the confirmation emailQueue must be durable; user must be told it is pending
  • Fail open or fail closed is a per-dependency decision: a rate limiter or feature-flag service usually fails open (allow), authentication and payment authorisation fail closed (deny).
  • Failure mode: a fallback that runs only during incidents is the least tested code you own, and it may load a different dependency that is not sized for it. Prefer fallbacks that are simpler than the main path and exercised regularly; some teams avoid distinct fallback paths for this reason.
  • Classify dependencies as critical or optional at design time. An "optional" dependency called without a timeout is critical.

Hedged requests and tail latency

Staying up

With fan-out, rare slowness becomes common: if one backend is slow 1 percent of the time, a request that needs 100 backends hits at least one slow response 63 percent of the time (1 - 0.99100). The tail of the dependency becomes the median of the caller.

The second request is sent only for the slowest few percent of calls, so the extra load is a few percent while the tail collapses.
  • Numbers: in "The Tail at Scale" (Dean and Barroso), hedging a BigTable read after 10 ms cut the 99.9th percentile from about 1800 ms to 74 ms for about 2 percent more requests.
  • Safe only for idempotent operations, normally reads. Hedging a non-idempotent write needs an idempotency key.
  • Cap it: hedges are extra load, so give them a budget (a few percent of traffic) and disable them when the backend reports overload. Unbounded hedging during an incident is a retry storm.
Other tail-latency tacticsIdea
Tied requestsSend to two replicas at once, each told of the other; whichever starts first cancels its twin
Better load balancingLeast-loaded or "power of two choices" instead of round robin, with outlier ejection
Good-enough resultsReturn when most shards have answered rather than waiting for the slowest
Reduce fan-outBatch, denormalise or cache so fewer calls sit on the critical path
Tame background workThrottle and stagger compactions, GC and cron jobs so they do not coincide across replicas

Thundering herd

Staying up

Many clients do the same thing at the same instant because they were synchronised by the same event. The load is not higher on average; it is concentrated.

TriggerEffectFix
A hot cache key expiresThousands of requests recompute it against the database at once (cache stampede)Request coalescing (single flight), stale-while-revalidate, jittered TTLs, early refresh
A server restarts or a connection dropsAll clients reconnect and re-authenticate togetherReconnect with exponential backoff and jitter; connection rate limits
A lock is releasedAll waiters wake and all but one failQueue waiters and wake only the next (the ZooKeeper lock recipe watches just the predecessor node)
Timers on the hourEvery cron job and every client refresh fires at :00Random offset per instance
A cold instance joinsIt receives a full share of traffic with empty caches and unwarmed runtimeSlow start: ramp traffic up over tens of seconds; pre-warm
A dependency recoversQueued and retried work arrives all at once and knocks it over againRetry budgets, gradual breaker close, drain queues at a limited rate

Interview tip: the general answer is "desynchronise and deduplicate": add randomness to anything periodic, and collapse identical concurrent work into one execution. Cache-specific detail is in Building Blocks.

Health checks

Staying up

LivenessReadiness
QuestionIs this process beyond repair without a restart?Should this instance receive traffic right now?
Action on failureRestart the process or containerTake it out of load balancing; leave it running
Should checkThe process itself: event loop responsive, not deadlockedWarm-up finished, config loaded, can accept connections, not draining
Should not checkAny dependency. A database outage must not restart every instanceShared dependencies deeply, or one outage marks the whole fleet unready
Failure when misusedRestart loops that make an incident worseLoad balancer with zero targets: total outage from a partial one
  • Shallow vs deep: a shallow check (process answers) misses "up but useless"; a deep check (calls dependencies) is correlated across the fleet. A workable middle: readiness reflects only what is local to the instance, and dependency failure is handled by breakers and degradation.
  • Fail open at the balancer: if most or all targets look unhealthy, the health check is more likely wrong than the fleet, so keep routing to all. Several load balancers behave this way by design.
  • Startup gets its own signal so slow-starting instances are not killed by liveness checks before they finish initialising.
  • Health checks detect dead instances, not slow ones. Pair them with outlier detection on real request latency and error rate.

Coordination patterns

Part 7 of 8 · exactly one worker, one owner, one number

Recurring "only one of us may do this" problems. The senior move in each is to ask whether a duplicate is merely wasteful or actually incorrect, because the two need very different machinery.

Distributed locks

Coordination patterns

First ask what the lock is for. Efficiency: avoid doing the same work twice; an occasional double run costs a little money. Correctness: a double run corrupts data. A best-effort lock is fine for the first and wrong for the second.

Why the single-node Redis lock is unsafe for correctnessWhat happens
Lease expiry while the holder is paused or slowThe holder passes its expiry without noticing (GC, stalled I/O, slow network), another client acquires, and both act. No TTL value fixes this.
Asynchronous replicationThe primary fails before the lock key reaches the replica; after failover a second client acquires the same lock
No fencing tokenThe random value identifies the holder but is not ordered, so the resource cannot tell old from new

The Redlock debate. Redlock acquires the lock on a majority of several independent Redis nodes within a validity window; Martin Kleppmann argued that its safety rests on timing assumptions (bounded clock drift, process pauses and network delay) and that it issues no fencing token, so it should not be used where correctness depends on the lock. Salvatore Sanfilippo (Redis's author) replied that those assumptions are reasonable in practice and that the lock's unique value can be used for compare-and-set on the resource; the disagreement is about system models, and neither side claims it replaces fencing at the resource for strict correctness.

Safer alternativeHowCost
Fencing token checked by the resourceLock service issues an increasing token; storage rejects older ones (fencing tokens)Resource must support the check
Consensus-backed lockZooKeeper ephemeral sequential node or etcd lease; no lost locks on failover; revision or zxid serves as the tokenA coordination cluster; a few ms per acquire. Still needs fencing against a paused holder
No lock: atomic conditional writeLet the storage decide: "update if version is still 7", insert against a unique constraint, DynamoDB condition expression, HTTP If-MatchLosers must retry or give up; only protects what lives in that store
No lock service and no timing assumption. The database's own atomicity picks one winner, and a paused worker simply loses its conditional write later.

Senior signal: "a lock with a TTL is a lease, a lease can be held by two parties at once from their own points of view, so the protected write must be conditional". If you can make the write conditional, you often do not need the lock.

Leader-follower work assignment

Coordination patterns

One elected leader decides which worker owns which shard, partition or task. Workers do not negotiate with each other; they heartbeat and obey.

Assignments are stamped with the leader's epoch. A worker ignores instructions from an older epoch, and downstream writes carry the epoch so a worker that missed a reassignment is fenced.
  • Gain: one place makes placement decisions, so balancing, draining a node and prioritising are simple and globally informed.
  • Pay: the leader must be elected and fenced; reassignment after a worker death waits for the failure detector; a rebalance can pause work.
  • Handover rule: the new owner of a shard starts only after the old owner's lease on it has expired or been explicitly released, and writes are fenced by epoch in case that rule is violated by a pause.
  • Where it shows up: Kafka's controller and consumer-group coordinator, HDFS NameNode with DataNodes, the GFS and Bigtable masters, most job schedulers.
  • Keep the leader off the data path: it hands out assignments, clients cache them and talk to workers directly.

Sharded workers with consistent hashing

Coordination patterns

No per-task assignment at all: every node computes the owner of a key from the membership list. Adding or removing a worker moves only about 1/N of the keys.

Ownership is a pure function of the key and the membership view. Only the departed worker's arc changes hands.
  • Use when there are many small, similar units of work (per-user timers, per-device sessions, cache shards) and central assignment would be a bottleneck.
  • Virtual nodes (100 or more points per worker) even out the load and spread a departed worker's keys across all survivors. Rendezvous hashing is a simpler alternative with the same minimal-movement property. Ring mechanics are in Building Blocks.
  • Failure mode: if membership is gossiped, two workers can hold different views for a few seconds and both believe they own a key. Either make the work idempotent, or take membership from a consensus store and fence by its version.
  • Hashing balances key count, not load: a hot key still overloads its owner.

Exactly one runner of a cron job

Coordination patterns

The job is deployed on N instances for availability, but each scheduled tick must run once. Under failures "exactly one" really means "at least one, and duplicates are harmless".

ApproachHowCaveat
Claim the tick with a unique insertEach instance tries to insert (job name, scheduled time) into a table with a unique constraint; the one that succeeds runsSimple and robust; needs a rule for a claimed tick whose runner died
Leader runs the schedulerOnly the lease holder fires jobsA paused old leader may still fire: combine with the unique insert or fencing
Durable job queueOne scheduler enqueues a job per tick; workers claim rows (for example SELECT ... FOR UPDATE SKIP LOCKED) with a visibility timeoutAt-least-once: a slow worker's job may be re-claimed
Platform schedulerKubernetes CronJob, a cloud schedulerStill not exactly-once: Kubernetes documents that a CronJob may occasionally create two jobs or none for a tick
  • Make the job idempotent regardless: key its effects by the scheduled time (settlement for 2026-11-17), not by "now".
  • Decide the missed-run policy explicitly: after an outage, run every missed tick, only the latest, or none.
  • Decide the overlap policy: if the 02:00 run is still going at 03:00, skip, queue or run concurrently.

Distributed counters and rate limits

Coordination patterns

An exact, always-current global count needs every increment to pass through one place. Most designs trade a little accuracy or freshness for a lot of throughput.

Counter designAccuracyCost / limit
Single row or key, atomic incrementExactOne hot key: contention, bounded by one node's write rate
Sharded counter (N sub-counters, sum on read)Exact once all shards are readReads fan out; fine for likes and views
Local batch then flush every few secondsEventually exact, lags; loses the unflushed batch on crashCheapest writes
Stream aggregationExact per window if the pipeline is effectively-onceSeconds of delay, a stream processor to run
CRDT counter (per-replica slots, merge by maximum)Converges across regions without coordinationCannot enforce a ceiling or a non-negative floor
Sketches (HyperLogLog, Count-Min)Approximate with known error (HyperLogLog about 1 to 2 percent in kilobytes of memory)Distinct counts and heavy hitters only
Distributed rate limitHowTrade-off
Central storeAtomic increment or token-bucket script in Redis per keyAccurate; one extra round trip per request; decide whether to fail open when the store is down
Static local shareEach of N instances enforces limit / NNo coordination; wrong when traffic is uneven or N changes
Local bucket with leased quotaInstances take chunks of the budget from a central store and spend them locally, syncing every few hundred msNo per-request round trip; overshoot bounded by the chunk size times instances

Interview tip: state the error you accept: "the limit may be exceeded by at most one chunk per instance during a sync interval". For limits that are money (quota billing, inventory), use the exact path.

Sequence generation

Coordination patterns

Ask which property is actually needed: unique, roughly time-ordered, or strictly increasing with no gaps. Each step up costs coordination.

SchemeOrderingCoordinationNotes
Database sequence / auto-incrementIncreasing; gaps on rollbackEvery id from one primarySimple; a bottleneck and a single point for writes; leaks volume
Range allocation (hi/lo, segments)Increasing per node, interleaved across nodesOne round trip per block of, say, 1000 idsGaps when a node restarts with an unused block
Snowflake-style 64-bit idRoughly time-ordered (k-sorted)None per id; unique worker id assigned once41 bits of milliseconds, 10 bits worker, 12 bits sequence in the original layout: 4096 ids per ms per worker, about 69 years of timestamps
UUIDv4NoneNone122 random bits; poor B-tree locality as a primary key
UUIDv7 / ULIDTime-ordered to the millisecondNone48-bit timestamp plus random bits; index-friendly; 128 bits wide
Central timestamp or sequence oracleStrictly increasingEvery id (batched) from a consensus-backed serviceUsed by some distributed databases for transaction timestamps; a deliberate central dependency
  • Snowflake failure mode: the clock stepping backwards produces duplicate or out-of-order ids. Generators refuse to issue ids until the clock catches up, and worker ids must never be shared by two live processes (assign them through a coordination service).
  • A gapless strictly increasing sequence (invoice numbers) requires a single serialised allocator in the same transaction as the row. Keep it off the hot path: assign it asynchronously after the order is created.
  • Time-ordered ids from different nodes are ordered only to within clock skew. Do not use them to decide which write happened first.

Consistency in practice

Part 8 of 8 · what a reader may see

Consistency models are promises about reads. Name the weakest one that keeps the product correct, because each stronger one costs latency or availability.

Linearizability vs serializability

Consistency in practice

Two different guarantees that are constantly confused. One is about recency of single operations across replicas, the other about isolation of multi-operation transactions.

LinearizabilitySerializability
AboutSingle operations on a single object (a register, a key)Transactions: groups of operations over many objects
PromiseEach operation appears to take effect at one instant between its start and its end; the system behaves like one copyThe result equals that of running the transactions one at a time in some order
Real-time orderYes: once a write has returned, every later read sees itNo: the equivalent serial order need not match wall-clock order, so a stale snapshot is allowed
Belongs toReplication. The "C" in CAPConcurrency control. The "I" in ACID
PreventsStale reads, two leaders both acquiring a lock, uniqueness violations across replicasLost updates, write skew, dirty and non-repeatable reads
Typical mechanismConsensus or a single leader with synchronous replication; reads confirmed by a quorumTwo-phase locking, serializable snapshot isolation, single-threaded execution
PriceLatency of a quorum round trip; unavailable on the minority side of a partitionAborts and retries, or lock waits and deadlocks
  • Strict serializability is both together: serializable, and the serial order respects real time. Spanner calls its version external consistency.
  • A serializable database read through asynchronous replicas is still serializable but not linearizable. A linearizable key-value store without multi-key transactions is not serializable.
  • Many databases default to something weaker than serializable (read committed or snapshot isolation). Check the default before relying on it.

Interview tip: "do you need linearizability?" is answered by finding the invariant: locks, leader election, unique usernames and "never oversell the last seat" need it; timelines, counters and catalogues do not.

Eventual consistency tactics

Consistency in practice

"Eventually consistent" only promises that replicas converge if writes stop. These are the mechanisms that actually make them converge, and decide what they converge to.

Read repair: the read that notices the stale replica also fixes it. Keys that are never read are never repaired this way.
TacticWhat it doesLimit
Read repairOn a read, compare replica versions and write the newest back to stale replicasOnly heals data that is read
Anti-entropyBackground process compares replicas (commonly with Merkle trees, so only differing ranges are transferred) and syncs themI/O cost; convergence time depends on how often it runs
Hinted handoffAnother node holds writes meant for an unreachable replica and replays them when it returnsA hint is not a replica: it improves availability, not durability
Conflict resolutionLast-write-wins, application merge of siblings, or CRDTsLWW silently drops concurrent writes and trusts clocks

CRDTs. Conflict-free replicated data types are structures (counters, sets, registers, sequences) whose merge is commutative, associative and idempotent, so replicas that have seen the same updates in any order, any number of times, reach the same state without coordination. They cost extra metadata (per-replica counts, tombstones) and cannot enforce invariants that need agreement, such as "balance never below zero" or "at most one winner".

Read-your-writes

Consistency in practice

After a user changes something, that user must see the change, even though replicas lag. Other users may see it later. This is much cheaper than linearizability and is what most products need.

OptionHowTrade-off
Read own data from the leaderRoute reads of things the user can edit (own profile, own orders) to the primarySimple; fails if most reads are of editable data
Leader for a window after a writeFor N seconds after a user writes, send that user's reads to the primary (flag in session or cookie)N must exceed replication lag; wrong when lag spikes
Version tokenThe write returns a log position or timestamp; the client sends it with reads; a replica serves only if it has applied that position, otherwise waits or forwards to the primaryPrecise, works across devices if the token is stored server-side per user; needs replica support
Sticky routingPin the user to one replicaGives monotonic reads (no going back in time); gives read-your-writes only if that replica has the write; breaks on failover
Quorum or synchronous readsRead from enough replicas to overlap the write set, or replicate synchronouslyHigher latency on every read or write
Client-side echoThe UI shows what the user just submitted from local stateCosmetic: a reload or another device shows the truth
  • Related session guarantees worth naming: monotonic reads (a user never sees data go backwards) and consistent prefix (never a reply before the message it answers).
  • The same problem appears with caches and search indexes: after a write, the user's next read must bypass or wait for the derived store.

Caches, CQRS and event sourcing

Consistency in practice

TopicThe one-line positionCovered in
Cache plus databaseUpdating both is a dual write. Treat the database as the source of truth, invalidate (delete) rather than update the cache after commit, and keep a TTL as the safety net for missed invalidations and racesBuilding Blocks
Replication lag, quorum reads and writes, isolation levelsThe storage-level mechanics behind the guarantees on this pageData Systems
CQRS and event sourcingSeparate write model and read models, fed by an ordered event log: the outbox idea taken to its conclusion, with read models that are eventually consistent by designArchitecture Styles

Cheat sheet

Problem, pattern, cost

ProblemPatternCost
Timeout: did it happen?Idempotency key plus retryDedup storage; key and effect in one transaction
Which write was first?Logical clock or a single sequencerMetadata, or a write bottleneck
Detect concurrent updatesVersion vectorsO(replicas) per value; merge logic
Exactly one leaderLease in a consensus store plus fencingCoordination cluster; resource must check tokens
Replicated state that must not divergeRaft / Paxos logMajority round trip per write; no writes without a majority
Cluster membership at scaleGossipEventually consistent view
DB write plus event publishTransactional outbox / CDCRelay to operate; at-least-once; lag
Multi-service business transactionSagaNo isolation; compensations to write and test
Atomic commit across databases2PCBlocking, locks held, availability multiplies down
Reserve across servicesTCCThree idempotent operations per participant
Duplicate messagesInbox or natural idempotencyDedup table and retention window
Per-entity orderingPartition keyHot partitions; no cross-key order
Message that always failsDead-letter queueBreaks order for that key; needs an owner
Transient errorsBackoff, jitter, budgetAdded latency; needs idempotency
Work for callers who gave upDeadline propagationPlumbing through every hop
Failing dependency drags callers downCircuit breaker, bulkheadTuning; idle reserved capacity; needs a fallback
More load than capacityLoad shedding, backpressureSome requests rejected on purpose
Slow tail on fan-outHedged requestsA few percent extra load; reads only
Only one worker may actConditional write, or lock plus fencingLosers retry; storage must enforce
User must see own writeVersion token or leader readMore load on the leader or waiting replicas
Replicas must converge without coordinationRead repair, anti-entropy, CRDTsMetadata; no global invariants

Which guarantee do I actually need?

Data guarantees. Walk it per invariant, not per system: one design usually ends in several different leaves.
Messaging and coordination guarantees. Three independent questions to ask of every asynchronous arrow and every background job.
  • Five sentences to have ready: a timeout is an unknown outcome; delivery is at-least-once so handlers are idempotent; a lease can be held twice so writes are fenced; a majority is needed for anything that must not diverge; pick the weakest consistency that preserves the invariant.

Next: API and Communication Design, where these guarantees are turned into concrete request, response and streaming contracts.