Database Storage Engines: Slotted Pages, Buffer Pool Management, and WAL/ARIES Recovery

1. Problem and Motivation

At the core of every database management system (DBMS)—from relational giants like PostgreSQL and MySQL InnoDB to embedded engines like SQLite and TiKV—lies the Storage Engine. The storage engine is responsible for the physical organization of bytes on disk, memory management, index traversal, and durability across unexpected power failures and kernel crashes.

Consider the engineering dilemma confronting a storage engine:

1. The Physical Memory Hierarchy Gap: CPU registers and L1/L2 caches operate in nanoseconds; DRAM operates in 50–100 nanoseconds; high-performance NVMe SSDs require 10–50 microseconds; traditional spinning hard drives require 5–10 milliseconds. A single unbuffered disk read is roughly 100,000 times slower than a memory lookup.
2. Variable-Length Data and Compaction: User data consists of variable-length strings (VARCHAR, TEXT, JSONB). As rows are updated and deleted, storage space fragments into non-contiguous gaps. The engine must pack and defragment records on disk without breaking external secondary index references.
3. The ACID Durability Dilemma (STEAL / NO-FORCE):
   • To achieve high write throughput, the engine cannot force every dirty database page to disk on every COMMIT (a FORCE policy would cause thousands of random disk I/O operations per second).
   • Under memory pressure, the engine must be able to evict a modified memory page to disk even if the modifying transaction has not yet committed (a STEAL policy).
   • How can a database guarantee that committed data is never lost (Durability) and uncommitted changes are never permanently visible (Atomicity) if pages are flushed asynchronously and uncommitted data resides on disk?

+---------------------------------------------------------------------------------------------------+
|                                 THE STEAL / NO-FORCE MATRIX                                       |
+---------------------------------------------------------------------------------------------------+
| Policy      | Meaning                                           | Architectural Implication       |
+-------------+---------------------------------------------------+---------------------------------+
| STEAL       | Buffer manager can flush dirty pages to disk      | Fast RAM management, BUT        |
|             | before the modifying transaction commits.         | requires UNDO logging in WAL.   |
| NO-STEAL    | Buffer manager CANNOT flush dirty pages to disk   | Enormous RAM required; limits   |
|             | until transaction commits.                        | max transaction size.           |
| FORCE       | All modified pages MUST be flushed to disk        | Catastrophic random I/O latency |
|             | before transaction commit completes.              | on transaction commit.          |
| NO-FORCE    | Transaction can commit as soon as its WAL log is  | Extremely fast commits, BUT     |
|             | flushed; dirty pages flushed lazily in background.| requires REDO logging in WAL.   |
+-------------+---------------------------------------------------+---------------------------------+
| MODERN DBMS CONSENSUS: STEAL + NO-FORCE (Maximizes throughput, requires rigorous WAL + ARIES).    |
+---------------------------------------------------------------------------------------------------+

2. Mental Model & Architectural Overview

The database storage engine operates as a layered hierarchy separating memory buffers from persistent storage.

SYSTEM ARCHITECTURE BLUEPRINTDATABASES

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. Page Header (Fixed Size ~24B) & Slot Directory (Grows Downward ↓)

Establishes the ingress and structural boundary across Page Header (Fixed Size ~24B) & Slot Directory (Grows Downward ↓): page_lsn (8B) • page_id (4B); free_start_ptr • free_end_ptr checksum, slot_count = 3; Array of item pointers (4B each).

Architectural Invariant: Tuple RID: (page_id, slot_number).

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Page Table (Hash Index in RAM) & Buffer Frames Array (Fixed Capacity)

Coordinates core data-plane execution and state transitions through Page Table (Hash Index in RAM) & Buffer Frames Array (Fixed Capacity): Maps page_id → frame_id Page 42 → Frame 3, Page 88 → Frame 0; Frame 0: [Data Page 88 | pin=2 | dirty=1]; Frame 1: [Data Page 12 | pin=0 | dirty=0].

Architectural Invariant: Reads: 8 KB block / Writes: Doublewrite buffer.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. Latch Crabbing Protocol (B+ Tree) & Transaction Mutation

