Log-Structured Merge Trees (LSM Trees)

Overview

A Log-Structured Merge Tree (LSM tree) is a data structure optimized for write-heavy workloads. Instead of updating data in-place (like B-trees), LSM trees buffer writes in memory and periodically flush them to disk as sorted, immutable files. This converts random I/O into sequential I/O, making writes extremely fast at the cost of potentially slower reads.

LSM trees power many modern databases: RocksDB (Facebook), LevelDB (Google), Cassandra, HBase, ScyllaDB, CockroachDB (via RocksDB/Pebble), and TiKV (via RocksDB).

Detailed Explanation

Why LSM Trees?

flowchart TD
    A["B-Tree Write Problem"] --> B["Each write = random I/O<br/>(find page, update in-place)"]
    B --> C["On HDD: ~10ms per write<br/>On SSD: ~100μs per write"]
    C --> D["LSM Solution:<br/>Buffer in memory, write sequentially"]

    style A fill:#ffcdd2
    style D fill:#c8e6c9

LSM Tree Architecture

flowchart TD
    subgraph Memory["In-Memory"]
        WAL2["WAL<br/>(durability)"] --> MT["Memtable<br/>(sorted, in-memory)"]
    end

    subgraph Disk["On-Disk"]
        L0["Level 0<br/>SSTables (overlapping)"]
        L1["Level 1<br/>SSTables (non-overlapping)"]
        L2["Level 2<br/>SSTables (non-overlapping)"]
        L0 --> L1
        L1 --> L2
    end

    MT -->|"Flush when full"| L0
    L0 -->|"Compaction"| L1
    L1 -->|"Compaction"| L2

    style Memory fill:#e1f5fe
    style Disk fill:#fff3e0

Components in Detail

1. Memtable

The memtable is an in-memory sorted data structure that absorbs all incoming writes.

flowchart TD
    A["Write: SET key=5, value='hello'"] --> B["Append to WAL"]
    B --> C["Insert into Memtable"]
    C --> D{"Memtable full?<br/>(e.g., 64MB)"}
    D -->|No| E["Continue accepting writes"]
    D -->|Yes| F["Freeze memtable → Immutable Memtable"]
    F --> G["Flush to disk as SSTable"]
    G --> H["Create new empty memtable"]

    style C fill:#c8e6c9
    style G fill:#e1f5fe

Common memtable implementations:

flowchart LR
    subgraph SkipList["Skip List (RocksDB default)"]
        direction TB
        HEAD --> L1["Level 3: HEAD → 50 → NIL"]
        HEAD --> L2["Level 2: HEAD → 10 → 30 → 50 → NIL"]
        HEAD --> L3["Level 1: HEAD → 5 → 10 → 20 → 30 → 40 → 50 → NIL"]
    end

    style SkipList fill:#e1f5fe

2. SSTable (Sorted String Table)

An SSTable is an immutable, sorted file on disk containing key-value pairs.

flowchart TB
    subgraph SSTable["SSTable Structure"]
        direction TB
        DATA["Data Block 1<br/>key1:val1, key2:val2, ..."]
        DATA2["Data Block 2<br/>key101:val101, ..."]
        IDX["Index Block<br/>key1→Block1 offset<br/>key101→Block2 offset"]
        FILTER["Bloom Filter<br/>(probabilistic membership)"]
        META["Footer<br/>(index block offset, magic number)"]

        DATA --> DATA2
        DATA2 --> IDX
        IDX --> FILTER
        FILTER --> META
    end

    style DATA fill:#e1f5fe
    style IDX fill:#fff3e0
    style FILTER fill:#c8e6c9
    style META fill:#ffcdd2

SSTable on-disk format (simplified, RocksDB):

┌─────────────────────────────────┐
│ Data Block 0                    │  ← Sorted key-value pairs
│  [key_len][key][val_len][val]   │     with prefix compression
│  ...                            │
├─────────────────────────────────┤
│ Data Block 1                    │
│  ...                            │
├─────────────────────────────────┤
│ Meta Block: Bloom Filter        │  ← "Is key X in this SSTable?"
├─────────────────────────────────┤
│ Meta Block: Properties          │  ← Smallest/largest key, count
├─────────────────────────────────┤
│ Index Block                     │  ← Maps last key of each data block
├─────────────────────────────────┤
│ Footer (fixed size)             │  ← Points to index block
└─────────────────────────────────┘

