Section 4 of 7 · Systems Foundations

Databases, Transactions & Durable Storage

ML data, feature state and checkpoints depend on relational correctness and crash semantics. This section connects queries to physical work and acknowledged writes to recoverable state.

9 units 22 topics 0/9

Units

9 in this section

4.1 Relational model, relational algebra and SQL joins
explain · implement
3 h
4.2 Aggregations, windows, nulls and point-in-time snapshots
implement
3 h
4.3 Pages, buffer pools and storage layouts
explain
4 h
4.4 Hash indexes, B-trees, selectivity and range scans
explain · derive
3 h
4.5 Sorting, join algorithms and query plans
derive · measure
6 h
4.6 Transactions and isolation anomalies
explain
4 h
4.7 Two-phase locking, timestamp ordering and MVCC
explain · derive
5 h
4.8 Write-ahead logging, recovery, checksums and durability
explain · implement
6 h
4.9 Record evolution, amplification and LSM trees
explain
4 h

Before moving on

Checkpoint

Recover a checksummed append-only store after crashes at every publish boundary, reproduce and prevent one transaction anomaly, and explain one query-plan change with measured logical and physical work.

Deliberately out of scope

Leave for later

Completing every BusTub project
Advanced query optimization and database research systems
Distributed transactions and production storage fleets

Resources for this section

Shared by every unit above

CMU 15-445/645 - database and storage core
Carnegie Mellon Database Groupcourse

primary

Use Fall 2025 Lectures 1-9, 11-18 and 20-22 with their notes: relational model, SQL, storage, buffer pools, layouts, indexes, execution, planning, concurrency, MVCC, logging and recovery. Complete the matching SQL, Storage, Indexes and Filters, Transactions and Recovery homeworks before considering a BusTub project.
PostgreSQL - EXPLAIN and transaction isolation lab
PostgreSQL Global Development Grouppractice

required

Create one normalized schema, joins, an aggregation and a window query. Compare EXPLAIN ANALYZE before and after one justified index. In two sessions, reproduce one documented isolation anomaly and prevent it with a stated database or application invariant.
Designing Data-Intensive Applications, 2nd edition - storage and transactions
Martin Kleppmann and Chris Riccominitheory

reference

Read only the sections on data models and query languages, storage and retrieval, encoding and evolution, and transactions that answer a live design question from the CMU route. Write one comparison table covering layout, index, isolation and recovery trade-offs.
Operating Systems: Three Easy Pieces - persistence and integrity
Remzi and Andrea Arpaci-Dusseautheory

support

Use Chapters 36, 39-45 to trace devices, filesystem structures, journaling, log-structured storage, flash and integrity. Apply the crash sequence to your own append-only store rather than repeating the SYS-1 file experiment.
CMU 15-445 - one reduced BusTub project slice
Carnegie Mellon Database Grouppractice

depth

If a C++ database implementation is the chosen depth lane, complete Project 1 Buffer Pool Manager or Project 2 Database Index, not both during the first pass. Follow the course publication rules and keep code private. The blank-file append-only store remains the core checkpoint.
Point-in-time joins
Feastdocumentation

reference

Read Point-in-time joins and Retrieving features as of the event time. Separate event-time eligibility from actual feature availability; implement the predicates in SQL, not a Feast installation.
CMU Lecture 19: Timestamp Ordering Concurrency Control
Carnegie Mellon Database Groupcourse

reference

Section 1 only, p. 1: timestamp order as a chosen serialization order. The section pool omits Lecture 19; this fills the timestamp-ordering vocabulary gap without assigning all of OCC.
SQLite Write-Ahead Logging
SQLitedocumentation

reference

Sections 1 and 3 only: rollback journaling remains the default and WAL is an opt-in mode. Correct the dated SQLite statement in CMU Lecture 21; inspect the bundled engine without running concurrent WAL writers.

Apply the section

Mini-project · Durable service state and PostgreSQL catalog with transaction evidence (14 to 20 h)

Make the service slice durable with a checksummed log, rebuildable index, crash recovery and versioned compaction, and keep tenant metadata in PostgreSQL 18. Produce the dossier SQL evidence for constraints, plans, transactions and visibility.

Steps

Store every write as a checksummed frame acknowledged only after fsync, refuse further writes after an fsync failure, and test every short-write and truncation boundary against an acknowledged-prefix oracle, rejecting corruption.
Rebuild a key-to-offset index with range support and check it against a replayed oracle, derive the ordered-index page cost against the hash rebuild, and model a pinned buffer pool with its no-victim and failed-writeback cases, choosing the layout for point and scan reads.
Compact by publishing a manifest with lab/publish.py that names the live generation, recover to one complete generation after a crash at each step, retain tombstones until safe, version records compatibly across all writer and reader combinations, and count logical bytes by kind.
Model tenants, credentials, segments and usage in PostgreSQL with keys and constraints doing the validation, and rewrite one join with its filter moved, proving bag equivalence both ways, with each rejection tested.
Export the as-served usage rows at a cutoff inside a read-only REPEATABLE READ transaction, cover nulls, ties and exact-cutoff rows with backfill stability, and store the query, cutoff and digest.
Compare EXPLAIN output before and after one index change with sizes and settings recorded and boundary results equal, force write skew across two SERIALIZABLE transactions with restart and recheck, and trace tuple visibility while separating lock waits from latches.

Deliverables

kv/store.py with checksummed log, rebuilt index, manifest compaction and versioned records, plus crash and compatibility tests.
The acknowledged-prefix report across every injected boundary with recovered prefixes and retained corruption cases.
The catalog, export, plan and transaction evidence with digests, equivalence proofs and visibility traces.
The buffer pool model with its failure tests and the layout choice for the store reads.

Checks

rubric · Self-grade with the rubric below

Rubric

Criterion	Pass	Strong
Durability and recovery	No write is acknowledged before `fsync`, failures stop writes, and the oracle passes at every boundary with corruption rejected.	The report states which failures the tests cover and which real faults lie outside them.
Index, versions and compaction	The rebuilt index matches the oracle, all version combinations pass, and recovery opens one complete generation with tombstones held.	An early tombstone drop is kept as a regression, and byte counters separate the kinds of work.
SQL and transactions	Constraints reject bad rows, the rewrite proves equivalent, the export verifies after backfill, and the skew test restarts cleanly.	Plans are explained from rows and buffers, and visibility evidence separates waits from latches.

Feeds into: Capstone service slice: durable state, recovery and the transaction invariant. The dossier keeps the SQL, plan and visibility evidence.