DDIA Chapter 8: The Trouble with Distributed Systems

Although we have already discussed many failures, the previous chapters were still too optimistic. Reality is darker. Now we maximize pessimism and assume that anything that can go wrong will go wrong.

Reading source

Faults and Partial Failures

In a distributed system, some parts may fail in unpredictable ways even while the rest works normally. This is called a partial failure. The challenge is that partial failures are nondeterministic: anything involving multiple nodes and a network may work sometimes and fail unpredictably at others.

Cloud Computing and Supercomputers

Two extremes:

High-performance computing (HPC): supercomputers with thousands of CPUs are typically used for computation-intensive scientific tasks, such as weather forecasting or molecular dynamics (simulating the motion of atoms and molecules).
Cloud computing: typically associated with multi-tenant data centers, commodity computers connected by IP networks (usually Ethernet), elastic/on-demand resource allocation, and metered billing.

Traditional enterprise data centers lie between these two extremes.

Unreliable Networks

Most internal networks on the Internet and in data centers (usually Ethernet) are asynchronous packet networks. In such a network, one node can send a message (a packet) to another, but the network cannot guarantee whether or when it will arrive. If you send a request and expect a response, many things can go wrong.

The request may be lost (perhaps someone unplugged a network cable).
The request may be queued and delivered later (perhaps the network or recipient is overloaded).
The remote node may have failed (perhaps crashed or shut down).
The remote node may have temporarily stopped responding (perhaps due to a long garbage-collection pause), but may respond later.
The remote node may have processed the request, but the response may be lost on the network (perhaps due to a misconfigured switch).
The remote node may have processed the request, but the response may be delayed and delivered later (perhaps the network or your own machine is overloaded).

The usual way to handle this is a timeout: give up waiting after some time and assume the response will not arrive. But when a timeout occurs, you still do not know whether the remote node received the request. If it is still queued somewhere, it may reach the recipient even after the sender has given up.

Detecting Faults

Many systems need to detect failed nodes automatically. For example:

A load balancer must stop forwarding requests to a dead node (that is, take it out of rotation).
In a distributed database with single-leader replication, if the leader fails, one replica must be promoted to the new leader.

Unfortunately, network uncertainty makes it difficult to judge whether a node is functioning. In some specific situations, you do get useful signals.

If you can reach the machine running a node but no process is listening on the target port (for example, because the process crashed), the operating system closes and reuses the TCP connection by sending FIN or RST. But if the node crashes while processing a request, you cannot know how much data it actually processed.
If the node process crashes (or an administrator kills it) while the node’s operating system is still running, a script can notify other nodes, allowing another node to take over quickly without waiting for a timeout.
If you can access a data-center network switch’s management interface, you can query it for hardware-level link failures (for example, whether a remote machine has lost power). This option disappears if you connect over the Internet, share a data center without switch access, or cannot reach the management interface because of network problems.
If a router confirms that the IP address you are trying to reach is unavailable, it may reply with an ICMP destination-unreachable packet. But routers have no magical failure-detection ability; they face the same limits as other network participants.

Timeouts and Unbounded Delays

So how long should a timeout wait? Unfortunately, there is no answer.

Long timeouts mean a long wait before a node is declared dead; during that time, users may have to wait or see error messages.

Short timeouts detect failures more quickly, but raise the risk of falsely declaring a node failed when it merely experienced a temporary slowdown, such as a load spike on the node or network. This can, for example, cause an email to be sent twice.

TCP performs flow control (also called congestion avoidance or backpressure), in which nodes limit their sending rate to avoid overloading network links or receiving nodes. That means extra queuing at the sender before data even enters the network.

For this reason, some latency-sensitive applications, such as video conferencing and Voice over IP (VoIP), use UDP rather than TCP. This trades reliability for lower latency variability: UDP does not perform flow control or retransmit lost packets.

Synchronous vs. Asynchronous Networks

Bounded delay: in a circuit-switched telephone network, bandwidth for a call is reserved at every hop. Because no other traffic can use that capacity and packets do not queue, the maximum end-to-end delay is fixed.

Circuits in telephone networks differ greatly from TCP connections: a circuit is a fixed amount of reserved bandwidth that no one else may use while it exists, whereas TCP packets use any available network bandwidth opportunistically. You can give TCP a variable-size block of data, such as an email or web page, and it transmits it as quickly as it can. An idle TCP connection uses no bandwidth.

If resources are statically partitioned—for example, dedicated hardware and dedicated bandwidth allocation—latency guarantees are possible in some environments. But that comes at the cost of lower utilization; in other words, it is more expensive. Multi-tenancy with dynamic resource allocation has better utilization, so it is cheaper, but suffers from variable latency.

