Reliability, Consensus and Recovery

Introduction

Distributed databases operate across machines, networks, storage devices, and administrative domains. Failure is therefore normal rather than exceptional. A server may crash, a disk may corrupt data, a network may partition, a process may become slow without stopping, or two isolated groups of replicas may both believe they are authoritative. Reliability engineering asks how a database continues to provide correct service despite such events.

This chapter examines failure detection, fault tolerance, logging, checkpointing, replica recovery, consensus, leader election, split-brain prevention, disaster recovery, and business continuity. The central principle is that availability is valuable only when it is achieved without violating the system's correctness guarantees.

Learning Objectives

By the end of this chapter, you should be able to:

1. Classify failures in distributed database systems and explain why detection is difficult.
2. Design fault-tolerant architectures using replication, quorum rules, and fencing.
3. Explain write-ahead logging, checkpoints, redo, undo, and recovery points.
4. Compare consensus and leader-election mechanisms.
5. Analyse split-brain risks and methods for preventing divergent authority.
6. Design replica-recovery, disaster-recovery, and business-continuity procedures.
7. Evaluate reliability using availability, recovery time, recovery point, and durability measures.

1. Failure Models and Reliability Goals

A failure model states what can go wrong and what assumptions the system makes. Common models include:

A failure detector does not normally prove that a remote process has failed. It infers failure from missing or late responses. Consequently, a slow but healthy node can be suspected, while a failed node may not yet be suspected. This distinction is fundamental: suspicion should trigger cautious actions, not immediate destruction of state.

Important reliability properties are:

• Availability: the proportion of time a service is able to respond.
• Durability: the probability that an acknowledged committed update will survive failure.
• Consistency: the rules governing which values clients may observe.
• Recoverability: the ability to restore service and data after failure.
• Fault tolerance: continued correct operation despite specified failures.

For independent components connected in series, where every component must work, system availability is approximately:

Here, A_i is the availability of component i. For redundant components in parallel, where at least one must work, availability is:

These formulas assume statistically independent failures. Real systems often violate this assumption because software defects, power failures, and network events create correlated failures. Thus, simply adding replicas in one data centre may provide much less protection than the formula suggests.

Availability is also commonly expressed through uptime and downtime. If a service operates for total time T and is unavailable for D, then:

A service-level objective must specify the measurement window, permitted downtime, and exclusions such as planned maintenance.

2. Failure Detection and Failure Handling

2.1 Heartbeats, leases, and accrual suspicion

A heartbeat is a periodic message indicating that a process is alive. A timeout-based detector marks a node suspect if no heartbeat arrives within a configured interval. Short timeouts detect failures quickly but create false suspicions under load or network delay; long timeouts reduce false suspicions but delay recovery.

A lease reverses the direction of authority: a node may act as leader only while its time-limited lease remains valid. Leases require carefully bounded clock uncertainty. A node whose lease has expired must stop serving authoritative writes even if it has not received a message saying that leadership was revoked.

Accrual failure detectors maintain a continuously increasing suspicion value rather than a binary status. This allows an operator or algorithm to choose a threshold according to workload and network conditions.

2.2 Detection is not recovery

Detection answers, “Which component may be unavailable?” Recovery answers, “What safe action can be taken?” A detector should therefore be integrated with:

1. Observation: collect heartbeats, request latency, log progress, and storage health.
2. Suspicion: classify the component as possibly failed.
3. Authority verification: determine whether another node has legitimately assumed its role.
4. Containment: fence or isolate the suspected node if it could still write.
5. Recovery: replay logs, rebuild replicas, or fail over.
6. Validation: verify consistency before returning the node to service.

The most dangerous response is automatic promotion without fencing. If the old leader can still write, two leaders may accept conflicting updates.

3. Fault-Tolerant Replication and Quorums

Replication maintains multiple copies of data. Synchronous replication waits for specified replicas before acknowledging a transaction; asynchronous replication acknowledges before all copies are updated. Synchronous replication usually offers stronger durability but increases latency and may reduce availability during partitions.

For a replicated object with N replicas, a read quorum of R and a write quorum of W should generally satisfy:

This intersection condition ensures that every successful read quorum intersects every successful write quorum. To ensure that two writes intersect, use:

These conditions are necessary for common quorum-consistency designs, but they are not sufficient by themselves for serializability, conflict resolution, or linearizability. Replica versioning, ordering, and a defined conflict policy are also required.

