The trouble with distributed systems
Node A sends a request to node B
t = 0 msTry: flip to the sender's view and run "request lost", "remote crashed" and "response lost"; A sees exactly the same thing. Then run "response lost" with retry on and count how many times B executed the request.
Round-trip times to a perfectly healthy node (4,000 requests)
Green responses beat the timeout; red ones came from a node that was fine but got declared dead. Try: set a tight 50 ms timeout, then raise the load to 90%. Queueing alone moves the whole tail, and no timeout is both fast and safe.
Time-of-day clock error vs true time
Each NTP sync yanks the time-of-day clock to the server's time, possibly backwards (amber markers). The monotonic clock is never stepped. Try: choose "stepped back 1.5 s" and time the 1-second operation starting at 59.5 s. Then pick "NTP unreachable" and watch the error grow without bound.
Client B increments x after reading A's write (it is causally later)
Every replica keeps the value with the greatest timestamp. Try: with node 3 just 3 ms slow, B's increment carries a smaller timestamp than the write it read, so every node silently discards it. Slide the skew positive, then switch to logical clocks.
Clock readings as confidence intervals
Shaded bars are each clock's [earliest, latest] interval; the dashed tick is what the clock reads, the solid tick the timestamp chosen. Try: with no commit wait and B starting 2 ms later, B gets a smaller timestamp and its snapshot misses A. Turn on commit wait: A sits out the uncertainty before acknowledging, so any later transaction must get a larger timestamp. Shrinking ε shrinks the wait.
A lease-based lock protecting a file in storage
Client 1 checked its lease, then froze. Try: a 45 s pause without fencing, then turn fencing on. Lower the pause below about 15 s and the lease is still valid when it wakes. A pause between roughly 15 and 30 s is the scary middle: client 1 writes without a lease and nothing notices, because client 2 has not written yet.
Five nodes, heartbeats and leader elections
tick 0A freezes at t=10 and wakes at t=34 still believing it leads. Its epoch-1 writes are refused. Green links work both ways, amber arrows only one way, faint red not at all. Try: the GC pause, then step the tick slider around 34–36 to watch A act as a zombie leader for two ticks.
- nothing yet
Byzantine faults: when nodes lie
byzantine-faultTwo quorums that must agree
A protocol must make progress after hearing from n − f nodes, because f may never answer. Any two such quorums overlap in n − 2f nodes, and at least one of those must be honest to carry the truth across. Try: f = 1 with crash faults needs 3 nodes; switch to Byzantine and n = 3 breaks (the lone overlap node tells each side what it wants), n = 4 works.
Pick a system model
| Crash-stop | Crash-recovery | Byzantine | |
|---|---|---|---|
| Synchronous | |||
| Partially synchronous | |||
| Asynchronous |
Try: compare partially synchronous × crash-recovery (what real systems assume) with asynchronous × crash-stop (FLP).
Safety or liveness?
- Uniqueness: no two nodes ever hold the same lock lease at once.
- Monotonic sequence: a later lock grant always carries a larger fencing token.
- Availability: a node that asks for the lock and doesn't crash eventually gets an answer.
- Replicas converge to the same value once writes stop.
- A write acknowledged as committed is never lost.
- A read never returns a value that no one wrote.
- Every request eventually receives a response.
Safety = nothing bad happens (a violation happens at a point in time and can't be undone). Liveness = something good eventually happens. Algorithms must keep safety in every model; liveness is allowed to depend on the network eventually behaving.
- takeawayA missing response tells you nothing: the request may have been lost, delayed or executed. Timeouts are the only detector, they are always a guess, and retries need idempotence.
- takeawayClocks drift, jump and disagree. Use monotonic clocks for durations, don't order cross-node events by wall-clock timestamps (LWW drops writes), and if you must, use explicit uncertainty intervals as Spanner does.
- takeawayA node can be paused or cut off at any moment without knowing it, so no single node decides. Use quorums for the truth and fencing tokens at the resource, and design for a partially synchronous, crash-recovery system model: safety always, liveness eventually.
Key concepts · 18
book chapter 8- Partial failure
Some parts of the system are broken in unpredictable ways while others keep working.
A single computer is designed to either work or crash cleanly; a distributed system is nondeterministic, and you may not even know whether an operation succeeded. Fault tolerance has to be designed in from the start.
↑ see it in the visualization - Asynchronous packet network
A network that gives no guarantee when, or whether, a packet will arrive.
When a request gets no response, it could have been lost, queued, the remote crashed or paused, or the response was lost. The sender cannot tell these apart, and a retry may execute the operation twice.
EthernetIPTCP↑ see it in the visualization - Timeouts as failure detection
Declaring a node dead when it hasn't responded within a fixed period.
A short timeout detects crashes quickly but falsely kills slow nodes, whose load moves to others and can cascade. A long timeout leaves users waiting. There is no correct value, only a trade-off.
↑ see it in the visualization - Unbounded delays and network congestion
Variable packet delay caused mostly by queueing: at switches, in the OS, at a busy CPU, under TCP flow control and retransmission.
Datacenter networks and the internet are packet-switched to use bandwidth efficiently, which means queues instead of reserved capacity. When load rises, the tail of the delay distribution grows without a hard limit.
TCP retransmissionnoisy neighbours in the cloud↑ see it in the visualization - Adaptive timeouts (phi accrual)
Choosing timeouts from the measured response-time distribution and its jitter instead of a constant.
Systems that observe round-trip times can raise their suspicion level gradually, which balances detection delay against false positives as conditions change.
AkkaCassandra↑ see it in the visualization - Time-of-day clock
A wall-clock reading (e.g. seconds since the epoch) kept in sync with NTP.
When NTP finds it too far off it can jump the clock backwards, so subtracting two readings can give a negative duration. It's fine for showing a date but wrong for measuring elapsed time.
clock_gettime(CLOCK_REALTIME)System.currentTimeMillis()↑ see it in the visualization - Monotonic clock
A clock guaranteed to move only forward, used to measure durations such as timeouts.
Its absolute value means nothing and can't be compared across machines, but the difference between two readings on one machine is a reliable elapsed time.
clock_gettime(CLOCK_MONOTONIC)System.nanoTime()↑ see it in the visualization - Clock drift and NTP synchronization
Quartz clocks run fast or slow depending on temperature; NTP corrects them over the network, only as accurately as the network delay allows.
Google assumes 200 ppm of drift: about 6 ms between syncs every 30 s, or 17 s a day. A firewalled NTP server, a misconfiguration or a VM pause can leave a clock badly wrong without anyone noticing.
↑ see it in the visualization - Last write wins under clock skew
Resolving conflicts by keeping the write with the greatest wall-clock timestamp.
A node whose clock is a few ms slow writes timestamps smaller than writes it has already seen, so its causally later writes are silently dropped. Logical clocks order events by causality instead.
CassandraRiak (LWW mode)↑ see it in the visualization - Clock confidence intervals (TrueTime)
Treating a clock reading as a range [earliest, latest] with an explicit uncertainty bound.
If two intervals don't overlap, the order of events is known. Spanner waits out the uncertainty before committing, which is why Google puts GPS receivers and atomic clocks in every datacenter to keep it around 7 ms.
Google SpannerAWS ClockBound↑ see it in the visualization - Process pauses
A thread stopped for an arbitrary time without noticing: stop-the-world GC, VM suspension, context switches, disk I/O, swapping, SIGSTOP.
Code that checks a condition and then acts can be frozen between the two steps. When it wakes up, the world, and its lease, may have moved on.
JVM GClive VM migration↑ see it in the visualization - Lease
A lock with a timeout: the holder must renew it before it expires, or someone else may take over.
Leases keep a crashed holder from blocking everyone forever, but a paused holder doesn't know its lease has run out and can act on stale authority.
ChubbyZooKeeperetcd↑ see it in the visualization - Fencing token
A number that increases every time the lock is granted, sent with every write to the protected resource.
The storage service rejects any write carrying a token older than one it has already seen, so a zombie client woken from a pause can't corrupt data. The resource itself has to check.
ZooKeeper zxid / cversion↑ see it in the visualization - The truth is defined by the majority
Decisions such as declaring a node dead or choosing a leader are made by a quorum vote, not by one node.
A node can't trust its own view: it may be the one cut off, or the one that just paused. If a majority declares it dead, it must step down, even if it feels fine.
↑ see it in the visualization - Network partition (netsplit)
Part of the network is cut off from the rest, while each side keeps working.
Only the side holding a majority can keep electing leaders and committing writes. Partitions are surprisingly common, even inside one datacenter, so software must handle them deliberately.
↑ see it in the visualization - Byzantine faults
Nodes that behave arbitrarily: they send corrupted or conflicting messages, or lie on purpose.
Tolerating f such nodes needs n ≥ 3f + 1, compared with 2f + 1 for crash faults. It matters for aerospace and blockchains. In a datacenter, nodes are usually assumed honest, but checksums and input validation still guard against weak forms of lying.
PBFTBitcoinflight computers↑ see it in the visualization - System model
An abstraction of the faults an algorithm must tolerate: timing (synchronous, partially synchronous, asynchronous) × node failures (crash-stop, crash-recovery, Byzantine).
An algorithm is only correct relative to a model. Partially synchronous with crash-recovery is the most realistic for most systems.
↑ see it in the visualization - Safety and liveness
Safety: nothing bad ever happens. Liveness: something good eventually happens.
A safety violation happens at a specific moment and can't be undone, so it must hold in every situation. Liveness may come with caveats, such as only once the network has recovered.
↑ see it in the visualization