A leveled LSM has a memtable, a write ahead log and 5 levels with a size ratio of 10. Compute the write amplification per byte ingested under the standard model, and say how the figure and its trade change under tiered compaction.

A leveled LSM has a memtable, a write ahead log and 5 levels with a size ratio of 10. Compute the write amplification per byte ingested under the standard model, and say how the figure and its trade change under tiered compaction.

Approach: Count every occasion on which a byte is written to disk on its journey from the log to the deepest level, including the bytes it is rewritten alongside at each merge.

52. A byte is written once to the write ahead log and once again when the memtable is flushed into level 0, which is 2. Merging level i into level i+1 rewrites the destination, and since level i+1 holds 10 times the data of level i, each byte promoted is written alongside roughly 10 bytes of existing data, so each level transition costs about 10 writes per ingested byte. Across 5 levels that is 50, and the total is 52. That figure is the answer to why a store ingesting 100 MB/s writes several GB/s to the device and wears it out. Tiered compaction changes the trade: it stacks several runs per level and merges only once a level has accumulated enough, so write amplification falls to roughly the number of levels, about 5 to 10, while read amplification rises because a read may probe several overlapping runs at each level, and space amplification rises because obsolete versions survive longer. Leveled compaction keeps space amplification near 1.1 and pays in writes; tiered keeps writes low and can hold close to two copies of the data at the moment of a large merge.

Follow-up: How does the arithmetic change if level 0 is allowed four overlapping files before compaction runs?

Key concepts: write amplification, leveled compaction, tiered compaction, space amplification.