Fault tolerance

Fault tolerance is a system’s ability to keep giving correct service while some of its parts are broken. Disks die, processes crash, switches drop packets and bugs fire on odd inputs; at scale that happens daily. Fault tolerance stops those faults before users notice, with redundancy for a spare, detection to notice, containment to limit the spread and recovery to get back to a correct state.

Picture it first: the wedding kitchen

A caterer is cooking for 800 wedding guests. One cook misreads the recipe card and adds salt by the tablespoon. Nothing tastes wrong until he cooks; then one pot of dal turns salty. If it reaches the buffet, guests notice.

Three different things happened, and a good caterer guards each:

• The fault is the misread card. Bigger print helps, but some mistake always slips through.
• The error is the salty pot, wrong but still inside the kitchen. A taster catches it (detection) and sets it aside (containment).
• The failure would be guests eating it. It never happens, because a second pot was cooking alongside (redundancy), or the cook dilutes and re-seasons (forward recovery), or starts again from raw ingredients (backward recovery).

Zoom out: if the caterer as a whole serves a bad meal, that is a fault for the wedding family, who may keep a sweet shop on standby. One system’s failure is the next system’s fault.

Map it back: cooks are processes and disks, the pot is state in memory or on disk, the taster is a checksum or health check, the second pot is a replica, and the buffet is your API.

Fault, error, failure

The standard vocabulary comes from Avižienis, Laprie, Randell and Landwehr’s 2004 paper “Basic Concepts and Taxonomy of Dependable and Secure Computing”. Each word points to a different defence.

• A failure is an event: the service a user receives deviates from correct service. Wrong, missing and too-late answers all count.
• An error is the part of the system’s state that may lead to a failure: a corrupt block, a wrong balance in memory. Many errors never reach the interface.
• A fault is the adjudged or hypothesised cause of an error: a bug, a worn disk, a flipped bit, a bad config value. It stays dormant until activated, the way a bug sleeps until its triggering input arrives.

The chain crosses boundaries. When an error reaches component A’s interface, A fails, and that failure reaches B, which depends on A, as an external fault. A disk’s failure is a fault for the storage server; the storage server’s failure is a fault for the database above it.

The paper sorts what you can do about faults into four means: prevention (stop faults being introduced), tolerance (avoid failures in the presence of faults), removal (find and fix them) and forecasting (estimate how many exist and what they will cost). Tolerance works by error detection plus recovery, against a fault assumption (the faults you designed for), with some coverage (the probability it works when a fault occurs). Coverage leaks when components misbehave in ways you didn’t assume (garbage instead of a crash), or when failures you assumed independent arrive together (two replicas taking one bad config): the shared fate behind hidden single points of failure.

Fault tolerance and its neighbours

These four terms overlap, but they answer different questions.

Availability is an outcome you measure (the nines, SLOs); fault tolerance is one way to earn it. Fast recovery can also buy availability, and a crash-tolerant system still goes down when an unassumed fault, such as a slow disk, arrives.

Fault models: what are you tolerating?

Every mechanism is built for a fault model, a statement of how components may misbehave. From mildest to worst:

• Crash-stop: a node halts for good. If others always detect it, that is fail-stop.
• Crash-recovery: a node halts and restarts with what it made durable, nothing from memory. Most servers work this way, hence write-ahead logs.
• Omission: a node or link silently drops messages.
• Timing: the right answer, too late, as with a GC pause or a crawling disk. Over a network, late and lost look the same until a timeout decides.
• Byzantine: anything at all, including wrong or inconsistent answers, from corrupt memory or a buggy or compromised node.

Faults also differ in duration. Transient ones strike once and a retry fixes them; permanent ones need a replacement, because retries just repeat the failure; intermittent ones come and go and are the hardest to diagnose.

What each model costs

The worse the behaviour you assume, the more replicas you need to survive f faulty ones.

The f + 1 row hides its catch: you must always tell dead from slow, which no asynchronous network promises, or two primaries run at once (failover covers fencing). Majority quorums drop that need. With 2f + 1 replicas, f can be down and f + 1 still form a majority, and any two majorities share a node, so a new leader always meets someone who saw the last committed write (consensus and leader election).

