Failure and recovery

What dependability is

Distributed systems run services we rely on daily: finance (online banking, stock trading), e-commerce, civil infrastructure (power grid, traffic control), entertainment (gaming, streaming), personal data storage (Dropbox, Google Drive, SkyDrive). A data centre brought down by a failure can cost tens to hundreds of thousands of euros per hour, in wasted expenses and lost revenue.

Dependability is not cheap either, which is possibly why nearly 60% of Fortune 500 companies suffer more than an hour and a half of downtime per week. A data centre costs from $450 per square foot for 99.671% availability (28.8 hours of downtime a year) to $1,100 for 99.995% (0.4 hours). To reduce that cost, the slides propose training more “engineers against downtime”.

The Oxford dictionary defines dependability as “the quality of being able to be relied on to do what somebody wants or needs”, synonym reliability. In systems engineering, a field much wider than computing, the two are closely related but not the same thing (§3).

Reasoning about it needs a model of the system and a model of the threats.

The system and its state

A system provides services to its users (clients), each through an interface; a functional specification defines what each should do. At each moment the system is in a state, determined collectively by its processes and threads: registers, stack, heap, file descriptors, kernel state… The part visible through user interaction is the external (observable) state, basically the abstract state of the specification. The rest is internal state.

So state serves recovery: a system can be brought back to where it was before a failure if its state was (consistently) captured and not lost, e.g. serialised to stable storage and intact after the failure. How do we capture the state of a distributed system at time t? First, fix the boundary, the line between the system's components (inside) and its environment: every other system that affects it in any way. Whether something is a system or a component depends on the level of abstraction. Second, “at time t” means little without a global clock (Ch. 2); §6 does without one.

Faults, errors and failures

A system not complying with its functional specification has a (service) failure, caused by wrong values in its state (errors), which in the causal model are caused by faults. So threats are modelled as sorts of faults. In Tanenbaum & van Steen's words:

A fault may be dormant: a bug harmless until its code runs, an unlocked shared variable harmless until two threads update it concurrently. When its condition is met, the fault is activated into an error, which propagates through interactions; when it reaches the interface, a service failure occurs. Since systems are composed recursively, a component's failure is a fault of the larger system. This is the chain of threats, and why “fault” and “failure” are often, somewhat improperly, used interchangeably.

Six ways to classify faults

Different sorts need different treatment. Six criteria:

1. Source. Hardware (power outages, hard-drive failures, bad memory chips), software (bugs such as race conditions, missing array bound checks), operator (misconfiguration, wrong upgrade procedures).
2. Intent. Non-malicious (a natural hardware fault, an unintended bug) or malicious: caused by someone intending harm, e.g. denying service to legitimate clients or compromising the service's integrity. The slides point here to commission and Byzantine faults.
3. Duration. Transient: activated momentarily, then dormant (a power spike). Intermittent: occurs, vanishes, reappears (a race condition). Permanent: stays until the component is repaired or the source addressed (a power outage, a process crash).
4. Manifestation. Content: wrong values passed on to other components, always the same ones, or different values to different components, the case modelled as Byzantine faults. Timing: replying too early or too late; at the extreme never, as when a component crashes or hangs (infinite loop, deadlock).
5. Reproducibility. Reproducible (deterministic), like a null-pointer access, easily identified and repaired; or nondeterministic, like a bad thread interleaving, hard to reproduce: Heisenbugs.
6. Relationship. Independent (no causal relationship) or correlated (one causes the other). Multiple components failing for a common reason are common mode failures.

Under manifestation, Byzantine means telling different parties different things, which a bug can do as well as an attacker. A commission fault is doing something that should not have been done, as opposed to omitting something.

Failure models

Tanenbaum & van Steen classify failures by a server's observable behaviour:

Failing well

1. Fail-stop. Dependability mechanisms make the system stop responding to requests when it fails, avoiding catastrophic consequences.
2. Fail-safe. Failure causes no great harm to human life or the environment: the system defines safe states and moves to one when it can no longer meet its specification. Nuclear plant control must be fail-safe.
3. Fail fast. The practice of halting immediately on an error state or unexpected condition. It enables early detection and diagnosis: a fault propagated to many components is much harder to pinpoint.

Attributes and metrics

Two lists from two books, overlapping but different: keep them apart.

Availability and reliability can serve as evaluation metrics; the other three are difficult to quantify. Availability, reliability and integrity are fundamental to all distributed systems; maintainability and safety are secondary or not always applicable.

Measuring them

Availability factors

1. MTTF, Mean Time To Failure: the average time until the system fails.
2. MTTR, Mean Time To Repair: the average time needed to repair it.
3. MTBF, Mean Time Between Failures: just MTTF + MTTR.

Five nines means 99.999%: a 10⁻⁵ probability of finding the system unavailable, at most 5.256 minutes of downtime a year. Reliability is the probability of correct service for a period Δt:

The slide adds “≈ proportional to MTTF” under λ.