Telephone switches use static partitioning; the Internet dynamically shares network bandwidth.

Variable network delay is not a law of nature; it is simply the result of a cost-benefit trade-off.

Unreliable Clocks

Every machine on a network has its own clock, a real hardware device usually based on a quartz crystal oscillator. These devices are not perfectly accurate, so each machine has its own idea of time, potentially a little faster or slower than others. Clocks can be synchronized to some degree: the most common mechanism is the Network Time Protocol (NTP), which adjusts a computer clock according to time reported by a set of servers. Those servers obtain time from more precise sources such as GPS receivers.

Monotonic Clocks and Time-of-Day Clocks

The time-of-day clock is also called wall-clock time. It is usually synchronized with NTP; examples include Linux’s clock_gettime(CLOCK_REALTIME) and Java’s System.currentTimeMillis().

A monotonic clock measures durations (time intervals), such as timeouts or service response times. Linux’s clock_gettime(CLOCK_MONOTONIC) and Java’s System.nanoTime() are monotonic clocks. The name comes from their guarantee to always move forward, whereas a time-of-day clock can jump backward.

The absolute value of a monotonic clock is meaningless: it may be nanoseconds since the computer booted. In particular, comparing monotonic-clock values from two different computers is meaningless because they are not the same thing.

In distributed systems, using a monotonic clock to measure elapsed time, such as a timeout, is usually sound because it assumes no synchronization between the clocks of different nodes and is insensitive to small measurement inaccuracies.

Clock Synchronization and Accuracy

Quartz clocks in computers are not accurate enough: they drift, running faster or slower than expected. Clock drift depends on the machine’s temperature. Google assumes a server clock drift of 200 ppm (parts per million), equivalent to 6 ms of drift when resynchronizing every 30 seconds, or 17 seconds when resynchronizing daily. Even when everything works normally, this drift limits the best achievable accuracy.

If a computer’s clock differs too much from an NTP server’s clock, synchronization may be refused or the local clock may be forcibly reset.
If a node is accidentally blocked from its NTP servers, it may ignore a bad configuration for some time.
NTP synchronization is only as good as network latency, so its accuracy is limited on a congested network with variable packet delays. Large network delays can make an NTP client give up entirely.
Some NTP servers are broken or misconfigured and report a time hours in the past. NTP clients are robust because they query multiple servers and ignore outliers.
The best way to handle leap seconds may be to gradually apply the adjustment across a day, called smearing.
In a virtual machine, hardware clocks are virtualized, creating extra challenges for applications that need precise timing. When a CPU core is shared among VMs, each VM may pause for tens of milliseconds while another runs. From the application’s perspective, this looks like the clock suddenly jumping forward.
If you run software on a device you do not fully control, such as a mobile or embedded device, you cannot trust its hardware clock.

Timestamps for Ordered Events

Last write wins (LWW) is widely used in multi-leader replication and leaderless databases. Clients use timestamps rather than arrival order to determine which value wins.

Logical clocks are based on incrementing counters rather than oscillating quartz crystals, making them a safer choice for ordering events. A logical clock measures neither time of day nor elapsed seconds, only the relative order of events.

Both the time-of-day clock and the monotonic clock are physical clocks: the former reports calendar time, while the latter measures elapsed duration.

Clock Readings Have a Confidence Interval

A machine’s clock is likely inaccurate. Using public Internet NTP servers, the best accuracy may be tens of milliseconds, and errors can exceed 100 milliseconds when the network is congested.

A confidence interval is [earliest time, latest time], reflecting time deviations caused by machine error. Most systems do not expose this uncertainty.

Synchronized Clocks for Global Snapshots

Only when intervals overlap are we uncertain about whether A or B happened first.

To ensure transaction timestamps reflect causality, Spanner deliberately waits for the duration of the confidence interval before committing a read-write transaction. This ensures that any transaction that might read the data is far enough in the future for its confidence interval not to overlap. To keep this wait as short as possible, Spanner needs clock uncertainty to be very small; Google deploys a GPS receiver or atomic clock in every data center, allowing clocks to synchronize to within about 7 milliseconds.

Process Pauses

Suppose you have a database with one leader per partition. Only the leader may accept writes. How can a node know that it is the leader—not declared dead by someone else—and that it can safely accept writes?

The leader obtains a lease from other nodes, similar to a lock with a timeout. Only one node may hold the lease at any moment, so when a node obtains one, it knows it is leader for a period until the lease expires. To remain leader, it must renew the lease periodically before expiry.

If the node fails, it stops renewing, so another node can take over when the lease expires.

This approach has several hazards:

The lease-expiration time is set by another machine but compared against the local clock, which may not be synchronized.
The actual task may run for a long time and outlast the lease.

