Storage engines trade read, write and space amplification; the workload picks the trade

heuristic
established
fragment

Scope. The claim that no access method minimizes read, update and space overhead at once is the RUM Conjecture — its authors call it a conjecture, not a theorem, and it is stated for access methods in general, not as a bound with constants. The three amplification ratios are RocksDB’s working definitions; real numbers depend on key distribution, value size, compaction settings and hardware, so the card gives directions of the trade, not magnitudes.

Versions. The Java fragment compiles against rocksdbjni 10.2.1 (setFilterPolicy replaced the deprecated setFilter). level_compaction_dynamic_level_bytes is on by default since RocksDB 8.4, so the explicit call matters only for older versions and for readability.

Primary sources: Athanassoulis, Kester, Maas, Stoica, Idreos, Ailamaki, Callaghan — Designing Access Methods, The RUM Conjecture (EDBT 2016)

References: RocksDB wiki — RocksDB Tuning Guide (amplification factors), RocksDB wiki — Leveled Compaction, RocksDB wiki — Universal Compaction, RocksDB wiki — Write Stalls, RocksDB wiki — RocksDB Bloom Filter, RocksDB wiki — Implement Queue Service Using RocksDB (tombstones and iteration), PostgreSQL 18 documentation — Write Ahead Log settings (full_page_writes)

Other claims on this card, typed separately:

- model
- context-dependent
An LSM tree defers and batches index changes from a memory component into disk components, cutting disk-arm movement for insert-heavy workloads relative to a B-tree, at the price of less efficient finds that need an immediate answer.
Primary sources: O’Neil, Cheng, Gawlick, O’Neil — The Log-Structured Merge-Tree (LSM-Tree) (Acta Informatica 1996)
- heuristic
- context-dependent
RUM Conjecture: an access method that sets an upper bound on two of the read, update and memory overheads has a hard lower bound on the third.
Primary sources: Athanassoulis et al. — Designing Access Methods, The RUM Conjecture (EDBT 2016)

Three ratios describe an engine: write amplification (bytes written to storage per byte written to the database), read amplification (disk reads per query) and space amplification (size on disk per byte of live data). A B-tree updates pages in place: a point read is one root-to-leaf path, but every change rewrites a page and also goes to the WAL. An LSM tree appends to a WAL and a memtable, flushes immutable sorted files and merges them in the background: writes are sequential and cheap up front, while a read may consult several sorted runs, and overwritten or deleted data occupies disk until compaction reaches it. No engine minimizes all three; choosing one without measuring them on your access pattern is choosing blind.

fragment

Java · RocksJava

// Each knob moves cost between the three ratios; none of them is free.
var table = new BlockBasedTableConfig()
    .setFilterPolicy(new BloomFilter(10));          // ~10 bits/key, ~1% false positives:
                                                    // fewer SST reads for point lookups (read amp),
                                                    // paid in memory; no help for plain range scans
var options = new Options()
    .setCreateIfMissing(true)
    .setCompactionStyle(CompactionStyle.LEVEL)      // leveled: low space and read amp,
                                                    // higher write amp than UNIVERSAL (tiered)
    .setLevelCompactionDynamicLevelBytes(true)      // level targets follow the real data size,
                                                    // which bounds space amp
    .setMaxBytesForLevelMultiplier(10)              // fanout: larger = fewer levels (reads),
                                                    // more rewriting per level (writes)
    .setTableFormatConfig(table);
// Switching to UNIVERSAL cuts write amp, but a full compaction keeps inputs and output
// on disk at once: provision free space for roughly twice the data.

The bills arrive late. An LSM engine that accepts writes faster than compaction can merge them accumulates debt, and RocksDB repays it with write stalls: too many immutable memtables, too many L0 files or too many pending compaction bytes slow writes down and then stop them for the whole database. Delete-heavy patterns (a queue, a TTL table) leave tombstones that range scans must step over until compaction removes them; bound the iterator and track the live range instead of scanning from the start. A B-tree pays differently: PostgreSQL writes a full page image to the WAL on the first change of each page after a checkpoint, so checkpoint frequency multiplies WAL volume, and MVCC leaves dead tuples that only vacuum turns back into usable space.

Decision rule. Write down the workload before the engine: point reads vs range scans, update and delete rate, value size, how much free disk and memory the node has, and which latency percentile matters (26). Then measure all three ratios on that workload with the engine’s own statistics rather than benchmark headlines (37). “LSM for writes, B-tree for reads” is a first guess, not an answer: compaction style, fanout, filters and fill factor move an engine far along the curve. Streaming state lives on the same engines, so the same bills show up as checkpoint size and recovery time (82).