LSM-tree

Deep dive

How it works

Parts:

• memtable — sorted in-memory map (skip list, 64 MiB) that takes all writes
• WAL — append-only log that makes the memtable durable
• SSTable — immutable sorted file: data blocks, index block, filter block, footer
• Bloom filter — per-file bit array that rules out files lacking the key
• manifest — atomically updated list of live files per level
• compaction — background merge of overlapping files into the next level

 put ──► WAL (append) + memtable (skip list, 64 MiB)
                │ full → immutable → flush
                ▼
 L0:  [sst][sst][sst]            overlapping, newest first
 L1:  [a-f][g-m][n-z]            256 MiB, non-overlapping
 L2:  [....10 × L1....]          each level about 10× the previous

1. Write: append to the WAL, insert into the memtable. A delete writes a tombstone.
2. Flush: freeze the full memtable, start a new one, write the frozen one as an SSTable: sorted data blocks (about 4 KiB), an index block (last key per block), a filter block and a footer.
3. Read: memtable → immutable memtables → every L0 file (newest first) → one file per deeper level, found by binary search on the file key ranges. Check the Bloom filter before touching a file. The first hit wins, and a tombstone means "not found".
4. Compaction: when Lᵢ exceeds its target size, pick a file, merge it with the overlapping files in Lᵢ₊₁ and write new files. Keep only the newest version of each key. Drop a tombstone only at the bottom level, or when no older version can exist below.

Code

use std::cmp::Reverse;
use std::collections::{BTreeMap, BinaryHeap};

type Key = Vec<u8>;
type Val = Option<Vec<u8>>; // None = tombstone

fn h64(k: &[u8]) -> u64 { // FNV-1a + final mix; use xxh3/wyhash in production
    let mut h = 0xcbf2_9ce4_8422_2325u64;
    for &b in k { h = (h ^ b as u64).wrapping_mul(0x100_0000_01b3); }
    h ^ (h >> 31)
}
fn probes(k: &[u8], m: u64) -> impl Iterator<Item = usize> {
    let h = h64(k);
    let (h1, h2) = (h, h.rotate_left(32) | 1); // double hashing: k probes from one hash
    (0..7u64).map(move |i| (h1.wrapping_add(i.wrapping_mul(h2)) % m) as usize)
}

struct Run { entries: Vec<(Key, Val)>, bloom: Vec<u64> } // sorted, one entry per key

impl Run {
    fn new(entries: Vec<(Key, Val)>) -> Run {
        let mut bloom = vec![0u64; entries.len() * 10 / 64 + 1]; // 10 bits/key, k=7 → ~1 % FPR
        let m = bloom.len() as u64 * 64;
        for (k, _) in &entries { for p in probes(k, m) { bloom[p / 64] |= 1 << (p % 64); } }
        Run { entries, bloom }
    }
    fn may_contain(&self, k: &[u8]) -> bool {
        let m = self.bloom.len() as u64 * 64;
        probes(k, m).all(|p| self.bloom[p / 64] & (1 << (p % 64)) != 0)
    }
}

pub struct Lsm { mem: BTreeMap<Key, Val>, mem_bytes: usize, limit: usize, runs: Vec<Run> } // runs newest first

impl Lsm {
    pub fn new(limit: usize) -> Self { Lsm { mem: BTreeMap::new(), mem_bytes: 0, limit, runs: vec![] } }
    pub fn put(&mut self, k: Key, v: Vec<u8>) { self.write(k, Some(v)) }
    pub fn delete(&mut self, k: Key) { self.write(k, None) }

    fn write(&mut self, k: Key, v: Val) { // real systems append to the WAL first
        self.mem_bytes += k.len() + v.as_ref().map_or(0, |v| v.len());
        self.mem.insert(k, v);
        if self.mem_bytes >= self.limit { self.flush(); }
    }

    fn flush(&mut self) {
        let entries: Vec<_> = std::mem::take(&mut self.mem).into_iter().collect(); // already sorted
        self.mem_bytes = 0;
        self.runs.insert(0, Run::new(entries));
        if self.runs.len() >= 4 { self.compact_all(); } // size-tiered trigger
    }

    pub fn get(&self, k: &[u8]) -> Option<Vec<u8>> {
        if let Some(v) = self.mem.get(k) { return v.clone(); }
        for r in &self.runs {
            if !r.may_contain(k) { continue; } // skips about 99 % of runs without the key
            if let Ok(i) = r.entries.binary_search_by(|(e, _)| e.as_slice().cmp(k)) {
                return r.entries[i].1.clone(); // tombstone → None, and stop: older runs are shadowed
            }
        }
        None
    }