The Byzantine bound comes from Lamport, Shostak and Pease’s 1982 paper: with unsigned messages, the loyal generals can agree only if more than two-thirds are loyal, so one traitor can confound two loyal generals. With quorums of 2f + 1 out of 3f + 1, two quorums share at least (2f + 1) + (2f + 1) − (3f + 1) = f + 1 nodes, so at least one of them is honest. The paper also shows that unforgeable signatures allow agreement with any number of traitors.

Shrink the fault model instead of paying for it

Most data-centre systems assume crashes, since you run every machine and Byzantine tolerance is expensive. They keep that assumption honest by turning worse faults into milder ones: a checksum turns silent corruption into a detected loss, a timeout turns slow into failed, fencing stops a zombie leader, and an assertion turns impossible state into a clean crash.

Gray failure and fail-slow

Textbook redundancy assumes a component is either working or stopped. In 2017 Huang and colleagues described what they actually met in Azure: gray failure, subtle faults such as severe slowdowns, random packet loss, flaky I/O and non-fatal exceptions that resist quick, definitive detection. In their experience it was behind most cloud incidents.

Its defining trait is differential observability: an app sees the system as unhealthy while the system’s own failure detector sees it as healthy, so recovery never starts. In one case a driver bug broke a VM’s networking, but its heartbeats reached the compute manager through a host agent over local calls, so the VM looked healthy until customers complained.

Gray failure can turn redundancy against you. If a request fans out to m back-ends across n core switches, the chance it crosses one particular switch is 1 − ((n − 1) ÷ n)^m. With n = 4 and m = 20 that is 1 − 0.75^20 ≈ 99.7%: one switch quietly dropping packets slows nearly every request. The paper also shows recovery that kills: a storage manager blind to a server’s capacity problem kept sending it writes until it crashed, rebooted and crashed again, and removing it overloaded its peers into the same fate.

Hardware does this too. Gunawi and colleagues collected 101 fail-slow hardware reports from 12 institutions (FAST 2018): disks at 100 KB/s from vibration, SSDs stalling for seconds on firmware bugs, CPUs at half speed, network cards down to kilobits per second. Pinpointing them took hours to months.

Make failures clean: fail fast on purpose

Your machinery handles crashes well, so turn slow and gray into crisp failures, as the fail-slow paper suggests:

• Timeouts on every remote call, set from the dependency’s p99.9 (timeouts, retries and backoff).
• Health checks that walk the real path: a synthetic request through the port, thread pool and disk users hit (health checks done right).
• Callers as observers: eject back-ends whose clients see them, say, five times slower than their peers.
• Self-checks and watchdogs: exit on impossible state; restart a node that stops responding.
• Skip the optional: bypass a slow cache instead of waiting on it.

The price is false positives: ejecting a merely busy node shifts its load onto peers. Cap how much of a pool can be ejected at once.

Redundancy in space, time and information

All fault tolerance rests on redundancy: something extra that isn’t needed while everything works.

Space helps only when copies fail independently; one build, config push or zone ties them back together. Time is cheapest but multiplies load: 3 attempts at each of 3 layers turn one request into 3 × 3 × 3 = 27 calls on the bottom service, the seed of a retry storm. Information adds bits computed from the data to detect damage (checksums) or repair it (ECC, parity, erasure codes).

Design diversity targets what identical copies can’t survive: a deterministic bug in all of them. The taxonomy notes that identical channels suit physical faults, which strike independently, but design faults need separately built implementations. N-version programming (independent teams, one spec, a majority voter) is costly, and versions can share the spec’s mistakes, so their failures correlate. Cheaper diversity: two payment providers, a simple fallback path, or mixed versions across cells during a rollout.

Replication vs erasure coding

A Reed–Solomon code RS(k, m) splits data into k pieces and adds m parity pieces; any k of the k + m rebuild the whole. It survives m losses at (k + m) ÷ k times the storage:

• 3× replication: 200% overhead, survives 2 losses.
• RS(6,3): 9 pieces per 6 of data, 50% overhead, survives any 3.
• RS(10,4): 40% overhead, survives any 4.