For example, with five replicas, R = 3 and W = 3 satisfy both conditions. A write must reach three replicas, and a read must consult three replicas. However, if the system allows concurrent writes, it still needs timestamps, a leader, compare-and-set operations, or another ordering mechanism.

Replication strategies

• Primary-backup: one primary orders writes; backups follow its log.
• Multi-primary: several replicas accept writes; conflicts must be detected and resolved.
• Chain replication: writes move through an ordered chain, often separating update and read responsibilities.
• Leaderless replication: clients or coordinators use quorum reads and writes.
• Erasure coding: data is divided into fragments with parity, reducing storage overhead for large objects but complicating repair.

Replication should be failure-domain aware. Three replicas in one rack do not protect against rack failure. Stronger designs place replicas across independent power, network, zone, and regional domains.

4. Logging, Atomicity, and Checkpointing

4.1 Write-ahead logging

Write-ahead logging (WAL) requires log records to reach durable storage before the corresponding data pages are written. For an update to page P, a log record might contain transaction identifier, page identifier, before-image, after-image, and log sequence number (LSN).

The fundamental ordering rule is:

In words, the log record describing a page modification must be durable before the modified page is flushed. This permits recovery even when a crash occurs between logging and page writing.

WAL supports two classic recovery actions:

• Redo: repeat committed changes not yet reflected in data pages.
• Undo: remove effects of incomplete transactions.

A database may use deferred update, where changes are applied mainly during redo, or immediate update, where uncommitted changes may reach pages and undo is therefore required. Modern systems often use physiological logging and additional transaction-status records.

4.2 Checkpoints

A checkpoint records sufficient information about the current recovery state, such as the active transaction table, dirty-page table, and a durable log position. It reduces recovery work by allowing the system to begin analysis near the checkpoint rather than scanning the entire log.

A fuzzy checkpoint does not stop all transactions. It records a consistent description while transactions continue, making it practical for high-throughput systems. Checkpoints do not replace logs: changes after the checkpoint still require recovery processing.

4.3 Recovery sequence

A widely used recovery pattern has three phases:

1. Analysis: identify transactions active at failure and pages that may need redo.
2. Redo: repeat history from the appropriate LSN so the database reflects all logged page changes.
3. Undo: roll back transactions that had not committed, usually by following compensation records.

Recovery must be idempotent: repeating a recovery action should not create an additional unintended effect. This is why durable LSNs, page identifiers, transaction states, and compensation log records are essential.

4.4 Replication logs and commit positions

In replicated databases, a log position may have several meanings:

• Appended: the leader has written the entry locally.
• Replicated: enough followers have stored the entry.
• Committed: the system's protocol guarantees that the entry will not be replaced.
• Applied: a replica has incorporated the entry into its user-visible state.

Confusing these positions causes stale reads, unsafe failover, and data loss. A client acknowledgement should be explicitly tied to a durability and consistency contract.

5. Consensus and Leader Election

Consensus enables distributed processes to agree on a value or ordered sequence despite failures. A consensus protocol is usually described by three properties:

• Agreement: correct participants do not decide different values.
• Validity: a decided value has an appropriate relationship to proposed values.
• Termination: correct participants eventually decide, subject to the protocol's timing assumptions.

The FLP result shows that in a completely asynchronous system, deterministic consensus cannot guarantee termination if even one process may crash. Practical protocols therefore use partial synchrony, timeouts, randomisation, or external failure-detector assumptions.

5.1 Raft-style replicated state machines

A replicated state machine applies the same deterministic command sequence to each replica. A Raft-like design divides time into terms and normally has one leader per term. The leader appends client commands, replicates them, and considers an entry committed when the protocol's majority rule makes it durable and safe. Followers reject stale-term messages.

The design separates:

1. leader election,
2. log replication,
3. commitment,
4. state-machine application.

A candidate requests votes using its term and log freshness. A voter grants at most one vote per term, subject to the protocol's rules. A majority intersection ensures that a committed entry is present in any later majority, provided the protocol's commitment rules are followed.

5.2 Paxos-style agreement

Paxos uses numbered proposals and acceptors. A proposer first establishes a proposal number, learns previously accepted values, and then proposes a value consistent with those observations. Its safety depends on quorum intersection and monotonically ordered proposal numbers. Paxos is influential but can be difficult to implement and explain operationally; production systems commonly expose a replicated-log abstraction rather than raw consensus rounds.

5.3 Leader election is not consensus