Enforces durability, state convergence, and output verification across Latch Crabbing Protocol (B+ Tree) & Transaction Mutation: Acquire child latch → verify child is safe Release parent latch (avoids deadlock); 1. Append log record to WAL Buffer; LSN 101: Tx1 UPDATE Page 88 (Old, New).

Architectural Invariant: Scans backward to roll back active TXs. Writes Compensation Log Records (CLRs) Guarantees no repeated undos on recrash!.

The Three Foundational Components:

1. Slotted Page Physical Storage: Disk files are divided into fixed-size blocks (typically 8 KB in PostgreSQL, 16 KB in MySQL InnoDB, 4 KB in SQLite). Within each page, a header and a slot directory grow downwards from the top, while variable-length user tuples grow upwards from the bottom.
2. Buffer Pool Manager: An in-memory cache of fixed-capacity page frames. It maintains an in-memory hash table mapping PageID -> FrameID. When a query requests a page, the buffer pool provides a memory pointer. If the page is missing, it evicts an unpinned frame (using Clock-Sweep, 2Q, or LRU-K) and reads the page from disk.
3. Write-Ahead Logging (WAL) & ARIES Recovery: An append-only sequential log recording every modification before that modification touches disk data pages. Every log record and page header stores a monotonically increasing Log Sequence Number (LSN). If the machine loses power, the ARIES algorithm analyzes the log, redoes all logged changes forward, and undoes all uncommitted transactions backward.

3. Terminology & Core Mechanics

• Page / Block: The fundamental unit of disk transfer and caching (typically 8 KB or 16 KB). The operating system and hardware disk controller transfer data in units of pages.
• RID (Record Identifier / Item Pointer): A stable logical pointer to a tuple, structured as a tuple (PageID, SlotNumber). Secondary indexes store RIDs rather than physical byte offsets.
• Slotted Page: A page organization format containing a fixed-size header, an array of slot pointers (offset and length), an unallocated free space hole, and variable-length data tuples.
• Buffer Frame: A region of contiguous RAM sized exactly to hold one physical disk page.
• Pin Count: An atomic reference counter tracking how many concurrent worker threads are currently executing operations on a page in memory. A frame with pin_count > 0 is strictly protected from buffer eviction.
• Dirty Bit: A boolean flag indicating that a page in the buffer pool has been modified in RAM but has not yet been written back to persistent disk storage.
• Log Sequence Number (LSN): A 64-bit integer monotonically assigned to every WAL record, representing its exact byte offset in the write-ahead log stream.
• ARIES (Algorithms for Recovery and Isolation Exploiting Semantics): The industry-standard recovery protocol invented by C. Mohan at IBM, providing atomicity and durability under concurrent transactions.

4. Internal Workings & Algorithms

1. Slotted Page Mechanics & page_lsn Recovery Anchors

In Step 16 (CORE-M08-004), we introduced the Slotted Page layout inside $B^{+}$-Tree leaf nodes for binary searching variable-length keys. Here in the storage engine layer, we focus on how slotted heap/index pages maintain stable external Record Identifiers (RID = (PageID, SlotNumber)) during in-page defragmentation and how the page header’s page_lsn field coordinates Buffer Pool eviction with Write-Ahead Logging (ARIES).

In early database architectures, rows were appended sequentially to pages. However, when an existing row was updated with longer data (e.g., updating 'John' to 'Jonathan'), or when rows were deleted, the page suffered severe fragmentation:

+-------------------------------------------------------------------------------+
|                       8 KB SLOTTED PAGE PHYSICAL LAYOUT                       |
+-------------------------------------------------------------------------------+
| [Page Header]                                                                 |
|   - page_lsn (8 bytes)         : LSN of the last update to this page          |
|   - checksum (4 bytes)         : CRC32 integrity checksum                     |
|   - page_id (4 bytes)          : Unique block index within tablespace file    |
|   - lower / free_start (2B)    : Byte offset to start of free space hole       |
|   - upper / free_end (2B)      : Byte offset to end of free space hole         |
|   - slot_count (2 bytes)       : Number of items in slot directory            |
+-------------------------------------------------------------------------------+
| [Slot Directory] (Grows Downward ->)                                          |
|   - Slot 0: offset = 8092, length = 100 bytes                                 |
|   - Slot 1: offset = 7942, length = 150 bytes                                 |
|   - Slot 2: offset = 7700, length = 242 bytes                                 |
+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
|                                                                               |
|                   CONTIGUOUS UNALLOCATED FREE SPACE HOLE                      |
|                     (free_start_ptr ---> free_end_ptr)                        |
|                                                                               |
+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
| [Tuple Storage] (<- Grows Upward)                                             |
|   - Tuple 2 at byte 7700: [Header (16B), "Carol", "carol@example.com", 29]    |
|   - Tuple 1 at byte 7942: [Header (16B), "Bob", "bob@example.com", 34]        |
|   - Tuple 0 at byte 8092: [Header (16B), "Alice", "alice@example.com", 28]    |
+-------------------------------------------------------------------------------+

