Levels — a staircase that bounds reads — Build an LSM-tree storage engine (LevelDB / RocksDB style)

Build an LSM-tree storage engine (LevelDB / RocksDB style) (11 scenes)

Scene 07 · Levels — a staircase that bounds reads

L0 may overlap; L1+ enforce non-overlap per level; each level is ~10× the size of the one above. A get touches at most one file per tier.

Previously

Compaction merges files. But picking WHICH files — and how the survivors are arranged on disk — is the choice that defines an LSM's personality.

Scene 07

Levels — a staircase that bounds reads

Watch

Diagram

A vertical staircase of LEVELS — that's the new term: numbered tiers L0, L1, L2 … where each level holds more bytes than the one above (default: 10× more). L0 at top: a few overlapping fat boxes (just-flushed SSTables, key ranges may overlap). L1+ are non-overlapping spans across the keyspace strip [a..z] — within any L1+ level, no two files share a key range, so binary search picks exactly one file per level. A descending GET CURSOR visits at most one box per L1+ tier (after bloom-checking every L0 file). RIGHT SIDE: a stacked bar showing bytes-per-level — typically ~90% concentrated at the bottom (geometric series).

Sources

Watch the staircase build out: L0 overlapping, then L1 non-overlapping across the keyspace, then L2. A get for k descends one file per level — not 100+.

Implementation

Leveled invariants

what each level's files MUST satisfy

1# L0 — overlapping allowed (it inherits memtable arrival order)
2# L1+ — non-overlapping within a level:
3#   for any two files f, g in level L (L >= 1):
4#     f.key_range ∩ g.key_range = ∅
5# bytes(L_i) ≈ multiplier × bytes(L_{i-1})
6# default multiplier = 10 (LevelDB / RocksDB)
7 
8# implication: a get touches
9#   memtable + #L0 (bloom-checked) + 1 per (L1..Ln)

L_i → L_{i+1} compaction

pick one file from L_i, merge with overlapping L_{i+1} files

1def compact_leveled(i):
2    f = pick_file(L[i])
3    overlap = [g for g in L[i+1] if g.key_range ∩ f.key_range]
4    new_files = merge_sort_split(f, overlap, target_size=L[i+1].size)
5    atomic_swap_files(
6        remove=[f] + overlap,
7        add_to_level={i+1: new_files},
8    )
9    # invariant preserved: L[i+1] still non-overlapping.

PreviousCompaction — the GC of sorted files NextEvery byte, written ten times