Fault Tolerance and Reliability
Open in the Padhaiko app8.1 Dependability Concepts: Availability, Reliability, Safety, Maintainability, MTTF, and MTTR
Dependability and Its Four Pillars
Dependability is the trustworthiness of a computing system such that reliance can justifiably be placed on the service it delivers. It comprises four core properties:
- Availability (): Readiness for correct service at any given instant in time (probability the system is operational right now).
- Reliability (): Continuity of correct service over a continuous time interval without interruption.
- Safety: Absence of catastrophic consequences on users and the environment even if a temporary failure occurs (e.g., fail-safe traffic lights defaulting to all-red).
- Maintainability: Ability to undergo repairs, upgrades, and recovery rapidly and easily after failure.
Quantitative Metrics: MTTF, MTTR, MTBF, and Availability
- MTTF (Mean Time To Failure): Average continuous uptime before a working component fails.
- MTTR (Mean Time To Repair): Average time required to detect, diagnose, repair, and restore a failed component.
- MTBF (Mean Time Between Failures): Average time from one failure to the next:
- Steady-State Availability ():
- Exponential Reliability Function: For constant hazard/failure rate , the probability of surviving without failure is:
| Aspect | Availability | Reliability |
|---|---|---|
| Question Answered | "Is the system working right now?" | "Did the system run without any interruption for hours?" |
| Sensitivity to Brief Outages | Tolerates tiny frequent crashes if MTTR is near zero | Any single crash during breaks reliability ( drops) |
| Example | A web server crashing for once per hour has | A -hour spacecraft burn or surgery monitor crashing for fails completely |
8.2 Fault, Error, and Failure; Failure Models and Byzantine Fault Tolerance
The Fault–Error–Failure Causal Chain
- Fault: The root cause (hardware defect, software bug, cosmic bit-flip, severed fiber cable). Faults may be transient (one-time interference), intermittent (recurring sporadically), or permanent (burned-out disk).
- Error: An unintended internal state inside the system produced when an active fault is triggered (e.g., corrupted variable in RAM).
- Failure: Observed deviation of the system's external service from its specification when an error propagates to the service boundary.
Classification of Distributed Failure Models
| Failure Class | Description | Representative Examples |
|---|---|---|
| Crash (Fail-Stop / Fail-Silent) | Server halts permanently and stops producing outputs (fail-stop if peers can reliably detect the halt) | Power loss, kernel panic |
| Omission (Send / Receive) | Server fails to send outgoing messages or drops incoming messages | Full NIC ring buffer, dropped UDP packets |
| Timing (Performance) | Server produces the correct value, but too early or too late (violates deadline) | Heavy GC pause, CPU starvation |
| Response (Value / State) | Server returns an incorrect value or transitions to wrong state | Buggy calculation, corrupted disk sector |
| Arbitrary / Byzantine | Node fails arbitrarily: crashes, lies, sends conflicting values to different peers, or colludes maliciously | Compromised node, silent memory corruption |
Byzantine Fault Tolerance (BFT)
To mask up to faulty processes:
- Crash / Fail-Silent Faults (-Fault Tolerance):
- If a passive/fail-silent system only needs at least one non-faulty node alive to reply, nodes suffice.
- For asynchronous crash consensus (Paxos/Raft, where up to nodes may be slow or crashed and remaining nodes must form a majority quorum without waiting for the slow ones), nodes are required.
- Byzantine Faults (Lamport, Shostak, Pease, 1982): Because up to Byzantine traitors can actively lie or impersonate silent nodes, among responding nodes up to could still be traitors outvoting honest nodes unless honest responders strictly outnumber traitors: :
(Minimum generals to tolerate traitor; nodes to tolerate traitors.)
8.3 Failure Detection, Process Resilience, and Redundancy Techniques
8.3.1 Failure Detection
In asynchronous networks, a slow node cannot be distinguished with certainty from a crashed node (unreliable failure detectors):
- Heartbeat / Ping-Ack: Processes exchange periodic keepalives. Missing consecutive heartbeats triggers suspicion (-accrual failure detectors adjust suspicion dynamically from observed jitter).
- Gossip-Based Detection (SWIM): Nodes randomly probe peers and ask third-party witnesses to verify indirect pings, avoiding false positives caused by asymmetric routing drops and keeping network load per node.
8.3.2 Process Resilience via Process Groups
To survive individual process crashes, identical processes are organized into process groups:
- Flat Group: Symmetric peers with no single point of failure, but decisions require distributed voting/consensus.
- Hierarchical Group: One coordinator directs workers—fast and simple, but requires leader election if the coordinator crashes.
8.3.3 Redundancy Techniques
- Information Redundancy: Adding extra check bits to detect or correct bit errors—Parity bits, CRC, Hamming ECC, and Erasure Coding (e.g., Reed-Solomon -of- fragments).
- Time Redundancy: Repeating an operation when a transient fault occurs (packet retransmissions, idempotent RPC retries, instruction replay).
- Physical / Hardware Redundancy: Adding spare hardware components in active or standby configurations:
- Active Replication / Triple Modular Redundancy (TMR): identical modules execute in parallel and feed a hardware/software majority voter (2-of-3)—masking any single module failure instantaneously!
- Passive / Hot-Warm-Cold Standby: Backup node takes over when primary fails.
8.4 Checkpointing, Message Logging, and Rollback Recovery
When a long-running distributed computation crashes, restarting from scratch wastes hours of work. Backward error recovery rolls processes back to a previously saved checkpoint on stable storage.
8.4.1 Consistent Global Checkpoints and the Domino Effect
- Orphan Message: A message whose receive event is recorded in a process's checkpoint, while its send event is not recorded in any sender's checkpoint (impossible in a real execution!).
- Domino Effect: Under uncoordinated (independent) checkpointing, rolling back one crashed process to eliminate an orphan message forces to roll back to an earlier checkpoint, which creates another orphan message forcing back further—cascading all the way to the initial state!
Solutions: Coordinated Checkpointing & Message Logging
- Coordinated Checkpointing: Processes synchronize via a distributed snapshot (Chandy-Lamport style) to record a globally consistent recovery line free of orphan messages. Eliminates the domino effect and needs only the latest checkpoint on disk, at the cost of coordination pauses.
- Message Logging (Sender-Based or Receiver-Based): Combines periodic uncoordinated checkpoints with logging every received message and non-deterministic event stably before delivery. On crash, the process reloads its last checkpoint and replays logged messages deterministically without forcing healthy peers to roll back!
- Pessimistic Logging: Log each message synchronously to stable storage before delivering it (zero orphan processes, slight runtime latency).
- Optimistic Logging: Buffer logs in RAM and flush asynchronously (zero runtime penalty, minor rollback risk if crash occurs before flush).
8.5 High Availability and Disaster Recovery: Failover, Geo-Redundancy, RPO, and RTO
Recovery Point Objective (RPO) and Recovery Time Objective (RTO)
- RPO (Recovery Point Objective): The maximum acceptable amount of data loss measured in time (i.e., age of the latest recoverable backup/replica before a disaster—determines how often replication/backups must occur).
- RTO (Recovery Time Objective): The maximum acceptable downtime allowed to restore service operations after a disaster occurs (determines how automated failover must be).
High Availability (HA) & Disaster Recovery (DR) Topologies
| DR Strategy | Standby State | Typical RPO | Typical RTO | Cost & Characteristics |
|---|---|---|---|---|
| Backup & Restore | Cold (snapshots in object storage) | Hours to | Hours to days | Lowest cost; provision infra and restore backups from scratch |
| Pilot Light | Core DB replicating; compute off | Minutes | Tens of minutes | Low cost; spin up and scale app servers on disaster |
| Warm Standby | Scaled-down production stack running | Seconds to minutes | Minutes | Moderate cost; scale up existing standby instances and switch DNS |
| Multi-Site Active-Active | Full geo-redundant capacity serving live traffic in multiple Regions | Near-zero () | Near-zero (automatic DNS/anycast health failover) | Highest cost ( infra); zero idle waste, supports regional routing |
- Failover Mechanisms: Automatic failover uses health probes + DNS/BGP/load-balancer draining + leader promotion (with fencing tokens or STONITH to prevent split-brain dual-leaders). Failback restores traffic safely to the recovered primary region once data re-synchronizes.
Worked Out Examples
8.1
A cloud database server has and (assume exponential failure distribution).
- Calculate its steady-state availability and expected downtime hours per -hour year.
- Calculate the composite availability if two identical independent servers are deployed in active-passive/active-active failover redundancy.
- Calculate the reliability of a single server running continuously without failure for .
1. Single-Server Availability and Annual Downtime:
2. Redundant Two-Server Parallel Availability:
3. Single-Server Reliability over ():
- Single-server availability ( downtime).
- Two-server redundant availability .
- Reliability for without crash .
8.2
- A distributed consensus cluster must remain safe and operational despite up to simultaneous node failures. Calculate the minimum total number of replicas required under (a) Crash-fault tolerance (Paxos/Raft) and (b) Byzantine fault tolerance (BFT).
- Triple Modular Redundancy (TMR): Each of three identical voting processor modules has reliability over a mission window. Assuming independent failures and a perfect majority voter, calculate the overall TMR system reliability (works if at least of modules succeed).
1. Minimum Replicas for :
- Crash Fault Consensus (Paxos/Raft): replicas.
- Byzantine Fault Tolerance (BFT): replicas.
2. TMR Reliability Calculation ():
Thus TMR raises mission reliability from to , cutting failure probability from down to !
- For : Crash consensus needs ; BFT needs .
- TMR reliability ().
8.3
Disaster Recovery & Checkpointing Sizing:
- An e-commerce payment database processes transactions/second, and management mandates and .
- At most how many committed transactions could be lost under a asynchronous replication lag, and what DR architecture satisfies ?
- A database snapshot must be restored across a internal storage fabric during disaster recovery. How long does the raw data restore take, and how much time remains inside the RTO budget for failure detection and DNS/load-balancer cutover?
1. RPO Transaction Exposure and DR Topology:
- With and , at most transactions could be unshipped in an asynchronous log buffer (so synchronous multi-AZ or asynchronous WAL shipping is needed).
- A Backup & Restore or Pilot Light strategy takes minutes to hours, violating . Either Hot/Warm Standby with automated failover or Multi-Site Active-Active is required.
2. Storage Restore & Cutover Budget: Restoring over a fabric takes:
Leaving for health-probe failure detection and automated DNS/load-balancer cutover—showing why sub- RTO demands pre-warmed replicated standbys rather than cold snapshot copies.
- risks up to transactions (use synchronous/near-sync replication); requires automated Hot Standby or Active-Active failover.
- Even at , restoring takes , leaving almost no margin for detection and cutover without live standby replicas.
Exercises
Practice Exercises — Fault Tolerance and Reliability
Define Availability, Reliability, Safety, and Maintainability. A microservice node has and . Compute its MTBF, steady-state Availability, and Reliability over a continuous -hour interval.
Dependability Terms:
- Availability: Probability the system is operational at a given instant.
- Reliability: Probability of continuous failure-free operation over .
- Safety: Freedom from catastrophic outcomes during failure.
- Maintainability: Ease and speed of repair/recovery.
Numerical Metrics (, , ):
, Availability , Reliability .
Distinguish between Fault, Error, and Failure, and rank the five failure models (Crash, Omission, Timing, Response, Byzantine) by severity. How many total nodes are required to tolerate faulty nodes under (a) Crash-fault consensus and (b) Byzantine fault tolerance?
Fault–Error–Failure and Failure Models: A fault (root cause) triggers an invalid internal error state, which propagates to an externally visible failure. Severity increases from Crash (stops cleanly) Omission (drops messages) Timing (late/early) Response (wrong output) Byzantine (arbitrary/malicious/contradictory behavior).
Replica Bounds for :
- Crash-fault consensus: nodes.
- Byzantine fault tolerance: nodes.
A fault causes an internal error leading to an external failure. For , crash consensus requires nodes and BFT requires nodes.
Explain how gossip-based failure detection avoids false positives compared to naive heartbeats. Also compute the system reliability of a Triple Modular Redundancy (TMR) flight controller whose three independent voter modules each have reliability .
Gossip-Based Failure Detection: Instead of declaring a node dead solely when one monitor's direct ping times out (which may be a transient link glitch between those two hosts), protocols like SWIM ask multiple random peers to send indirect probes and disseminate confirmed failures via epidemic gossip—dramatically reducing false suspicions at per-node overhead.
TMR Reliability ():
Gossip detection cross-checks indirect probes via random peers to prevent single-link false positives. TMR reliability with is ().
What is an orphan message, and how does it cause the domino effect in uncoordinated checkpointing? Compare Coordinated Checkpointing and Message Logging (pessimistic vs. optimistic) as solutions.
Orphan Messages and the Domino Effect: An orphan message is a message whose receipt is saved in a receiver's checkpoint while its send was lost before the sender's earlier checkpoint. Rolling back the sender forces the receiver to roll back before the orphan receipt, potentially invalidating earlier messages in a cascade back to the start (domino effect).
Coordinated Checkpointing vs. Message Logging:
- Coordinated Checkpointing: Synchronizes all processes to capture a globally consistent cut with zero orphan messages (simple recovery, periodic coordination overhead).
- Message Logging: Saves periodic local checkpoints plus all received messages stably so a crashed node replays its own log alone without rolling back healthy peers (pessimistic logs before delivery; optimistic buffers in RAM for speed).
An orphan message (received in a checkpoint, sent before the sender's checkpoint) triggers cascading rollbacks (domino effect). Coordinated checkpointing captures a consistent global cut, whereas message logging replays logged inputs locally without rolling back other nodes.
Define RPO and RTO, and compare Backup & Restore, Pilot Light, Warm Standby, and Multi-Site Active-Active disaster recovery architectures across cost, RPO, and RTO.
RPO and RTO Definitions:
- RPO (Recovery Point Objective): Maximum tolerable data loss window (drives replication/backup frequency).
- RTO (Recovery Time Objective): Maximum tolerable downtime window to restore service (drives automation/pre-warming).
DR Architectures Comparison:
- Backup & Restore: Lowest cost, hours RPO/RTO.
- Pilot Light: Core DB live-replicated, compute off; minutes RPO, tens-of-minutes RTO.
- Warm Standby: Scaled-down stack always running; seconds-to-minutes RPO/RTO.
- Multi-Site Active-Active: Live traffic in multiple Regions; near-zero RPO and RTO at highest infrastructure cost.
RPO bounds acceptable data loss and RTO bounds acceptable downtime. Moving from Backup & Restore Pilot Light Warm Standby Active-Active drives RPO and RTO down toward zero at increasing infrastructure cost.