Why the Slot Directory is Invaluable:

1. Zero External Index Invalidation: Secondary indexes (e.g., index on email) store RID = (Page 42, Slot 1). If Bob’s record is moved within Page 42 during defragmentation, only Slot 1’s internal offset pointer is updated. Secondary B+ Tree indexes require zero updates!
2. Constant-Time Deletion (Tombstones): Deleting a record sets Slot.offset = 0 (a tombstone). The slot remains in the directory so slot numbers for subsequent tuples do not shift.
3. Contiguous Compaction: Because the free space is maintained as a single hole between lower and upper, defragmenting a page is an $O(N)$ memory copy that shifts tuples to the bottom of the page and recalculates slot directory offsets.

2. Buffer Pool Management & The Clock-Sweep Algorithm

The Buffer Pool is a pre-allocated array of in-memory frames. The storage engine maintains a Page Table (hash map) to locate pages in RAM without scanning disk:

Incoming Query (Page ID 42)
         |
         v
+------------------+     Page in RAM?
|    Page Table    | -------------------> Frame 3 returned (Increment pin_count)
+------------------+
         |
         | Page Miss
         v
+------------------+
| Eviction Policy  | ---> Find unpinned victim frame (pin_count == 0)
+------------------+
         |
         | Is victim frame dirty?
         v
+------------------+
| Write to Disk    | ---> [WAL check: PageLSN <= FlushedLSN] -> Flush to disk
+------------------+
         |
         v
+------------------+
| Read Page 42     | ---> Read from disk into victim frame -> Update Page Table
+------------------+

Why Standard LRU Fails (Buffer Cache Pollution):

In a standard Least-Recently-Used (LRU) queue, a large sequential table scan (e.g., SELECT * FROM large_log_table) reads millions of pages that are accessed only once. This flushes the entire buffer pool, evicting frequently accessed index root pages and hot customer records!

The Clock-Sweep (Second-Chance) Replacement Algorithm:

Database engines (such as PostgreSQL) implement the Clock-Sweep algorithm to achieve near-LRU efficiency with $O(1)$ overhead and zero lock contention on page hits:

1. Frames are arranged in a circular buffer with a sweeping Clock Hand.
2. Each frame maintains a usage counter ref_bit (or usage count $\mathrm{0..5}$).
3. When a page is accessed in memory, its ref_bit is incremented.
4. When an eviction candidate is needed:
   • The clock hand inspects frame[hand].
   • If pin_count > 0: Skip (page is actively in use).
   • If ref_bit > 0: Decrement ref_bit and advance the hand.
   • If ref_bit == 0: Select this frame as victim! Advance the hand and terminate.

3. Coordinating B+ Tree Latch Crabbing with Buffer Pool Pinning

In CORE-M08-004, we examined how Latch Crabbing (Lock Coupling) prevents root serialization during concurrent $B^{+}$-Tree splits. At the Buffer Pool layer, every latch operation is paired with frame pinning (pin_count) and page_lsn updates:

• Before acquiring a Shared (S) or Exclusive (X) latch on a child page, the worker thread must first call acquirePage(childPageId) on the Buffer Pool Manager to increment pin_count > 0 so the Clock-Sweep evictor cannot steal the frame while the thread waits on or holds the latch.
• When releasing a parent latch during crabbing (releaseShared() / releaseExclusive()), the thread immediately calls unpinPage(parentPageId, isDirty)—setting isDirty = true and advancing the slotted page header’s page_lsn whenever an in-place tuple mutation or split modified the page:

