Read amplification, update amplification and memory amplification cannot all be minimised at once. Levelled trees, tiered trees and B-trees sit at three corners of the same triangle, each best at something and paying for it somewhere else — and the disk bandwidth an engine needs is the ingest rate multiplied by its update amplification, which is never the ingest rate.
Core ideas
Three ratios that describe any storage engine, and the observation that pushing any one of them down pushes another up.
Read amplification is the storage reads one logical lookup performs. Update amplification is the bytes written per byte ingested. Memory amplification is the bytes stored per byte of unique data. Every engine has all three, all three are ratios, and a design is a choice about which of them to make small.
A tiered tree writes each byte only 5 times, the least of the three, and pays by probing 50 runs on a lookup and keeping 10 copies of a key. A levelled tree buys the reads back to 5 and writes 25. A B-tree reads in 4 and writes 31.25 bytes to change one row. The connection is causal rather than coincidental: merging less means keeping more, and keeping more means searching more.
At 50 MB/s of ingest the three engines demand 1.25 GB/s, 250.00 MB/s and 1.56 GB/s of sustained write bandwidth. None of those is 50 MB/s. Sizing the disk to what the application hands the engine is the misconception this page exists to kill, and it is off by between five and thirty-one times.
The material
What each shape is best at, what it pays for it, and how much disk bandwidth each one actually needs.
For a storage engine, read amplification RA is the number of storage reads a logical lookup performs; update amplification UA is the bytes written to storage per byte ingested; memory amplification MA is the bytes occupied per byte of unique data.
The RUM conjecture is that no engine minimises all three: a design that is best in one is, in general, worse in at least one other.
Memory amplification is a measure of space, not of RAM. A tiered tree with MA = 10 is keeping ten copies of a key on disk while it waits to merge them, and that is ten times the storage bill for the same unique data. The word is historical and it costs people an argument every time.
The two LSM rows are the same tree with two compaction policies. A levelled tree merges each incoming run into the level below immediately, so each level holds one sorted run and a lookup probes L of them — at the cost of rewriting F/2 bytes per byte per level. A tiered tree lets runs accumulate and merges F of them at once, so it writes each byte once per level and a lookup has F runs to search on every level. RA and UA swap places almost exactly.
Nothing in the B-tree row is a table lookup. Its read amplification is the height — 4, from a billion keys at a fanout of 500, by the integer search of “The Height of a B-tree”. Its update amplification is page over row: writing a whole 4 000 B page to change a 128 B row is 4 000/128 = 31.25. Its memory amplification is one over the fill factor: pages kept about two-thirds full occupy 1/(2/3) = 3/2 times the space of the rows in them.
Compaction bandwidth is ingest × UA, and it is the number a device is chosen against. At 50 MB/s the levelled tree needs 1.25 GB/s, the B-tree 1.56 GB/s and the tiered tree 250.00 MB/s. The tiered engine is the only one of the three that a modest device can feed, and it is also the one that will probe fifty runs to answer a lookup. That is the trade stated in the two units that matter.
So the way to use the triangle is not to rank the corners. It is to name the amplification your workload cannot afford and then read what the other two cost. A write-heavy ingest pipeline that is queried rarely can live at the tiered corner. A point-lookup service on expensive storage cannot afford MA = 10 and will not go there. A workload with both constraints is a workload that needs two engines.
What the triple does not include: compression, which moves MA and nothing else; a block cache, which moves the observed RA without moving the engine's; and any constant factor at all. These are ratios, so they compare shapes rather than products, and an implementation can be a factor of two better or worse than its shape at every corner.
Interactive
Read, update and memory amplification, computed for three engine shapes
Method
The engine is chosen last. The first three steps are about the workload and the device.
How many lookups a second and how many of them miss; how many bytes a second arrive; how much storage you are willing to buy. Those are the read, update and memory sides, stated before any engine is named.
L and F give both LSM rows. The page size, the row size and the fill factor give the B-tree's update and memory amplification, and its height gives its read amplification.
That is the sustained write bandwidth each engine requires. Compare the three numbers against the device you actually have, and some corners will disappear before you have chosen anything.
Every engine is expensive somewhere. The decision is finished when you can say which amplification you are paying and what it costs in the unit it is measured in — probes, bytes a second, or terabytes.
Same parameters, three shapes, and then the one column that turns the comparison into a hardware decision.
Read down each block and then across. Every engine is best at something: the tiered tree writes the least, the B-tree reads the least, the levelled tree stores the least. Every engine is worst at something too, and the worst figure is always the direct consequence of the best one.
None of the three bandwidth figures is 50 MB/s. That is the misconception the page is built around, and it is the most expensive arithmetic error in this course: a device chosen against the ingest rate is short by a factor of between five and thirty-one, and the failure arrives weeks later as compaction debt rather than immediately as an error.
For a faded rehearsal, drop the fanout to 4 and keep five levels. The supplied first move is that the levelled update amplification falls to 10. Compute all three triples at F = 4, say which engine moved most and which did not move at all, and then compute the three bandwidths at the same 50 MB/s. Check them in the lab before opening the quiz.
You should be able to compute all three amplifications for a levelled tree, a tiered tree and a B-tree from stated parameters, turn each update amplification into a device bandwidth, and name which corner a given workload is paying in.
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.