Unit 4.9 · about 4 h
265 / 324Record evolution, amplification and LSM trees
Assume Programming's schema-evolution-migrations unit. Stored encodings outlive deployed code, and compaction rewrites persistent history; this unit goes below Alembic into record compatibility and storage-engine amplification.
- explain
You can now
- Specify old/new reader and writer compatibility for stored records, including defaults and unknown fields.
- Explain memtable flush, sorted-run compaction, tombstones and Bloom-filter lookup decisions.
- Account for read, write and temporary-space amplification at a named storage layer.
Covers
- Schema and encoding evolution for stored records
- Read, write, space and compaction amplification vocabulary
- LSM compaction mechanics and bloom filters
Study, in this order
3 steps
- DDIA, second edition: log-structured storageDesigning Data-Intensive Applications, 2nd edition - storage and transactions
Chapter 4, Log-Structured Storage, printed pp. 118-124, including SSTables, Bloom filters and compaction strategies; Comparing B-Trees and LSM-Trees, pp. 129-132
- DDIA, second edition: encoding and evolutionDesigning Data-Intensive Applications, 2nd edition - storage and transactions
Chapter 5, Formats for Encoding Data and JSON, XML, and Binary Variants, printed pp. 163-168; Field tags and schema evolution, p. 171; Dataflow Through Databases, pp. 178-179
Depth · Use compatibility and field-identity rules. Skip byte-by-byte format comparisons and RPC; no protobuf or Avro installation is required.
- Lecture 9: Bloom filtersCMU 15-445/645 - database and storage core
Sections 1-2, Index vs. Filters and Bloom filter, pp. 1-2
Depth · Stop before Skip List. LSM mechanics and Bloom filters are the optional topic's bounded extension, not a full storage engine.
Focus on
- Backward compatibility is new readers accepting old records; forward compatibility is old readers accepting new records. Unknown-field preservation matters when old code reads, modifies and writes a new record.
- An LSM writes to a memtable and durability log, flushes sorted immutable runs, then merges runs by key and recency. A tombstone cannot be dropped while an older value can still be reached or a supported snapshot needs it.
- Write amplification needs a byte or operation denominator and a layer boundary. Count log writes, flushes and compaction separately; engine bytes are not flash-controller bytes.
- Bloom filters can rule out a missing key, but a positive answer still needs lookup. The no-false-negative property assumes correct construction and publication with the matching run; ordinary membership filters do not answer arbitrary intervals.
Reproduce closed-book
[(1,1),(2,1),(3,1)] and newer run [(1,2),(2,2),(4,1)], where each pair is (key,value), and keep the newer duplicate: [(1,2),(2,2),(3,1),(4,1)]. Encode each pair using struct.pack('>QQ',key,value), exactly 16 bytes. Count only run-file writes: the two initial runs total 96 bytes and compaction writes 64, so total writes/input update bytes is \(160/96=5/3\). Keeping both inputs until output publication uses \(160/64=2.5\) times the compacted live-record bytes. These are exact model byte counts, excluding WAL, manifests, filters, filesystem blocks and device GC, not measured device amplification. Then specify a JSON record v1 with key and value, and a compatible v2 that adds optional expires_at defaulting to null. Test all four old/new writer-reader combinations in Python; the old reader must preserve unknown fields if it rewrites records, and the new reader must fill the absent default. Changing value from an integer to an object is a separate breaking change, not the optional-field case.Traps
- Reporting only memtable ingestion bytes as LSM write amplification. Deferred flush and compaction still consume writes.
- Deleting tombstones before considering older runs and active snapshots, allowing old values to reappear.
- Dropping unknown fields on an old reader's rewrite, or reusing a retired binary field tag for a different meaning.
Practice
The section mini-project covers this: versioned record decoding, a four-way compatibility matrix, crash-safe compaction publication, tombstone-retention tests, and separate logical byte counters for append, flush and rewrite work.
Self-test
-
Why is the compaction model's write amplification \(5/3\) rather than \(64/96\)?
The numerator includes both initial run writes and the compaction output: \(96+64\). Counting only the output omits the initial writes. -
Why can temporary space exceed final live data even though compaction removes duplicates?
Old input runs must coexist with the new output until safe publication and reader release. The final output is smaller, but the peak includes both. -
Can a correct Bloom filter's positive answer establish that a value exists?
No. Other keys may have set all queried bits. Lookup must verify the key and handle versions or tombstones. -
Does successfully reading a v2 record with old code prove a safe rolling upgrade?
No. Check new readers on old records, old readers on new records, defaults, and rewrites that preserve unknown fields; rollback may encounter data written by the new version.
Completion criterion
Stop when
Your merged state and byte accounting match the model, all compatibility cases include rewrite checks, and you can explain when tombstones and input runs remain necessary.
Mark passed, then open 5.1 Only mark this when you can do it without notes.Leads to
- 7.7 Compatibility, rollback and revocation during changes Use the compatibility matrix to define rollback boundaries.
Comes after
- 4.8 Write-ahead logging, recovery, checksums and durabilityPreserve this recovery contract during format changes and compaction.
Resources for this unit
- CMU 15-445/645 - database and storage core 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.
- Designing Data-Intensive Applications, 2nd edition - storage and transactions 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.
Also in this section
- PostgreSQL - EXPLAIN and transaction isolation lab 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.
- Operating Systems: Three Easy Pieces - persistence and integrity 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 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 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 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 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.