And availability ≠ reliability: a system failing frequently but recovering very quickly may have high availability and very low reliability.

Means to achieve dependability

Zhao lists four approaches:

1. Fault avoidance. Quality software and hardware, less prone to failures. For software: correct design and implementation before deployment, through rigorous design (possibly formal methods to verify properties) and rigorous testing.
2. Fault detection & diagnosis. Crash faults are trivial to detect by periodically probing each component's health. But components may fail in other ways than crashing, where probing does not always help, and if a fault is not detected, the integrity of the system cannot be guaranteed. Diagnosis then confirms the fault and pinpoints the faulty component, with formal models and (statistical) tools. Exception handling is an example of detection and handling.
3. Fault removal. The fault is isolated and removed; the component is repaired or replaced and reintroduced. This reconfiguration needs a notion of membership: the faulty component is excluded, the repaired one rejoins. Special case: software update.
4. Fault tolerance. Hardware fails, so robust software is not enough; and unless a system is fully stateless, restarting it does not restore its state.

Applications needing high availability but not necessarily high reliability could be served by logging and checkpointing; more demanding ones by recovery-oriented computing. Both rely on rollback recovery: going back to the most recent recorded correct state. Alternatively, failures can be masked, hidden from other processes, by redundancy:

1. Information redundancy, e.g. extra bits.
2. Time redundancy, e.g. redoing a transaction after it aborts.
3. Physical redundancy, typical of biological systems; replicas are the distributed form (Ch. 5).

M1's lessons: dependability is essential, it needs models of systems and threats, and the failure-handling techniques determine the level reached. The rest of this chapter follows the rollback route.

Rollback recovery: the toolkit

C2 starts from interaction. Components (with their functions, services, tasks, goals…) do not work in isolation: they interact over time and space because they depend on each other, and a “mischievously simple” way to model dependencies is causality. In general causality is subtle: a human cognitive tool (“mind reading” others' goals), a word nineteenth-century physics papers used in titles but almost never in the text, and not the same as correlation (the tobacco industry's hypothetical genotype causing both cancer and smoking). Pearl [2009] makes it precise. Distributed systems need less: cause tied to the system model, defining dependencies between processes, with causes preceding effects. That is happens-before (Ch. 2).

To recover to the point right before the failure, all incoming messages are typically logged too, and possibly other nondeterministic events. Both are rollback recovery: back to a state prior to the failure. Roll-forward mechanisms exist but typically cost more runtime overhead and physical resources.

Checkpointing and logging are the most fundamental dependability techniques, used at every level. Alone, they are relatively easy to implement with low runtime overhead, but limited: with checkpointing only, some information can be lost, and recovery is typically slower than with more sophisticated approaches.

The model

N processes interact by message exchange, and with the outside world through input and output.

Fault model

1. Failures occur in processes.
2. Fail-stop. A failed process simply stops executing and loses all its volatile state.
3. Reliable, FIFO communication (e.g. TCP): message ordering is maintained, and there is no network partition.

A process's state is, from the operating system's viewpoint, its entire address space, which a generic checkpointing library saves whole. Application semantics can define a smaller one. Stable storage is essential: it survives process failures, so its contents are available to the recovering process, and all checkpoints and logged messages must go there. Its forms:

1. Local disks, enough to tolerate process failures only.
2. Redundant disks (RAID-1, RAID-5), to tolerate disk failures.
3. Replicated or cloud-based file systems, for more robust stable storage.

Consistent global states

The state of a distributed system, its global state, includes the state of every process. Aggregating them is not enough: messages move information between processes and change their states, so processes causally depend on each other, and dependencies cannot be lost in the global state.

The slides' example: processes P0, P1, P2 with checkpoints C0, C1, C2 and messages m0 (P0 → P1), m1 (P1 → P2). P0 and P1 are bank accounts A and B; m0 is a $100 deposit from A to B.

In scenario (c), if m0 is saved in C0 as channel state and m1 in C1, recovery becomes possible. A usable global state is consistent process states plus channel states.

Checkpointing protocols

Checkpoint-based protocols focus on state rather than events, so they do not rely on the piecewise deterministic assumption (§9). They are simpler and less restrictive: no need to identify and log every nondeterministic event. The price: unless a checkpoint precedes every event, which is typically not realistic, some execution is lost.

Uncoordinated checkpointing

In uncoordinated checkpointing, each process autonomously decides when to checkpoint. After a failure, recovery goes backwards to select the most recent set of consistent checkpoints. The main problem: the checkpoints might not allow a consistent global state to be reconstructed. To select one, the dependencies between checkpoints must be determined and recorded with each checkpoint, which adds overhead and complexity.

Coordinated checkpointing: Tamir & Sequin

Tamir & Sequin [1984] is a coordinated checkpointing protocol. A coordinator knows all the other processes, the participants, and uses two-phase commit to make the local checkpoints mutually consistent. The round is an atomic transaction: either all processes create a new set of checkpoints, or they abandon it and revert to the previous set. Phase one creates a quiescent point of the system state; phase two atomically moves from the old checkpoint to the new one. A round aborts when a participant fails to respond.

