Relational Database Internals (Write Path and Recovery)

0) Problem Restatement

Design the core of a relational database like MySQL or PostgreSQL (asked at Flipkart), or the write path and crash recovery of a cloud database that separates compute from storage, like Amazon Aurora (asked at Amazon). You should explain how a SQL query runs, how data is stored on disk, how a commit becomes durable, how concurrent transactions are isolated, and how the database recovers after a crash without losing committed data.

1) Requirements

1.1 Functional

• Tables, rows and SQL queries (SELECT, INSERT, UPDATE, DELETE).
• Indexes for fast lookups and range queries.
• Transactions with ACID properties:
• Atomic: all or nothing.
• Consistent: constraints hold.
• Isolated: concurrent transactions don't see each other's half-done work.
• Durable: once committed, it survives crashes.

1.2 Non-Functional

• Fast point lookups and range scans.
• High concurrency (many transactions at once).
• Quick crash recovery.
• (Cloud variant) Survive the loss of a machine or an availability zone with no data loss.

2) Architecture of One Database Node

2.1 Components

• Parser: turns SQL text into a tree.
• Planner/optimizer: picks the cheapest way to run the query (which index, join order), using statistics about the data.
• Executor: runs the plan, pulling rows from the storage engine.
• Storage engine: pages on disk, B+ tree indexes, the buffer pool, the write-ahead log (WAL), and lock or MVCC management.

2.2 Architecture Diagram

flowchart LR
    C["Client SQL"] --> P["Parser"]
    P --> O["Optimizer - uses statistics"]
    O --> E["Executor"]
    E --> BP["Buffer pool - cached pages"]
    E --> TM["Transaction manager - MVCC, locks"]
    BP -->|"read/write pages"| D[("Data files - B+ tree pages")]
    TM --> WAL[("Write-ahead log")]
    CP["Checkpointer"] --> BP
    CP --> D

3) Storage: Pages and B+ Trees

• Data lives in fixed-size pages (e.g., 8 KB or 16 KB). Disk I/O is done in pages.
• A B+ tree index keeps keys sorted. Inner nodes guide the search, and leaf nodes hold the keys (and rows or row pointers), linked together for fast range scans. With ~500 keys per page, a tree of height 3–4 covers billions of rows, so a lookup is 3–4 page reads, and the top levels are usually cached.
• The buffer pool caches pages in memory. Changed ("dirty") pages are written back later, not on every change.

4) The Write Path (how a commit becomes durable)

Writing every changed page to disk on each commit would be slow (random writes). Instead:

1. The transaction changes pages in the buffer pool (in memory).
2. Each change is also described in a write-ahead log (WAL) record, e.g., "page 812, slot 4: set balance from 100 to 70".
3. On COMMIT, the database appends a commit record and fsyncs the WAL. This is a sequential append, which is fast. Only now does the client hear "committed".
4. Dirty pages are written to the data files later, in the background.

The rule: log first, data later. A data page may never reach disk before the log records describing its changes.

5) Crash Recovery

After a crash, memory is gone, but the WAL and the data files are on disk. Recovery (as in the ARIES algorithm):

1. Analysis: read the log from the last checkpoint (a point where the database recorded which pages were dirty) to find unfinished transactions.
2. Redo: replay logged changes to bring every page up to date, including changes of committed transactions that hadn't reached the data files.
3. Undo: roll back changes from transactions that never committed.

6) Isolation: MVCC and Locks

• MVCC (Multi-Version Concurrency Control): an update creates a new version of the row instead of overwriting it. Each transaction reads from a snapshot, the versions committed when it started. Readers never block writers, and writers never block readers.
• Writers still take row locks so two transactions can't update the same row at once. The second waits, or fails under stricter isolation.
• Isolation levels: Read Committed (each statement sees the latest committed data), Repeatable Read/Snapshot (the whole transaction sees one snapshot), Serializable (behaves as if transactions ran one at a time, using extra checks).
• Old versions are cleaned up later (vacuum in PostgreSQL, purge in MySQL).

7) Cloud Variant — Separate Compute and Storage (Aurora-style)

In a classic setup, the database writes both log and pages, and replicas copy everything, which means a lot of network traffic. Aurora's idea: "the log is the database".

• The compute node sends only WAL records to a distributed storage layer, which keeps 6 copies across 3 availability zones.
• A write is committed when 4 of 6 storage nodes confirm (a quorum), so it survives losing a whole zone.
• Storage nodes apply log records to pages themselves in the background. Compute never writes full pages.
• Crash recovery is nearly instant: storage already has the log, so the new primary just asks storage where the log ends.
• Read replicas share the same storage and get a stream of log records to update their caches. Replica lag is usually milliseconds, and failover to a replica is fast.

8) Trade-offs & Alternatives

9) Wrap-Up

A relational database parses and plans SQL, then runs it against pages cached in a buffer pool and indexed by B+ trees. Commits are durable because the write-ahead log is fsynced first (with group commit for speed), while pages are written later. Checkpoints plus redo/undo recover from crashes, and MVCC gives each transaction a consistent snapshot. Cloud designs go further by shipping only log records to quorum-replicated storage across zones.