Problem RestatementProblem
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.
RequirementsRequirements
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.
Architecture of One Database NodeArchitecture
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
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
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 --> DStorage: 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.
The Write Path (how a commit becomes durable)
Writing every changed page to disk on each commit would be slow (random writes). Instead:
- The transaction changes pages in the buffer pool (in memory).
- Each change is also described in a write-ahead log (WAL) record, e.g., "page 812, slot 4: set balance from 100 to 70".
- 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".
- 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.
Group commit: many transactions that commit around the same time share one fsync, which greatly raises throughput.Crash Recovery
After a crash, memory is gone, but the WAL and the data files are on disk. Recovery (as in the ARIES algorithm):
- Analysis: read the log from the last checkpoint (a point where the database recorded which pages were dirty) to find unfinished transactions.
- Redo: replay logged changes to bring every page up to date, including changes of committed transactions that hadn't reached the data files.
- Undo: roll back changes from transactions that never committed.
Deep Dive — Readers and writers getting out of each other's wayDeep dive
A report scans a million rows for thirty seconds while transactions update those same rows. What the engine does with that overlap defines its concurrency story.
Lock everything a transaction touches
Readers take shared locks, writers take exclusive ones, held until commit.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
RPT["Reporting query - 30 s scan"] --> SL["Shared locks on a million rows"]
TX["UPDATE one order"] --> XL["Wants an exclusive lock"]
SL --> BLOCK["Writer waits 30 seconds"]
XL --> BLOCK2["A long write blocks every reader on those rows"]
BLOCK --> TO["Application timeouts, retries, lock queues"]Correct and serialising. One analyst's query stops the application from writing, and one slow write stops everyone from reading. The database has plenty of capacity; it is the locking protocol that is idle.
Row-level locks and weaker isolation levels
Lock rows rather than pages or tables, and let readers run at READ COMMITTED so they do not hold read locks for the whole statement.
This is a large improvement and it is where many systems stop. But a long-running report still sees rows shifting under it as transactions commit mid-scan, so a total computed at the start disagrees with the rows counted at the end — and getting a consistent view back means asking for stronger isolation, which brings the blocking back.
Multi-version concurrency control
Do not overwrite a row; write a new version of it, tagged with the transaction that created it. Every reader is given a snapshot — the set of versions committed as of the moment its statement or transaction began.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
W["UPDATE order 42"] --> V2["Version 2 - created by txn 991"]
V1["Version 1 - created by txn 870"] --> KEEP["Kept while any snapshot can still see it"]
R["Reporting query - snapshot at txn 985"] --> V1
R --> CONS["Consistent view for the whole scan - no locks taken"]
W --> NOBLOCK["Writer never waits for the reader"]
V1 --> GC["Vacuum / undo reclaims versions no snapshot needs"]The costs are real and worth naming:
- Old versions must be reclaimed. Postgres vacuums dead tuples; MySQL and Oracle keep them in an undo log. Either way, a long-running transaction pins every version created since it started — which is why one forgotten open transaction bloats a database.
- Writers still conflict with writers. Two transactions updating the same row still need a lock or a conflict check; MVCC removes the read/write conflict, not the write/write one.
- Snapshot isolation is not serialisable. Two transactions can each read a consistent snapshot and commit changes that could not have happened in any serial order — write skew. Engines that need full serialisability add predicate locking or conflict detection on top.
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.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Index | B+ tree | Fast reads and ranges | LSM tree: faster writes, slower reads |
| Durability | WAL + fsync on commit | Sequential writes, crash-safe | Write pages on commit: slow random I/O |
| Concurrency | MVCC + row locks | Readers don't block writers | Only locks: readers wait on writers |
| Cloud storage | Ship log to quorum storage | Less network, fast recovery | Full page replication: heavy traffic |
Wrap-UpWrap-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.