Leveled Compaction and the Shape of the LSM Tree

Compaction policy decides everything that an LSM engine is judged on: how much write bandwidth a sustained ingest consumes, how many files a read must consult, and how much disk is occupied by data that has been superseded. The three quantities are connected, and the shape of the level structure is the knob that sets where on the curve an engine sits.

The size ratio invariant

Leveled compaction maintains levels $L_0, L_1, \dots, L_n$ where each level below the first is a factor $T$ larger than the one above, with $T$ commonly 10. Within a level below $L_0$, files cover disjoint key ranges. $L_0$ is the exception: its files come from memtable flushes, their ranges overlap, and it is bounded by a file count rather than a size.

The invariant is what produces the read behaviour. A lookup at level $i$ needs to examine at most one file, because the files partition the key space. It finds that file by binary search over an in-memory array of the level’s first keys, which is small: a level holding 100 GiB in 64 MiB files has 1600 files, and 1600 boundary keys are a few tens of kilobytes. So the read cost per level is one binary search in memory plus one file read, and the total read cost is the number of levels, which for a database of $N$ bytes with a level-one size of $S$ is about $\log_T(N/S)$.

The space cost is bounded by the same structure. A key can exist in at most one file per level, and there are $n+1$ levels, so at most $n+1$ versions of any key exist on disk. The bottom level is by far the largest, so the excess space is roughly the size of the levels above the bottom, which is about $1/(T-1)$ of the total. With $T = 10$ that is about 11 percent; with $T = 4$ it is about 33 percent.

Why a compaction must rewrite the whole overlap

A compaction from level $i$ to level $i+1$ selects some files of level $i$, then must merge them with every file of level $i+1$ whose range overlaps. It cannot write the merged output into the gaps between existing files, because the output’s key range is the union of the inputs’ ranges and the invariant demands that files in a level not overlap. So the unit of work is the whole overlap, and the bytes rewritten are the level-$(i+1)$ overlap plus the level-$i$ input.

That is where the write amplification comes from, and it explains why the choice of which level-$i$ file to compact matters. Compacting a file whose range overlaps a large fraction of the next level rewrites a large fraction of that level. Compacting one whose range is narrow rewrites little. A policy that always picks the file with the smallest overlap minimizes bytes written per compaction but leaves the level uneven, with some regions compacted many times and others never; a policy that picks round-robin keeps the level even but pays more per compaction. A workable compromise chooses among the files with small overlap rather than the single smallest, and compensates by preferring the file whose size most exceeds its share of the level.

The total amplification follows from the ratio. Each level-$i$ byte is eventually merged into level $i+1$ once, and in doing so is written once and read once; the level-$i+1$ bytes it displaces are rewritten too, and the ratio of displaced to incoming is about $T$. Summing over levels gives the $T \log_T(N/M)$ figure, which is flat in $T$ and grows only logarithmically in the database size.

Tiered compaction and the other corner

Tiered compaction abandons the disjointness invariant. Files are grouped into runs of similar age, and a compaction merges all files in a run into one larger file, which joins the next run up. Since runs are not required to have disjoint ranges, a read must consult a file per run — but the number of runs is bounded by the number of tiers, and each tier is $T$ times larger than the one below, so the read cost is again logarithmic.

The gain is write amplification. Each byte is rewritten once per tier it passes through, so the total is about $\log_T(N/M)$ with no multiplicative factor, which for ten tiers of ratio 10 is about 10 rather than about 100. The loss is space amplification: a key may exist once per run, and with many runs live at once the number of stale versions grows. With a tiering factor of $T$, the space overhead is roughly $T$ times the live data in the worst case, which is the reason tiering is used for ingest-heavy workloads where disk is cheaper than write bandwidth, and leveled compaction is used where space matters.

The practical policies mix them. A common arrangement is tiering at the top levels, where files are small and ingest lands, and leveled compaction below, where the bulk of the data lives and space amplification matters. The transition point is a tuning decision with a clear rationale: the top levels hold a small fraction of the bytes, so the space cost of tiering there is small, while the write cost of leveled compaction there is paid on every byte that passes.

Where compaction competes with reads

Compaction consumes disk bandwidth and CPU, and on a device with a finite queue depth it competes directly with foreground reads. An engine that compacts aggressively has low read amplification and high write amplification; one that compacts lazily has the reverse, until the backlog of unmerged data makes reads slow enough that the compaction can no longer keep up.

The failure mode when compaction falls behind is not graceful. The level-zero file count grows past its threshold, so reads consult more files; the memtable flush queue grows, so writes stall; and the space occupied by superseded versions grows, so the disk fills. All three symptoms come from one cause, and the recovery is to give compaction more bandwidth or reduce the ingest rate.

There is also a correctness interaction with snapshots and with transactional visibility. A compaction may not drop an old version of a key that a still-open snapshot needs to see, so a long-running read transaction pins the versions it might read, and compaction must carry those versions forward. A single long-lived snapshot can therefore raise space amplification substantially and prevent the bottom level from ever being fully compacted, which is a case where the garbage collector is blocked by a reader and no amount of tuning helps. The same version-visibility problem appears in the B-tree world under a different name, and the tombstone mechanics that make deletion work in an append-only structure are covered in point lookups and tombstones in LSM trees.

Choosing the ratio

The ratio is the one parameter that trades space against write cost directly. Small ratios give dense levels, low space amplification, and many levels: more write amplification per byte descending, and a longer level count for the read path to traverse. Large ratios give fewer levels and cheaper descent but leave more room for stale versions in the upper levels.

The useful way to choose is to fix the constraints and see what is left. If the disk can hold at most 1.2 times the live data, the space budget allows $1/(T-1) \le 0.2$, so $T \ge 6$. If the device’s endurance budget allows a write amplification of 20 and the database is 20 times the memtable size, then $T \log_T(20) \le 20$ holds for a wide range of $T$ and the constraint does not bind. The constraint that usually binds is the read path: each level costs a filter check and a possible read, and a level count of ten means ten chances for a filter false positive to become a disk read.

The shape of the tree is therefore not a property of the algorithm alone. It is the resolution of a space budget, an endurance budget, and a latency target against a workload’s ratio of reads to writes, and the reason two engines with the same compaction algorithm can behave very differently on the same data is that they resolved it differently.

The bottom level is special

The bottom level holds most of the data and receives the final version of every key. Two properties follow. First, it is the level whose files are largest, so a compaction into it rewrites the most bytes per operation, and a policy that compacts the bottom level frequently is expensive. Second, it is the level where stale versions can finally be dropped, because nothing below it needs them.

Some engines therefore treat the bottom level differently: they allow it to be compacted in background passes that take a long time, and they may defer compaction there until the level’s overlap with the level above exceeds a threshold rather than compacting each file as it arrives. This is why the steady state of a large LSM tree is that the bottom level is compacted rarely and the levels above it churn constantly, and why the bottom level’s file count, rather than its size, is the thing to watch when diagnosing a tree that has stopped making progress.

The B-tree has no analogue of this structure at all. Its pages are rewritten in place, so a key’s location is fixed by its value rather than by its age, and the only versioning is what the engine maintains separately for concurrency. The comparison between the two families is easiest to state as what each one refuses to do: the B-tree refuses to write sequentially, and the LSM refuses to overwrite in place. Everything else, including the shape of the tree, follows from which refusal was chosen, which is the framing in the LSM write path from memtable to sorted run.