Control messages

1. CHECKPOINT: initiates a global checkpoint and establishes a quiescent point where all processes have stopped normal execution.
2. SAVED: a participant has taken its local checkpoint.
3. FAULT: a timeout occurred; abort the round.
4. RESUME: participants can resume normal execution.

Coordinator

1. Starts the first phase: stops normal execution and sends CHECKPOINT to every process.
2. Waits for incoming CHECKPOINT messages from all processes; aborts if some are missing.
3. Checkpoints its state.
4. Waits for SAVED from every process; aborts if some are missing, sending FAULT.
5. Switches to the new checkpoint and sends RESUME to every process.
6. Resumes normal execution.

Participant

1. Stops normal execution when it receives CHECKPOINT.
2. Sends CHECKPOINT through all its outgoing channels, and waits for CHECKPOINT from all its incoming channels; aborts if some are missing.
3. Checkpoints its state.
4. Sends its SAVED, and passes SAVED from its downstream neighbours up to its upstream neighbour, towards the coordinator.
5. On RESUME, commits the checkpoint and propagates RESUME through every outgoing channel except the one it came from.
6. Resumes normal execution.

Channel state is captured in the state machines' waiting state: a process waiting for CHECKPOINT that receives a regular message logs it. Channels are FIFO, so a channel's CHECKPOINT arrives after everything its sender sent before stopping. When CHECKPOINT has arrived on every incoming channel, those channels are drained and their in-transit messages are in the log. The quiescent point does not mean “no messages in transit”, but “every in-transit message accounted for”.

Chandy–Lamport snapshots

Tamir & Sequin is blocking: normal execution is suspended during each round. The Chandy & Lamport distributed snapshot protocol [1985] is non-blocking: normal execution is never interrupted. But it is only concerned with how to produce a consistent global checkpoint. It prescribes no mechanism to determine the end of the round, nor to switch atomically to the new global checkpoint.

1. Two states. A process is either Normal or Checkpointing.
2. Initiation. Any process can initiate: it takes a local checkpoint, sends a Marker on all its outgoing channels, and moves to Checkpointing.
3. First Marker. A Normal process receiving a Marker does the same, and also records the Marker certificate, to be completed with a Marker from every incoming channel.
4. Completion. When the certificate is complete, the process goes back to Normal.

While Checkpointing, a regular message arriving on a channel whose Marker has not arrived yet is appended to that channel's state, and executed; after the Marker, messages are just executed. So a channel's state is the messages arriving after the process's own local checkpoint and before the Marker on that channel. The channel that brought the first Marker is empty: by FIFO, everything sent on it before the sender's checkpoint has already arrived. The state machine's final “report completion” is local; how the round ends is left open.

Comparing the two protocols

Analogies

1. Basically the same system model, and a special control message to propagate and coordinate the global checkpoint.
2. Both recognise the need to capture channel state for recoverability.
3. Virtually the same mechanism to capture it.
4. Identical communication overhead.

Differences

1. The blocking protocol is more conservative, but blocking.
2. The blocking protocol is more complete and robust.
3. The non-blocking protocol provides no mechanism for the atomicity of the round.
4. The blocking protocol is coordinated; the non-blocking one lets any process initiate, which may suit different sorts of systems.

Log-based protocols

Log-based protocols save events rather than state, and can recover to the state right before the failure, provided all events are logged and the log is available on recovery. They rest on an assumption:

Execution is modelled as consecutive state intervals, each started by a nondeterministic event (such as a message receipt) or by the process's initialisation, and followed by deterministic state changes. If the starting event is logged, the entire interval can be replayed.

Sorts of logging protocols [Alvisi & Marzullo, 1998]

1. Pessimistic. A received message is logged synchronously, before it is executed.
2. Optimistic. To reduce latency, nondeterministic events go first to volatile memory, then asynchronously to stable storage. A failure may lose some messages permanently, forcing a rollback to a state earlier than the one at failure.
3. Causal. Events not yet on stable storage are piggybacked on every message sent, so a process can access all nondeterministic events that may causally affect its state, enabling consistent recovery.

Long story short: optimistic and causal logging must track dependencies and piggyback them on every message. That complicates logging and, above all, makes recovery sophisticated and expensive: the recovering process must examine its logs, find missing messages, and often trigger cascading recovery at other processes. Pessimistic logging is much simpler, and its recovery can be much faster.

Logging and checkpointing together

In practice, logging is always used with checkpointing: states saved as checkpoints, events logged from one checkpoint to the next. Two benefits:

1. Limited recovery time. Restart from the last checkpoint, not the initial state, then replay the logged nondeterministic events.
2. Limited log size. Events logged before a checkpoint can be garbage collected.

C2's lessons: dependability requires a coherent notion of dependencies and causality, and simple techniques like checkpointing and logging improve the chance of recovery.