Faults and Partial Failures

Why a distributed system can be half broken, why a missing reply tells you almost nothing, and the tools that keep it correct anyway: timeouts, retries with idempotency keys, circuit breakers and fencing tokens.

Overview

A program on one computer either works or it stops. A distributed system can do something worse: part of it can fail while the rest keeps running. This is a partial failure, and it is the reason distributed systems are hard.

One machine against many

On a single machine, a hardware fault usually stops the whole machine, so a bug shows up as a crash you can see. In a distributed system, one node can be down, slow or cut off while others are healthy. Worse, the working nodes often cannot tell which of these happened.

When something breaks — Usually the whole program stops — One part fails; the rest keeps going
Can you see the failure? — Yes: a crash or an error — Often not: you just hear nothing
Same input, same result? — Yes, nearly always — No: timing and lost messages change the outcome
How you design — Assume it works; handle crashes — Assume anything can fail at any moment

A missing reply tells you almost nothing

When node A sends a request to node B and hears nothing back, there are many possible causes. A cannot tell them apart. Some of them mean the request was never done; others mean it was done and only the reply was lost.

The only tool the caller has is a timeout: wait a while, then assume something went wrong. A timeout does not tell you what went wrong, and it cannot tell you whether the work happened. Everything else in this chapter follows from that.

Networks really do fail

Most data center networks are asynchronous: a packet can be delayed for any length of time, dropped, or duplicated, and nothing puts an upper bound on the delay. Engineers at Sun summed up the wrong assumptions people make in the fallacies of distributed computing: L Peter Deutsch drafted seven in 1994, and James Gosling added the eighth in 1997.

The network is reliable — Packets and links are lost; partitions happen
Latency is zero — Every call has a delay, and the delay varies
Bandwidth is infinite — Large transfers queue up and slow everyone
The network is secure — Traffic can be read or forged
Topology does not change — Nodes, routes and addresses change all the time
There is one administrator — Many teams and providers own parts of the path
Transport cost is zero — Moving data costs time, CPU and money
The network is homogeneous — Different hardware, software and protocols meet

These failures are common in practice. Peter Bailis and Kyle Kingsbury collected published reports in 2013. One study of Microsoft data centers they cite found an average of 5.2 device failures and 40.8 link failures per day. Google reported that its Chubby lock service had 61 outages over 700 days, 9 of them longer than 30 seconds.

Timeouts: too short or too long

A timeout trades two risks. If it is short, you notice a dead node quickly, but you also declare healthy nodes dead when they are only slow. If it is long, you rarely make that mistake, but callers wait and hold resources while a node is really down.

Short — Fast detection; callers free up soon — Slow but healthy nodes are declared dead; failover may start for nothing
Long — Few false alarms — Threads and connections are held for a long time; users wait

A common way to choose is to measure the real response times of the dependency and set the timeout a little above a high percentile, such as the p99.9, so only rare, truly stuck calls hit it. Declaring a node dead has a cost too: its work moves to other nodes, which adds load exactly when the system may already be overloaded.

Retries, backoff and idempotency

After a timeout, the usual move is to retry. Two things can go wrong. First, if the first attempt actually succeeded, a retry does the work twice. Second, if many clients retry at once, they add load to a service that is already struggling.

The fix for the first problem is idempotency: an operation you can apply twice with the same effect as once. Stripe's API does this with an Idempotency-Key header. The server saves the status and body of the first response for a key, and returns the same saved response for any retry with that key. Stripe may prune keys once they are at least 24 hours old, and it rejects a retry whose parameters differ from the original.

The fix for the second problem is exponential backoff with jitter: wait longer after each failure, and pick a random wait so clients do not retry in lockstep. Marc Brooker's AWS article compares the options and recommends 'full jitter': sleep a random time between zero and min(cap, base * 2^attempt).

It is safest to retry at one layer only. If three layers each retry three times, one user request can turn into 27 calls to the bottom service.

Circuit breakers

A circuit breaker stops calls to a dependency that keeps failing, so callers fail fast instead of waiting on timeouts. Martin Fowler describes three states.

While the breaker is open, return a fallback if you have one: a cached value, a default, or a clear error. This is graceful degradation: the page still loads, without the part that is broken.

Paused processes and fencing tokens

A node can stop for a while without crashing. A stop-the-world garbage collection pause, a virtual machine being moved, or the operating system swapping memory to disk can freeze a process. When it resumes, it does not know that time has passed.

This breaks locks and leases. Martin Kleppmann describes the case: a client gets a lock with a time limit, then pauses. The lock expires and another client takes it. The first client wakes up, still believes it holds the lock, and writes. Now two clients write at once.

The fix is a fencing token: a number that goes up every time the lock is granted. The client sends the token with every write, and the storage rejects any write whose token is lower than one it has already seen. Kleppmann notes that ZooKeeper's zxid or a znode version number can serve as the token.

The lesson is general: a node cannot trust its own view of the world. A decision such as 'I am the leader' or 'I hold the lock' must come from a quorum, a majority of nodes, and the resources it touches must check it.

Fault models

To reason about an algorithm, you state which faults it must survive. The usual models, from weakest to strongest assumption about misbehavior, are these.

Crash-stop — Stops and never comes back — Replication, failover
Crash-recovery — Stops, then restarts with what it saved to disk — Write-ahead logs, Raft, Paxos
Byzantine — Anything: lies, sends conflicting messages — Byzantine fault-tolerant protocols

Most databases and coordination services assume crash-recovery faults and trust their own nodes. Byzantine tolerance is expensive: Lamport, Shostak and Pease showed in 1982 that with oral messages you need more than two-thirds of the nodes to be honest, so tolerating m traitors takes at least 3m + 1 nodes. It is used where parties do not trust each other, such as some blockchains, and rarely inside one company's data center.

What you will be able to do

Explain why a timeout cannot tell you whether a remote operation happened.
Choose a timeout and a retry policy, and say what each choice costs.
Make a retried operation safe with an idempotency key.
Explain how a process pause breaks a lock, and how a fencing token fixes it.
Name the fault model a system assumes and why Byzantine tolerance is rare.

Key concepts

Partial failure: Some parts of a system fail while others keep working, and the working parts may not know it. Absent on one machine, normal on many.
Asynchronous network: A network with no upper bound on how long a message can take. Most data center and internet networks behave this way.
Timeout: How long a caller waits before assuming a failure. It bounds waiting, but cannot say whether the work happened.
Idempotency key: A unique ID the client sends with a request so the server can recognize a retry and return the saved result instead of doing the work again.
Exponential backoff with jitter: Waiting longer after each failed attempt, with a random part, so many clients do not retry at the same moment.
Circuit breaker: A wrapper that stops calling a dependency after repeated failures, then lets a trial call through after a reset timeout.
Fencing token: A number that increases each time a lock is granted. Storage rejects writes carrying a lower number than it has already seen.
Byzantine fault: A node that behaves arbitrarily, including lying. Tolerating m such nodes takes at least 3m + 1 nodes.

When to use it

Adding timeouts, retries and circuit breakers to calls between services
Making payments, orders or any other side effect safe to retry
Designing leader election, locks or leases that must survive pauses
Explaining in an interview why distributed transactions and failover are hard

Interview questions

A call to a payment service times out. What do you do?
How would you choose a timeout for calls to a dependency?
Why can a garbage collection pause break a distributed lock, and how do you fix it?
What is a circuit breaker, and when does it help?
Why do most systems ignore Byzantine faults?