3. Write Path (Putting It All Together)

sequenceDiagram
    participant C as Client
    participant WAL2 as WAL
    participant MT as Memtable
    participant L0 as Level 0 SSTables
    participant L1 as Level 1 SSTables

    C->>WAL2: SET user:1001 → "Alice"
    WAL2->>WAL2: Append to WAL file, fsync
    WAL2->>MT: Insert into memtable (skip list)
    Note over MT: Memtable is 63MB...

    C->>WAL2: SET user:1002 → "Bob" (memtable now 64MB!)
    WAL2->>MT: Insert triggers flush
    MT->>L0: Freeze memtable, write SSTable to L0
    Note over MT: Create new empty memtable
    L0->>L0: Now has 3 SSTables (overlapping keys)
    L0->>L1: Compaction: merge L0 SSTables into L1

4. Read Path

Reads are more complex because data may be in the memtable, any L0 SSTable, or any level below:

flowchart TD
    A["Read: GET key=1001"] --> B["Check Memtable"]
    B -->|Found| Z["Return value"]
    B -->|Not found| C["Check Immutable Memtable (if any)"]
    C -->|Found| Z
    C -->|Not found| D["Check Level 0 SSTables (newest first)"]
    D -->|Found| Z
    D -->|Not found| E["Check Level 1 SSTables"]
    E -->|Found| Z
    E -->|Not found| F["Check Level 2..."]
    F -->|Not found| G["Return NOT FOUND"]

    style Z fill:#c8e6c9
    style G fill:#ffcdd2

Optimizations for reads:

flowchart TD
    A["Read Optimizations"] --> B["Bloom Filters<br/>Skip SSTables that definitely<br/>don't contain the key"]
    A --> C["Block Cache<br/>Cache hot data blocks in memory"]
    A --> D["Key Hints / Index<br/>Binary search within SSTable"]
    A --> E["Fence Pointers<br/>Sparse index for block lookup"]

    style B fill:#c8e6c9
    style C fill:#e1f5fe
    style D fill:#fff3e0
    style E fill:#fff3e0

5. Bloom Filters

A Bloom filter is a probabilistic data structure that answers “Is this key definitely not in the SSTable?” with zero false negatives:

flowchart LR
    A["Key 'alice'"] --> B["Hash functions:<br/>h1=3, h2=7, h3=11"]
    B --> C["Set bits 3, 7, 11<br/>in Bloom filter"]
    C --> D["Lookup 'alice':<br/>Check bits 3, 7, 11"]
    D --> E{"All set?"}
    E -->|Yes| F["Maybe in SSTable<br/>(could be false positive)"]
    E -->|No| G["Definitely NOT in SSTable<br/>(zero false negatives)"]

    style F fill:#fff3e0
    style G fill:#c8e6c9

6. Range Queries and Iterators

LSM trees support efficient range scans via merge iterators that walk all levels simultaneously:

flowchart TD
    A["Range scan: WHERE key BETWEEN 100 AND 200"] --> B["Create MergeIterator"]
    B --> C["Sub-iterator: Memtable"]
    B --> D["Sub-iterator: L0-SST1"]
    B --> E["Sub-iterator: L0-SST2"]
    B --> F["Sub-iterator: L1-SST3"]
    B --> G["Sub-iterator: L2-SST4"]

    C --> H["Priority Queue<br/>(min-heap by key)"]
    D --> H
    E --> H
    F --> H
    G --> H

    H --> I["Yield keys in sorted order<br/>(skipping duplicates/tombstones)"]

    style H fill:#fff3e0
    style I fill:#c8e6c9

Tombstones (Deletions)

LSM trees are append-only, so deletions are handled with tombstone markers:

sequenceDiagram
    participant C as Client
    participant MT as Memtable
    participant SST as SSTable

    C->>MT: DELETE key=1001
    MT->>MT: Insert tombstone: key=1001 → TOMBSTONE

    Note over MT: Later, during compaction...
    MT->>SST: Merge: if key=1001 has tombstone<br/>and exists in older SSTable,<br/>remove both entries

Problem: Tombstones consume space until compaction runs. A “range tombstone” (DELETE WHERE key BETWEEN 100 AND 200) is more efficient than individual tombstones.