+---------------------------------------------------------------------------------------------------+
|                                 B+ TREE LATCH CRABBING RULES                                      |
+---------------------------------------------------------------------------------------------------+
|  1. Read Traversal:                                                                              |
|     - Acquire Shared (S) latch on Child.                                                         |
|     - Release Shared (S) latch on Parent.                                                        |
|     - Repeat down to leaf. (Allows thousands of concurrent readers).                             |
|                                                                                                   |
|  2. Write / Insert Traversal:                                                                     |
|     - Acquire Exclusive (X) latch on Parent.                                                     |
|     - Acquire Exclusive (X) latch on Child.                                                      |
|     - Check if Child is "Safe" (has room for insertion without splitting).                       |
|     - IF Child is Safe: Immediately RELEASE Exclusive (X) latches on Parent and all ancestors!   |
|     - IF Child is Unsafe (Full): Retain latches on ancestors to support upward node split.       |
+---------------------------------------------------------------------------------------------------+

5. Mathematical / Performance Model

Let us mathematically analyze buffer pool hit ratios, disk I/O savings, and write amplification.

1. Buffer Pool Hit Ratio and Effective Access Time (AMAT)

Let:

• $T_{\text{RAM}}=100\text{ ns}$ (memory access latency)
• $T_{\text{Disk}}=100\mu \text{s}=100,000\text{ ns}$ (NVMe SSD random read latency)
• $H$: Buffer pool cache hit ratio ($0\le H\le 1$)

The Average Memory Access Time (AMAT) for a database page is: $$\text{AMAT}=T_{\text{RAM}}+(1-H)\cdot T_{\text{Disk}}$$

2. Write Amplification: B+ Trees vs. LSM Trees

Consider a transaction that updates a single 50-byte balance column in a user account record:

• In-Place Update (B+ Tree / InnoDB):

  1. Append a 60-byte log entry to the Write-Ahead Log: $W_{\text{WAL}}=60\text{ bytes}$.
  2. The page in RAM becomes dirty.
  3. When the buffer pool flushes the dirty page to disk, it writes the entire 16 KB page: $W_{\text{Page}}=16,384\text{ bytes}$.
  4. With a doublewrite buffer, it writes $16\text{ KB}\times 2=32,768\text{ bytes}$.
  $${\text{Write Amplification Factor (WAF)}}_{\text{B+Tree}}=\frac{32,768+60}{50}\approx 656$$

• Append-Only Engine (LSM Tree / RocksDB):

  1. Append 60-byte log entry to WAL: $W_{\text{WAL}}=60\text{ bytes}$.
  2. Insert entry into in-memory Memtable (zero immediate disk data writes).
  3. Background compaction merges sorted runs sequentially in large contiguous batches. Average LSM write amplification ranges between 10 and 30.

This explains why LSM Trees are vastly superior for write-heavy ingestion workloads, whereas B+ Trees excel at predictable, low-latency point reads and range scans.

6. Real Implementation & Systems Comparison

7. Production Code Engine: Slotted Page & Buffer Pool Manager

The following TypeScript implementation demonstrates:

1. Physical binary serialization of an 8 KB Slotted Page with slot directory offsets and reverse tuple packing.
2. An in-memory Buffer Pool Manager with frame tables, page pinning, dirty-page tracking, and the Clock-Sweep eviction algorithm.

/**
 * Production-Grade Database Storage Engine Simulator
 * Slotted Page Binary Layout and Clock-Sweep Buffer Pool Manager.
 */

export const PAGE_SIZE = 8192; // 8 KB Page
export const PAGE_HEADER_SIZE = 24; // Bytes

export interface SlottedPageHeader {
  pageLsn: bigint; // 8 bytes
  checksum: number; // 4 bytes
  pageId: number; // 4 bytes
  freeStart: number; // 2 bytes (lower boundary: end of slot directory)
  freeEnd: number; // 2 bytes (upper boundary: start of bottom-most tuple)
  slotCount: number; // 2 bytes
}

export interface Slot {
  offset: number; // 2 bytes
  length: number; // 2 bytes
}

/**
 * Slotted Page Binary Serialization & Defragmentation Engine
 */
export class SlottedPage {
  public readonly buffer: Uint8Array;
  private readonly view: DataView;