HDFS documents exactly these trade-offs: 200% overhead for 3× replication, and a 6-block file taking 18 blocks replicated but 9 under RS(6,3), its default policy. You pay elsewhere: rebuilding one piece reads six over the network instead of copying one, reads touch several nodes, encoding costs CPU, and RS(6,3) needs at least 9 DataNodes and (6 + 3) ÷ 3 = 3 racks to survive losing a rack. HDFS pitches it for warm and cold data, where extra replicas are rarely read anyway.

Detect, contain, recover

Redundancy gives you a spare. Turning it into tolerance takes three moves.

Detect errors end to end

Saltzer, Reed and Clark’s 1984 end-to-end argument says a check like “the file arrived intact” can be done completely and correctly only at the end points; lower-layer checks are just performance enhancements. Their MIT example: a network checksummed every packet on every hop, but data sat unprotected in gateway memory, and one gateway swapped a byte pair about once per million bytes copied. Owners repaired the corrupted files by hand from old printouts. So compute a checksum where data is created and verify it where it is used, and reconcile a ledger against the bank instead of trusting each hop.

Contain errors behind boundaries

Errors spread until something stops them: process boundaries (a crash takes one process, not the fleet), validation at interfaces (B rejects nonsense from A), bulkheads (a pool per dependency, so one slow bank can’t drain every thread) and cells (a bad deploy hits one slice of customers). The taxonomy calls fault tolerance recursive: voters, health checkers and recovery code fail too.

Recover: go back, go forward, or mask

• Rollback (backward recovery) returns to a saved state and tries again: retry, abort a transaction, restart from a checkpoint, replay a log. It needs no diagnosis but loses work since the checkpoint.
• Rollforward (forward recovery) moves to a new correct state: park a poison message in a dead-letter queue, rebuild a block from parity, refund a debit whose credit failed (sagas). Fast, but application-specific.
• Compensation masks the error with redundancy already in the state: a majority vote, ECC fixing a bit, a quorum read ignoring a stale replica.

Rollback is only as safe as re-execution: a timed-out request may have succeeded, so idempotency keys or conditional writes must stop a retry doing the work twice.

Supervisors and crash-only design

An Erlang/OTP supervisor restarts child processes when they die: just the crashed child (one_for_one), all its siblings (one_for_all), or it and those started after it (rest_for_one). If there are more than intensity restarts in period seconds (defaults 1 and 5), it stops its children and itself and escalates to its parent, so a process that keeps dying for the same reason isn’t restarted forever. Workers skip defensive handling of the unexpected and crash into a known-good restart, the style Erlang programmers call “let it crash”. It works because most production faults are transient.

Candea and Fox’s crash-only software (HotOS 2003) goes further: the only way to stop is to crash and the only way to start is recovery, so recovery code runs constantly and stays tested. Their crash reboots beat clean ones (75 versus 104 seconds for Red Hat 8). It needs state in crash-safe stores, timeouts on every call, and idempotent requests.

Durability: fault tolerance for data

Data faults are often silent: wrong bytes, a lost write the firmware acknowledged, a sector decaying unread. Durable stores layer the techniques above: copies or erasure-coded pieces across zones (data replication); checksums on every read, repairing from another copy; scrubbing cold data for latent errors before a second fault hits the same block; fast repair, since data is lost only if more pieces fail than the code tolerates before repair ends; and versioning and backups for faults that redundancy copies faithfully (disaster recovery).

AWS says S3 Standard is designed for 99.999999999% (eleven nines) durability and 99.99% availability a year, across at least three Availability Zones, surviving the loss of a whole zone, with regular checksum verification and quick repair. Eleven nines is a yearly loss chance of about 10⁻¹¹ per object: store 10 million objects and you expect 10⁷ × 10⁻¹¹ = 10⁻⁴ losses a year, about one object every 10,000 years (blob storage, design an object store).

Going deeper: metastable failures

Some outages outlive their cause. Bronson, Aghayev, Charapko and Zhu (HotOS 2021) call this a metastable failure: a trigger pushes the system into a bad state that persists after the trigger is gone, held there by a sustaining effect, usually work amplification. Goodput stays near zero until a strong push: a big load cut or a restart.