LSM vs B+ Tree: The Full Tradeoff

The table at the top of this page says LSM wins writes and B-trees win reads; that is the folk summary. The real comparison is three amplification ratios plus a latency distribution, and every one of them is computable. (The theoretical frame is the RUM Conjecture: read, update, and memory overhead are mutually exclusive minima, so the question is never “which is better” but “which two overheads did each structure pin, and what floor does that force on the third.”)

Write amplification, computed

B+tree: an update to a record rewrites the leaf page it lives on (read-modify-write) plus a WAL record. Worst case per logical update: one full page write, so WAF ≈ page_size / record_size (a 16 KiB page holding 200-byte records ⇒ ~80 bytes written per byte changed, before fill-factor slack), plus WAL. Crucially this cost is independent of dataset size and mostly absorbed by the buffer pool for hot pages — but it is random I/O, the pattern spinning disks and early SSDs hated.

Leveled LSM: every byte gets written once to WAL + memtable, flushed to L0, then rewritten each time it is merged across a level boundary. With size ratio T and L = log_T(N / L0) levels, a record is rewritten ~T times per level crossing, giving:

WAF_leveled ≈ 1 + T × L          (T=10, 5 levels ⇒ ~50x, observed 10–30x when
                                  compaction work is shared/compacted lazily)
WAF_tiered  ≈ 1 + L              (tiered merges each run once per tier:
                                  ~T less write amp, ~T more read amp)

So the fundamental comparison is: B+tree write amplification is large-per-update but constant and random; LSM write amplification is amortized, sequential, and grows logarithmically with data size — and it is a budget you pay in background I/O rather than on the write path. That is exactly the property write-heavy ingest wants, and it is why Facebook migrated UDB from InnoDB to MyRocks (completed 2017), citing space and write amplification — with a reported 62.3% instance-size reduction.

Read amplification

B+tree: depth d = log_F(N) — 3–5 levels for most OLTP datasets; a point lookup is d page reads when cold, ~1 when the upper levels are cached. Range scans walk the leaf chain sequentially. Read cost is essentially independent of how much you’ve written recently.

LSM: a point lookup must check L0 (up to ~T overlapping files), then one file per level, with Bloom filters collapsing the misses: expected reads ≈ L0_files + Σ FPR(level) + 1 (with the 10-bits-per-key filter from earlier, FPR ≈ 1%). The T-tiered/leveled trade shows up here: leveled has one run per level (read amp ~L, write amp ~T·L); tiered stacks T runs per level (read amp ~T·L, write amp ~L). Bloom filters, block cache, and fence pointers are MO investments that buy the read path back — the RUM triangle moving a knob inside one structure.

Space amplification

B+tree: splits leave leaves half-empty after random inserts (50–70% fill ⇒ ~1.4–2.0x slack), plus inner-node overhead. Bounded, always.

LSM: dead versions and tombstones live until a compaction reaches them; in steady state, leveled compaction’s overlap bound is T/(T-1) (~1.11x at T=10) plus per-file metadata — but the bound only holds if compaction keeps up. A compaction backlog is unbounded space amplification (and the disk-full outage that follows), which is why compaction lag is a first-order production metric.

Latency tail

The B+tree’s write cost is paid inline and is small but predictable; occasional page splits are the only spike. The LSM’s write path is uniformly fast, and the cost reappears as compaction spikes: L0 buildup triggers write stalls (RocksDB documents its stall conditions explicitly), merges saturate shared I/O, and read p99 degrades while compaction runs. Engineering responses: a rate limiter to pace compaction I/O, reserved bandwidth for flush vs compaction threads, and scheduler designs like bLSM (SIGMOD 2012) that pace merges specifically to bound operation latency. Read the two tails correctly: B+tree gives you a tight distribution around a slower median; LSM gives you a faster median with fatter tails you must actively manage.

When each wins

The decision procedure: sustained write rates that approach or exceed compaction capacity (write-heavy ingest, high-churn mutable state, streams) favor the LSM — but budget background I/O the way you budget any other resource, and monitor compaction backlog as an SLO. Read-dominated workloads, large range scans, transactional workloads that need tight tails, and datasets small enough that everything is cached anyway favor the B+tree. The hybrid era is real: RocksDB-derived engines run petabyte systems (MyRocks at Meta; CockroachDB’s Pebble; TiKV), while the default OLTP engines people actually transact on remain B+tree-based — and delta-update trees like the Bw-tree (see Bw-Tree and ART) occupy the middle ground by softening the B+tree’s update path without abandoning its read structure. The one durable lesson from the RUM frame: every hardware generation re-opens the question — NVMe’s reduced read/write asymmetry is exactly why the debate is alive again.