  constructor(pageId: number, pageLsn = 0n) {
    this.buffer = new Uint8Array(PAGE_SIZE);
    this.view = new DataView(this.buffer.buffer);

    // Initialize Header
    this.view.setBigUint64(0, pageLsn, false); // page_lsn
    this.view.setUint32(8, 0, false); // checksum
    this.view.setUint32(12, pageId, false); // page_id
    this.view.setUint16(16, PAGE_HEADER_SIZE, false); // free_start
    this.view.setUint16(18, PAGE_SIZE, false); // free_end
    this.view.setUint16(20, 0, false); // slot_count
  }

  public get header(): SlottedPageHeader {
    return {
      pageLsn: this.view.getBigUint64(0, false),
      checksum: this.view.getUint32(8, false),
      pageId: this.view.getUint32(12, false),
      freeStart: this.view.getUint16(16, false),
      freeEnd: this.view.getUint16(18, false),
      slotCount: this.view.getUint16(20, false),
    };
  }

  /**
   * Inserts a serialized tuple into the page.
   * Slot directory grows downward; tuple grows upward.
   */
  public insertTuple(data: Uint8Array, lsn: bigint): number | null {
    const hdr = this.header;
    const requiredSpace = 4 + data.length; // 4 bytes for slot pointer + payload
    const availableSpace = hdr.freeEnd - hdr.freeStart;

    if (availableSpace < requiredSpace) {
      return null; // Page is full
    }

    // Allocate tuple at top of freeEnd
    const tupleOffset = hdr.freeEnd - data.length;
    this.buffer.set(data, tupleOffset);

    // Record slot directory entry at freeStart
    const slotIndex = hdr.slotCount;
    const slotDirOffset = PAGE_HEADER_SIZE + slotIndex * 4;
    this.view.setUint16(slotDirOffset, tupleOffset, false);
    this.view.setUint16(slotDirOffset + 2, data.length, false);

    // Update Header
    this.view.setBigUint64(0, lsn, false);
    this.view.setUint16(16, slotDirOffset + 4, false); // free_start moves DOWN
    this.view.setUint16(18, tupleOffset, false); // free_end moves UP
    this.view.setUint16(20, slotIndex + 1, false);

    return slotIndex; // Return RID slot index
  }

  public readTuple(slotIndex: number): Uint8Array | null {
    const hdr = this.header;
    if (slotIndex >= hdr.slotCount) return null;

    const slotDirOffset = PAGE_HEADER_SIZE + slotIndex * 4;
    const offset = this.view.getUint16(slotDirOffset, false);
    const length = this.view.getUint16(slotDirOffset + 2, false);

    if (offset === 0 && length === 0) return null; // Tombstone / deleted tuple

    return this.buffer.slice(offset, offset + length);
  }
}

/**
 * In-Memory Buffer Pool Manager with Clock-Sweep Eviction
 */
export interface FrameControlBlock {
  frameId: number;
  pageId: number;
  page: SlottedPage | null;
  pinCount: number;
  isDirty: boolean;
  refBit: boolean;
}

export class BufferPoolManager {
  private readonly frames: FrameControlBlock[];
  private readonly pageTable = new Map<number, number>(); // PageID -> FrameID
  private clockHand = 0;

  constructor(
    public readonly poolSize: number,
    private readonly diskStorage: Map<number, SlottedPage>
  ) {
    this.frames = Array.from({ length: poolSize }, (_, i) => ({
      frameId: i,
      pageId: -1,
      page: null,
      pinCount: 0,
      isDirty: false,
      refBit: false,
    }));
  }

  /**
   * Fetches a page into memory and increments its pin count.
   */
  public acquirePage(pageId: number): SlottedPage {
    // 1. Cache Hit
    if (this.pageTable.has(pageId)) {
      const frameId = this.pageTable.get(pageId)!;
      const fcb = this.frames[frameId];
      fcb.pinCount++;
      fcb.refBit = true;
      return fcb.page!;
    }

    // 2. Cache Miss: Find victim frame using Clock-Sweep
    const victimFrameId = this.selectVictimFrame();
    const victimFcb = this.frames[victimFrameId];

    // Flush dirty page to disk if needed
    if (victimFcb.isDirty && victimFcb.page) {
      this.flushPageToDisk(victimFcb.pageId, victimFcb.page);
    }

    // Remove old page from Page Table
    if (victimFcb.pageId !== -1) {
      this.pageTable.delete(victimFcb.pageId);
    }

    // Read new page from backing storage
    let page = this.diskStorage.get(pageId);
    if (!page) {
      page = new SlottedPage(pageId);
      this.diskStorage.set(pageId, page);
    }

    // Load into frame
    victimFcb.pageId = pageId;
    victimFcb.page = page;
    victimFcb.pinCount = 1;
    victimFcb.isDirty = false;
    victimFcb.refBit = true;

    this.pageTable.set(pageId, victimFrameId);
    return page;
  }