A stable system recovers from any trigger. Above a hidden load threshold it is vulnerable: healthy, possibly for months or years, and more efficient, so many systems run there by choice. A trigger then tips it into the metastable state. The loops usually come from features meant to help, like retries and caches.

Take an illustrative seat-availability service in a tatkal rush. Its database handles 2,000 queries a second; beyond that, latency explodes. The app gives each query 500 ms and retries once. At 10 am, 1,500 requests a second arrive.

• Vulnerable. Retries can double the load, which stays under 2,000 only below 1,000 requests a second. At 1,500 all is fine, one trigger from trouble.
• Trigger. The database stalls for 15 seconds; every query times out and is retried.
• Sustaining loop. The database returns to 1,500 × 2 = 3,000 queries a second, 1.5× capacity. Latency passes 500 ms, every first attempt times out and is retried, and the database stays 100% busy on queries whose callers have given up. Goodput ≈ 0, trigger long gone.
• Way out. Shed load below 1,000 a second, or cap retries at 10% of requests: 1,500 × 1.1 = 1,650 a second fits under 2,000, so the backlog drains.

Other loops from the paper: a lost cache (at a 90% hit rate, losing it is a 10× amplification, and a look-aside cache can’t refill while the app times out), slow error paths (stack traces and logging make failures costlier than successes), and a link-imbalance failure that took over two years to explain and one line to fix.

Fix the loop, not the trigger, because triggers are many: retry budgets with retries at lower priority, small queues and LIFO serving under overload, load shedding, circuit breakers, cheap error paths, and enough capacity to survive an empty cache. Beware optimisations that cut average load and tempt you to hand back capacity.

Testing fault tolerance

A mechanism that never runs is a guess; you can only estimate coverage by causing faults on purpose.

• Fault injection in CI: kill processes, drop and delay packets, fill disks, corrupt bytes, skew clocks, then check invariants.
• Jepsen-style tests: partition, pause and crash nodes under a workload, then check the recorded history for lost acknowledged writes or stale reads.
• Chaos engineering: define steady state as a business metric, inject a real event (kill an instance, add 2 seconds of latency) on a small slice of production, and compare with a control group.
• Game days rehearse the people and runbooks (failover).

Inject gray faults, not just kill -9: a disk at 1 MB/s, 1% packet loss. And test recovery from cold: empty caches and every client reconnecting at once.

Worked example: a UPI-style payment

Walk a design layer by layer: name the likely fault, then how you detect, contain and recover. Assume an illustrative app at 5,000 payments a second, 30 stateless back-end instances in three zones, a three-replica ledger, and banks behind a central switch (design a payment system).

1. Lost reply (omission). The payment succeeds but the reply dies on flaky 4G. The app times out after 10 seconds and retries with the same payment ID, created on the phone before the first attempt, and gets the stored result. Without the ID, a retry is a second payment.
2. Back-end crash. Each instance carries 5,000 ÷ 30 ≈ 167 payments a second; at about a second each, roughly 167 are in flight when one dies. Two failed health checks 5 seconds apart remove it in about 10 seconds, and because payment state lives in the ledger, retries resume elsewhere.
3. Ledger faults. A checksum mismatch on read is repaired from a peer. If the primary dies, majority commit across three zones (2f + 1 = 3) keeps every acknowledged payment.
4. Slow bank (gray). A bank’s API takes 8 seconds while its health check stays green. Callers see p99 and errors climb; a 2-second timeout, a per-bank pool and a circuit breaker protect the other banks. A timed-out debit may have happened, so don’t retry it: mark it pending, check its status, and reverse it if the payee was never credited.
5. Recovery storm. When the bank returns, drain pending status checks from a queue at a fixed rate, with jitter.
6. End to end. Daily reconciliation against bank settlement files catches whatever every layer missed.

Cheat sheet

How to say it in the interview

When asked “how do you make this fault-tolerant?”, walk six steps instead of reciting patterns: fault model → redundancy → detection → containment → recovery → testing, picking tools from the reliability patterns cheat sheet at each step.

