A levelled log-structured tree never writes randomly, and it writes everything about twenty-five times. Each of L levels rewrites a byte passing through it about F/2 times, so WA ≈ L·F/2; and a lookup that finds nothing has to try every level, so RA ≈ L before any filter. Append-only describes the pattern of the writes, not their number.
Core ideas
One new idea — the F/2 — and two consequences of it that decide what hardware the engine needs.
Merging a run into a level rewrites the part of that level it overlaps. When the merge happens, the level is on average about half full of the data it will eventually hold, so a byte crossing it is rewritten about F/2 times before it moves on. That is the F/2, and it is an average over the level's filling cycle rather than a count of anything.
There are L levels between the memtable and the bottom and a byte crosses all of them, so 5 levels at F/2 = 5 rewrites each is 25 bytes written for every byte the engine was handed. Every one of those writes was sequential. There were simply twenty-five times as many of them as the writer asked for.
A key that is not present has to be searched for on every level, because no level can prove the absence of a key that another might hold. That is RA ≈ L = 5 probes for a miss. It is the one number on this page that can be bought back cheaply, and “Bloom Filters: Bits per Key” is where it is bought.
The material
Why sequential writing is not the same as cheap writing, and what number to size a device against.
Write amplification is the bytes an engine writes to durable storage for every byte the application hands it. Read amplification is the storage reads a single logical lookup performs.
For a levelled LSM tree with fanout F and L levels these are WA ≈ L·F/2 and RA ≈ L. Both are counts, both are ratios, and neither is a latency.
The F/2 is the part worth slowing down for. It is not F. A merge into a level rewrites whatever part of that level overlaps the incoming run, and a level spends its life filling from empty to full between merges — so averaged over that cycle, a byte passing through is rewritten about half of F times rather than F times. Every figure on this page inherits that word “about”.
The last column is the whole lesson. A device sized to the ingest rate needs 50 MB/s; the engine needs 1.25 GB/s, and it needs it whether or not anybody is reading. That factor of twenty-five is not overhead in the loose sense — it is the mechanism by which the writes became sequential in the first place.
The level count is not really a setting. Level capacities are memtable × Fᴸ, so at a 64 MB memtable and F = 10 the levels hold 640 MB, 6.40 GB, 64 GB, 640 GB and 6.40 TB. A terabyte of data does not fit in four levels and does fit in five, so L = 5 — found by the same integer search that gives a B-tree its height, multiplying F in until the capacity covers the data.
It means sequential, which is a claim about the first term of the read-time formula and a good one: an LSM has no random writes at all on the ingest path, which is exactly what “The Write Cost of an Index” showed a B-tree paying k + 1 of. What it does not mean is few. The engine bought a better access pattern by agreeing to rewrite the data twenty-five times, and both halves of that sentence are the design.
Lowering the fanout lowers the write amplification and raises everything else. At F = 4 the same terabyte over the same memtable forces 7 levels, so WA falls to 14 — 700 MB/s of compaction instead of 1.25 GB/s — and RA rises from 5 probes to 7. There is no setting of F that improves both, which is the shape “The RUM Trade-off” draws as a triangle.
Two caveats the lab carries. WA ≈ L·F/2 describes levelled compaction; a tiered engine merges whole runs instead and pays L rather than L·F/2, in exchange for a much worse read amplification. And compaction is bursty: 1.25 GB/s is the average the device must sustain, while the instantaneous demand during a large merge is higher and the demand between merges is lower.
Interactive
L levels at F/2 rewrites each, and the compaction bandwidth that implies
Method
Get the level count from the data before you trust the level count in the configuration.
Multiply the memtable size by F repeatedly until the capacity covers the dataset, and count the multiplications. A configured level count below that is not a smaller tree; it is a tree that will grow one.
That is the write amplification, and it is a pure ratio: bytes written per byte ingested, with no device in it yet. At F = 10 and L = 5 it is 25.
50 MB/s × 25 = 1.25 GB/s of sustained write bandwidth. This is the number a device is chosen against, and it is the one nobody quotes.
RA ≈ L probes on a miss, before filters. Doing this in the same breath is what stops a fanout change from looking like a free improvement, because the two amplifications move in opposite directions.
The level count comes from the data, the amplification comes from the level count, and the bandwidth comes from the amplification.
Two numbers describe the same engine and only one of them is ever on a dashboard. The ingest is 50 MB/s; the disk sees 1.25 GB/s. Sizing a device against the first figure is not a small error — it is off by a factor of twenty-five, and the symptom is an engine that keeps up until compaction falls behind and then never catches up again.
Lower the fanout to 4 and the arithmetic moves the other way: the terabyte now forces 7 levels, WA falls to 14 and the compaction bandwidth to 700 MB/s, while the read amplification rises from 5 probes to 7. Cheaper writes, dearer reads, bought at a fixed exchange rate.
For a faded rehearsal, keep F = 10 and set the level count to 3. The supplied first move is that WA falls to 15. Compute the compaction bandwidth at 50 MB/s, then read the capacity column and say what the largest dataset three levels can actually hold over a 64 MB memtable — which is the constraint the setting was hiding. Check both in the lab before opening the quiz.
You should be able to derive the level count from the memtable and the dataset, compute both amplifications from F and L, and turn the write amplification into the sustained device bandwidth the engine actually needs.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.