Designing Data-Intensive Applications, session 11

The trouble with
distributed systems

Anything that can go wrong will. A pessimist’s tour of networks, clocks, and pauses.

→ next · ← back · N notes · F full screen

On one machine, things work or crash. Across machines, they partly fail.

A single computer is deterministic: a bug or crash is total. In a distributed system, some parts break while others keep going, and you often can’t even tell which.

Supercomputers

Checkpoint, and restart the whole job on failure.

Internet services

Must stay up. Build a reliable system from unreliable parts, like TCP over lossy IP.

01

Unreliable networks

You sent a request. No reply. Now what?

No reply can mean six different things.

Request lostRequest queuedRemote node crashedRemote node pausedResponse lostResponse delayed

From the sender’s side they all look identical. The only tool you have is a timeout, and even then you don’t know whether the request ran.

Lab: choosing a timeout

healthy requests wrongly treated as dead
how long a real crash goes unnoticed
02

Unreliable clocks

Every machine has its own idea of now.

Two kinds of clock.

Time-of-day clock
Monotonic clock
System.currentTimeMillis()
System.nanoTime()
Synced with NTP, can jump backwards
Always moves forward
Comparable across machines, roughly
Meaningless across machines
Use for: timestamps people read
Use for: measuring durations and timeouts
200 ppm
typical quartz drift Google assumes
~17 s/day
what that drift adds up to without resync
±ms
realistic NTP accuracy, if the network is kind

Last-write-wins by timestamp drops data silently.

Google Spanner reports a confidence interval [earliest, latest] instead and waits out the uncertainty before committing.

Your process can freeze at any moment.

A lease check that isn’t safe
while (true) {
  request = queue.next();
  if (lease.expiresAt() - now() < 10_000) {
    lease = lease.renew();
  }
  // a 15 s GC pause here, and the
  // lease has expired before we write
  if (lease.isValid()) process(request);
}
Stop-the-world GCVM suspended or migratedLaptop lid closedContext switchesSlow disk I/O, even class loadingSwapping to diskSIGSTOP
03

Knowledge, truth, and lies

A node can’t trust its own judgment.

Fencing tokens make leases safe.

A node that’s been declared dead by a majority must step down, even if it feels fine.

Byzantine faults and system models.

Byzantine faults

Nodes that lie. Relevant for aerospace and blockchains. Inside our own datacenter we generally assume nodes are honest but unreliable.

Cheap defences

Checksums against corrupted packets, input validation, multiple NTP servers.

Safety vs liveness

Safety: nothing bad ever happens (no duplicate fencing tokens). Liveness: something good eventually happens (a request gets an answer).

Now, our system.

Unknown outcomes

When a call to a bank or payment provider times out, what do we do? Can we safely retry without paying twice?

Clock-based cut-offs

Settlement windows and cut-off times depend on clocks. Which server’s clock decides, and what if it’s off by a few seconds?

Durations

Do we measure durations or timeouts with currentTimeMillis anywhere?

Scheduled job locks

Our scheduled jobs use locks to run once. If an instance pauses past its lock, can two runs overlap? Do we fence?

Next session

Consistency and ordering

Linearizability, causality, Lamport clocks, and total order broadcast. Chapter 9.