دردسرهای سیستم‌های توزیع‌شدهThe Trouble with Distributed Systems

A program on a healthy single computer is deterministic: every run of an operation gives the same result. Broken hardware usually kills everything at once (kernel panic) — no ambiguity. But with several machines joined by a network, part of the system may be broken while the rest is fine; that's partial failure, and worse, it's non-deterministic: the same operation sometimes succeeds, sometimes not.

The good news: this same fault tolerance enables rolling upgrades — restarting nodes one by one without downtime. Unreliable parts can build a reliable system — provided you first know exactly what can break. The systems in this book are mostly shared-nothing: machines with independent memory and disk that talk only over the network.

Ethernet and internet networks are asynchronous packet networks: no guarantee about delivery time — or delivery at all. Send a request, get no reply, and six indistinguishable things may have happened:

• Your request was lost in the network (someone pulled the cable).
• The request is queued and arrives later (network or receiver busy).
• The destination node crashed or is powered off.
• The node is temporarily unresponsive (e.g. a long GC pause) but comes back later.
• The node applied the request but the reply was lost in the network.
• The node applied it and the reply is on its way — just late.

Your only information: “no reply yet.” Even the sender can't know whether the packet arrived; only the receiver can report back, and that report may be lost too. So a timeout is a guess, not proof of failure — and the “abandoned” request may still arrive later!

TCP is famous for “reliable delivery”: it retransmits lost packets, reorders shuffled ones, catches data corruption with checksums and throttles send rate with congestion control. But that “reliability” doesn't fix our problem:

• TCP can't tell a lost outbound packet from a lost returning acknowledgment; it just resends, and a pulled cable defeats it entirely.
• Dedup works only inside one connection; if the connection drops and the app reconnects and resends, data may duplicate.
• If a connection closes with an error, you can't know exactly how far the destination processed.
• Even an ACK only means “the destination OS kernel got it”, not “the application did it”; for certainty you need the application's own explicit reply.
• Retransmission delay shows up to the user as latency, not an explicit error.

You'd think decades made networks reliable; studies say otherwise. One mid-size datacenter logged ~12 network failures a month (half killing one machine, half a whole rack). Adding redundant gear helps less than expected, because human error (misconfigured switches) is the main failure path. WAN fiber cuts were dealt by cows, beavers, even sharks (!), and cross-region cloud round-trips reached minutes at high percentiles.

Stranger cases: asymmetric links (A talks to B, B to C, but A not to C), NICs silently dropping only inbound packets, and short outages whose effects linger far longer than the outage. So any network link can fail; no escape. And “tolerating” needn't mean “keeping going”: showing the user an error is a valid strategy — provided you know how your software reacts and that it recovers once fixed.

The main source of delay variance is queueing — exactly like street traffic:

• Several machines sending to one destination at once make the switch queue packets; a full queue drops packets, which must be resent.
• Arriving at the destination with all CPUs busy, the request waits in the kernel queue — unknown delay.
• In virtual environments a VM may pause tens of milliseconds while packets pile in the hypervisor buffer.
• TCP itself throttles sending to protect the network (backpressure).
• On multi-tenant clouds a noisy neighbor grabs shared resources and jitters latency.

Many systems must detect dead nodes automatically (a load balancer cutting it out, a follower taking the leader's place). Sometimes you get explicit feedback: an RST/FIN reply when nothing listens, a crash-notification script (like HBase's), switch management, or an ICMP Destination Unreachable. But none is reliable; in practice assume no reply ever comes and declare the node “dead” after a timeout.

The book's fantasy assumption: if the network guaranteed max delay d and processing max r, a sane timeout would be 2d + r. But real networks have unbounded delay and servers guarantee no time ceiling; so timeouts have no “correct” value and must be measured empirically: observe the RTT distribution over time, then balance detection speed against premature-declaration risk.

Combining “timeout means nothing” with “the service must return” gives every network request a dangerous state: outcome unknown. Three choices there: retry, give up, or learn the state another way. The diagram below is one request's full state machine.

After a timeout, decide structurally instead of guessing. The tree below shows the thinking order: first ask whether the operation is safely repeatable at all, then whether you can read its state, and if not, whether your write needs a guard.

Programs use clocks for two kinds of questions: durations (how many seconds did this request take?) and points in time (when was this article published?). In a distributed system each machine has its own quartz clock differing from the rest, and inter-machine links aren't instant; so “event order” scrambles easily.

Modern computers have at least two clocks: time-of-day (wall clock, e.g. System.currentTimeMillis) and monotonic (stopwatch, e.g. System.nanoTime). But ordering in distributed systems offers two more options: the logical clock and the uncertainty-interval clock. The diagram below lines all four up like a UML class diagram.