LSM in Different Databases

flowchart TD
    subgraph LevelDB["LevelDB (Google)"]
        direction TB
        L1[Single-threaded compaction]
        L2[Level-based compaction only]
        L3["Two memtables (active + immutable)"]
    end

    subgraph RocksDB["RocksDB (Facebook)"]
        direction TB
        R1[Multi-threaded compaction]
        R2[Level-based + Universal + FIFO]
        R3[Column families]
        R4[Prefix Bloom filters]
        R5[Block cache + compressed cache]
    end

    subgraph Cassandra["Cassandra"]
        direction TB
        C1[LSM per table]
        C2[Size-tiered + Leveled + TWCS]
        C3[Partition-level sorting]
    end

    style LevelDB fill:#e1f5fe
    style RocksDB fill:#c8e6c9
    style Cassandra fill:#fff3e0

Cross-References

• Compaction — Strategies for merging and cleaning SSTables
• Database Engines — How LSM engines compare to B-tree engines
• WAL — The durability layer that precedes the memtable
• Key-Value Stores — LSM trees are the backbone of KV stores
• Column-family Stores — Cassandra and HBase use LSM trees
• B-Tree — The alternative to LSM for read-heavy workloads
• The RUM Conjecture — the read/update/space overhead frame that makes the LSM-vs-B-tree tradeoff precise
• Bw-Tree and ART — delta-updating trees: the middle ground between the two corners

Interview Questions

Beginner

Q: What is an LSM tree? A: An LSM tree is a write-optimized data structure that buffers writes in an in-memory sorted structure (memtable), then periodically flushes it to disk as an immutable sorted file (SSTable). Reads check the memtable first, then SSTables from newest to oldest.

Q: Why are LSM trees faster for writes than B-trees? A: B-trees update data in-place, requiring random I/O to find and modify the correct page. LSM trees buffer writes in memory and flush them sequentially to disk, converting random I/O to sequential I/O, which is much faster especially on HDDs.

Q: What is a memtable? A: A memtable is an in-memory sorted data structure (usually a skip list) that buffers incoming writes. When it reaches a size threshold, it’s frozen and flushed to disk as an SSTable, and a new empty memtable is created.

Intermediate

Q: Explain the read path in an LSM tree. How can reads be slow? A: A read must check: (1) the memtable, (2) immutable memtable, (3) L0 SSTables (may have overlapping keys), (4) L1+ SSTables. In the worst case, this means checking many files. Optimizations include Bloom filters (skip SSTables that don’t contain the key), block cache (cache hot blocks), and compaction (merge levels to reduce files).

Q: What is a Bloom filter and how does it help LSM reads? A: A Bloom filter is a probabilistic set membership data structure with zero false negatives. Each SSTable has a Bloom filter. Before reading from an SSTable, the engine checks the Bloom filter — if it says “not present,” the SSTable is skipped entirely. This eliminates most unnecessary I/O for point lookups.

Q: How do deletions work in an LSM tree? A: Deletions insert a tombstone marker instead of actually removing data. The tombstone propagates through levels during compaction. When the tombstone reaches the bottom level and all older versions of the key have been compacted away, the tombstone itself can be removed.

Advanced (FAANG-Level)

Q: What are the three types of read amplification in LSM trees, and how do you minimize each? A:

1. Read amplification from multiple levels: A point lookup may check O(L) levels. Mitigated by Bloom filters (check each level with ~1 false positive rate).
2. Read amplification within a level: Binary search within an SSTable reads O(log B) blocks. Mitigated by block index cache and fence pointers.
3. Read amplification from merging: Range scans must merge-sort across all levels. Mitigated by compaction (fewer overlapping files per level).

Total read amplification ≈ O(L × log B) for point lookups with Bloom filters, where L = number of levels, B = block size.

Q: Design a system to handle 1 million writes/second with LSM trees. What tunings would you make? A:

• Large memtable (256MB+) to reduce flush frequency
• Multiple memtables (pipeline memtable in RocksDB) for concurrent writes
• Larger L0 size before triggering compaction to absorb write bursts
• Rate limiter on compaction to prevent I/O stalls
• Direct I/O to bypass OS page cache (avoid double buffering)
• Separate WAL disk (NVMe) from data disk
• Disable WAL for non-durable workloads (e.g., cache)
• Universal compaction (better for write-heavy) instead of leveled

Q: Explain the LSM-tree write amplification problem. How does leveled compaction reduce it compared to size-tiered? A: Write amplification = total bytes written to disk / bytes written by application. In size-tiered compaction, when L0 fills, all L0 SSTables are merged into L1 — but L1 may already have SSTables, causing cascading merges. Worst case: O(N) per level. In leveled compaction, each level has a size limit (L1 = 10× L0, L2 = 10× L1). When L1 overflows, only one SSTable is merged into L2, and only the overlapping SSTables in L2 are rewritten. This limits write amplification to ~O(level_size_ratio × num_levels) ≈ 10-30×, much better than size-tiered for large datasets.

Common Mistakes

1. Ignoring write amplification: LSM trees can have 10-30x write amplification. On SSDs, this affects lifespan. Monitor with rocksdb.stats in RocksDB.

2. Forgetting about tombstone accumulation: In delete-heavy workloads, tombstones accumulate until compaction reaches the bottom level. Range tombstones are more efficient than individual tombstones.

3. Assuming LSM reads are always slow: With Bloom filters and block cache, point lookups in LSM trees are often as fast as B-trees. Range scans are where LSM trees pay the price.

4. Not tuning compaction: Default compaction settings are rarely optimal. Write-heavy workloads need different tuning (larger L0, universal compaction) than read-heavy (leveled compaction, smaller levels).

5. Disabling WAL without understanding the risk: Disabling WAL improves write throughput by ~2x but means uncommitted memtable data is lost on crash. Only safe for ephemeral data or when replication provides durability.

Summary and Revision Notes

• LSM tree = WAL + Memtable + SSTables (sorted, immutable files on disk)
• Write path: WAL → Memtable → Flush to L0 SSTable → Compaction merges levels
• Read path: Memtable → L0 (newest) → L1 → L2 → … (use Bloom filters to skip)
• Memtable: In-memory sorted structure (skip list); frozen and flushed when full
• SSTable: Immutable sorted file with data blocks, index, Bloom filter
• Compaction: Merges SSTables across levels; reclaims space, removes tombstones
• Bloom filters: Probabilistic “definitely not in this SSTable” → skip unnecessary reads
• Tombstones: Mark deletions; removed during compaction
• Write amplification: Key tradeoff — LSM trades write amplification for write throughput
• RocksDB: Most popular LSM engine; supports level-based, universal, and FIFO compaction
• LevelDB: Simpler predecessor by Google; single-threaded compaction
• LSM vs B+ tree: B-tree pays constant, random, in-line write amplification (page rewrites + WAL) and reads in log-depth; LSM pays amortized, sequential, background write amplification (≈ T×L) and reads across levels with Bloom filters — pick by workload mix and latency-tail tolerance, not doctrine
• Compaction stalls: the LSM’s deferred cost becoming visible; rate-limit compaction and monitor backlog as an SLO

References

1. P. O’Neil, E. Cheng, D. Gawlick, E. O’Neil. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica 33(4), 1996. DOI: 10.1007/s002360050048 — the original leveling/tiering cost model.
2. R. Sears, R. Ramakrishnan. bLSM: A General Purpose Log Structured Merge Tree. SIGMOD 2012. DOI: 10.1145/2213836.2213862 — merge pacing to bound latency.
3. W. Matsunobu, S. Dong, H. Lee. MyRocks: LSM-Tree Database Storage Engine Serving Facebook’s Social Graph. PVLDB 13(12), 2020. DOI: 10.14778/3415478.3415546 — UDB migration from InnoDB (2017); 62.3% instance-size reduction.
4. RocksDB Wiki: Write Stalls and Rate-Limiter — stall conditions and compaction I/O pacing.
5. M. Athanassoulis, M. S. Kester, L. M. Maas. Designing Access Methods: The RUM Conjecture. EDBT 2016. DOI: 10.5441/002/edbt.2016.42 — the theoretical frame for the LSM-vs-B+tree comparison.