Recovery Concepts

The recovery manager can guarantee durability only if it can write data to storage that actually survives failures. But here's an uncomfortable truth: no physical storage device is perfectly reliable. Disks fail. SSDs corrupt. Entire data centers lose power. Yet databases promise that committed transactions persist forever.

How can we build reliable systems from unreliable components? The answer is stable storage—an abstraction that provides reliability guarantees through redundancy, replication, and carefully designed I/O patterns. Understanding stable storage is understanding how theoretical durability becomes practical reality.

Database theory defines stable storage as an idealized abstraction:

Definition: Stable storage is an abstraction of storage that never loses data. Once data is written to stable storage, it can always be read back, regardless of any failures.

Of course, this is physically impossible—any storage can be destroyed by sufficient physical force. But the abstraction is useful because we can approximate stable storage to an arbitrarily high degree of reliability using redundancy.

Storage Reliability Hierarchy:

Approximating Stable Storage:

Since true stable storage is impossible, databases use multiple independent redundant copies to approximate it:

                    ┌────────────────────────────────────────────┐
  Write Request ──▶ │            Stable Storage Interface        │
                    └────────────────┬───────────────────────────┘
                                     │
                    ┌────────────────┼───────────────────────────┐
                    │                │                           │
                    ▼                ▼                           ▼
              ┌──────────┐    ┌──────────┐               ┌──────────┐
              │  Copy 1  │    │  Copy 2  │      ...      │  Copy N  │
              │ (Disk A) │    │ (Disk B) │               │ (Site Z) │
              └──────────┘    └──────────┘               └──────────┘
                    │                │                           │
                    └────────────────┴───────────────────────────┘
                                     │
  Read Request  ◀───────────────────┘ (any surviving copy)
                    (validate, resolve conflicts if needed)

The key insight: if copies are independent (stored on different physical devices, in different locations), then all copies failing simultaneously becomes arbitrarily unlikely.

Probability Example:

If a single disk has 99.9% annual reliability (0.1% failure rate):

• Single disk: 0.1% chance of annual data loss
• Two independent mirrored disks: 0.1% × 0.1% = 0.0001% chance (both fail simultaneously)
• Three independent copies: 0.000001% chance

With sufficient redundancy, data loss becomes vanishingly improbable—approximating stable storage.

RAID is the foundational technology for implementing stable storage in practice. By spreading data across multiple disks with redundancy, RAID provides both improved performance and fault tolerance.

RAID Levels Relevant to Database Storage:

Database Log vs Data File RAID Considerations:

The RAID 5 Write Penalty:

RAID 5 has a notorious write penalty. For each small write:

1. Read old data block
2. Read old parity block
3. Calculate new parity
4. Write new data block
5. Write new parity block

This '4 I/O for 1 write' penalty makes RAID 5 unsuitable for transaction logs or high-write workloads. RAID 1/10, with only 2 writes per I/O, is preferred for performance-critical paths.

Even with redundant disks, careless write protocols can corrupt data. Stable storage implementations must carefully handle partial writes and write ordering to prevent corruption.

The Partial Write Problem:

A disk block write is atomic (either it completes or it doesn't), but database pages are often larger than disk blocks. An 8KB database page may span multiple 512-byte or 4KB disk sectors. If power fails during a page write, some sectors may have new data, others have old data—a torn page.

Torn Page Preventions:

Write Ordering and Barrier Semantics:

Storage devices and operating systems may reorder writes for performance. This can violate assumptions about ordering:

Application writes:
  1. Write log record (commit indication)
  2. Acknowledge commit to application
  3. Write data page (lazily)

Without barriers, storage might reorder to:
  1. Write data page
  2. Write log record
  3. [CRASH HERE]

Result: Data page written without corresponding log record.
         Recovery cannot redo/undo correctly.

Barrier Operations:

• fsync() / fsyncdata() — Force all preceding writes to persistent storage before returning
• O_DIRECT — Bypass OS page cache, write directly to disk (but doesn't guarantee order)
• Write barriers — Linux blkdev flush commands that order writes

Databases must use appropriate barrier operations after log writes and before data writes to ensure correct ordering. This is a common source of bugs in database storage engines.

Beyond RAID's local disk mirroring, databases employ additional mirroring and replication strategies for higher levels of durability:

Levels of Durability Through Replication:

Synchronous vs Asynchronous Replication:

Durability strength correlates with replication synchronicity:

• Synchronous Replication: Transaction doesn't commit until all replicas acknowledge the write. This guarantees durability even if the primary fails immediately after commit. Cost: increased commit latency.

• Asynchronous Replication: Transaction commits when primary writes complete; replication happens in background. If primary fails before replication completes, committed transactions may be lost. Benefit: no added commit latency.

The Commit Latency Budget:

For a transaction commit involving synchronous cross-region replication:

• Local log write fsync: ~1 ms
• Network round-trip to replica: ~50-100 ms
• Replica log write fsync: ~1 ms
• Total: ~52-102 ms per commit

For latency-sensitive applications, this may be unacceptable. Solutions:

• Accept asynchronous replication with potential data loss (RPO > 0)
• Use quorum replication (wait for K of N replicas)
• Keep replicas geographically close
• Accept the latency for true durability

The choice of storage media significantly impacts stable storage implementation. Each technology has different reliability characteristics and requires different handling:

Comparison of Storage Technologies:

Stable Storage Implications:

HDDs:

• Mechanical arms must physically move, creating multi-millisecond latency
• Sequential writes are far faster than random (arm movement avoidance)
• Physical magnetic storage retains data without power indefinitely
• SMART monitoring can predict failures days/weeks in advance
• Good for capacity-oriented storage, log archival

SSDs:

• No mechanical parts = consistent low latency
• Random and sequential writes are similar performance
• Flash cells wear out after limited write cycles (DWPD = Drive Writes Per Day)
• Enterprise SSDs include power-loss protection (capacitors to complete writes)
• Consumer SSDs may lose in-flight writes on power loss
• Watch for write cliff when cells exhaust spare capacity

NVMe SSDs:

• PCIe-attached, bypassing SATA bottleneck
• Dramatically higher IOPS, lower latency
• Group commit becomes less necessary (fast fsync)
• Enterprise NVMe includes power-loss protection
• Enables performance profiles previously impossible

Database Configuration Differences:

With NVMe, traditional wisdom changes:

• Group commit batch sizes can shrink (less benefit from batching)
• Checkpoint frequency can increase (less impact)
• Log placement on separate device matters less
• SSD settings like trim, write caching require attention

Stable storage must not only survive failures but also detect corruption. Silent data corruption—where bits flip without detection—can be worse than outright failure because it propagates unnoticed.

Sources of Silent Corruption:

Checksum Strategies:

Per-Page Checksums: Databases store a checksum with each page (PostgreSQL, MySQL, Oracle). When reading a page, recalculate the checksum and compare:

┌──────────────────────────────────────────────────────────┐
│  Page Header                                              │
│  ├── Page LSN                                             │
│  ├── Checksum (CRC32, xxHash, etc.)                       │
│  └── Other metadata                                       │
├──────────────────────────────────────────────────────────┤
│  Page Data (rows, index entries, etc.)                    │
├──────────────────────────────────────────────────────────┤
│  Page Footer (optional additional checksum, etc.)         │
└──────────────────────────────────────────────────────────┘

Detection Coverage:

Recovery from Detected Corruption:

• Restore page from replica (if available)
• Restore from backup
• Attempt partial recovery from log records
• Fail fast to prevent corruption spread

Modern production databases implement stable storage through careful combination of multiple techniques:

PostgreSQL Stable Storage Implementation:

MySQL/InnoDB Stable Storage Implementation:

Cloud Database Implementations:

Cloud databases often provide stable storage as a managed service:

• Amazon Aurora: Storage layer automatically replicates across 3 AZs, 6 copies per segment, 4/6 write quorum
• Google Cloud Spanner: Synchronous Paxos replication across zones/regions
• Azure Cosmos DB: Multi-region writes with configurable consistency

These managed implementations abstract stable storage complexity, providing durability guarantees without manual RAID/replication configuration.

Stable storage is the foundation upon which durability is built. Through redundancy, careful protocols, and verification, we transform unreliable physical components into reliable logical storage. Let's consolidate the key insights:

What's Next:

With stable storage providing the reliable foundation and the recovery manager coordinating operations, we're ready to explore recovery algorithm overviews. The next page will survey the major recovery algorithm families—from simple deferred/immediate update schemes to the sophisticated ARIES algorithm that powers most modern databases.