• Ordinary quartz drifts up to ~200 ppm (≈ 17 seconds a day at one sync per day); temperature affects drift too.
• A machine clock far from the NTP server may be forcibly reset, and the app sees time jump back!
• One wrong firewall rule can cut NTP and nobody notices for ages; drift quietly accumulates.
• Public-internet NTP error is tens of milliseconds, over 100ms when busy; some NTP servers misreport too.
• A leap second makes a 59- or 61-second minute and breaks unprepared systems (practical fix: “smearing” the correction gradually). No more leap seconds after 2035.
• On a VM, a pause looks to the app like a sudden time jump, and the in-VM NTP client never learns.
• On unmanaged devices (the user's phone) never trust the hardware clock — some users shift it on purpose!

The most dangerous temptation: ordering writes by timestamp. In last-write-wins (LWW), the write with the greatest timestamp wins. If two nodes' clocks skew slightly, a “newer” write may carry a smaller timestamp and vanish forever.

If a clock returns an interval instead of a number ([earliest, latest]), we can reason: non-overlapping intervals of two events mean their order is certain; only overlapping intervals leave us unsure which came first. Google Spanner's TrueTime and Amazon's ClockBound give exactly this. So a transaction's timestamp can't violate causality, Spanner waits out the interval's width (commit wait) — with GPS and atomic clocks in every datacenter shrinking the width to ~7ms.

Suppose each shard has one leader and only the leader may write. How does it stay sure it's still leader? The usual answer is a lease: a lock with a timeout that must be renewed before expiry. Now look at this code:

It has two flaws: first it leans on a synchronized clock (expiry set by another machine, compared against the local clock); second and more importantly, it assumes little time passes between checking the clock and processing the request. Now imagine that thread pauses for 15 seconds: the lease expires, another node becomes leader, and when the thread wakes it never knew it slept — executing the same unsafe request.

Real causes of such pauses are far from rare:

• GC: “stop-the-world” pauses of old JVMs reached minutes; modern GCs are better but still noticeable.
• Live VM migration: arbitrary stalls of unknown length.
• context switch and hypervisor steal time; under heavy load thread queues run long.
• Synchronous I/O, page faults and swap; under memory pressure the system thrashes.
• A SIGSTOP signal (e.g. an ops engineer's mistaken Ctrl-Z).

An old lease holder that hasn't realized its lease ended and keeps writing is called a zombie. Two famous book scenarios (both really happened in HBase): (1) client 1 pauses, the lease expires, client 2 writes, then client 1 returns and writes the same file; (2) client 1 dies but its write request sticks in the network and arrives only after the lease moved on. Both leave two writers interleaving and corrupt data.

The naive fix (killing the zombie over the network or via the hypervisor) isn't enough: it doesn't guard against scenario (2)'s long delay, everyone may kill everyone at once, and by the time the zombie is found the data is corrupt. The right fix is a fencing token: every lock grant carries an increasing number, and the storage service accepts only writes whose token exceeds the last accepted one.

The rule is simple: every storage write must carry the writer's current token, and storage remembers the greatest token seen. The diagram below retells Figure 9-6 of the book.

The book's nightmare scenario: a node can receive every message while its outbound messages get lost. Everyone declares it dead after timeouts while it screams “I'm not dead!” — and nobody hears. Or: a node pauses a minute, everyone buries it, then it returns healthy and surprised!

The lesson: no node may trust its own judgment. So distributed algorithms lean on quorum (voting among nodes): decisions need a minimum of votes. Usually an absolute majority (over half) — 3 nodes tolerate 1 failure, 5 nodes tolerate 2. And crucially: two contradictory majorities can't exist at once. If a quorum declares you dead, step aside even if you're alive.

So far we assumed nodes are unreliable but honest: they may be slow or silent, but their answers never lie. If nodes can lie (forged messages, conflicting votes), the problem becomes the “Byzantine generals” — far harder.

• Where truly needed: flight control (memory damage by radiation), multi-party systems with hostile sides (blockchain).
• Where not: your own datacenter with controlled nodes — Byzantine protocols are expensive and usually impractical.
• If the bug is in the software and all nodes run the same version, Byzantine tolerance won't save you; that needs several independent implementations.
• Against attackers, authentication, encryption and firewalls remain the main shield.
• Take weak forms of lying seriously: app-layer checksums, input validation, and multi-server NTP clients dropping outliers.

To talk about an algorithm's “correctness” we must first write down its assumed world: the system model. The model has two dimensions: timing assumptions (synchronous, partially synchronous, asynchronous) and failure assumptions (crash-stop, crash-recovery, partial slowness, Byzantine). The diagram below maps this space like a class diagram.

With this many possible states, how do we know our algorithm is right? The book's answer: combine theoretical analysis with empirical testing. Neither alone suffices.

• ❌ “timeout means the server is broken.” → ✅ timeout only means “no reply arrived in this window”; the write may have applied.
• ❌ “TCP delivers reliably, so no duplicates.” → ✅ after reconnects and app-level retransmits, repeats are fully possible.
• ❌ “We sync clocks with NTP, so timestamps are valid.” → ✅ skew always exists and NTP errs too; LWW can silently drop data.
• ❌ “We use a distributed lock, so there's exactly one writer.” → ✅ without fencing, a zombie can write concurrently.
• ❌ “nondeterminism is only about race conditions.” → ✅ network delay, pauses and clock jumps are nondeterminism too.
• ❌ “For safety we retry without limit.” → ✅ retries need a budget and backoff, or they become the attack.
• ❌ “The system tolerates faults, so it tolerates network faults.” → ✅ say explicitly which faults and by what measure (f nodes? how many zones?).
• ❌ “We use the monotonic clock to order events.” → ✅ monotonic is meaningful on one machine only.

1. Name the three confusion sources: network, clocks, process pauses.
2. Review the six “no reply” states and say why they're indistinguishable.
3. Draw Diagram 2 from memory: Sent → Awaiting → (Confirmed | Timed Out) → Retry → (Deduplicated | Duplicate).
4. State the fencing rule: 33 < 34, and storage decides.
5. The two clocks' difference and uses + why timestamps are dangerous for ordering.
6. Define safety and liveness, and which one eventual consistency is (liveness).
7. The realistic system model: partially synchronous + crash-recovery.
8. One sentence on idempotency and one on quorum.