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

Levels — a staircase that bounds reads — non-overlapping key ranges, 10x per tier

Sort the SSTables into numbered tiers where each tier (except the freshly-flushed top) holds non-overlapping key ranges that are 10x bigger than the tier above — and a get touches at most one file per tier, capping read cost regardless of total data.

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

  1. Watch
  2. Try it
  3. Predict
  4. Capture
L0100101102103L1azbytes per levelL0 100%L1 0%level multiplier: 10× (each level holds 10× the bytes of the one above)L0 may overlap (just-flushed). L1+ are non-overlapping per level — exactly one file per tier covers each key.
What to watch for

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+.

Continue unlocks when the animation finishes.
Implementation

Highlighted lines are the ones running in the diagram right now.

Leveled invariants
what each level's files MUST satisfy
# L0 — overlapping allowed (it inherits memtable arrival order)
# L1+ — non-overlapping within a level:
#   for any two files f, g in level L (L >= 1):
#     f.key_range ∩ g.key_range = ∅
# bytes(L_i) ≈ multiplier × bytes(L_{i-1})
# default multiplier = 10 (LevelDB / RocksDB)
 
# implication: a get touches
#   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
def compact_leveled(i):
    f = pick_file(L[i])
    overlap = [g for g in L[i+1] if g.key_range ∩ f.key_range]
    new_files = merge_sort_split(f, overlap, target_size=L[i+1].size)
    atomic_swap_files(
        remove=[f] + overlap,
        add_to_level={i+1: new_files},
    )
    # invariant preserved: L[i+1] still non-overlapping.
Sources

Where this sits in Build an LSM-tree storage engine (LevelDB / RocksDB style)

Scene 07 of 11, in the Compaction act — Levels, write amplification, the amp triangle.. 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.

Up next. Bounded levels are not free. Every byte gets rewritten on its way down — and the multiplier we just chose is the cost dial. Time to count the bytes that hit the disk.

All 11 scenes in Build an LSM-tree storage engine (LevelDB / RocksDB style) · Every curriculum

Designs that use this

Built with Arqly
Every scene in Build an LSM-tree storage engine (LevelDB / RocksDB style) builds on the one before it.All 11 Build an LSM-tree storage engine (LevelDB / RocksDB style) scenes