LSM-Tree, in depth: invariants, a working implementation, the k-way merge and the amplification cost model

The structure at a glance

From first principles: why sorted runs

Start from the cost of a B-tree insert on disk. The tree places each key at a fixed position, so inserting random keys means reading and rewriting a random page for each write. Random I/O on disks, and small random writes on SSDs, are expensive. An append-only log is the opposite: writes are sequential and fast, but finding a key means scanning the log.

The LSM-tree takes the log's write pattern and recovers ordered lookups by sorting in batches. Writes go to an in-memory sorted structure, the memtable, often a skip list. When it reaches a size limit, it is written to storage as one sorted, immutable run. Runs accumulate, so a background process merges them into fewer, larger runs, exactly like the merge step of merge sort. Every byte is written sequentially, many times over, and that repeated rewriting is the price paid for cheap writes.

The four invariants

Four invariants make the structure correct, and every bug in an LSM implementation breaks one of them.

• Runs are immutable. A run is never modified after it is written; it is only replaced by the output of a merge. That makes concurrent reads, caching and crash recovery simple.
• Newer beats older. Every write gets a monotonically increasing sequence number. When the same key appears in several places, the version with the highest sequence number wins. Reads search from newest to oldest and stop at the first hit.
• Deletes are writes. A delete writes a tombstone, a marker that says the key is gone as of this sequence number. It must survive until every older version of the key below it has been merged away, otherwise the old value resurrects.
• Levels are ordered by age. Data only moves downward, from memtable to the first level to later levels, so anything in a higher level is newer than anything below it for the same key.

A working mini-LSM in Python

The following implementation is under 70 lines and runs. It keeps runs in memory as sorted lists so the logic is visible; a real engine stores them as files with block indexes. It uses size-tiered merging: when there are too many runs, they are merged into one.

import bisect, heapq, itertools

TOMBSTONE = object()

class MiniLSM:
    def __init__(self, memtable_limit=4, max_runs=3):
        self.mem = {}                  # key -> (seq, value)
        self.runs = []                 # newest first; each a sorted list of (key, seq, value)
        self.seq = itertools.count(1)
        self.memtable_limit, self.max_runs = memtable_limit, max_runs

    def put(self, key, value):
        self.mem[key] = (next(self.seq), value)
        if len(self.mem) >= self.memtable_limit:
            self._flush()

    def delete(self, key):
        self.put(key, TOMBSTONE)

    def get(self, key):
        if key in self.mem:
            seq, value = self.mem[key]
            return None if value is TOMBSTONE else value
        for run in self.runs:                       # newest first
            i = bisect.bisect_left(run, (key,))
            if i < len(run) and run[i][0] == key:
                value = run[i][2]
                return None if value is TOMBSTONE else value
        return None

    def scan(self, lo, hi):
        mem_run = sorted((k, s, v) for k, (s, v) in self.mem.items())
        for key, seq, value in self._merge([mem_run] + self.runs, drop_tombstones=True):
            if lo <= key < hi:
                yield key, value

    def _flush(self):
        run = sorted((k, s, v) for k, (s, v) in self.mem.items())
        self.runs.insert(0, run)
        self.mem = {}
        if len(self.runs) > self.max_runs:
            # merging every run means this output is the bottom: tombstones can go
            self.runs = [list(self._merge(self.runs, drop_tombstones=True))]

    @staticmethod
    def _merge(runs, drop_tombstones):
        # order by key ascending, then sequence descending: newest version first
        streams = [((k, -s, v) for k, s, v in run) for run in runs]
        last = None
        for key, neg_seq, value in heapq.merge(*streams, key=lambda t: (t[0], t[1])):
            if key == last:
                continue                           # older version, shadowed
            last = key
            if value is TOMBSTONE and drop_tombstones:
                continue
            yield key, -neg_seq, value

The heart of it is _merge, a k-way merge over sorted streams using a heap, the same algorithm as merge sort's merge step generalised to k inputs. Ordering by key and then by descending sequence number puts the newest version of each key first, so the merge keeps the first occurrence and skips the rest. The same function serves range scans and compaction. Each element costs O(log k) for a merge of k runs.

Worked example: tracing writes, a delete and a merge

Trace it with a memtable limit of 4 and at most 3 runs. Put a, b, c, d: the fourth put fills the memtable, which is flushed as run R1 = [a1, b2, c3, d4], where the number is the sequence. Put b again, delete a, put e and f: flush gives R2 = [a6 tombstone, b5, e7, f8], placed in front of R1. Now get("a") misses the memtable, finds the tombstone in R2 first and returns nothing, even though R1 still holds a1. get("b") finds b5 in R2 and never looks at the older b2. Two more flushes make four runs, exceeding the limit, so all are merged: the shadowed b2 disappears, and because this merge covers every run, the tombstone for a is dropped along with a1. Had the merge covered only R2 and a newer run while R1 stayed below, dropping the tombstone would have resurrected a1. That is the tombstone invariant in action.

