LSM compaction

Deep dive

How it works

Parts:

• run — sorted immutable entries, stored as one or more SSTables
• level or tier — runs of similar size (leveled: one run per level; tiered: up to T)
• picker — chooses inputs by score, size ratio, key-range overlap
• merge — newest version wins; shadowed versions and eligible tombstones dropped
• throttle — slows or stops writes when L0 files or pending bytes pile up

Operations:

1. Flush: a full memtable becomes an L0 run; L0 runs may overlap.
2. Leveled pick (RocksDB): score of Ln = size / target; L0 = files / trigger (level0_file_num_compaction_trigger, default 4). Highest score first. Take one file of Ln by compaction_pri (default kMinOverlappingRatio: least overlap in Ln+1 relative to its size; kRoundRobin: cursor; LevelDB rotates through the key space) plus its overlapping files of Ln+1. L0 to L1 takes all L0 files.
3. Trivial move: a file with no overlap below moves down without a rewrite (leveled always; universal opt-in).
4. Tiered pick: Cassandra STCS buckets SSTables within 0.5-1.5× of the bucket average and merges 4 to 32. RocksDB universal merges runs adjacent in age, trying in order: age, space amplification (max_size_amplification_percent, default 200), size ratio, run count.
5. Time-window (Cassandra TWCS): STCS in the current window; at its end all its SSTables become one, never compacted again, and dropped whole when expired.
6. FIFO (RocksDB): all files in L0; delete the oldest when the total exceeds max_table_files_size (or ttl).
7. Throttle: RocksDB slows writes at 20 L0 files and stops at 36 (defaults); so do pending compaction bytes.
8. Tombstones: a merge drops one only when no older data lies below (LevelDB: no overlapping file in a deeper level). Cassandra also waits gc_grace_seconds (864000 s) and needs every older SSTable of the partition in the merge. RocksDB ttl (default 30 days) and periodic_compaction_seconds force old files through compaction.

 leveled, T=4                           tiered, T=4
 L0 [r][r]      overlap, <= 4 files     L0 [r][r][r]    4th run triggers merge
 L1 [==========]  1 run, ~4x L0         L1 [====][====]  runs ~4x bigger
 L2 [=======================] ~4x L1     L2 [================]
 Ln file + overlap in Ln+1 -> Ln+1      4 runs of Ln -> 1 run of Ln+1

Worst-case O() values: Luo and Carey survey, Table 1; lazy leveling (tiered, last level leveled): survey text.

Code

Model of both policies. Write amplification = entries written (flush plus merges) per user write; probes = runs searched.

use std::collections::BTreeMap;

type Run = Vec<(u32, Option<u32>)>; // sorted; None = tombstone

/// `newer` wins ties; `last` = nothing older below, so tombstones go.
fn merge(newer: &Run, older: &Run, last: bool) -> Run {
    let (mut i, mut j, mut out) = (0, 0, Run::new());
    while i < newer.len() || j < older.len() {
        let take_new = j == older.len() || (i < newer.len() && newer[i].0 <= older[j].0);
        let e = if take_new { newer[i] } else { older[j] };
        if take_new && j < older.len() && newer[i].0 == older[j].0 { j += 1; } // shadowed
        if take_new { i += 1 } else { j += 1 }
        if !(last && e.1.is_none()) { out.push(e); }
    }
    out
}

struct Lsm { tiered: bool, t: usize, cap: usize, mem: BTreeMap<u32, Option<u32>>,
             lv: Vec<Vec<Run>>, // runs per level, newest first
             user: u64, written: u64 }

