Why CockroachDB Uses LSM Trees (And Why B-Trees Fail at Scale)
In this post we will walk through exactly how LSM trees work - from the in-memory MemTable that absorbs every write, to the immutable SST
Why CockroachDB Uses LSM Trees (And Why B-Trees Fail at Scale)
This is in continuation to my previous story CRDB Key-Value Storage
In this post we will walk through exactly how LSM trees work — from the in-memory MemTable that absorbs every write, to the immutable SST files on disk, to the background compaction process that keeps everything sorted. We will also cover bloom filters, tombstones, MVCC versioning, and the three fundamental trade-offs (write, read, and space amplification) that every engineer working with these databases should understand.
The Problem LSM Solves
Traditional B-Tree databases write directly to disk at random locations:
B-Tree write: “update row at page 4821”
Disk: [page1][page2].......[page4821]...[pageN]
▲
│ seek head here
│ write 8KB
Random I/O — disk head physically moves to location
HDDs: 5-10ms per seek × millions of writes = bottleneck
Even SSDs: random writes wear out cells fasterLSM’s insight: always write sequentially, never randomly. Sort it out later.
Level 0 — The Write Path (MemTable)
Every write goes to memory first:
INCOMING WRITES
│
INSERT (1001,"INFY",50) UPDATE (1001,"RELI",qty=80)
INSERT (2005,"INFY",200) DELETE (1001,"TCS")
│
▼
┌────────────────────────────────────────────────────┐
│ MemTable │
│ (in RAM — sorted by key) │
│ │
│ /Table/54/1/1001/"INFY"/0 @T3 → {qty:50} │
│ /Table/54/1/1001/"RELI"/0 @T4 → {qty:80} │
│ /Table/54/1/1001/"TCS"/0 @T5 → TOMBSTONE │
│ /Table/54/1/2005/"INFY"/0 @T3 → {qty:200} │
│ │
│ (Red-Black tree or skiplist internally) │
│ Size limit: ~64MB │
└────────────────────────────────────────────────────┘
│
│ also written to
▼
┌────────────────────────────────────────────────────┐
│ WAL (Write-Ahead Log) │
│ (sequential append to disk) │
│ │
│ [T3: INSERT 1001/INFY][T3: INSERT 2005/INFY] │
│ [T4: UPDATE 1001/RELI][T5: DELETE 1001/TCS]... │
│ │
│ Purpose: crash recovery only │
│ If node dies → replay WAL → rebuild MemTable │
└────────────────────────────────────────────────────┘ Write is complete the moment it hits MemTable + WAL. No disk seek. Always sequential.
Tombstome: A tombstone is how LSM handles deletes. Because SST files are immutable (you cannot modify a file once written), you cannot actually remove a key from an existing SST file. So instead of removing it, you write a special marker that says “this key is deleted.”
MemTable Fills Up → Flush to L0
When MemTable hits ~64MB, it freezes and flushes to disk as an SST file (Sorted String Table):
MemTable FULL → freeze → become “Immutable MemTable” New writes go to a fresh empty MemTable simultaneously.
Immutable MemTable flushes to disk in background.
FLUSH
│
▼
┌─────────────────────────────────────────────────────────────┐
│ LEVEL 0 (L0) │
│ (on disk — SST files) │
│ │
│ ┌──────────────────┐ ┌──────────────────┐ │
│ │ SST file 1 │ │ SST file 2 │ │
│ │ (oldest flush) │ │ (newest flush) │ │
│ │ │ │ │ │
│ │ 1001/"INFY" @T1 │ │ 1001/"INFY" @T3 │← NEWER version. │
│ │ 1001/"RELI" @T1 │ │ 1001/"RELI" @T4 │ │
│ │ 2005/"INFY" @T1 │ │ 1001/"TCS" @T5 │← TOMBSTONE │
│ │ 2005/"WIPRO"@T1 │ │ 2005/"INFY" @T3 │ │
│ └──────────────────┘ └──────────────────┘ │
│ │
│ KEY RANGES OVERLAP between files ← this is L0's property │
│ Both files have 1001/"INFY" — different timestamps │
└─────────────────────────────────────────────────────────────┘ L0 files can have overlapping key ranges — that’s okay because we know newer file = newer version.
The Full LSM Structure — All Levels
WRITES
│
▼
┌────────────────────────┐
│ MemTable │ RAM ~64MB
│ (mutable, sorted) │
└────────────┬───────────┘
│ flush when full
▼
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ DISK ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
┌──────────────────────────────────────────────────────┐
│ L0 │ SST1 │ SST2 │ SST3 │ SST4 │ │ ~256MB
│ │ overlapping key ranges allowed │
└──────────────────────────────────────────────────────┘
│ compact when L0 has 4+ files
▼
┌──────────────────────────────────────────────────────┐
│ L1 │=====│=====│=====│=====│=====│=====│=====│ │ ~256MB
│ │ NO overlapping ranges — each file owns a span │
└──────────────────────────────────────────────────────┘
│ compact when L1 exceeds size
▼
┌──────────────────────────────────────────────────────┐
│ L2 │==│==│==│==│==│==│==│==│==│==│==│==│==│==│ │ ~2.5GB
│ │ NO overlapping ranges │
└──────────────────────────────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────────┐
│ L3 │=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│ │ ~25GB
│ │ NO overlapping ranges │
└──────────────────────────────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────────┐
│ L4 │=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│ │ ~250GB
│ │ NO overlapping ranges │
└──────────────────────────────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────────┐
│ L5 │=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│=│ │ ~2.5TB
│ │NO overlapping ranges — bulk of data lives here│
└──────────────────────────────────────────────────────┘ - Size multiplier per level: 10x.
- Most data lives at the bottom. Top levels are tiny.
What Is Inside an SST(Sorted String Table) File
Each SST file is an immutable sorted file on disk.
SST File Layout:
┌─────────────────────────────────────────────────────┐
│ DATA BLOCKS │
│ ┌─────────────────────────────────────────────┐ │
│ │ Block 1 (4KB) │ │
│ │ /Table/54/1/1001/"INFY"/0 @T3 → {qty:50} │ │
│ │ /Table/54/1/1001/"RELI"/0 @T4 → {qty:80} │ │
│ └─────────────────────────────────────────────┘ │
│ ┌─────────────────────────────────────────────┐ │
│ │ Block 2 (4KB) │ │
│ │ /Table/54/1/1001/"TCS"/0 @T5 → TOMBSTONE │ │
│ │ /Table/54/1/2005/"INFY"/0 @T3 → {qty:200} │ │
│ └─────────────────────────────────────────────┘ │
│ │
│ INDEX BLOCK │
│ ┌─────────────────────────────────────────────┐ │
│ │ Block 1 → first key: 1001/"INFY", offset:0 │ │
│ │ Block 2 → first key: 1001/"TCS", offset:4K│ │
│ └─────────────────────────────────────────────┘ │
│ │
│ BLOOM FILTER │
│ ┌─────────────────────────────────────────────┐ │
│ │ Probabilistic: "does key X exist here?" │ │
│ │ False positive possible, false negative NOT│ │
│ │ Fits in RAM (~10 bits per key) │ │
│ └─────────────────────────────────────────────┘ │
│ │
│ FOOTER │
│ ┌─────────────────────────────────────────────┐ │
│ │ smallest_key, largest_key, checksum │ │
│ └─────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────┘ Compaction — The Heart of LSM
When L0 has too many files (slow reads, overlapping ranges) → compaction merges and sorts them into L1.
BEFORE COMPACTION:
L0: [SST-A: 1001/INFY@T1, 2005/INFY@T1]
[SST-B: 1001/INFY@T3, 1001/RELI@T4] ← newer, overlaps SST-A
[SST-C: 1001/TCS@T5(tombstone)]
L1: [SST-X: 1001/INFY@T0 → 2005/WIPRO@T0] ← old data, no overlapsCOMPACTION PROCESS:
Step 1: Read all L0 files + overlapping L1 files
Step 2: Merge-sort all KV pairs
Step 3: For same key, keep ONLY newest version:
1001/"INFY" appears in SST-A @T1 and SST-B @T3
→ keep @T3 only, discard @T1
1001/"TCS" appears in SST-C @T5 as TOMBSTONE
→ if no older versions survive → DROP ENTIRELY
Step 4: Write sorted output as new SST files in L1
Step 5: Delete old SST files (L0 files + old L1 file) AFTER COMPACTION:
L0: (empty)
L1: [SST-NEW1: 1001/INFY@T3] {qty:50} ← T3 survived, T1 dropped
[SST-NEW2: 1001/RELI@T4] {qty:80}
[SST-NEW3: 2005/INFY@T1] {qty:200}
[SST-NEW4: 2005/WIPRO@T0] {qty:75}
(1001/TCS is GONE — tombstone + old version both removed) Compaction is always read-old → merge → write-new. Always sequential I/O.
Read Path — How a Key Is Found
READ: SELECT qty WHERE user_id=1001 AND stock_symbol='INFY'
Target key: /Table/54/1/1001/"INFY"/0
Step 1: Check MemTable (RAM)
┌─────────────┐
│ MemTable │ ← binary search in skiplist
│ has key? │ → YES → return immediately (fastest path)
└─────────────┘
│ NO
▼
Step 2: Check Immutable MemTable (RAM, being flushed)
┌──────────────────────┐
│ Immutable MemTable │ → YES → return
└──────────────────────┘
│ NO
▼
Step 3: Check L0 files (newest first — they can overlap)
┌────────────────────────────────────────────────┐
│ SST file 4 (newest L0) │
│ Check bloom filter: "is 1001/INFY here?" │
│ Bloom says NO → skip entire file (no disk I/O)│
└────────────────────────────────────────────────┘
┌────────────────────────────────────────────────┐
│ SST file 3 │
│ Check bloom filter: YES (maybe) │
│ Check footer: smallest=1001/HDFC, │
│ largest=1001/TCS │
│ 1001/INFY falls in this range → check index │
│ Binary search index → find block offset │
│ Read 4KB block → find key → return value │
└────────────────────────────────────────────────┘
│ NOT IN L0
▼
Step 4: Check L1 (no overlaps → only ONE file can have this key)
Check each SST footer: does range contain 1001/INFY?
Binary search → find the one SST → bloom filter → read block
│ NOT IN L1
▼
Step 5: L2, L3... until found
Worst case: MemTable miss + L0(all files) + L1 + L2 + L3 + L4 + L5
= many disk reads → this is LSM's read amplification problemBloom Filter — The Magic That Makes Reads Fast
Without bloom filters, every read would have to check every SST file. Bloom filters make this O(1) per file.
Bloom filter for SST file: A bit array of N bits, all starting at 0
INSERT key "1001/INFY":
Hash with 3 different hash functions:
h1("1001/INFY") = 4 → set bit 4 = 1
h2("1001/INFY") = 17 → set bit 17 = 1
h3("1001/INFY") = 31 → set bit 31 = 1
Bit array:
[0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
▲ ▲ ▲
bit 4 bit 17 bit 31
LOOKUP key "2005/WIPRO" (not in this file):
h1("2005/WIPRO") = 4 → bit 4 = 1 ✓
h2("2005/WIPRO") = 22 → bit 22 = 0 ✗ ← STOP
Result: DEFINITELY NOT in this file → skip entire file
LOOKUP key "1001/INFY":
h1("1001/INFY") = 4 → bit 4 = 1 ✓
h2("1001/INFY") = 17 → bit 17 = 1 ✓
h3("1001/INFY") = 31 → bit 31 = 1 ✓
Result: PROBABLY in this file → go do actual disk read
False positive: all 3 bits happen to be set by OTHER keys
→ bloom says "maybe" → disk read → key not found
→ wasted one read, but correctness maintained
False negative: NEVER possible
→ if key is in file, its bits are always set Bloom filters live in RAM (~10 bits per key). 1 billion keys = ~1.25GB of bloom filters in RAM.
The Three Amplification Trade-offs
LSM makes a deliberate trade-off.
- Write Amplification
One logical write → written multiple times during compaction
L0→L1→L2→L3 compaction = same data written 4 times
Write amp factor: typically 10-30x
Example: INSERT one row
1. Write to WAL
2. Flush to L0 SST
3. Compact into L1 SST
4. Compact into L2 SST
...
CRDB mitigates: compaction runs in background, doesn't block writes- Read Amplification
One logical read → may check multiple SST files
Worst case: check all levels
Read amp factor: number of levels (typically 5-7)
CRDB mitigates: bloom filters skip most files instantly
block cache keeps hot SSTs in RAM - Space Amplification
Old versions + tombstones exist until compaction cleans them
A deleted row still takes space until GC + compaction
Space amp factor: typically 1.1x (10% overhead)
CRDB mitigates: MVCC GC runs after 25h TTL compaction drops tombstones Writes Reads Space
B-Tree: HIGH LOW LOW ← random I/O writes
LSM: MEDIUM MEDIUM MEDIUM ← sequential everything 메타데이터
- post_id
- 3a5ec87dfae4
- slug
- lsm-trees-demystified-how-cockroachdb-and-rocksdb-store-your-data-3a5ec87dfae4
- url
- https://medium.com/@meenakshi_kumari/lsm-trees-demystified-how-cockroachdb-and-rocksdb-store-your-data-3a5ec87dfae4
- canonical_url
- https://medium.com/@meenakshi_kumari/lsm-trees-demystified-how-cockroachdb-and-rocksdb-store-your-data-3a5ec87dfae4
- author_url
- https://medium.com/@meenakshi_kumari
- status
- ok
- fetched_at
- 2026-06-09 15:37:30
