Point Lookups, Tombstones, and Read Amplification in LSM Trees

A read in an LSM tree is a search for the newest version of a key across a sequence of structures that are individually sorted and collectively overlapping. The naive cost is one search per structure, and the design of the read path is almost entirely about making most of those searches terminate without touching a disk.

The search order, and why it is a merge

The structures a lookup must consider are the active memtable, the frozen memtables queued for flushing, the level-zero files, and then each level below. They are consulted from newest to oldest, and the first hit that is visible to the reader’s snapshot is the answer. This is exactly a merge of the same structures that compaction performs, evaluated lazily and stopping at the first result, which is why the read path and the compaction path share their comparison logic and their notion of a sequence number.

The sequence number is what makes the order well-defined. Every write receives one, monotonically increasing, and every read is evaluated at a snapshot sequence. A version is visible if its sequence is at or below the snapshot’s. A lookup that finds a key in the memtable with a sequence above the snapshot must continue to older structures, because the memtable’s version is too new. That is the mechanism by which a long-running read sees a consistent past state while newer writes pile up in front of it, and it is the same mechanism that pins versions and blocks compaction.

Level zero is the awkward part. Its files come from independent memtable flushes and their key ranges overlap, so a lookup cannot binary search them; it must consult each one whose range contains the key. The file count at level zero is therefore a direct multiplier on the worst-case read cost, and the threshold that triggers compaction exists to keep it small.

Filters make absence cheap

A lookup for a key that does not exist is the worst case: it must consult every structure and finds nothing. Without a filter, each consultation is a disk read, and the cost is the number of files in the tree. With a filter per file, each consultation is a memory probe and the disk read happens only when the probe says the key might be present.

A Bloom filter of $m$ bits over $n$ keys with $k$ hash functions has a false-positive probability near

$$f \approx \left(1 - e^{-kn/m}\right)^{k}$$

which for $m/n = 10$ bits per key and $k = 7$ gives about 0.008. So a tree with 100 files turns a worst-case lookup from 100 reads into about one expected read plus 100 memory probes. The probes cost a handful of cache misses each, so the cost moves from the device to the memory hierarchy, which is the trade the filter is making: it converts I/O into computation, and the computation is bounded by the number of files rather than by the size of the data.

The filter has a known limitation with range scans. A Bloom filter answers membership for a key, not for an interval, so a range scan must consult every file whose range overlaps the scan’s range and cannot use the filter to skip any of them. Some engines add a prefix filter or a range-aware structure for this, and others accept the cost because a range scan amortizes the per-file read over many rows.

The filter is built over the keys of the file, and a file that holds a key’s only live version still must be consulted. That is why filter accuracy and level count together, not either alone, determine read amplification: a tree with many levels and a poor filter reads many files, and improving either one alone has less effect than improving both.

Deletion writes data

An append-only structure cannot remove a key in place, so deletion writes a tombstone: a record with the key, the deletion’s sequence number, and a marker distinguishing it from a value. A subsequent lookup that reaches the tombstone before finding a live version returns “absent”, which is the correct answer, and it must do so even though a live version exists further down, because the tombstone is newer.

The tombstone is not a space optimization; it is a space cost. It occupies an entry in the memtable, in the log, and in the run it flushes to, and it must be carried down through every compaction until it reaches the level where no older version of its key can exist. Only there can it be dropped, and the rule for “no older version can exist” is that the compaction’s inputs include every file that could contain the key — in practice, the bottom level, or a compaction that covers the key’s full range down to the bottom.

The consequence is that a workload deleting a large fraction of its keys occupies more space, not less, until the tombstones reach the bottom and are dropped. A mass deletion can therefore temporarily increase disk usage and read cost, and the process that reclaims it is the same compaction that everything else waits on. Engines expose a compaction that rewrites a range specifically to push tombstones through, and it is a manual operation because doing it automatically would consume write bandwidth at the worst possible time.

There is a second interaction, with snapshots. A tombstone may not be dropped while a snapshot that predates it is open, because that snapshot must still see the older version the tombstone shadows. A long-lived read transaction therefore pins tombstones as well as versions, and the space they occupy cannot be reclaimed. The analogous problem in a versioned B-tree is the same and is handled by the same means: the engine tracks the oldest visible snapshot and refuses to discard anything newer than it.

Read amplification, stated as a sum

The cost of a lookup can be written as a sum over the structures consulted. Let $M$ be the memtable search, $F$ the number of files that a filter must be probed for, $f$ the filter’s false-positive rate, and $L$ the number of levels. Then

$$C \approx M + F \cdot (p_f + f \cdot p_r) + L \cdot f \cdot p_r$$

where $p_f$ is the cost of a filter probe and $p_r$ the cost of a file read. The third term is the one that matters at scale, and it is the product of two things the engine controls: the number of levels, set by the compaction ratio, and the false-positive rate, set by bits per key.

This is why a well-tuned tree with four levels and 10 bits per key expects a miss to cost a fraction of a read, and why the same tree with a filter disabled costs four reads per miss. It also explains the shape of the tuning space: doubling bits per key roughly squares the false-positive rate down, at the cost of memory, while halving the level count requires a much larger compaction ratio and therefore more space amplification. The shape of the level structure is the other half of the same equation.

Caching changes which term dominates

A block cache in front of the files converts some fraction of the $p_r$ terms into memory hits, and the fraction depends on access skew. For a workload reading a small hot set, most lookups are served from cache and the level structure stops mattering; for a workload reading uniformly across a large key space, almost nothing is cached and the level structure dominates. The same tree therefore behaves very differently under two workloads, which is why benchmarks that report read latency without stating the key distribution are not comparable.

The filter’s own memory is part of the same budget. A filter at 10 bits per key over a billion keys is 1.25 GB, which does not fit alongside a block cache of comparable size on a modest machine. Engines therefore often place filters in a separate, lower-priority cache, or use a partitioned filter that is loaded per file on demand. The latter keeps filter memory proportional to the working set rather than the data set, at the cost of a possible read to load the filter itself, which is a read the filter was supposed to avoid.

When the read path is genuinely worse than a B-tree

For a point lookup on a key that exists, a B-tree reads one leaf page after a descent through cached internal pages. An LSM tree reads the memtable, then a filter probe per level, then one file. The B-tree’s cost is one page and the LSM’s is one file plus several probes, and a file is larger than a page, so the B-tree is usually cheaper for a single point lookup.

The LSM wins when the lookup is for a key that does not exist, where its filters make the cost sub-linear in the data size, and when the reads are batched, where the merge of many lookups through the same set of files amortizes the per-file cost. It also wins when the alternative would be random page writes, which is to say under heavy write load. The comparison that matters is not lookup against lookup but the whole workload against the whole workload, which is the argument made in clustered and secondary access paths.