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
| Part | Question it answers | Patterns |
|---|---|---|
| 1. Why distributed is hard | What can go wrong that cannot on one machine? | Failure model, fallacies, partial failure, impossibility results |
| 2. Time and order | Which event happened first? | Lamport, vector and hybrid clocks, sequence numbers |
| 3. Agreement | How do nodes agree on one leader or one log? | Leases, fencing, Raft, quorums, gossip |
| 4. Distributed transactions | How do two systems change together? | 2PC, sagas, outbox, TCC |
| 5. Messaging correctness | What happens when a message arrives twice, late or never? | Idempotency, inbox, DLQ, retries, deadlines |
| 6. Staying up | How does one slow dependency not take everything down? | Circuit breaker, bulkhead, shedding, backpressure, hedging |
| 7. Coordination patterns | How does exactly one worker do a thing? | Locks, work assignment, singleton jobs, counters, IDs |
| 8. Consistency in practice | What 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: which failures you design for
- The fallacies of distributed computing: eight wrong assumptions and their consequences
- Partial failure and timeouts: slow and dead look the same
- Two generals and FLP: what no protocol can give you
The failure model
State the failures you tolerate before you pick a protocol. A design is only "correct" relative to a failure model.
| Failure | What happens | Typical cause | Standard defence |
|---|---|---|---|
| Crash-stop | Node halts and never returns | Hardware loss, terminated instance | Replication, failover |
| Crash-recovery | Node halts, later returns with its disk state but not its memory | Restart, deploy, OOM kill | Durable log (fsync before ack), rejoin protocol |
| Omission | A message is never sent or never received | Full queue, dropped packet, overloaded receiver | Timeouts, retries, idempotency |
| Network partition | Two groups of healthy nodes cannot talk to each other | Switch or link failure, misconfiguration, zone isolation | Majority 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, overload | Deadlines, circuit breakers, hedging, outlier ejection |
| Byzantine | Node sends arbitrary or malicious messages | Compromise, bugs that corrupt messages | Out 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
Eight assumptions (Deutsch and others at Sun) that are false in production. Each one maps to a design rule.
| False assumption | Design consequence |
|---|---|
| The network is reliable | Every remote call needs a timeout, a retry policy and an idempotent receiver |
| Latency is zero | Count round trips; batch, cache and co-locate chatty services; no remote calls in loops |
| Bandwidth is infinite | Paginate, compress, send deltas, keep payloads small |
| The network is secure | Authenticate and encrypt between services (mTLS), not only at the edge |
| Topology does not change | Service discovery and health checks, never hard-coded addresses |
| There is one administrator | Versioned, backward-compatible APIs; other teams deploy on their own schedule |
| Transport cost is zero | Serialisation costs CPU and cross-zone or cross-region traffic costs money |
| The network is homogeneous | Standard protocols, explicit schemas, expect mixed versions during rollouts |
Partial failure and timeouts
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.
- 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
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: why wall-clock timestamps cannot order events
- Lamport clocks: one counter, consistent with causality
- Vector clocks: detecting concurrent updates
- Hybrid clocks and TrueTime: physical time with guarantees
- Total order vs partial order
- Idempotent sequence numbers: order and dedup on one stream
Physical clocks
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.
- 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
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.
| Tells you | Does 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
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.
| Tells you | Does not tell you / costs |
|---|---|
| Exactly whether a happened before b, b before a, or they are concurrent | Which concurrent write should win: that is an application merge or a sibling returned to the client |
| Enough to detect conflicting updates without losing either | Size 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
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.
| Clock | Size | Respects causality | Detects concurrency | Related to real time |
|---|---|---|---|---|
| Wall clock (NTP) | 8 bytes | No | No | Approximately, unbounded error in the worst case |
| Lamport | 8 bytes | Yes | No | No |
| Vector | O(nodes) | Yes | Yes | No |
| HLC | 8 to 12 bytes | Yes | No | Yes, within the assumed skew bound |
| TrueTime-style interval | 2 timestamps | Yes, by waiting out uncertainty | No | Yes, 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
| Partial order | Total order | |
|---|---|---|
| Definition | Some pairs of events are incomparable (concurrent) | Every pair is ordered, and every node sees the same order |
| Source | Causality: happens-before, vector clocks | A single sequencer: one leader's log, one partition, a consensus log |
| Cost | No coordination; conflicts must be merged | Every write goes through one place; throughput and availability of that place bound the system |
| Use when | Operations 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
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.
- 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
- Fencing tokens: making a stale leader harmless
- Consensus in plain terms
- Raft: roles and terms
- Raft: log replication and commit
- Raft: leader election
- Raft under a partition
- Paxos in one paragraph
- Quorums and why majorities
- Split brain
- Coordination services: ZooKeeper and etcd
- Gossip protocols
- Failure detection and membership
Leader election and leases
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.
| Choice | Short lease (1 to 5 s) | Long lease (30 s or more) |
|---|---|---|
| Failover time | Fast | Slow: the system is leaderless until expiry |
| False failovers | More: a GC pause or a network blip loses the lease | Fewer |
| Load on the lease store | Higher renewal rate | Lower |
- 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
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.
- 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-Matchversion 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
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.
| Property | Meaning | Kind |
|---|---|---|
| Agreement | No two nodes decide different values | Safety: holds always |
| Validity | The decided value was proposed by some node | Safety |
| Integrity | A node decides at most once | Safety |
| Termination | Every non-faulty node eventually decides | Liveness: 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
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.
- 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:
RequestVoteandAppendEntries(which doubles as the heartbeat when empty).
Raft: log replication and commit
- Consistency check: each
AppendEntriesnames 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
- 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
- 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
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
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.
| Nodes | Majority | Failures tolerated | Comment |
|---|---|---|---|
| 1 | 1 | 0 | No fault tolerance |
| 2 | 2 | 0 | Worse than 1: either node failing stops writes |
| 3 | 2 | 1 | The usual minimum; one node per zone |
| 4 | 3 | 1 | Same tolerance as 3, slower commits |
| 5 | 3 | 2 | Survives one failure during maintenance of another |
| 7 | 4 | 3 | Rare: 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
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).
| Prevention | How it works | Cost / caveat |
|---|---|---|
| Majority quorum for promotion | A node may lead only with votes from more than half of a fixed membership | Needs 3 or more voters; a minority side stops serving writes |
| Witness / tiebreaker | A small third voter (often in a third zone) that holds no data | One more thing to run; still must be a real voter |
| Fencing token / epoch | Storage and followers reject the older epoch | Every write path must check it |
| STONITH | Power off or isolate the old primary before promoting | Needs a reliable out-of-band control path |
| Synchronous replication to a quorum | An isolated primary cannot acknowledge writes | Write 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
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 for | Mechanism |
|---|---|
| Leader election | Ephemeral sequential znode (lowest wins) or an etcd key bound to a lease; the creation revision or zxid is the fencing token |
| Locks and leases | Same primitives; holder loses the lock when its session or lease expires |
| Membership and discovery | Each instance registers an ephemeral key; watchers are notified on change |
| Configuration and metadata | Small values (shard maps, feature flags, schemas) updated with compare-and-set, pushed by watches |
| Do not use for | Why |
|---|---|
| Application data or large values | Designed 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 rates | Every 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 bus | Watches are change notifications, not a durable high-volume stream |
| A lock on the hot path of every request | Adds a consensus round to each request and makes the service a global bottleneck |
| A hard runtime dependency for serving traffic | Cache 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
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.
| Gain | Pay |
|---|---|
| Scales to thousands of nodes, constant load per node | Only eventual: for a few rounds nodes disagree about the state |
| Tolerates node loss and message loss without special handling | Redundant messages; state must be mergeable (versioned per node) |
| No leader, no quorum, works during partitions | Cannot 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
| Detector | How it decides | Trade-off |
|---|---|---|
| Heartbeat with fixed timeout | Dead if no heartbeat for T | One number trades detection speed against false positives; wrong whenever the network gets slower than usual |
| Phi accrual | Outputs a suspicion level computed from the observed distribution of heartbeat arrival gaps, and the caller picks a threshold | Adapts to each link; still a guess |
| SWIM-style probing | Ping 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 membership | Consensus-based membership | |
|---|---|---|
| View | Each node has its own, converging over time | One agreed, versioned view |
| Available during partition | Yes, each side keeps its view | Only the majority side can change it |
| Good for | Routing hints, load balancing, replica placement in AP stores | Anything where two owners is a bug: shard ownership, leader identity, lock holders |
| Examples | Cassandra ring state, Serf | ZooKeeper 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
- Two-phase commit (and 3PC in one line)
- Sagas: local transactions plus compensations
- Saga choreography
- Saga orchestration
- What isolation a saga loses
- Transactional outbox and CDC
- Try-confirm-cancel
- Avoiding the distributed transaction
The dual-write problem
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.
| Order of the two writes | Failure in between gives |
|---|---|
| DB commit, then publish | Lost event: downstream never hears of a real change |
| Publish, then DB commit | Phantom event: downstream acts on a change that was rolled back |
| Either order, two concurrent requests | The 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
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.
| Property | Detail |
|---|---|
| Gives | Atomic commit across participants: all commit or all abort |
| Blocking | A prepared participant cannot decide alone; rows stay locked for as long as the coordinator is down |
| Latency | Two round trips and several forced log writes, with locks held throughout |
| Availability | Needs every participant and the coordinator up: availability multiplies down |
| Does not give | Isolation 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
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.
| Step | Service | Local transaction | Compensation | Kind |
|---|---|---|---|---|
| 1 | Order | Create order as PENDING | Mark order REJECTED | Compensable |
| 2 | Inventory | Reserve stock | Release reservation | Compensable |
| 3 | Payment | Capture payment | None needed if it fails; refund if a later step could fail | Pivot: the go / no-go point |
| 4 | Order | Mark order CONFIRMED | None | Retriable: must eventually succeed |
| 5 | Shipping | Create shipment | None | Retriable |
- 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
No central controller. Each service subscribes to the others' events and reacts, including to failure events.
- 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
One orchestrator owns the workflow as a persisted state machine. It sends commands, waits for replies, and on failure issues compensations in reverse order.
- 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
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.
| Anomaly | Example | Countermeasure |
|---|---|---|
| Dirty read | A report counts revenue from a payment that is refunded seconds later | Semantic lock: a PENDING state on the record that readers must respect |
| Lost update | A user edits the order while the saga is running and the saga overwrites it | Version check: each step updates with a conditional write on the record version |
| Acting on a reservation that disappears | Stock shown as available, then taken back by a compensation, or the reverse | Reserve, do not decrement: hold quantities in a separate reserved bucket until confirmed |
| Out-of-order effects | Cancel arrives before the create it cancels | Commutative 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
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.
| Relay style | How | Trade-off |
|---|---|---|
| Polling publisher | Query unpublished outbox rows every N ms, publish, mark as sent | Simple, any database; adds polling load and latency; ordering needs care with concurrent transactions |
| Log-based CDC | Tail 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
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.
- 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
The cheapest distributed transaction is the one you design away. Ask first whether the boundary that forces it is in the right place.
| Redesign | How it removes the problem | Cost |
|---|---|---|
| Co-locate the data | Put 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 derived | Commit to one store; feed search, cache, analytics and other services from its log | Derived views lag |
| Single-entry ledger of intents | Record "transfer T: A to B, 500" once; both balances are computed or updated from that one record | Readers must understand pending entries |
| Idempotent retry instead of atomicity | Make each step safe to repeat and drive the operation to completion with retries | Temporary inconsistency; needs a completion driver |
| Reconciliation | Accept rare divergence; detect and repair with a periodic compare job | Detection delay; needs a trustworthy source |
| A database that does it for you | Use a distributed SQL database with cross-shard transactions | Higher 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: at-most-once, at-least-once, effectively-once
- Idempotency keys: an idempotent payment endpoint
- Ordering guarantees and partition keys
- The inbox pattern
- Poison messages and dead-letter queues
- Retries, backoff and jitter
- Timeouts and deadline propagation
Delivery semantics
| Semantics | How you get it | What can happen | Fits |
|---|---|---|---|
| At-most-once | Send without retry, or acknowledge before processing | Loss, never duplicates | Metrics samples, best-effort notifications |
| At-least-once | Retry until acknowledged; acknowledge after processing | Duplicates, 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" together | Message may be delivered and even executed twice, but the observable effect happens once | Payments, ledgers, counters |
- 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
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.
| Retry finds | Server does |
|---|---|
| No row | Insert IN_PROGRESS and execute |
| COMPLETED, same request hash | Return the stored response without executing |
| IN_PROGRESS, lock not expired | Return a conflict (commonly 409) so the client retries later; do not execute concurrently |
| IN_PROGRESS, lock expired | Take over: ask the downstream for the outcome using the same derived key, then finish |
| Same key, different request hash | Reject (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
A partitioned log orders messages within a partition and promises nothing across partitions. You choose what is ordered by choosing the key.
| What breaks per-key order | Guard |
|---|---|
| Producer retries with several requests in flight | Idempotent 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 pool | Serialise per key inside the consumer (hash key to a worker), or process sequentially |
| Changing the partition count | Key-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 queue | The failed message is overtaken by later ones of the same key: block the key, or make handlers tolerate reordering with versions |
| Rebalance during processing | Two 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
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.
- 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
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.
- 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
Retries turn transient failures into successes and turn overload into an outage. The rules exist to keep the first effect and prevent the second.
| Rule | Why |
|---|---|
| Retry only idempotent operations | A timeout does not mean the first attempt failed |
| Retry only retryable errors | Timeouts, connection resets, 503, 429 (after Retry-After). Never 400, 401, 403, 404, 422 |
| Exponential backoff | Give a struggling dependency progressively more room |
| Jitter | Clients that failed together otherwise retry together, in synchronised waves that re-create the spike at 100 ms, 200 ms, 400 ms |
| Retry at one layer | Three attempts at each of three layers is up to 27 attempts at the bottom |
| Retry budget | Cap 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
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.
- 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
| Link in the chain | Pattern that breaks it |
|---|---|
| Callers wait indefinitely on a slow dependency | Timeouts and deadlines |
| Callers keep sending to a failing dependency | Circuit breaker: fail fast, let it recover |
| One dependency's slowness consumes all threads | Bulkhead: it can exhaust only its own pool |
| Retries multiply load | Backoff, jitter, retry budgets |
| Server accepts more work than it can finish | Load shedding and backpressure |
| The whole request fails because an optional part did | Graceful degradation |
| Health checks eject everything at once | Shallow checks, fail-open load balancing |
| Recovery triggers a synchronised stampede | Jitter, 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
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.
| Setting | Typical choice | Why it matters |
|---|---|---|
| Trip condition | Error or slow-call rate above about 50 percent over a 10 to 30 s rolling window, with a minimum request count | A raw count trips on low traffic; no minimum trips on one bad call |
| What counts as failure | Timeouts, connection errors, 5xx. Not 4xx | Client errors say nothing about the dependency's health |
| Cool-down | Seconds, often growing on repeated trips | Too short keeps hammering; too long delays recovery |
| Scope | Per dependency, ideally per endpoint or per host | One 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
Partition resources so that a failure in one compartment cannot sink the others. Give each dependency, tenant or request class its own bounded pool.
| Level | Isolation unit |
|---|---|
| In process | Thread pool, semaphore or connection pool per dependency |
| Per tenant or priority | Separate queues and concurrency limits, so one tenant's spike or a batch job cannot starve interactive traffic |
| Deployment | Separate instance groups for critical and non-critical endpoints |
| Infrastructure | Cells 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
Both reject requests. They answer different questions and belong in different places.
| Rate limiting | Load shedding | |
|---|---|---|
| Question | Is this client within its allowance? | Can this server finish more work right now? |
| Decided by | Policy per client, key or tenant | The server's own state: concurrency, queue time, CPU |
| Protects | Fairness, cost, abuse limits | The server's ability to keep serving what it has accepted |
| Response | 429 with Retry-After | 503, quickly, ideally with a hint not to retry at once |
| Where | Edge 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
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.
| Mechanism | Example |
|---|---|
| Bounded queue, block or reject when full | Thread pool with a fixed queue and a rejection policy |
| Window or credit based flow control | TCP receive window, HTTP/2 flow control, Reactive Streams request(n) |
| Pull instead of push | Kafka consumers fetch at their own pace; the durable log is the buffer and consumer lag is the signal |
| Explicit slow-down response | 429 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
Decide per dependency whether the request can still succeed without it, and what it returns instead.
| Fallback | Example | Watch for |
|---|---|---|
| Stale data | Serve the last cached price list or profile | Bound the staleness; never for balances or permissions |
| Default or static response | Popular items instead of personalised recommendations | Make it obvious in metrics that defaults are being served |
| Drop the optional feature | Render the product page without reviews | Callers must treat the field as optional |
| Reduced mode | Read-only mode while the primary database fails over | Needs to be a designed, tested mode |
| Defer | Accept the order, queue the confirmation email | Queue 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
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.
- 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 tactics | Idea |
|---|---|
| Tied requests | Send to two replicas at once, each told of the other; whichever starts first cancels its twin |
| Better load balancing | Least-loaded or "power of two choices" instead of round robin, with outlier ejection |
| Good-enough results | Return when most shards have answered rather than waiting for the slowest |
| Reduce fan-out | Batch, denormalise or cache so fewer calls sit on the critical path |
| Tame background work | Throttle and stagger compactions, GC and cron jobs so they do not coincide across replicas |
Thundering herd
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.
| Trigger | Effect | Fix |
|---|---|---|
| A hot cache key expires | Thousands 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 drops | All clients reconnect and re-authenticate together | Reconnect with exponential backoff and jitter; connection rate limits |
| A lock is released | All waiters wake and all but one fail | Queue waiters and wake only the next (the ZooKeeper lock recipe watches just the predecessor node) |
| Timers on the hour | Every cron job and every client refresh fires at :00 | Random offset per instance |
| A cold instance joins | It receives a full share of traffic with empty caches and unwarmed runtime | Slow start: ramp traffic up over tens of seconds; pre-warm |
| A dependency recovers | Queued and retried work arrives all at once and knocks it over again | Retry 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
| Liveness | Readiness | |
|---|---|---|
| Question | Is this process beyond repair without a restart? | Should this instance receive traffic right now? |
| Action on failure | Restart the process or container | Take it out of load balancing; leave it running |
| Should check | The process itself: event loop responsive, not deadlocked | Warm-up finished, config loaded, can accept connections, not draining |
| Should not check | Any dependency. A database outage must not restart every instance | Shared dependencies deeply, or one outage marks the whole fleet unready |
| Failure when misused | Restart loops that make an incident worse | Load 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
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 correctness | What happens |
|---|---|
| Lease expiry while the holder is paused or slow | The holder passes its expiry without noticing (GC, stalled I/O, slow network), another client acquires, and both act. No TTL value fixes this. |
| Asynchronous replication | The primary fails before the lock key reaches the replica; after failover a second client acquires the same lock |
| No fencing token | The 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 alternative | How | Cost |
|---|---|---|
| Fencing token checked by the resource | Lock service issues an increasing token; storage rejects older ones (fencing tokens) | Resource must support the check |
| Consensus-backed lock | ZooKeeper ephemeral sequential node or etcd lease; no lost locks on failover; revision or zxid serves as the token | A coordination cluster; a few ms per acquire. Still needs fencing against a paused holder |
| No lock: atomic conditional write | Let the storage decide: "update if version is still 7", insert against a unique constraint, DynamoDB condition expression, HTTP If-Match | Losers must retry or give up; only protects what lives in that store |
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
One elected leader decides which worker owns which shard, partition or task. Workers do not negotiate with each other; they heartbeat and obey.
- 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
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.
- 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
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".
| Approach | How | Caveat |
|---|---|---|
| Claim the tick with a unique insert | Each instance tries to insert (job name, scheduled time) into a table with a unique constraint; the one that succeeds runs | Simple and robust; needs a rule for a claimed tick whose runner died |
| Leader runs the scheduler | Only the lease holder fires jobs | A paused old leader may still fire: combine with the unique insert or fencing |
| Durable job queue | One scheduler enqueues a job per tick; workers claim rows (for example SELECT ... FOR UPDATE SKIP LOCKED) with a visibility timeout | At-least-once: a slow worker's job may be re-claimed |
| Platform scheduler | Kubernetes CronJob, a cloud scheduler | Still 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
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 design | Accuracy | Cost / limit |
|---|---|---|
| Single row or key, atomic increment | Exact | One hot key: contention, bounded by one node's write rate |
| Sharded counter (N sub-counters, sum on read) | Exact once all shards are read | Reads fan out; fine for likes and views |
| Local batch then flush every few seconds | Eventually exact, lags; loses the unflushed batch on crash | Cheapest writes |
| Stream aggregation | Exact per window if the pipeline is effectively-once | Seconds of delay, a stream processor to run |
| CRDT counter (per-replica slots, merge by maximum) | Converges across regions without coordination | Cannot 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 limit | How | Trade-off |
|---|---|---|
| Central store | Atomic increment or token-bucket script in Redis per key | Accurate; one extra round trip per request; decide whether to fail open when the store is down |
| Static local share | Each of N instances enforces limit / N | No coordination; wrong when traffic is uneven or N changes |
| Local bucket with leased quota | Instances take chunks of the budget from a central store and spend them locally, syncing every few hundred ms | No 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
Ask which property is actually needed: unique, roughly time-ordered, or strictly increasing with no gaps. Each step up costs coordination.
| Scheme | Ordering | Coordination | Notes |
|---|---|---|---|
| Database sequence / auto-increment | Increasing; gaps on rollback | Every id from one primary | Simple; a bottleneck and a single point for writes; leaks volume |
| Range allocation (hi/lo, segments) | Increasing per node, interleaved across nodes | One round trip per block of, say, 1000 ids | Gaps when a node restarts with an unused block |
| Snowflake-style 64-bit id | Roughly time-ordered (k-sorted) | None per id; unique worker id assigned once | 41 bits of milliseconds, 10 bits worker, 12 bits sequence in the original layout: 4096 ids per ms per worker, about 69 years of timestamps |
| UUIDv4 | None | None | 122 random bits; poor B-tree locality as a primary key |
| UUIDv7 / ULID | Time-ordered to the millisecond | None | 48-bit timestamp plus random bits; index-friendly; 128 bits wide |
| Central timestamp or sequence oracle | Strictly increasing | Every id (batched) from a consensus-backed service | Used 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
- Eventual consistency tactics: read repair, anti-entropy, CRDTs
- Read-your-writes: implementation options
- Caches, CQRS and event sourcing: where they are covered
Linearizability vs serializability
Two different guarantees that are constantly confused. One is about recency of single operations across replicas, the other about isolation of multi-operation transactions.
| Linearizability | Serializability | |
|---|---|---|
| About | Single operations on a single object (a register, a key) | Transactions: groups of operations over many objects |
| Promise | Each operation appears to take effect at one instant between its start and its end; the system behaves like one copy | The result equals that of running the transactions one at a time in some order |
| Real-time order | Yes: once a write has returned, every later read sees it | No: the equivalent serial order need not match wall-clock order, so a stale snapshot is allowed |
| Belongs to | Replication. The "C" in CAP | Concurrency control. The "I" in ACID |
| Prevents | Stale reads, two leaders both acquiring a lock, uniqueness violations across replicas | Lost updates, write skew, dirty and non-repeatable reads |
| Typical mechanism | Consensus or a single leader with synchronous replication; reads confirmed by a quorum | Two-phase locking, serializable snapshot isolation, single-threaded execution |
| Price | Latency of a quorum round trip; unavailable on the minority side of a partition | Aborts 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
"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.
| Tactic | What it does | Limit |
|---|---|---|
| Read repair | On a read, compare replica versions and write the newest back to stale replicas | Only heals data that is read |
| Anti-entropy | Background process compares replicas (commonly with Merkle trees, so only differing ranges are transferred) and syncs them | I/O cost; convergence time depends on how often it runs |
| Hinted handoff | Another node holds writes meant for an unreachable replica and replays them when it returns | A hint is not a replica: it improves availability, not durability |
| Conflict resolution | Last-write-wins, application merge of siblings, or CRDTs | LWW 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
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.
| Option | How | Trade-off |
|---|---|---|
| Read own data from the leader | Route reads of things the user can edit (own profile, own orders) to the primary | Simple; fails if most reads are of editable data |
| Leader for a window after a write | For 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 token | The 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 primary | Precise, works across devices if the token is stored server-side per user; needs replica support |
| Sticky routing | Pin the user to one replica | Gives monotonic reads (no going back in time); gives read-your-writes only if that replica has the write; breaks on failover |
| Quorum or synchronous reads | Read from enough replicas to overlap the write set, or replicate synchronously | Higher latency on every read or write |
| Client-side echo | The UI shows what the user just submitted from local state | Cosmetic: 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
| Topic | The one-line position | Covered in |
|---|---|---|
| Cache plus database | Updating 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 races | Building Blocks |
| Replication lag, quorum reads and writes, isolation levels | The storage-level mechanics behind the guarantees on this page | Data Systems |
| CQRS and event sourcing | Separate 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 design | Architecture Styles |
Cheat sheet
Problem, pattern, cost
| Problem | Pattern | Cost |
|---|---|---|
| Timeout: did it happen? | Idempotency key plus retry | Dedup storage; key and effect in one transaction |
| Which write was first? | Logical clock or a single sequencer | Metadata, or a write bottleneck |
| Detect concurrent updates | Version vectors | O(replicas) per value; merge logic |
| Exactly one leader | Lease in a consensus store plus fencing | Coordination cluster; resource must check tokens |
| Replicated state that must not diverge | Raft / Paxos log | Majority round trip per write; no writes without a majority |
| Cluster membership at scale | Gossip | Eventually consistent view |
| DB write plus event publish | Transactional outbox / CDC | Relay to operate; at-least-once; lag |
| Multi-service business transaction | Saga | No isolation; compensations to write and test |
| Atomic commit across databases | 2PC | Blocking, locks held, availability multiplies down |
| Reserve across services | TCC | Three idempotent operations per participant |
| Duplicate messages | Inbox or natural idempotency | Dedup table and retention window |
| Per-entity ordering | Partition key | Hot partitions; no cross-key order |
| Message that always fails | Dead-letter queue | Breaks order for that key; needs an owner |
| Transient errors | Backoff, jitter, budget | Added latency; needs idempotency |
| Work for callers who gave up | Deadline propagation | Plumbing through every hop |
| Failing dependency drags callers down | Circuit breaker, bulkhead | Tuning; idle reserved capacity; needs a fallback |
| More load than capacity | Load shedding, backpressure | Some requests rejected on purpose |
| Slow tail on fan-out | Hedged requests | A few percent extra load; reads only |
| Only one worker may act | Conditional write, or lock plus fencing | Losers retry; storage must enforce |
| User must see own write | Version token or leader read | More load on the leader or waiting replicas |
| Replicas must converge without coordination | Read repair, anti-entropy, CRDTs | Metadata; no global invariants |
Which guarantee do I actually need?
- 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.