    /// K-way merge of all runs. The newest version of each key wins, tombstones are dropped (bottom level).
    fn compact_all(&mut self) {
        let mut heap = BinaryHeap::new();
        for (ri, r) in self.runs.iter().enumerate() {
            if let Some((k, _)) = r.entries.first() { heap.push(Reverse((k.clone(), ri, 0usize))); }
        }
        let mut out: Vec<(Key, Val)> = Vec::new();
        while let Some(Reverse((k, ri, pos))) = heap.pop() { // ties pop the lowest ri = newest run
            let r = &self.runs[ri];
            if let Some((nk, _)) = r.entries.get(pos + 1) { heap.push(Reverse((nk.clone(), ri, pos + 1))); }
            if out.last().map_or(false, |(lk, _)| *lk == k) { continue; } // older, shadowed version
            out.push((k, r.entries[pos].1.clone()));
        }
        out.retain(|(_, v)| v.is_some());
        self.runs = vec![Run::new(out)];
    }
}

Complexity and constants

• Levels L ≈ log_T(N / memtable size). With RocksDB defaults (64 MiB memtable, 256 MiB L1, T = 10, 7 levels), the data size reaches the TB range before the last level fills.
• Write amplification: leveled ≈ T·L in the worst case (each byte is rewritten about T times per level), tiered ≈ L. Read amplification for a point read is about 1 I/O with filters and cached index blocks. A range scan must merge one iterator per L0 file plus one per level.
• Bloom memory: 10 bits/key = 1.25 B/key, so 1.25 GB per 10⁹ keys. Monkey-style allocation gives more bits to the smaller levels.
• Flush and compaction are sequential I/O, so even HDDs reach about 100 MB/s or more, and NVMe several GB/s.

Efficiency

• Cost: a write is a WAL append plus a memtable insert; a point read is about 1 disk read with 10 bits/key Bloom filters (1.25 B/key); flush and compaction are sequential I/O (HDD about 100 MB/s, NVMe several GB/s, order of). Bound: disk bandwidth spent on compaction; leveled write amplification is about T·L.
• Levers:
  • tiered or lazy-leveling compaction — write amplification from about T·L to about L (Dostoevsky, SIGMOD 2018) — write-heavy loads that accept more files per read
  • Bloom filters with more bits on small levels — about 1 % false positives at 10 bits/key (Monkey, SIGMOD 2017) — point reads
  • key-value separation — compaction moves only keys (WiscKey, FAST 2016) — large values
  • pinned L0/L1 index and filter blocks, LZ4 above and zstd at the bottom — fewer I/Os and bytes (order of) — mixed workloads
  • merge operators and range tombstones — no read-modify-write, no millions of point deletes — counters, bulk deletes
• Naive → standard → state of the art:
  • update pages in place · one random I/O per write
  • leveled LSM (LevelDB, RocksDB) · sequential writes, write amplification about T·L, space amplification about 1.1×
  • lazy leveling, Monkey filters, value log · write amplification about L on upper levels, about 1 I/O per point read

Implementation notes

• Memtable: a concurrent skip list (RocksDB default) allows lock-free reads and ordered iteration for the flush.
• Block format: about 4 KiB data blocks with prefix-compressed keys and a restart point every 16 keys (binary search over restart points, then a linear scan). Compress blocks with LZ4 in the upper levels and zstd at the bottom.
• Block cache holds uncompressed blocks. Pin the index and filter blocks of L0 and L1 in it.
• Backpressure: RocksDB slows writes at 20 L0 files and stops them at 36 (defaults). Without it, reads degrade without bound.
• Prefix Bloom filters or range filters are needed if scans have a fixed prefix. Plain filters do nothing for ranges.
• Large values: store them in a separate value log (WiscKey, RocksDB BlobDB) so compaction moves only keys.
• Range deletes: write a range tombstone instead of millions of point tombstones.

Pitfalls

• Tombstone build-up: queue-like workloads (insert, then delete) make scans step over millions of tombstones (a known Cassandra issue). Trigger compaction on tombstone density.
• Compaction debt: if ingest outpaces compaction, L0 fills, write stalls follow, and the tree never recovers. Size compaction threads and I/O budget for the peak ingest rate.
• Compaction needs free space for the old and new files at once (tiered can need about 2×).
• Read-modify-write is a read plus a write. Use merge operators to avoid the read.
• A crash between flush and WAL truncation needs a manifest (the list of live files) that is updated atomically.

Variants and alternatives

In production

• Databases: LevelDB, RocksDB (MyRocks), Pebble (CockroachDB), Cassandra, ScyllaDB, HBase, Bigtable, TiKV, Badger.
• Blockchains: Bitcoin Core keeps its chainstate and block index in LevelDB; Ethereum clients keep state in LevelDB or Pebble (Geth).
• Stream processing: Kafka Streams state stores and the Flink RocksDB state backend.
• Distributed storage: Ceph BlueStore keeps object metadata in RocksDB.

Implementations

Sources

• P. O'Neil, E. Cheng, D. Gawlick, E. O'Neil, The Log-Structured Merge-Tree (LSM-Tree), Acta Informatica, 1996. paper
• F. Chang et al., Bigtable: A Distributed Storage System for Structured Data, OSDI, 2006. paper
• L. Lu et al., WiscKey: Separating Keys from Values in SSD-conscious Storage, FAST, 2016. paper
• N. Dayan, M. Athanassoulis, S. Idreos, Monkey: Optimal Navigable Key-Value Store, SIGMOD, 2017. 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 · DOI