Database Management Systems (DBMS) Module 14 – Storage engines, NoSQL and analytics
LSM trees and write-optimised storage
How LSM trees make writes sequential with memtables, SSTables and compaction, and how leveled and tiered compaction trade reads, writes and space.
What you will learn
- Explain how memtables, SSTables, compaction and tombstones turn random writes into sequential ones
- Compare leveled and tiered compaction by read, write and space amplification, with measured numbers
- Choose between a B+ tree engine and an LSM engine for a given workload
Before you start
What you’ll learn · Before you start
What you will learn
- Explain how memtables, SSTables, compaction and tombstones turn random writes into sequential ones
- Compare leveled and tiered compaction by read, write and space amplification, with measured numbers
- Choose between a B+ tree engine and an LSM engine for a given workload
Before you start
On this page
A log-structured merge tree, or LSM tree, is a storage structure that never updates data where it lies. A write is appended to a log, so that it survives a crash, and inserted into a sorted table in memory, the memtable. When the memtable is full it is written out in one sequential sweep as an immutable sorted file, an SSTable, and background compaction merges SSTables, keeping the newest version of each key and throwing the older ones away. Writes become cheap and sequential; a read may have to look in several files, which Bloom filters and compaction keep in check. The design comes from O’Neil, Cheng, Gawlick and O’Neil, who in 1996 proposed deferring and batching index changes and cascading them from a memory component to disk components by merging (O’Neil et al.). RocksDB and Apache Cassandra are built this way, while PostgreSQL, SQLite and MySQL’s InnoDB keep their indexes in B-trees whose pages change in place (MySQL 8.4: InnoDB indexes).
Why updating in place is slow for writes
A B+ tree keeps every key in a leaf page, and a page is the unit the engine reads and writes: 8 kB in PostgreSQL (PostgreSQL 18: page layout), 16 KB by default in InnoDB (MySQL 8.4), and 4,096 bytes by default in SQLite (SQLite: page_size). Change one 100-byte row and the whole page around it must eventually be written back. If random updates are spread over a table much larger than memory, each one tends to dirty a page that no other update shares before it is written, so the disk writes 4,096 to 16,384 bytes for 100 bytes of new data: 41 to 164 times as much, before the log is counted. The writes also land at random places on the disk.
An LSM tree changes the arithmetic. It collects thousands of writes in memory, sorts them, and writes them out together as one file, so the cost of a page write is shared by every key on the page. It pays later instead, when compaction rewrites the data a few times on its way down. Whether that later cost is smaller than the B+ tree’s depends on the compaction policy, which is the question this lesson measures.
The write path: log, memtable, flush
Every write goes to two places, as the RocksDB documentation puts it: the write-ahead log on disk and the memtable in memory (RocksDB: WAL). The log is only appended to, which is the cheapest write a disk can do, and its only job is recovery: after a crash, replaying it rebuilds the memtable that was lost. The memtable keeps the recent writes sorted by key, so that it can answer reads and can be written out in order.
The write path and the read path of an LSM tree
Text description of the diagram
The figure has two panels, the write path on top and the read path under it.
The write path starts with a write, put(key, value) or delete(key). A delete is a write too: it stores a tombstone for the key.
- The write is first appended to the write-ahead log on disk, which is replayed after a crash to rebuild the memtable.
- The write is then inserted into the memtable, a structure in memory kept sorted by key.
- When the memtable is full it is flushed: written out in one sequential sweep as a sorted, immutable file called an SSTable, in level 0. Files in level 0 may cover overlapping key ranges.
- Compaction merges SSTables into the deeper levels 1, 2, 3 and so on, each larger than the one above, and drops versions that newer ones have replaced.
The read path: a read, get(key), checks the memtable first and then the SSTables from newest to oldest, skipping every file whose Bloom filter says the key is not there. The first version it finds, a value or a tombstone, is the answer; a tombstone means the key is deleted.
When the memtable reaches its size limit, the engine starts a new one and flushes the full one: it writes the sorted entries out as an SSTable, short for sorted string table. An SSTable holds its entries in key order, split into blocks, then an index of the blocks and a Bloom filter of its keys, the layout RocksDB’s table format describes (RocksDB: table format). It is never modified again, which is what Cassandra’s documentation means when it calls SSTables immutable and says each one is written once, when a memtable is flushed (Cassandra: storage engine). Once the flushed data is safe in an SSTable, the part of the log that covered it can be deleted.
Fresh SSTables pile up in level 0. Each covers the keys written during one memtable’s lifetime, so their key ranges overlap. Left alone, they would make every read slower; keeping them in check is the job of compaction.
The read path, and Bloom filters
A point lookup, get(key), wants the newest version of the key. It looks in the memtable first, then in the SSTables
from newest to oldest, and stops at the first version it finds. That version may be a value, or it may be a
tombstone, the marker a delete leaves behind, in which case the key counts as deleted even if older files still hold
a value for it. The trace below runs both paths on a few keys:
"""The write and read paths of an LSM tree, traced on six keys, and what goes
wrong when a compaction drops a tombstone too early."""
TOMBSTONE = None # the value a delete writes
def flush(memtable, runs):
"""Write the memtable out as a new sorted run, placed first: newest first."""
runs.insert(0, sorted(memtable.items()))
memtable.clear()
def merge(runs, drop_tombstones):
newest = {}
for run in reversed(runs): # oldest first, so newer versions overwrite
newest.update(run)
return [(k, v) for k, v in sorted(newest.items()) if not (drop_tombstones and v is TOMBSTONE)]
def get(key, memtable, runs):
"""The newest version wins: memtable first, then the runs from newest to oldest."""
if key in memtable:
return memtable[key], "the memtable"
for i, run in enumerate(runs):
for k, v in run:
if k == key:
return v, f"run {len(runs) - i}"
return TOMBSTONE, None
def show_run(name, run):
entries = ", ".join(f"{k}={'(tombstone)' if v is TOMBSTONE else v}" for k, v in run)
print(f" {name}: {entries}")
def show_get(key, memtable, runs):
value, where = get(key, memtable, runs)
if where is None:
answer = "not found (in no run)"
elif value is TOMBSTONE:
answer = f"deleted (a tombstone in {where})"
else:
answer = f"{value} (from {where})"
print(f" get({key}) -> {answer}")
memtable, runs = {}, []
memtable.update({"delhi": 1, "agra": 2, "pune": 3})
flush(memtable, runs) # run 1
memtable.update({"agra": 20, "surat": 4})
memtable["pune"] = TOMBSTONE # delete(pune) is a write too
flush(memtable, runs) # run 2
memtable["kochi"] = 5 # not flushed yet
print("runs on disk, newest first:")
for i, run in enumerate(runs):
show_run(f"run {len(runs) - i}", run)
print("reads:")
for key in ("kochi", "agra", "delhi", "pune", "goa"):
show_get(key, memtable, runs)
print("compact run 2 on its own and drop its tombstones (too early):")
show_get("pune", {}, [merge([runs[0]], drop_tombstones=True), runs[1]])
print("compact run 2 on its own and keep its tombstones:")
show_get("pune", {}, [merge([runs[0]], drop_tombstones=False), runs[1]])
print("compact runs 2 and 1 together, the oldest data, and drop tombstones:")
bottom = merge(runs, drop_tombstones=True)
show_run("run", bottom)
show_get("pune", {}, [bottom])Output
runs on disk, newest first: run 2: agra=20, pune=(tombstone), surat=4 run 1: agra=2, delhi=1, pune=3 reads: get(kochi) -> 5 (from the memtable) get(agra) -> 20 (from run 2) get(delhi) -> 1 (from run 1) get(pune) -> deleted (a tombstone in run 2) get(goa) -> not found (in no run) compact run 2 on its own and drop its tombstones (too early): get(pune) -> 3 (from run 1) compact run 2 on its own and keep its tombstones: get(pune) -> deleted (a tombstone in run 2) compact runs 2 and 1 together, the oldest data, and drop tombstones: run: agra=20, delhi=1, surat=4 get(pune) -> not found (in no run)
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 lsm_trace.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Reading delhi meant looking in run 2 before finding it in run 1. With dozens of SSTables, most of those looks find
nothing, and each one costs a read from disk. The fix is a Bloom filter per SSTable, the structure Burton Bloom
described in 1970 (Bloom): a bit array and k hash functions. Adding a key
sets k bits; testing a key checks the same k bits. If any bit is 0, the key was never added, so a “no” is always
right. If all are 1, the key is probably there, but the bits may have been set by other keys, so a “maybe” is
sometimes wrong. With m bits for n keys and k hash functions, the chance of a wrong “maybe” is about
, smallest when k is about 0.69 times the bits per key.
"""How often a Bloom filter says "maybe" for a key it never saw, measured at three
sizes and compared with the formula (1 - e^(-k n / m))^k."""
import math
MASK = (1 << 64) - 1
def mix64(x):
"""A fixed 64-bit hash of an integer (the finaliser of splitmix64)."""
x = (x + 0x9E3779B97F4A7C15) & MASK
x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK
x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK
return x ^ (x >> 31)
class Bloom:
def __init__(self, n, bits_per_key):
self.m = n * bits_per_key # bits in the filter
self.k = max(1, round(bits_per_key * math.log(2))) # hash functions: ln 2 x bits per key
self.bits = bytearray(self.m // 8 + 1)
def positions(self, key):
h = mix64(key)
h1, h2 = h & 0xFFFFFFFF, (h >> 32) | 1
return [(h1 + i * h2) % self.m for i in range(self.k)]
def add(self, key):
for p in self.positions(key):
self.bits[p >> 3] |= 1 << (p & 7)
def might_contain(self, key):
return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self.positions(key))
N, PROBES = 10_000, 100_000
print(f"{N:,} keys added; {PROBES:,} other keys tested")
print(f"{'bits/key':>9}{'k':>4}{'size':>10}{'measured':>11}{'formula':>10}")
for bits in (5, 10, 15):
f = Bloom(N, bits)
for key in range(N):
f.add(key)
assert all(f.might_contain(key) for key in range(N)) # never a false "no"
false_maybes = sum(f.might_contain(key) for key in range(N, N + PROBES))
formula = (1 - math.exp(-f.k * N / f.m)) ** f.k
print(f"{bits:>9}{f.k:>4}{f.m // 8:>8,} B{false_maybes / PROBES:>10.2%}{formula:>10.2%}")Output
10,000 keys added; 100,000 other keys tested
bits/key k size measured formula
5 3 6,250 B 9.46% 9.18%
10 7 12,500 B 0.87% 0.82%
15 10 18,750 B 0.08% 0.07%
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 bloom_filter.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
At 10 bits per key the measured rate is 0.87 %, close to the formula’s 0.82 %, and each 5 extra bits divide it by about ten. RocksDB’s guide gives the same rule of thumb, about 10 bits per key for a 1 % rate (RocksDB: Bloom filter). A filter of 10,000 keys takes 12,500 bytes, small enough to keep in memory for every SSTable.
Filters help only when the exact key is known. The same guide says whole-key filters are used only for point
lookups; filters built on key prefixes can help a scan that stays inside one prefix, and nothing else. A range
scan, such as every key from agra to kochi, must open every SSTable whose key range overlaps the range and merge
their entries in key order. Range scans are where the number of SSTables shows most directly.
Deletes are writes: tombstones
An LSM tree cannot remove a key from an SSTable, because SSTables are never modified. A delete is therefore a write
of a tombstone, and the trace shows its effect: get(pune) stops at the tombstone in run 2 and reports the key
as deleted, although run 1 still holds the value 3.
The last three steps of the trace show why tombstones must live a while. When compaction merged run 2 on its own and dropped its tombstone, the old value in run 1 came back: a deleted key returned. A tombstone can only be dropped by a compaction that includes every older run that might hold the key, which in practice means a merge into the bottom level. Until then it takes space and slows reads, and a range scan over deleted keys still has to read past each tombstone. Bulk deletes are therefore expensive in an LSM tree, and engines add range deletes and compactions triggered by deletes for that case (RocksDB: deleting a range).
Compaction: leveled and tiered
Compaction merges sorted runs, much as the merge step of merge sort does, keeping only the newest version of each key. The policies differ in when they merge and what they merge together, and that choice sets three costs:
- Write amplification: bytes written to disk for each byte the application wrote.
- Read amplification: SSTables a read must look in.
- Space amplification: bytes on disk for each byte of live data, inflated by old versions and tombstones not yet merged away.
Leveled compaction keeps one sorted run per level below level 0, and each level may hold a fixed factor more data than the one above it, the size ratio T, often 10. In RocksDB, each level except level 0 is one sorted run split into many SSTable files, and when a level grows past its target size, part of it is merged into the overlapping part of the next level (RocksDB: leveled compaction). A read looks in at most one run per level. The cost is rewriting: data arriving in a level is merged with what is already there, so a level is rewritten many times before it fills. RocksDB’s guide calls leveled write amplification “often larger than 10”.
Tiered compaction lets each level collect up to T runs of similar size and merges them all into one run of the next level only when the level is full. Each byte is rewritten about once per level, but a read may have to look in up to T runs per level, and old versions survive longer. RocksDB’s universal compaction belongs to this family, and its documentation describes the trade: lower write amplification, paid for with read and space amplification, and a full compaction that can briefly need double the disk space (RocksDB: universal compaction).
Leveled and tiered compaction with a size ratio of 10
Text description of the diagram
The figure shows the same LSM tree under two compaction policies, with a size ratio of 10 between levels.
Leveled compaction, on top: level 0 holds a few runs that came straight from memtable flushes. Below it, each level holds exactly one sorted run: up to 10 units of data in level 1, up to 100 in level 2 and up to 1,000 in level 3. Runs from level 0 are merged with the overlapping part of level 1, and whenever a level grows past its limit, the overflow is merged into the level below. Every merge rewrites data that is already in the lower level.
Tiered compaction, below: each level holds up to 10 runs of about the same size, 1 unit in level 0, 10 in level 1 and 100 in level 2. When a level has 10 runs, they are merged into one new run that moves to the next level. Each merge rewrites only the runs it merges, so data is rewritten about once per level, but a level can hold up to 10 runs that a read may have to check.
| Cost | Leveled | Tiered |
|---|---|---|
| Writes: rewrites per level | Many: a level is merged again each time data arrives | About one: runs are merged once, when the level fills |
| Point reads without filters | One run per level | Up to T runs per level |
| Range scans | One run per level to merge | Up to T runs per level to merge |
| Space | Close to the live data: few stale versions | Stale versions pile up until the level merges |
| Typical fit | Reads and space matter most | Write-heavy work, such as logs and metrics |
Three amplifications, measured
The store below is a small LSM tree in Python of about 160 lines, written for this lesson to count bytes rather than to be fast: a memtable of 1,000 entries, level 0 compacted when it holds 4 runs, a size ratio of 10, and both policies. The same seeded workload, 100,000 writes over 20,000 keys with 10 % deletes, runs on each, and every read is checked against a dictionary of the expected values:
compaction/measure.py
"""Run the same seeded workload on a leveled and a tiered LSM store and measure
the three amplifications: bytes written, space used and runs read."""
import random
from lsm import Store
KEYS, OPS, DELETES, RATIO = 20_000, 100_000, 0.10, 10
def run_workload(store):
"""100,000 random writes, 10 % of them deletes. Space and runs are sampled after every flush."""
rng = random.Random(42) # the same writes, in the same order, for both stores
truth, space, runs = {}, [], []
for i in range(OPS):
key = rng.randrange(KEYS)
if rng.random() < DELETES:
store.delete(key)
truth.pop(key, None)
else:
store.put(key, f"v{i}")
truth[key] = f"v{i}"
if not store.memtable: # a flush (and any compaction) has just happened
space.append(store.entries_on_disk() / len(truth))
runs.append(len(store.runs()))
store.flush()
return truth, space, runs
def mean(values):
return sum(values) / len(values)
rows = {}
for policy in ("leveled", "tiered"):
store = Store(policy, memtable_entries=1000, ratio=RATIO, l0_trigger=4)
truth, space, runs = run_workload(store)
assert all(store.get(k)[0] == truth.get(k) for k in range(KEYS)), "a read returned a wrong value"
store.build_filters(bits_per_key=10)
rng = random.Random(7)
present = rng.sample(sorted(truth), 2000)
absent = [KEYS + i for i in range(2000)] # keys that were never written
rows[policy] = [
f"{store.write_amplification():.2f}",
f"{mean(space):.2f}",
f"{max(space):.2f}",
f"{mean(runs):.1f}",
str(max(runs)),
f"{mean([store.get(k)[1] for k in present]):.2f}",
f"{mean([store.get(k, use_filters=True)[1] for k in present]):.2f}",
f"{mean([store.get(k)[1] for k in absent]):.2f}",
f"{mean([store.get(k, use_filters=True)[1] for k in absent]):.3f}",
f"{mean([store.runs_overlapping(a, a + 99) for a in range(0, KEYS - 100, 97)]):.1f}",
]
labels = [
"write amplification (bytes to runs / user bytes)",
"space amplification, mean (entries / live keys)",
"space amplification, worst",
"runs on disk, mean",
"runs on disk, worst",
"runs read for a key that exists, no filters",
"runs read for a key that exists, with filters",
"runs read for a missing key, no filters",
"runs read for a missing key, with filters",
"runs a 100-key range scan merges",
]
print(f"{OPS:,} writes ({DELETES:.0%} deletes) over {KEYS:,} keys, memtable 1,000 entries, size ratio {RATIO}")
print("every get agreed with a dictionary of the expected values; filters use 10 bits per key")
print(f"{'':50}{'leveled':>9}{'tiered':>9}")
for i, label in enumerate(labels):
print(f"{label:50}{rows['leveled'][i]:>9}{rows['tiered'][i]:>9}")Output
100,000 writes (10% deletes) over 20,000 keys, memtable 1,000 entries, size ratio 10
every get agreed with a dictionary of the expected values; filters use 10 bits per key
leveled tiered
write amplification (bytes to runs / user bytes) 4.03 1.69
space amplification, mean (entries / live keys) 1.17 2.49
space amplification, worst 1.38 4.41
runs on disk, mean 2.9 8.9
runs on disk, worst 5 17
runs read for a key that exists, no filters 2.90 8.60
runs read for a key that exists, with filters 1.02 1.07
runs read for a missing key, no filters 3.00 17.00
runs read for a missing key, with filters 0.018 0.139
runs a 100-key range scan merges 3.0 17.0
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 measure.py
compaction/lsm.py
"""A small LSM store: a memtable, sorted runs "on disk", Bloom filters and two
compaction policies, written to measure them rather than to be fast.
A run (an SSTable) is a sorted list of (key, value) pairs, and the value None is
a tombstone: the record of a delete. Every entry written to a run counts as
ENTRY_BYTES bytes, so write amplification is the bytes written to runs divided
by the bytes the user wrote.
"""
from bisect import bisect_left
ENTRY_BYTES = 100
TOMBSTONE = None
MASK = (1 << 64) - 1
def merge(runs, drop_tombstones):
"""Merge runs, given newest first, into one sorted run that keeps only the
newest version of each key. Tombstones are dropped only when asked: that is
safe only if no older run can still hold the key."""
newest = {}
for run in reversed(runs): # oldest first, so newer versions overwrite older ones
newest.update(run)
out = sorted(newest.items())
if drop_tombstones:
out = [(k, v) for k, v in out if v is not TOMBSTONE]
return out
def mix64(x):
"""A fixed 64-bit hash of an integer (the finaliser of splitmix64)."""
x = (x + 0x9E3779B97F4A7C15) & MASK
x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK
x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK
return x ^ (x >> 31)
class Bloom:
"""A Bloom filter over integer keys: "no" is always right, "maybe" sometimes wrong."""
def __init__(self, keys, bits_per_key=10):
self.m = max(1, len(keys) * bits_per_key)
self.k = max(1, round(bits_per_key * 0.6931)) # k = ln 2 x bits per key is the best choice
self.bits = bytearray(self.m // 8 + 1)
for key in keys:
for p in self.positions(key):
self.bits[p >> 3] |= 1 << (p & 7)
def positions(self, key):
h = mix64(key)
h1, h2 = h & 0xFFFFFFFF, (h >> 32) | 1 # two hashes make all k (double hashing)
return [(h1 + i * h2) % self.m for i in range(self.k)]
def might_contain(self, key):
return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self.positions(key))
class Store:
def __init__(self, policy, memtable_entries=1000, ratio=4, l0_trigger=4):
assert policy in ("leveled", "tiered")
self.policy = policy
self.memtable_entries = memtable_entries
self.ratio = ratio # T, the size ratio between neighbouring levels
self.l0_trigger = l0_trigger
self.memtable = {}
self.levels = [[]] # levels[i] holds runs, newest first; level 0 gets the flushes
self.user_bytes = self.flushed_bytes = self.compacted_bytes = 0
self.filters = None
# ---- the write path ------------------------------------------------------
def put(self, key, value):
self.user_bytes += ENTRY_BYTES # a real engine appends it to its log first
self.memtable[key] = value
if len(self.memtable) >= self.memtable_entries:
self.flush()
def delete(self, key):
self.put(key, TOMBSTONE)
def flush(self):
if not self.memtable:
return
run = sorted(self.memtable.items())
self.memtable = {}
self.flushed_bytes += len(run) * ENTRY_BYTES
self.levels[0].insert(0, run)
if self.policy == "leveled":
self.compact_leveled()
else:
self.compact_tiered()
# ---- compaction ----------------------------------------------------------
def _write(self, inputs, into, drop_tombstones):
"""Merge the input runs and count the merged run's bytes as written."""
out = merge(inputs, drop_tombstones)
self.compacted_bytes += len(out) * ENTRY_BYTES
while len(self.levels) <= into:
self.levels.append([])
return out
def _nothing_below(self, level):
return all(not runs for runs in self.levels[level + 1:])
def target(self, level):
"""Leveled: the entries level 1, 2, 3 ... may hold before it is pushed down."""
return self.memtable_entries * self.l0_trigger * self.ratio ** (level - 1)
def compact_leveled(self):
"""One sorted run per level below level 0: a full level is merged into the next."""
if len(self.levels[0]) < self.l0_trigger:
return
level = 0
while True:
below = self.levels[level + 1] if level + 1 < len(self.levels) else []
out = self._write(self.levels[level] + below, level + 1, self._nothing_below(level + 1))
self.levels[level] = []
self.levels[level + 1] = [out] if out else []
level += 1
if len(out) <= self.target(level):
return
def compact_tiered(self):
"""Up to `ratio` runs per level: a full level is merged into one new run of the next."""
level = 0
while len(self.levels[level]) >= self.ratio:
bottom = level + 1 >= len(self.levels) or (not self.levels[level + 1] and self._nothing_below(level + 1))
out = self._write(self.levels[level], level + 1, bottom)
self.levels[level] = []
if out:
self.levels[level + 1].insert(0, out) # newer than every run already there
level += 1
# ---- the read path -------------------------------------------------------
def runs(self):
"""Every run, newest first (level 0 first, then deeper levels)."""
return [run for runs in self.levels for run in runs]
def build_filters(self, bits_per_key=10):
self.filters = [Bloom([k for k, _ in run], bits_per_key) for run in self.runs()]
def get(self, key, use_filters=False):
"""Return (value or None, runs read). A tombstone ends the search: the key is deleted."""
if key in self.memtable:
return self.memtable[key], 0
reads = 0
for i, run in enumerate(self.runs()):
if use_filters and not self.filters[i].might_contain(key):
continue # the filter says "not here": this run is never read
reads += 1
j = bisect_left(run, (key,))
if j < len(run) and run[j][0] == key:
return run[j][1], reads
return None, reads
def runs_overlapping(self, low, high):
"""Runs a range scan of keys low..high must read and merge."""
return sum(1 for run in self.runs() if run and run[0][0] <= high and run[-1][0] >= low)
def entries_on_disk(self):
return sum(len(run) for run in self.runs())
def write_amplification(self):
return (self.flushed_bytes + self.compacted_bytes) / self.user_bytesRuns on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Tiered compaction wrote 1.69 bytes for each byte of data against 4.03 for leveled, less than half. It paid in space and runs: on average it held 2.49 entries for each live key, against 1.17, at worst 4.41, and up to 17 runs, so a missing key cost 17 looks without filters and a range scan merged 17 runs. Bloom filters hid most of the read difference for point lookups, 1.07 runs against 1.02 for keys that exist, but no filter helps the range scan.
These writes amplified little because the data set is small: three levels, counting level 0. The leveled store’s cost grows with every level it adds, which the next run shows by making the data ten times larger, twice:
compaction/growth.py
"""Write amplification as the data grows tenfold, twice: a leveled store pays
for every level it adds, a tiered store much less."""
import random
from lsm import Store
print("memtable 100 entries, size ratio 10, five writes per key (10 % deletes)")
print("write amplification, and the deepest level the leveled store reached")
print(f"{'keys':>8}{'levels':>8}{'leveled':>10}{'tiered':>9}")
for keys in (1_000, 10_000, 100_000):
amplification = {}
for policy in ("leveled", "tiered"):
store = Store(policy, memtable_entries=100, ratio=10, l0_trigger=4)
rng = random.Random(42)
for i in range(5 * keys):
key = rng.randrange(keys)
if rng.random() < 0.10:
store.delete(key)
else:
store.put(key, i)
store.flush()
amplification[policy] = store.write_amplification()
if policy == "leveled":
levels = len(store.levels) - 1 # levels below level 0
print(f"{keys:>8,}{levels:>8}{amplification['leveled']:>10.2f}{amplification['tiered']:>9.2f}")Output
memtable 100 entries, size ratio 10, five writes per key (10 % deletes)
write amplification, and the deepest level the leveled store reached
keys levels leveled tiered
1,000 2 2.98 1.46
10,000 3 6.90 2.42
100,000 4 12.26 3.42
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 growth.py
compaction/lsm.py
"""A small LSM store: a memtable, sorted runs "on disk", Bloom filters and two
compaction policies, written to measure them rather than to be fast.
A run (an SSTable) is a sorted list of (key, value) pairs, and the value None is
a tombstone: the record of a delete. Every entry written to a run counts as
ENTRY_BYTES bytes, so write amplification is the bytes written to runs divided
by the bytes the user wrote.
"""
from bisect import bisect_left
ENTRY_BYTES = 100
TOMBSTONE = None
MASK = (1 << 64) - 1
def merge(runs, drop_tombstones):
"""Merge runs, given newest first, into one sorted run that keeps only the
newest version of each key. Tombstones are dropped only when asked: that is
safe only if no older run can still hold the key."""
newest = {}
for run in reversed(runs): # oldest first, so newer versions overwrite older ones
newest.update(run)
out = sorted(newest.items())
if drop_tombstones:
out = [(k, v) for k, v in out if v is not TOMBSTONE]
return out
def mix64(x):
"""A fixed 64-bit hash of an integer (the finaliser of splitmix64)."""
x = (x + 0x9E3779B97F4A7C15) & MASK
x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK
x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK
return x ^ (x >> 31)
class Bloom:
"""A Bloom filter over integer keys: "no" is always right, "maybe" sometimes wrong."""
def __init__(self, keys, bits_per_key=10):
self.m = max(1, len(keys) * bits_per_key)
self.k = max(1, round(bits_per_key * 0.6931)) # k = ln 2 x bits per key is the best choice
self.bits = bytearray(self.m // 8 + 1)
for key in keys:
for p in self.positions(key):
self.bits[p >> 3] |= 1 << (p & 7)
def positions(self, key):
h = mix64(key)
h1, h2 = h & 0xFFFFFFFF, (h >> 32) | 1 # two hashes make all k (double hashing)
return [(h1 + i * h2) % self.m for i in range(self.k)]
def might_contain(self, key):
return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self.positions(key))
class Store:
def __init__(self, policy, memtable_entries=1000, ratio=4, l0_trigger=4):
assert policy in ("leveled", "tiered")
self.policy = policy
self.memtable_entries = memtable_entries
self.ratio = ratio # T, the size ratio between neighbouring levels
self.l0_trigger = l0_trigger
self.memtable = {}
self.levels = [[]] # levels[i] holds runs, newest first; level 0 gets the flushes
self.user_bytes = self.flushed_bytes = self.compacted_bytes = 0
self.filters = None
# ---- the write path ------------------------------------------------------
def put(self, key, value):
self.user_bytes += ENTRY_BYTES # a real engine appends it to its log first
self.memtable[key] = value
if len(self.memtable) >= self.memtable_entries:
self.flush()
def delete(self, key):
self.put(key, TOMBSTONE)
def flush(self):
if not self.memtable:
return
run = sorted(self.memtable.items())
self.memtable = {}
self.flushed_bytes += len(run) * ENTRY_BYTES
self.levels[0].insert(0, run)
if self.policy == "leveled":
self.compact_leveled()
else:
self.compact_tiered()
# ---- compaction ----------------------------------------------------------
def _write(self, inputs, into, drop_tombstones):
"""Merge the input runs and count the merged run's bytes as written."""
out = merge(inputs, drop_tombstones)
self.compacted_bytes += len(out) * ENTRY_BYTES
while len(self.levels) <= into:
self.levels.append([])
return out
def _nothing_below(self, level):
return all(not runs for runs in self.levels[level + 1:])
def target(self, level):
"""Leveled: the entries level 1, 2, 3 ... may hold before it is pushed down."""
return self.memtable_entries * self.l0_trigger * self.ratio ** (level - 1)
def compact_leveled(self):
"""One sorted run per level below level 0: a full level is merged into the next."""
if len(self.levels[0]) < self.l0_trigger:
return
level = 0
while True:
below = self.levels[level + 1] if level + 1 < len(self.levels) else []
out = self._write(self.levels[level] + below, level + 1, self._nothing_below(level + 1))
self.levels[level] = []
self.levels[level + 1] = [out] if out else []
level += 1
if len(out) <= self.target(level):
return
def compact_tiered(self):
"""Up to `ratio` runs per level: a full level is merged into one new run of the next."""
level = 0
while len(self.levels[level]) >= self.ratio:
bottom = level + 1 >= len(self.levels) or (not self.levels[level + 1] and self._nothing_below(level + 1))
out = self._write(self.levels[level], level + 1, bottom)
self.levels[level] = []
if out:
self.levels[level + 1].insert(0, out) # newer than every run already there
level += 1
# ---- the read path -------------------------------------------------------
def runs(self):
"""Every run, newest first (level 0 first, then deeper levels)."""
return [run for runs in self.levels for run in runs]
def build_filters(self, bits_per_key=10):
self.filters = [Bloom([k for k, _ in run], bits_per_key) for run in self.runs()]
def get(self, key, use_filters=False):
"""Return (value or None, runs read). A tombstone ends the search: the key is deleted."""
if key in self.memtable:
return self.memtable[key], 0
reads = 0
for i, run in enumerate(self.runs()):
if use_filters and not self.filters[i].might_contain(key):
continue # the filter says "not here": this run is never read
reads += 1
j = bisect_left(run, (key,))
if j < len(run) and run[j][0] == key:
return run[j][1], reads
return None, reads
def runs_overlapping(self, low, high):
"""Runs a range scan of keys low..high must read and merge."""
return sum(1 for run in self.runs() if run and run[0][0] <= high and run[-1][0] >= low)
def entries_on_disk(self):
return sum(len(run) for run in self.runs())
def write_amplification(self):
return (self.flushed_bytes + self.compacted_bytes) / self.user_bytesRuns on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Each extra level added about 4 to 5 to the leveled store’s write amplification and about 1 to the tiered store’s. That is the shape of a simple model: with size ratio T, a level receives about T batches from the level above before it overflows, and each batch rewrites what is already there, so a byte is rewritten about T/2 times per full level under leveled compaction and once under tiered. With T = 10 and four full levels the model gives for leveled and for tiered, counting the flush as 1. The measured stores stayed below that, at 12.26 and 3.42, because their deepest level was far from full. Real engines differ in detail too: RocksDB merges a few files at a time and sizes its levels from the bottom up, so that about 90 % of the data sits in the last level (RocksDB: leveled compaction).
Choosing a B+ tree engine or an LSM engine
Athanassoulis and colleagues named the underlying trade the RUM conjecture, after read, update and memory overhead: a design that caps two of the three cannot push the third below some floor (RUM conjecture). B+ trees favour reads; LSM trees favour updates; Bloom filters and compaction policies move an LSM tree along the line between them.
| Workload | Better fit | Why |
|---|---|---|
| Many small writes to random keys: events, metrics, messages, counters | LSM | Writes are batched and sequential; write amplification can stay well below a page per row |
| Mostly reads by key and short range scans, few writes | B+ tree | One path from root to leaf, no runs to merge |
| Keys that arrive in increasing order, such as timestamps | Either | Appends to the right edge of a B+ tree are cheap too |
| Data larger than memory on flash storage | LSM | Fewer bytes written, files that compress well, less wear |
| Steady low read latency at peak load | B+ tree, or an LSM with spare I/O | Compaction competes with reads for the disk |
| Bulk deletes of large key ranges | B+ tree | Tombstones cost reads and space until compaction removes them |
Compaction is the part that bites in production. It needs disk bandwidth that the foreground work also wants, and when it falls behind, files accumulate: RocksDB then slows writers down and finally stops them, which it calls a write stall (RocksDB: write stalls). An LSM engine is sized for its compaction, not only for its writes.
Exercise
Exercise · Medium · Python
Merge sorted runs the way compaction does
Write two functions in compaction.py. A run is a list of (key, value) pairs sorted by key, and the value None is a tombstone, the mark a delete leaves. runs lists the runs newest first, so runs[0] holds the most recent writes.
- compact(runs, bottom) merges the runs into one run sorted by key that keeps only the newest version of each key. It keeps tombstones, unless bottom is True: then no older run exists below, and tombstones are dropped. - get(key, runs) returns the newest value of key, or None when the newest version is a tombstone or the key is in no run.
Neither function may change the lists it is given.
Starter code · compaction.py
"""Compaction of sorted runs. A run is a list of (key, value) pairs sorted by key;
the value None is a tombstone. runs is given newest first."""
def compact(runs, bottom):
"""One sorted run with the newest version of each key; tombstones dropped only at the bottom."""
# Replace this line with your code.
return []
def get(key, runs):
"""The newest value of key, or None if it is deleted or was never written."""
# Replace this line with your code.
return NoneThe sample tests · test_compaction.py
from compaction import compact, get
OLD = [("agra", 2), ("delhi", 1), ("pune", 3)]
NEW = [("agra", 20), ("pune", None), ("surat", 4)]
def test_newest_version_wins():
"""a key in several runs keeps the value from the newest run"""
assert compact([NEW, OLD], bottom=False) == [("agra", 20), ("delhi", 1), ("pune", None), ("surat", 4)]
def test_output_is_sorted_by_key():
"""keys from different runs come out in one sorted order"""
assert compact([[("m", 1), ("z", 1)], [("a", 0), ("q", 0)]], bottom=False) == [("a", 0), ("m", 1), ("q", 0), ("z", 1)]
def test_tombstones_stay_above_the_bottom():
"""above the bottom, a tombstone must stay, or the older value would come back"""
assert compact([[("pune", None)]], bottom=False) == [("pune", None)]
def test_tombstones_go_at_the_bottom():
"""at the bottom no older run exists, so tombstones are dropped"""
assert compact([NEW, OLD], bottom=True) == [("agra", 20), ("delhi", 1), ("surat", 4)]
def test_a_value_written_after_a_delete_survives():
"""put, delete, put again: the last put is the newest version"""
runs = [[("goa", 3)], [("goa", None)], [("goa", 1)]]
assert compact(runs, bottom=True) == [("goa", 3)]
assert compact(runs, bottom=False) == [("goa", 3)]
def test_empty_input():
"""no runs, or only empty runs, give an empty run"""
assert compact([], bottom=True) == []
assert compact([[], []], bottom=False) == []
def test_inputs_are_not_changed():
"""compaction writes a new run; the old ones stay as they were"""
new, old = list(NEW), list(OLD)
compact([new, old], bottom=True)
assert new == NEW and old == OLD
def test_get_reads_newest_first():
"""get returns the newest value; a tombstone or a missing key gives None"""
assert get("agra", [NEW, OLD]) == 20
assert get("delhi", [NEW, OLD]) == 1
assert get("pune", [NEW, OLD]) is None
assert get("goa", [NEW, OLD]) is NoneA hint
Go through the runs from the oldest, the last one in the list, to the newest, and store each pair in a dictionary: a newer version then overwrites an older one. Sort the dictionary's items by key at the end, and leave out the tombstones only when bottom is true. For get, the first run that holds the key, starting from the newest, decides.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
Check yourself
5 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
Interview questions
Fresher · What is a tombstone in an LSM tree, and why is it not removed straight away?
A tombstone is the record an LSM tree writes when a key is deleted. SSTables are immutable, so a delete cannot remove the old value; it writes a newer entry that says “deleted”, and a read that finds it first reports the key as gone. The tombstone must stay until compaction has merged it with every older SSTable that might still hold the key, which usually means until it reaches the bottom level. Dropped earlier, it would let an older value become visible again, so a deleted key would come back. Until then, tombstones cost disk space and slow down range scans, which is why mass deletes are expensive in LSM engines.
Key takeaways
- An LSM tree appends each write to a log, buffers it in a sorted memtable, and flushes full memtables as immutable sorted SSTables; compaction merges SSTables and keeps the newest version of each key.
- A point read checks the memtable, then SSTables from newest to oldest. Bloom filters, about 10 bits per key for a 1 % false-positive rate, skip most SSTables; range scans get no help from them.
- A delete writes a tombstone, which can be dropped only when compaction reaches every older version of the key.
- Leveled compaction keeps one run per level: less space, fewer runs, more rewriting. Tiered compaction keeps several runs per level: less rewriting, more space and runs. In the measured run, 4.03 against 1.69 bytes written per byte, and 1.17 against 2.49 entries per live key.
- B+ trees favour reads and steady latency, LSM trees favour heavy writes; the RUM conjecture says no structure wins on reads, updates and space at once.
References
- P. O'Neil, E. Cheng, D. Gawlick and E. O'Neil: The log-structured merge-tree (LSM-tree) (Acta Informatica (Springer))
- B. H. Bloom: Space/time trade-offs in hash coding with allowable errors (Communications of the ACM)
- M. Athanassoulis et al.: Designing Access Methods: The RUM Conjecture (EDBT 2016 (OpenProceedings))
- RocksDB wiki: Leveled Compaction (The RocksDB project)
- RocksDB wiki: Universal Compaction (The RocksDB project)
- RocksDB wiki: RocksDB Bloom Filter (The RocksDB project)
- RocksDB wiki: Write Ahead Log (WAL) (The RocksDB project)
- RocksDB wiki: Write Stalls (The RocksDB project)
- RocksDB wiki: Rocksdb BlockBasedTable Format (The RocksDB project)
- RocksDB wiki: Delete A Range Of Keys (The RocksDB project)
- MySQL 8.4 Reference Manual: The Physical Structure of an InnoDB Index (Oracle Corporation)
- Apache Cassandra documentation: Storage Engine (The Apache Software Foundation)
- PostgreSQL 18 Documentation: Database Page Layout (The PostgreSQL Global Development Group)
- SQLite: Pragma statements (page_size) (SQLite)
Report a problem with this lesson
Kept only in this browser. Your Learn progress