The cost model: write, read and space amplification

Three numbers describe any LSM configuration. Write amplification is bytes written to storage per byte the application wrote. Read amplification is the number of runs, or I/Os, a lookup may touch. Space amplification is bytes on disk per byte of live data. Their balance is set by the size ratio T between adjacent levels and by the merge policy. With N bytes of data and a memtable of B bytes, the number of levels is about L = log base T of N/B.

Worked sizing: 1 TB of data, a 64 MB memtable and T = 10. N/B is about 16,000, so L is log10 of 16,000, roughly 4.2, which rounds up to 5 levels. Under leveling, each byte is rewritten up to about T times as it moves into each level; with the average closer to T/2, a rough write amplification is 5 x 5 = 25, plus one for the log. Under tiering the same data is rewritten about once per level, about 5 to 6 times in total, but a point read may have to look in up to ten runs per level. This is why write-heavy, scan-light workloads favour tiering and read-heavy ones favour leveling, and why the B-tree comparison depends on the workload rather than on one winner. Treat these as order-of-magnitude estimates; real engines add partial merges, overlapping first levels and dynamic level sizes.

Bloom filters and the read path

Read amplification would make point lookups slow if every run had to be searched. Engines attach a Bloom filter to each run so a lookup can skip runs that certainly lack the key. A filter with m bits, n keys and k hash functions has a false-positive rate of about (1 - e^(-kn/m))^k. At 10 bits per key, the best k is about 0.69 x 10, so 7, and the rate is (1 - e^(-0.7))^7, about 0.0082, under 1 percent. Each extra bit per key cuts the rate by roughly a factor of 1.6.

import math

def bloom_fpr(bits_per_key, k=None):
    k = k or max(1, round(bits_per_key * math.log(2)))
    return (1 - math.exp(-k / bits_per_key)) ** k

for b in (5, 8, 10, 16):
    print(b, round(bloom_fpr(b), 5))
# 10 bits per key -> 0.00819

For a lookup of a missing key across 5 levels with filters at 1 percent, the expected wasted run probes are about 0.05, so most misses cost no I/O. Filters do not help range scans, which must merge every run whose key range overlaps the query. That is the scan cost of an LSM-tree and the reason compaction keeps the run count low.

Failure modes

• Write stalls. If merges fall behind the write rate, runs pile up in the first level, reads slow down, and engines throttle or stop writes until compaction catches up. Size compaction throughput for peak, not average, ingest.
• Tombstone build-up. Deleting many keys, or using short time-to-live values, leaves tombstones that every scan must step over until they reach the bottom. Queue-like delete patterns are the classic victim.
• Temporary space spikes. A merge writes its output before deleting its inputs, so a large merge can need free space comparable to the data it rewrites. Keep headroom on disk.
• Resurrected data. Dropping a tombstone before every older version beneath it is gone brings deleted values back. Only drop tombstones in merges that include the bottom of the key's history.
• Large values. Rewriting big values at every level wastes bandwidth. Key-value separation, as in the WiscKey design, stores values in a log and merges only keys, at the cost of garbage collection for the value log.

Trade-offs

The LSM-tree trades read cost and background work for cheap, sequential writes. It shines for ingest-heavy workloads such as time series, event logs and wide-column stores, compresses well because runs are immutable and sorted, and is friendly to SSD endurance compared with in-place random writes of small pages. It costs more on point reads without good filters, on range scans across many runs, and in operational complexity, because compaction is a second workload sharing the same disks. Every tuning knob, from size ratio to filter bits to memtable size, is a move along the curve between write, read and space amplification.

What to do next

1. Run the mini implementation, add a counter of bytes written, and measure write amplification as you vary the memtable size and run limit.
2. Extend it to two-level leveling and check that point reads touch at most one run per level.
3. Compute L, rough write amplification and Bloom filter memory for your own data size and size ratio before choosing a compaction strategy.
4. On a real engine, find the metrics for pending compaction bytes, first-level run count and write stalls, and alert on them.
5. Audit delete-heavy tables for tombstone build-up and choose a time-to-live or partitioning scheme that lets whole runs expire.
6. Read the compaction and LSM-versus-B-tree articles linked above, then pick a strategy by workload rather than by default.