  public unpinPage(pageId: number, isDirty: boolean): void {
    const frameId = this.pageTable.get(pageId);
    if (frameId === undefined) return;

    const fcb = this.frames[frameId];
    if (fcb.pinCount > 0) fcb.pinCount--;
    if (isDirty) fcb.isDirty = true;
  }

  /**
   * Clock-Sweep Replacement Algorithm
   */
  private selectVictimFrame(): number {
    const n = this.poolSize;
    let scans = 0;

    while (scans < n * 2) {
      const fcb = this.frames[this.clockHand];

      if (fcb.pinCount === 0) {
        if (!fcb.refBit) {
          const selected = this.clockHand;
          this.clockHand = (this.clockHand + 1) % n;
          return selected; // Found unpinned victim with refBit == 0
        }
        // Give second chance: clear refBit and advance
        fcb.refBit = false;
      }

      this.clockHand = (this.clockHand + 1) % n;
      scans++;
    }

    throw new Error('Buffer pool exhaustion: all frames are currently pinned!');
  }

  private flushPageToDisk(pageId: number, page: SlottedPage): void {
    // In production: verify PageLSN <= FlushedLSN before writing
    this.diskStorage.set(pageId, page);
  }
}

function runDemo(): void {
  console.log('=== Storage Internals: Buffer Pool Manager & LRU Replacement ===');
  const disk = new Map([[101, new SlottedPage(101)], [102, new SlottedPage(102)]]);
  const bpm = new BufferPoolManager(4, disk);
  const p1 = bpm.acquirePage(101);
  const p2 = bpm.acquirePage(102);
  console.log('Acquired pages 101 and 102 into memory frames');
  bpm.unpinPage(101, true);
  bpm.unpinPage(102, false);
  console.log('Unpinned pages (101 dirty, 102 clean)');
}
runDemo();

8. Write-Ahead Logging & ARIES Crash Recovery

The gold standard for database durability and crash recovery is ARIES (Algorithms for Recovery and Isolation Exploiting Semantics).

The Fundamental WAL Invariant:

Before any dirty page is written from the buffer pool to persistent disk, all WAL log records up to and including that page’s PageLSN must be flushed (fsync) to the write-ahead log file. This guarantees that if a crash occurs immediately after the page hits disk, the database has the log records required to UNDO uncommitted changes.

[ RAM Buffer Pool ]                             [ Persistent Disk ]
+-------------------------+                   +-------------------------+
| Dirty Page 42           |                   | WAL Log File            |
| Header: PageLSN = 105   |                   | ...                     |
+-------------------------+                   | Record LSN 104          |
             |                                | Record LSN 105          |
   Attempt Disk Flush                         +-------------------------+
             |                                             ^
             v                                             |
   WAL Rule Check: -------------------------------> FlushedLSN >= 105 ?
   - IF FlushedLSN < 105: fsync WAL buffer FIRST!          |
   - THEN: write Page 42 to tablespace file                v
                                              +-------------------------+
                                              | Data File (tablespace)  |
                                              | Page 42 on Disk         |
                                              +-------------------------+

The Three Phases of ARIES Recovery

When a database restarts following a sudden power failure or OS kernel crash, ARIES executes three sequential phases:

Crash Point (Machine Restarts)
       |
       v
+---------------------------------------------------------------------------------------------------+
| 1. ANALYSIS PHASE (Forward Scan from Last Checkpoint to Crash Point)                             |
|    - Scans forward to reconstruct the state of the system at the exact instant of crash.          |
|    - Identifies all Active Transactions (the "Losers" that were uncommitted).                    |
|    - Reconstructs the Dirty Page Table (DPT) and determines the smallest RecLSN.                  |
+---------------------------------------------------------------------------------------------------+
       |
       v