An election chooses who may coordinate; consensus establishes agreement on decisions or log entries. An election without durable terms, quorum validation, and fencing can produce two apparent leaders. Conversely, a consensus protocol may internally elect leaders but still needs explicit rules for client redirection and lease expiration.

6. Split-Brain Prevention

Split brain occurs when two or more components independently believe they have write authority. It can result from a network partition, asymmetric routing, delayed messages, or a failed fencing mechanism. The consequences include divergent histories, duplicate identifiers, incorrect financial balances, and irreversible conflict.

Reliable prevention combines several controls:

• Majority quorum: only a partition containing a quorum may commit authoritative writes.
• Epochs or terms: every authority assignment has a monotonically increasing number.
• Fencing tokens: storage or services reject commands carrying an older token.
• STONITH: “shoot the other node in the head”—power off or isolate the suspected old leader.
• Witnesses: an independent vote prevents two equal-sized groups from both forming a majority.
• Lease discipline: authority expires unless renewed under safe clock assumptions.
• Client routing: clients accept writes only through the currently authenticated authority.

A witness must be independent enough to avoid sharing the same failure. A third voting member in the same power domain as one of two data replicas may not provide meaningful protection.

7. Replica Recovery and Rejoining

When a replica returns after failure, it must not simply begin serving traffic. A safe rejoin procedure is:

1. Authenticate and verify software version and configuration.
2. Determine the last durable log position and epoch.
3. Compare the replica with an authoritative source.
4. Transfer missing log entries if the required history exists.
5. If history is unavailable, create a fresh snapshot and stream subsequent changes.
6. Verify checksums, row counts, indexes, and log continuity.
7. Mark the replica as catching up, then healthy, before adding it to serving quorums.

Incremental recovery is faster and reduces network usage, but it depends on retaining the relevant log. Snapshot recovery is more expensive but works when the replica has fallen too far behind or its local state is suspected to be corrupt.

Repair bandwidth must be controlled. Rebuilding a replica can compete with foreground traffic and cause additional failures. Systems may use throttling, priority scheduling, repair windows, and topology-aware source selection.

Integrity verification should include cryptographic or strong checksums, page-level validation, application invariants, and comparison of replicated log positions. A replica that is available but silently corrupted is more dangerous than an obviously failed replica.

8. Disaster Recovery and Business Continuity

Disaster recovery addresses restoration after major loss of infrastructure; business continuity includes the wider organisational capability to maintain critical services. Planning begins with a business impact analysis that identifies processes, dependencies, acceptable downtime, and acceptable data loss.

Two key objectives are:

• Recovery Time Objective (RTO): maximum acceptable time until service is restored.
• Recovery Point Objective (RPO): maximum acceptable amount of data loss measured in time.

If backups are taken every six hours and the latest usable backup is six hours old, the technical RPO may be up to six hours, although the actual loss depends on replication and backup timing. RTO is not calculated from backup frequency; it includes detection, decision-making, provisioning, restoration, validation, and traffic redirection.

A useful recovery architecture separates:

1. primary production systems,
2. replicated or standby systems,
3. immutable backups,
4. key and identity-management backups,
5. documented runbooks,
6. communication and escalation channels.

Backup types and trade-offs

• Full backup: copies all selected data; simplest restoration but costly.
• Incremental backup: copies changes since a prior backup; efficient creation but may require a chain.
• Differential backup: copies changes since the last full backup; restoration is simpler than a long incremental chain.
• Snapshot: captures storage state at a point in time; fast, but may depend on the underlying platform.
• Logical export: represents tables or objects; portable but often slower.

Backups must be encrypted, access-controlled, tested, and protected from ransomware. An immutable or offline copy is important because an attacker who can alter production data may also attempt to alter online backups.

A common resilience principle is the 3-2-1 pattern: at least three copies, on two media or storage systems, with at least one copy off-site. It is a guideline, not a substitute for threat analysis.

9. Measuring Reliability and Recovery

For a service with mean time between failures (MTBF) and mean time to repair (MTTR), a simplified steady-state availability estimate is:

MTBF and MTTR must use the same time unit. The approximation assumes repeated cycles, stable rates, and a clearly defined failure and repair population. It is less meaningful when failures are correlated or when planned downtime is included inconsistently.

For example, if MTBF is 99 hours and MTTR is 1 hour, then A ≈ 99/(99+1) = 0.99, or 99%. This is not a guarantee that every 100-hour period will contain exactly one hour of downtime.

Useful operational indicators include:

• acknowledged writes lost after failover,
• stale-read rate,
• election frequency,
• replication lag,
• time to detect failure,
• time to fence authority,
• time to restore service,
• percentage of successful backup-restore tests,
• checksum and invariant violations.

A mature reliability programme measures not only uptime but also correctness during degraded operation.

10. Illustrative Case: Regional Payment Ledger

Background

A financial-services company operates a distributed ledger across three availability zones. One node is the leader, two are followers, and an independent witness participates in elections. Transactions require a majority acknowledgement. Backups are encrypted and copied to a separate region.

Problem

A routing failure isolates the leader from one follower. The leader can still reach the other follower but cannot reach the witness. Simultaneously, an administrator observes high latency and manually restarts the isolated node.

Analysis

The system must distinguish a slow node from a partitioned node. Because the leader cannot establish the required quorum and cannot renew its authority under the configured lease, it must stop accepting authoritative writes. The isolated follower must not promote itself merely because it cannot see the leader. The witness and quorum rules prevent an isolated minority from electing a new leader.

The remaining reachable data-bearing nodes and witness form the eligible election group. A new leader is elected only if its log is sufficiently current. Clients are redirected using authenticated service discovery. The former leader is fenced before it can rejoin.

Approach and solution

The recovery runbook performs the following actions:

1. Confirm the network partition using independent monitoring paths.
2. Verify the current term and quorum membership.
3. Fence the old leader through infrastructure control.
4. Elect a leader in the surviving quorum.
5. Accept transactions only after the new leader's log is committed according to protocol.
6. Rebuild the fenced node from a trusted snapshot if its log cannot be safely reconciled.
7. Run ledger invariants, checksum checks, and duplicate-transaction checks.
8. Restore the node as a non-voting learner before full membership.

Outcome

The service experiences a controlled write interruption rather than accepting conflicting transactions. No committed transaction is lost because acknowledgement required quorum durability. The business remains within its defined RTO, while the RPO for acknowledged transactions is zero under the stated assumptions.

Learning points

Consensus, fencing, and operational runbooks must be designed together. A quorum alone does not protect a system if an old leader can continue writing to clients or storage. Recovery validation is part of correctness, not merely an administrative step.

11. Governance, Security, and Contemporary Practice

Reliability mechanisms have governance consequences. Recovery administrators possess powerful access to data, keys, and production infrastructure. Duties should be separated, actions audited, and emergency access reviewed. Encryption keys must be recoverable during disaster scenarios without being broadly accessible during normal operation.

Data residency and sector regulations may restrict where replicas and backups are stored. Retention policies must balance legal obligations, privacy, and the need to recover from corruption. Immutable backups can preserve evidence but may conflict with deletion requirements unless carefully scoped.

Automation and AI can assist with anomaly detection, capacity forecasting, log classification, and incident summarisation. They should not silently change quorum policy, promote leaders, or delete recovery data without deterministic safeguards and human accountability. A false anomaly alert is inconvenient; an unsafe automated failover can corrupt an entire system.

Best practice is to test failure deliberately: kill processes, delay messages, fill disks, corrupt test pages, revoke network paths, and perform full regional restoration. Such exercises should be controlled, documented, and followed by remediation. Recovery that has never been tested is an assumption rather than a capability.

Chapter Summary

Distributed database reliability depends on explicit failure models, conservative detection, quorum-based authority, durable logging, and tested recovery procedures. Heartbeats and timeouts provide suspicion, not proof. Replication improves resilience only when failure domains, acknowledgement semantics, and consistency rules are understood. Write-ahead logging enables redo and undo, while checkpoints reduce recovery work without replacing logs.

Consensus establishes agreement despite failures; leader election provides coordination but is not equivalent to consensus. Split-brain prevention requires quorum rules, epochs, leases, fencing, and safe client routing. Replica recovery must validate log continuity and data integrity before a node serves traffic. Disaster recovery combines replication, immutable backups, RTO/RPO targets, runbooks, and regular exercises. Finally, reliability must be measured through both availability and correctness indicators.

Key Terms

Failure detector: A mechanism that infers whether a component may have failed.

Crash-stop failure: A failure in which a process stops permanently.

Network partition: A communication failure dividing nodes into disconnected groups.

Fault tolerance: Continued correct operation despite specified failures.

Write-ahead logging: Requiring log records to be durable before modified pages are written.

Log sequence number: An ordered identifier for a log record or position.

Redo: Reapplying logged changes during recovery.

Undo: Reversing effects of incomplete transactions.

Checkpoint: A durable recovery marker that limits the amount of log processing.

