SQL SQL In Depth
0%
Guided SQL & Engine Coding Lab

8KB Slotted Page + Write-Ahead Log Crash Recovery Simulator

A disk-page storage engine implementing an 8KB slotted page with downward line-pointer array growth and upward tuple growth, PageLSN tracking, and 3-phase ARIES crash recovery (Analysis, Redo, Undo).

~45 min Advanced Lessons: Hands-On Build: 8KB Slotted Page + Write-Ahead Log Crash Recovery Simulator, Inside an 8KB Slotted Database Page: Header, Line Pointers, Tuples & TOAST, Heap Files, Index Write Amplification, PostgreSQL HOT Updates & fillfactor, Buffer Pool Manager: Pin Counts, Dirty Pages, Clock-Sweep & LRU-K Eviction, Write-Ahead Logging (WAL), Log Sequence Numbers (LSN) & Group Commit, Checkpoints, Dirty Page Flushing & Torn-Page Protection (Full Page Writes)
Guided Algorithm Coding Lab 0/4 Steps Completed

Code & Verify SQL & Storage Engine Invariants in the Browser Workbench

Complete 4 progressive algorithmic steps with guided hints in C++20 (WebAssembly), TypeScript, or JavaScript against automated unit test assertions — zero local setup required.

Architectural Overview

A disk-page storage engine implementing an 8KB slotted page with downward line-pointer array growth and upward tuple growth, PageLSN tracking, and 3-phase ARIES crash recovery (Analysis, Redo, Undo).

In production relational and analytical database systems—spanning PostgreSQL, SQLite, MySQL/InnoDB, and DuckDB—understanding how query clauses, schema constraints, index structures, and storage engines execute under the hood separates surface-level query authors from staff-level database engineers. This capstone build lab guides you through implementing 8KB Slotted Page + Write-Ahead Log Crash Recovery Simulator from first principles with deterministic self-test invariants.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: 8KB Slotted Page Tuple Allocation (pd_lower & pd_upper)

  • Core Database Concept: Growing Line Pointer Slots Downward From Header and Tuple Payloads Upward From Page End
  • Target Module: index.js (SlottedPageWalEngine.insertTuple)
  • Engineering Specification: Implement insertTuple(payloadStr, lsn) to allocate space in an 8192-byte slotted page where header pd_lower grows downward by 4 bytes per slot and pd_upper grows upward by tuple byte length.
  • Implementation Hint: Check freeSpace >= 4 + byteLength; allocate tuple at pd_upper - len, append slot { offset, length, dead: false }, and advance pd_lower += 4.
  • Verification Invariant: deterministic assertion verified in test.js step 1

Step 2: Tuple Deletion & In-Place Page Compaction

  • Core Database Concept: Defragmenting Dead Tuple Holes While Preserving External Slot Numbers (TIDs)
  • Target Module: index.js (SlottedPageWalEngine.compactPage)
  • Engineering Specification: Implement deleteTuple(slotId, lsn) and compactPage() so that dead tuple bytes are reclaimed and pd_upper is restored while every live tuple keeps its original slotId.
  • Implementation Hint: Repack all live tuples contiguously from pageSize downward, updating each live slot’s offset without changing its slot index.
  • Verification Invariant: deterministic assertion verified in test.js step 2

Step 3: ARIES WAL Analysis Phase (Active Tx Table & Dirty Page Table)

  • Core Database Concept: Reconstructing Loser Transactions and Redo Start LSN from the Write-Ahead Log
  • Target Module: index.js (SlottedPageWalEngine.analyzeWal)
  • Engineering Specification: Implement analyzeWal(walRecords) to identify uncommitted loserTxs and the minimum redoStartLsn across dirty pages.
  • Implementation Hint: Scan WAL forward: track active/loser transactions on BEGIN/UPDATE/COMMIT, and record first recLSN per page in dirtyPages.
  • Verification Invariant: deterministic assertion verified in test.js step 3

Step 4: ARIES Redo (Repeating History) & Undo (Loser Rollback)

  • Core Database Concept: Applying Logged Changes Where pageLSN < record.lsn and Rolling Back Losers in Reverse LSN Order
  • Target Module: index.js (SlottedPageWalEngine.recoverWal)
  • Engineering Specification: Implement recoverWal(walRecords, initialPages) to execute ARIES Redo followed by reverse-LSN Undo of uncommitted loser transactions.
  • Implementation Hint: Redo all UPDATE records forward to reconstruct state at crash, then walk loserTx UPDATE records in reverse LSN order restoring beforeImage.
  • Verification Invariant: deterministic assertion verified in test.js step 4

Relational & Storage Engine Guarantees

  • Curriculum Domain: Storage Engines, Buffer Pool & WAL
  • Difficulty & Time Budget: Advanced (~45 minutes)
  • Key Architectural Highlights:
    • 8KB Slotted Page memory layout growing line pointers downward and variable-length tuples upward
    • In-place line-pointer compaction reclaiming fragmented tuple space without changing external TIDs
    • Three-phase ARIES WAL recovery (Analysis, Redo from minRecLSN, and reverse Undo with CLR logging)
  • Core Primitives & Tags: Slotted Page, Write-Ahead Logging, ARIES Recovery, PageLSN, Buffer Pool

Related Curriculum Units

Production Database Context & Verification

This from-scratch relational engine component is engineered with zero external dependencies and deterministic verification harnesses. Every internal database invariant—from three-valued logic (TRUE / FALSE / UNKNOWN), referential integrity, and fan-out-free join pre-aggregation to B+Tree page splits, MVCC snapshot visibility (xmin / xmax), slotted-page compaction, and ARIES write-ahead log crash recovery—is asserted directly in test.js. Use the interactive browser workbench above to complete the 4 guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.