+---------------------------------------------------------------------------------------------------+
| 2. REDO PHASE: "Repeating History" (Forward Scan from min(RecLSN) to Crash Point)                 |
|    - Replays ALL logged changes forward (both committed AND uncommitted transactions!).           |
|    - If PageLSN on disk >= LogRecord.LSN, skip (already on disk).                                 |
|    - Restores the database pages to the exact physical state prior to the crash.                  |
+---------------------------------------------------------------------------------------------------+
       |
       v
+---------------------------------------------------------------------------------------------------+
| 3. UNDO PHASE (Backward Scan from Crash Point back to Oldest Active Transaction)                  |
|    - Reverses the changes of all uncommitted "Loser" transactions.                                |
|    - For every undone action, writes a Compensation Log Record (CLR) to WAL.                      |
|    - The CLR contains an UndoNextLSN pointer; if the system crashes during recovery,               |
|      it never re-undos an already undone operation!                                               |
+---------------------------------------------------------------------------------------------------+

9. Operational Perspective, Latency & Failure Modes

10. Knowledge Check

Review the core architectural principles, then complete the 4-question interactive assessment quiz at the end of this lesson:

1. Slotted Page RIDs: Explain why decoupling physical byte offsets from logical slot indices prevents secondary index rewrites during compaction.
2. Buffer Frame Pinning: Trace how pin counts prevent active memory pages from being selected as eviction victims during concurrent query execution.
3. The WAL Invariant: State the formula relating PageLSN and FlushedLSN, and prove why violating it destroys ACID Atomicity during a crash.
4. ARIES Repeating History: Articulate why the Redo phase replays changes for uncommitted transactions before the Undo phase reverses them.

11. Practical Exercises & Deliverables

Exercise 1: Implement Variable-Length Tuple Compaction

Problem: When tuples are deleted from a slotted page, non-contiguous holes fragment the page.
Deliverable:

1. Add a defragment() method to the SlottedPage TypeScript class in Section 7.
2. Simulate inserting 10 tuples, deleting tuples at slots 2, 5, and 7, and invoking defragment().
3. Prove that all surviving tuples are repacked contiguously against PAGE_SIZE and that freeEnd - freeStart equals the total contiguous unallocated free space.

Exercise 2: Benchmark Clock-Sweep vs. Strict LRU under Sequential Scans

Problem: Demonstrate the vulnerability of naive LRU to buffer cache pollution during full table scans.
Deliverable:

1. Implement a strict LRU buffer manager with 100 frames.
2. Populate the frames with 80 “hot” pages queried 1,000 times each.
3. Simulate a sequential scan of 500 “cold” pages accessed once.
4. Measure the cache hit ratio of subsequent hot queries under LRU vs. Clock-Sweep with usage counters. Graph the results.

12. Summary & Architectural Decision Guide

• Slotted Pages are Universal: Standard page sizes (8 KiB in PostgreSQL, 16 KiB in MySQL InnoDB) balance I/O throughput and fragmentation.
• WAL Invariant is Absolute: Dirty page flush before WAL commit causes catastrophic unrecoverable corruption on crash.
• Clock-Sweep over Pure LRU: High-concurrency engines prefer Clock-Sweep or 2Q eviction to avoid hot mutex bottlenecks on LRU head pointers.
• ARIES Steal/No-Force Policy: Modern databases steal frames (flush uncommitted pages to free RAM) and avoid forcing (relying on WAL replay during crash recovery).

13. Authoritative References & Version Context

• C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz (1992), “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging”, ACM TODS 17(1) — doi.org/10.1145/128765.128770
• Goetz Graefe (2011), “Modern B-Tree Techniques”, Foundations and Trends in Databases 3(4) — doi.org/10.1561/1900000028
• PostgreSQL 16 Documentation — Chapter 30: Reliability and the Write-Ahead Log (WAL) — postgresql.org/docs/16/wal.html
• Version Context: Storage engine architectures reflect PostgreSQL 16 (8 KiB buffer pool), MySQL 8.0/8.4 LTS InnoDB (16 KiB pages), and SQLite 3.45+ WAL mode.