impl Lsm {
    fn new(tiered: bool, t: usize, cap: usize) -> Self {
        Lsm { tiered, t, cap, mem: BTreeMap::new(), lv: vec![], user: 0, written: 0 }
    }
    fn write(&mut self, k: u32, v: Option<u32>) {
        self.user += 1;
        self.mem.insert(k, v);
        if self.mem.len() >= self.cap {
            let run: Run = std::mem::take(&mut self.mem).into_iter().collect();
            self.written += run.len() as u64; // the flush
            self.add(0, run);
        }
    }
    fn add(&mut self, l: usize, run: Run) {
        while self.lv.len() <= l + 1 { self.lv.push(vec![]); }
        let last = self.lv[l + 1..].iter().all(|r| r.is_empty()); // no older data below l
        if self.tiered {
            self.lv[l].insert(0, run);
            if self.lv[l].len() >= self.t { // T runs: merge all into one run of level l+1
                let runs = std::mem::take(&mut self.lv[l]);
                let mut out = runs[0].clone();
                for r in &runs[1..] { out = merge(&out, r, false); }
                if last { out.retain(|e| e.1.is_some()); }
                self.written += out.len() as u64;
                self.add(l + 1, out);
            }
        } else { // leveled: one run per level, capacity cap * T^(l+1)
            let old = self.lv[l].pop().unwrap_or_default();
            let out = merge(&run, &old, last);
            self.written += out.len() as u64;
            if out.len() > self.cap * self.t.pow(l as u32 + 1) { self.add(l + 1, out) } else { self.lv[l].push(out) }
        }
    }
    fn get(&self, k: u32) -> (Option<u32>, usize) {
        if let Some(v) = self.mem.get(&k) { return (*v, 0); }
        let mut probes = 0;
        for r in self.lv.iter().flatten() {
            probes += 1;
            if let Ok(i) = r.binary_search_by_key(&k, |e| e.0) { return (r[i].1, probes); }
        }
        (None, probes)
    }
    fn stored(&self) -> usize { self.lv.iter().flatten().map(|r| r.len()).sum() }
    fn tombstones(&self) -> usize { self.lv.iter().flatten().flatten().filter(|e| e.1.is_none()).count() }
    fn compact_all(&mut self) { // one run, no tombstones
        let mut out = Run::new();
        for r in self.lv.iter().flatten().rev() { out = merge(r, &out, false); } // oldest first
        let top: Run = std::mem::take(&mut self.mem).into_iter().collect();
        self.lv = vec![vec![merge(&top, &out, true)]];
    }
}

fn main() {
    let (n, keys) = (200_000u32, 20_000u32);
    for (name, tiered) in [("leveled", false), ("tiered", true)] {
        let (mut db, mut model, mut x) = (Lsm::new(tiered, 4, 1000), BTreeMap::new(), 12345u64);
        for _ in 0..n {
            x = x.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            let (k, r) = ((x >> 33) as u32 % keys, (x >> 20) % 100);
            if r < 85 { db.write(k, Some(r as u32)); model.insert(k, r as u32); } else { db.write(k, None); model.remove(&k); }
        }
        let (mut probes, mut live) = (0, 0);
        for k in 0..keys {
            let (v, p) = db.get(k);
            assert_eq!(v, model.get(&k).copied()); // same answers under both policies
            probes += p; live += v.is_some() as usize;
        }
        println!("{name}: WA {:.2} probes {:.2} stored {} live {live} SA {:.2} tombstones {}",
                 db.written as f64 / db.user as f64, probes as f64 / keys as f64, db.stored(),
                 db.stored() as f64 / live as f64, db.tombstones());
        db.compact_all();
        assert_eq!((db.tombstones(), db.stored()), (0, model.len()));
    }
    // a tombstone must outlive the value it hides: dropped only when merged into the last level
    let mut d = Lsm::new(false, 2, 2);
    for k in 1..=6 { d.write(k, Some(0)); } // key 1 sinks to L1
    d.write(1, None); d.write(7, Some(0));
    assert_eq!(d.tombstones(), 1);
    let mut k = 100;
    while d.tombstones() > 0 { assert_eq!(d.get(1).0, None); d.write(k, Some(0)); k += 1; }
    assert!(d.lv.iter().flatten().flatten().all(|e| e.0 != 1)); // old value left with its tombstone
    assert_eq!(d.get(1).0, None);
}

Run on this Mac (Apple M4 Pro): 200,000 operations on 20,000 keys (85 % puts, 15 % deletes), T = 4, memtable 1,000 entries. Counts are exact:

• leveled: write amplification 6.29, 1.99 probes per get, 36,469 entries stored for 17,010 live (space 2.14×), 2,896 tombstones left.
• tiered: write amplification 2.80, 3.74 probes per get, 57,841 stored (space 3.40×), 6,207 tombstones left.

Space amplification exceeds 1.1× most likely because the levels are not full (not profiled). Forcing last = true in add makes the asserts fail: deleted values reappear.

Complexity and constants

• Levels L ≈ log_T(N / memtable). Worst case per entry: write O(T·L/B) leveled, O(L/B) tiered (B entries per page); point read and short scan O(L) vs O(T·L) (survey Table 1).
• RocksDB's guide example (512 MB L1, T = 10, 500 GB): space 1.14×, write amplification about 1 + 2 + 10 + 10 + 10 = 33.
• Cost drivers: T, levels, overlap with the next level, share of overwritten or deleted data.

Efficiency

• Cost: merges are sequential; sustainable ingest = disk write bandwidth / write amplification (tuning guide: WA 50 on 500 MB/s gives 10 MB/s). Bound: disk bandwidth, then merge CPU.
• Levers:
  • tiered or universal — fewer rewrites, more reads and space (RocksDB wiki) — ingest leveled cannot sustain
  • kMinOverlappingRatio — write amplification more than halved on two Facebook workloads (RocksDB tuning guide) — random updates
  • trivial moves — no rewrite without overlap (RocksDB wiki) — key-ordered inserts
  • larger write buffers — less write amplification (RocksDB write-stalls wiki) — bursty ingest
  • whole-file expiry (TWCS, FIFO) — expired data is never rewritten; FIFO write amplification 1 (Cassandra, RocksDB docs) — TTL data in time order
• Naive → standard → state of the art:
  • merge all data on every flush · rewrites everything each time
  • leveled, picked by overlap · about T per level (33 above)
  • per-level tiered/leveled mix (lazy leveling, UCS) · write cost near tiered, reads near leveled (survey)

Implementation notes

• Cut output files at a target size (LevelDB 2 MB, RocksDB 64 MB) and when they overlap over ten files below (LevelDB).
• max_subcompactions (default 1) splits a job by key range; threads reach max_background_jobs × max_subcompactions.
• Free space: a universal full compaction can double usage; Cassandra LCS needs about 10 %. level_compaction_dynamic_level_bytes (default true) bounds space.

Pitfalls

• A Cassandra tombstone that never drops: sstableexpiredblockers lists the SSTables blocking it. gc_grace_seconds below the repair interval resurrects deleted data.
• TWCS fails to expire files when old and new data share an SSTable (USING TIMESTAMP, read repair).
• One column family's write stall stops the whole RocksDB database.
• FIFO with 1000 L0 files and 1 % Bloom false positives: about 10 extra I/Os per query.

Variants and alternatives

In production

• Databases: Cassandra (STCS default; LCS, TWCS; UCS recommended for new tables in the latest docs); ScyllaDB (STCS, LCS, ICS, TWCS); Pebble in CockroachDB (level-based only); TiKV on RocksDB.
• Time-series and IoT: Cassandra docs recommend TWCS for time-series and TTL data; RocksDB docs, FIFO for event logs.
• Stream processing: Flink's RocksDB state backend defaults to LEVEL (also UNIVERSAL, FIFO); state TTL runs in a compaction filter.
• Blockchain: Bitcoin Core wraps LevelDB; go-ethereum has a Pebble backend.

Implementations

Sources

• P. O'Neil, E. Cheng, D. Gawlick, E. O'Neil, The Log-Structured Merge-Tree (LSM-Tree), Acta Informatica, 1996. paper
• N. Dayan, S. Idreos, Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores, SIGMOD, 2018. paper
• C. Luo, M. Carey, LSM-based Storage Techniques: A Survey, VLDB Journal, 2020. paper
• RocksDB wiki: Leveled, Universal, FIFO, Compaction, Tuning Guide, Subcompaction, Write Stalls, Trivial Move; source: advanced_options.h, table_properties_collectors.h
• LevelDB implementation notes
• Cassandra docs: STCS, LCS, TWCS, UCS, tombstones
• ScyllaDB · Pebble · TiKV · Flink config, state TTL