“Fault model: crashes of any one machine or zone, plus slow dependencies; checksums catch corruption, and no Byzantine tolerance because we run every machine. Redundancy: stateless services N+1 across three zones, and the ledger on three replicas with majority commit, so one can die without losing an acknowledged payment. Detection: timeouts from each callee’s p99.9, health checks through the real request path, and callers’ error rates. Containment: a bulkhead per dependency and validation at boundaries. Recovery: idempotent retries under a budget, pending states with status checks and reversals, and supervisors restarting crashed workers. And we inject faults, slow ones included, every week.”

Why three replicas and not two? Two survive a crash only if you can always tell dead from slow; otherwise both may act as primary. Three let a majority of two decide, and majorities always share a node, so no acknowledged write is lost. Four add nothing; five tolerate two.

What is a gray failure? A component its own detector calls healthy while users see errors or slowness. Probe the real path, eject outliers by the callers’ view, and let timeouts turn slow into failed.

Your retries made the outage worse. Why? Retries fix transient faults but multiply load in overload, and can sustain a metastable failure after the trigger ends. Retry at one layer, with jittered backoff and a budget of about 10%.

Replication or erasure coding for a photo store? Both: replicate recent, hot photos for fast reads and cheap repair; move older ones to RS(6,3), which halves raw storage (1.5× instead of 3×) and survives three losses instead of two, at the cost of six-block reads per rebuild.

With eleven nines of durability, do you need backups? Yes. Durability guards against the provider losing data, not against your own deletes or bad writes, which it stores faithfully. Use versioning, object locks or a copy in another account.

Where to go next

• Single point of failure: finding what has no spare, and shared fate.
• Failover: detect, decide, promote, redirect, and fencing.
• Reliability patterns cheat sheet: timeouts, retries, breakers, bulkheads and shedding.
• Availability and the nines: what redundancy buys in nines.
• Consensus and leader election: 2f + 1 in practice with Raft and Paxos.
• Backend failure modes: how real components break.
• Backpressure and load shedding: the push that ends a metastable failure.

References and further reading

1. Basic Concepts and Taxonomy of Dependable and Secure Computing (Avižienis, Laprie, Randell and Landwehr, IEEE TDSC, 2004)landwehr.orgFault, error and failure; the chain across components; the four means; rollback, rollforward and compensation; coverage and the fault assumption.
2. The Byzantine Generals Problem (Lamport, Shostak and Pease, ACM TOPLAS, 1982)lamport.azurewebsites.netWith unsigned messages, agreement needs more than two-thirds loyal generals (3m + 1); with unforgeable signed messages, any number of traitors can be tolerated.
3. Gray Failure: The Achilles’ Heel of Cloud-Scale Systems (Huang et al., HotOS 2017)microsoft.comDifferential observability, the Azure VM-heartbeat and storage-manager cases, and the fan-out formula showing how redundancy can hurt.
4. Fail-Slow at Scale: Evidence of Hardware Performance Faults in Large Production Systems (Gunawi et al., FAST 2018)usenix.org101 fail-slow incidents from 12 institutions, their symptoms and long detection times, and the case for converting fail-slow into fail-stop.
5. Metastable Failures in Distributed Systems (Bronson, Aghayev, Charapko and Zhu, HotOS 2021)sigops.orgStable, vulnerable and metastable states; retry, cache and slow-error-path sustaining effects; and the mitigations used in industry.
6. End-to-End Arguments in System Design (Saltzer, Reed and Clark, ACM TOCS, 1984)web.mit.eduWhy correctness checks belong at the end points, and the MIT gateway that swapped a byte pair about once per million bytes.
7. Crash-Only Software (Candea and Fox, HotOS 2003)usenix.orgStop only by crashing, start only by recovering; clean versus crash reboot times; state stores, timeouts, leases and idempotent requests.
8. Erlang/OTP design principles: Supervisor Behaviourgithub.comone_for_one, one_for_all and rest_for_one restarts, and the maximum restart intensity (default 1 restart in 5 seconds) that escalates to the parent.
9. Apache Hadoop: HDFS Erasure Codinghadoop.apache.org3× replication’s 200% overhead, the 18-versus-9-block example, RS(6,3) as the default policy, and its node and rack requirements.
10. Amazon S3 User Guide: Data protection in Amazon S3docs.aws.amazon.comEleven nines of designed durability, 99.99% availability, at least three Availability Zones, checksum verification and versioning.