Threads can pause for a long time for many reasons:

A programming language’s garbage collector occasionally stops every thread, potentially for minutes.
In a virtualized environment, a VM can be suspended (pausing all processes and saving memory to disk) and resumed (restoring it and continuing execution). The pause duration depends on the rate of memory writes.
On a laptop, execution may pause and resume arbitrarily, such as when the lid is closed.
When the operating system context-switches to another thread, or the hypervisor switches to another VM, the currently running thread can be paused at any point in the code.
If an application performs synchronous disk access, a thread may pause while waiting for a slow disk I/O operation to complete.
If the operating system allows swapping to disk (paging), a simple memory access can trigger a page fault, requiring a disk page to load into memory. The thread pauses during that slow I/O operation.
A Unix process can be paused by a SIGSTOP signal, for example by pressing Ctrl-Z in a shell. The signal immediately prevents further CPU cycles until SIGCONT resumes it. Even if your environment does not normally use SIGSTOP, an operations engineer may send it accidentally.

Response-Time Guarantees

Hard real-time systems: some software environments have strict requirements, and failing to respond within a specified time can cause severe loss.

Truth Is Defined by the Majority

If a quorum of nodes declares another node dead, that node must be considered dead even if it still believes itself alive. Individual nodes must respect the quorum’s decision and step down.

Leaders and Locks

Usually, some things can exist only once in a system. For example:

A database partition can have only one leader node, to avoid split brain.
A lock on a particular resource or object may be held by only one transaction/client, to prevent concurrent writes and corruption.
A particular username may be registered by only one user because it must uniquely identify that user.

If a client holding a lease pauses for too long, its lease expires. Another client can obtain a lease for the same file and begin writing it. When the paused client returns, it believes it still has a valid lease and continues writing. The clients’ writes then conflict and corrupt the file.

The solution is to assume that whenever a lock server grants a lock or lease, it also returns a fencing token—a number incremented with every grant, for example by the locking service. We then require clients to include the current fencing token in every write request to the storage service.

Client 1 obtains a lease with token 33, then enters a long pause and its lease expires. Client 2 obtains a lease with token 34—the number always increases—and sends a write request to storage including token 34. Later, client 1 resumes and sends its write including token 33. But the storage server remembers that it has processed a write with the higher token number, 34, so it rejects the request carrying token 33.

Byzantine Faults

If nodes might “lie”—send arbitrary erroneous or corrupted responses—distributed systems become harder. For example, a node might claim it never received a particular message. This behavior is called a Byzantine fault, and the problem of reaching consensus in an untrusted environment is called the Byzantine Generals Problem.

A system is Byzantine fault-tolerant when it continues working correctly despite some nodes failing, violating the protocol, or even attacking maliciously and disrupting the network. This concern is meaningful in certain contexts, such as aerospace systems.

System Models and Reality

Synchronous model

Assume that network delay, process pauses, and clock error are all bounded. This does not mean perfectly synchronized clocks or zero network delay; it means you know that network delay, pauses, and clock drift will never exceed a fixed upper bound. The synchronous model is not the real-world model for most systems because unbounded delays and pauses do happen.

Partially synchronous model

This means a system behaves like a synchronous system most of the time, but occasionally exceeds the bounds on network delay, process pauses, and clock drift. It is the real-world model for many systems: networks and processes behave well most of the time, or we would never get anything done, but we must acknowledge that these assumptions can break at any time. When that happens, network delay, pauses, and clock error can become quite large.

Asynchronous model

In this model, an algorithm may make no assumptions about timing—it does not even have a clock, so it cannot use timeouts. Some algorithms are designed for the asynchronous model, but they are highly constrained.

The three most common node-failure system models are:

Crash-stop failure: an algorithm may assume a node can fail only by crashing. The node may stop responding suddenly at any time and then disappears forever—it never returns.
Crash-recovery failure: a node may crash at any time but may begin responding again after an unknown period. In the crash-recovery model, a node is assumed to have stable storage (nonvolatile disk storage) that survives a crash, while in-memory state is lost.
Byzantine (arbitrary) failure: a node can do anything in the literal sense, including trying to trick and deceive other nodes.

If we are generating fencing tokens for a lock, we require the algorithm to have these properties:

Uniqueness: no two fencing-token requests return the same value.
Monotonic sequence: if request $x$ returns token $t_x$, request $y$ returns $t_y$, and $x$ finishes before $y$ begins, then $t_x < t_y$.
Availability: a node that requests a fencing token and does not crash eventually receives a response.

Safety and liveness: in the example above, uniqueness and monotonic sequence are safety properties, while availability is a liveness property.

Safety is commonly defined informally as nothing bad happens, while liveness is something good eventually happens.