Quorum: A sufficiently large voting or replica subset required for an operation.

Consensus: Agreement among distributed participants on a value or ordered commands.

Leader election: Selection of the process authorised to coordinate a group.

Term or epoch: A monotonically advancing authority period.

Fencing: Preventing a suspected old authority from performing writes.

Split brain: Simultaneous, conflicting claims of write authority.

Replica recovery: Reconstructing and validating a failed or stale replica.

RTO: Maximum acceptable time to restore service.

RPO: Maximum acceptable time-based data loss.

MTTR: Mean time required to repair or restore service.

Immutable backup: A backup protected against alteration or deletion for a defined period.

Review Questions

5 Short Answer Questions

1. Why can a failure detector falsely suspect a healthy node?
2. State the usual quorum intersection condition for reads and writes.
3. What is the purpose of write-ahead logging?
4. Distinguish RTO from RPO.
5. Why is fencing necessary after leader failover?

5 Long Answer Questions

1. Explain the relationship among failure detection, authority verification, fencing, and recovery.
2. Compare primary-backup, multi-primary, chain, and leaderless replication.
3. Describe analysis, redo, and undo in crash recovery.
4. Explain how consensus protocols support replicated state machines and why partial synchrony matters.
5. Design a disaster-recovery architecture for a regulated distributed database.

3 Analytical / Application Questions

1. A five-replica database uses read quorum 2 and write quorum 3. Determine whether every read intersects every write and whether two writes must intersect. Explain the consequences.
2. A regional partition leaves two database nodes on one side and two on the other, with one independent witness. Propose a safe election and fencing procedure.
3. A company reports excellent uptime but has never performed a restore test. Evaluate the reliability claim and propose measurable corrective actions.

Multiple Choice Questions with Answers

Question 1

Which statement best describes a failure detector in a distributed system?

A. It proves mathematically that a remote process has failed.

B. It infers possible failure from observations such as missing or late responses.

C. It permanently deletes all state belonging to an unresponsive process.

D. It guarantees that network messages arrive in order.

Correct Answer: B. It infers possible failure from observations such as missing or late responses.

Question 2

For a replicated object, which condition ensures that a read quorum intersects a write quorum?

A. R + W > N

B. R + W < N

C. R = W = 1

D. R − W > N

Correct Answer: A. R + W > N

Question 3

What is the primary purpose of write-ahead logging?

A. To reduce the number of database indexes.

B. To ensure log information is durable before corresponding data-page changes.

C. To eliminate the need for backups.

D. To prevent all network partitions.

Correct Answer: B. To ensure log information is durable before corresponding data-page changes.

Question 4

Which recovery action reverses the effects of transactions that had not committed at failure?

A. Redo

B. Checkpointing

C. Undo

D. Replication

Correct Answer: C. Undo

Question 5

Which property of consensus means that correct participants do not decide different values?

A. Agreement

B. Validity

C. Termination

D. Availability

Correct Answer: A. Agreement

Question 6

What is the main purpose of fencing in leader failover?

A. To increase query parallelism.

B. To prevent an old leader from continuing to perform writes.

C. To compress the transaction log.

D. To remove the need for quorum membership.

Correct Answer: B. To prevent an old leader from continuing to perform writes.

Question 7

A system has MTBF of 99 hours and MTTR of 1 hour. Using A ≈ MTBF/(MTBF + MTTR), what is its approximate availability?

A. 0.50

B. 0.90

C. 0.99

D. 1.99

Correct Answer: C. 0.99

Question 8

Which statement correctly distinguishes RTO and RPO?

A. RTO concerns acceptable data loss; RPO concerns restoration time.

B. RTO concerns restoration time; RPO concerns acceptable data loss measured in time.

C. Both measure only network latency.

D. Both are types of consensus quorum.

Correct Answer: B. RTO concerns restoration time; RPO concerns acceptable data loss measured in time.

Question 9

Why should a recovered replica normally rejoin as a learner or catch-up node first?

A. To allow validation before it participates fully in serving or voting.

B. To guarantee that it never receives log entries.

C. To make checksum verification unnecessary.

D. To bypass authentication.

Correct Answer: A. To allow validation before it participates fully in serving or voting.

Question 10

Which situation is an example of split brain?

A. A replica is rebuilding from a trusted snapshot.

B. Two isolated components both accept authoritative writes.

C. A checkpoint reduces recovery scanning.

D. A follower applies a committed log entry.

Correct Answer: B. Two isolated components both accept authoritative writes.