The writes nobody counted

Every counter on this site charges the same for a read and a write. Counted has separate tallies for reads and writes and no essay has ever needed the distinction: a comparison is a comparison, a slot is a slot, and the two counts move together closely enough that no argument has turned on their ratio.

That symmetry is a property of memory, and it fails completely one level down. A block that is only read can be dropped when memory needs the space. A block that has been written has to be carried back out, so it costs a transfer on the way in and another on the way out — and on storage hardware the second transfer is more expensive than the first in every way that can be measured: latency, energy, and, on flash, the finite number of times the cell can be written at all.

Write amplification, defined by measuring it #

The quantity is the ratio of data written to storage against data the application asked to store, and it is one per key in the ideal case.

An in-place B-tree cannot come close to the ideal case for random keys, and the reason is entirely about which block is dirtied. Each insertion descends the tree, arrives at one leaf, and modifies it. The leaves are scattered — that is what “random keys” means — so with 256 leaf blocks and 64 blocks of memory, a dirtied leaf is almost always evicted before another key lands in it. One key stored, one block written. At B = 64 that is 64 elements written per element stored, and the measurement gives 49.3 because a fraction of the insertions do find their leaf still resident.

A log-structured merge tree never modifies a block. Keys accumulate in memory; when M of them have arrived they are sorted and written out as one sequential run; runs at a level are merged into a larger run at the next level when T of them have collected. Every write is a whole block of useful data, and the price is that each key is rewritten once per level it passes through — so the amplification is about T·log_T(n/M) elements per element, divided by nothing, because the writes are in units of B.

The two structures fail in opposite directions and the arithmetic is worth putting side by side:

At B = 64 and a modest number of levels, the first is 64 and the second is single digits. The gap is a factor of B over the log, and it grows as blocks get bigger, which they have done continuously for forty years.

The trade this buys and the trade it costs #

Nothing about the log-structured design is free, and an essay that stopped at the previous figure would have measured the resource where it wins and skipped the one where it loses.

A read against a B-tree costs the height — three or four transfers, measured in a tree with nodes the size of a block as 1.99 with a warm top. A read against a log-structured store has to consider every run that might contain the key, because the key could be at any level, and the structure is a set of sorted runs rather than one index. Without help that is one lookup per run, and the number of runs grows with the number of levels.

The help exists and it is a structure this site has already measured: a Bloom filter per run, sized so that a run which does not contain the key is skipped without a transfer at all. That is a filter allowed to be wrong’s subject in its most important application — the false-positive rate is exactly the probability of paying a wasted transfer, and the sizing formula from the formula everybody sizes filters with is the calculation an engine actually performs when it decides how many bits per key to spend.

So the comparison is not “fewer writes against more reads”. It is:

• the B-tree pays B per write and log_B n per read;
• the log-structured store pays T·log_T(n/M) per write and log_B n per read plus a filter probe per level, most of which are answered from memory.

Which is better is a question about the workload’s read/write ratio, and it has no answer without one. This is the frontier between time and space’s shape applied to two kinds of transfer: a Pareto trade rather than a ranking, and the reason both structures ship in production systems rather than one having won.

The size ratio is a threshold somebody chose #

The parameter T — how many runs collect at a level before they are merged into the next — is the log-structured store’s minrun, and the figure sweeps it for the same reason the practice phase swept Timsort’s constants.

At T = 2 every level holds one run and merges constantly: the fewest levels, the most rewriting per level. At T = 16 a level holds sixteen runs before merging: fewer merges and therefore fewer writes, but sixteen runs to consult on a read and sixteen filter probes to pay.

Neither end minimises anything on its own, and the shipped values in real engines cluster around 10. Sweeping T here reproduces the shape — the write amplification falls with T over the range measured, which is only half the picture, and the read cost that rises with it is the half this instrument cannot price. Saying so is more useful than picking a winner, and it is the same discipline the practice phase settled on: a threshold is a parameter with the shipped value as its default, and a sweep that holds every other counter fixed is measuring one face of a decision made against several.

Which arrangement the plate measured, read off the sweep #

The formula quoted for the log-structured side is $T\log_T(n/M)$ and its gloss is each key rewritten once per level. Those are two different quantities, and the sweep decides which one the figure drew.

Once per level is $\log_T(n/M)$, plus one for the write out of memory that makes the first run. At $n = 16{,}384$ and $M = 4{,}096$ the ratio $n/M$ is 4, so that expression gives 3.0 at $T = 2$, 2.0 at $T = 4$, 1.67 at $T = 8$ and 1.5 at $T = 16$.

The plate’s figure at $T = 4$ is 2.0.

The other expression gives 4.0 at $T = 2$, 4.0 at $T = 4$, 5.33 at $T = 8$ and 8.0 at $T = 16$ — twice the measurement at the point where the measurement is quoted, and rising rather than falling across the sweep.

So the direction of the sweep identifies the arrangement, and it is not a close call. The essay’s own later section names them: tiering writes each key once per level and reads from up to $T$ runs; levelling keeps one run per level and rewrites it, costing about $T$ times as much per key. Amplification falling with $T$ is tiering’s signature. Under levelling the curve would have a minimum near $T = 3$ — the point where $T/\ln T$ turns — and climb from there, so a sweep from 2 to 16 would have gone the other way over most of its range.

That reconciles the formula, the gloss and the plate, and it settles the parameter sweep’s meaning rather than leaving it as falls with T, which is half the picture. The falling half is tiering’s write cost. The rising half the instrument cannot price is tiering’s read cost, which grows with $T$ because there are up to $T$ runs at each level to consult — and it is precisely $T$ Bloom filter probes per level, which is why a filter allowed to be wrong is not an aside in this design but the thing that makes a large $T$ affordable at all.

It also quantifies the factor the two arrangements trade, at these parameters rather than in general. At $T = 4$ it is 2.0 against 4.0; at $T = 16$ it is 1.5 against 8.0, a factor of 5.3. The trade is not a constant — it widens with $T$, which is why a real engine tiers at the small levels, where merging is cheap and runs are few, and levels at the large ones, where a read that consults sixteen runs is the expensive event.

One further check falls out for free, and it is the kind that is worth more than the result. The second figure doubles the keys, the block and the memory: $n = 32{,}768$ with $M = 8{,}192$. That holds $n/M$ at 4, so $1 + \log_T(n/M)$ predicts no movement at all in the log-structured figures — and the caption reports that they barely move, while the in-place figure rises with $B$ as it must.

A parameter change chosen to check that a comparison is about the structures turns out to have held the log-structured expression’s only argument fixed. The prediction and the observation agree, and the agreement is evidence about the expression rather than about the sweep — the same use a tree with nodes the size of a block makes of a height computed two ways.

What the model gets right here, and what it flattens #

The model charges one for a read transfer and one for a write transfer, and the whole argument above turns on writes being more expensive than that in reality. So the honest position is that the model undercounts the advantage of the log-structured design rather than overstating it, and the direction of the error is worth having explicitly.

On flash, a write is not a write. A page can be programmed once and must be erased in much larger units — a block of many pages — before being rewritten, so a random in-place update triggers a read-modify-erase-program cycle inside the device, and the device’s own garbage collector performs a second, hidden write amplification on top of whatever the application caused. Measured amplifications of 3 to 10 inside consumer SSDs were routine, which multiplies the 49.3 in the figure rather than replacing it.

That is why log-structured designs took over storage engines at exactly the moment flash did, and it is a rare case of a hardware change reversing a structural preference that had held since the 1970s. The B-tree was designed for a device where a random write cost the same as a random read, and that device was the disk.

There is also a cost the model cannot see at all, and it belongs in this essay because it is the standard objection. Log-structured stores exhibit compaction stalls: the merge of a large level is a burst of I/O that arrives at an unpredictable moment and delays whatever else is happening. The average write cost is excellent and the tail is not, which is exactly the shape the probe nobody waits for is about — a technique whose reported number improves while the quantity a user experiences does not.

A count of transfers is a count and not a schedule. Nothing in this model expresses when a transfer happens, and a structure that does the same total work in bursts is a different product from one that spreads it evenly.

Where the reads go, and why this instrument cannot price them #

The honest accounting requires the read side, and this is the point at which the instrument runs out — so the rest of this section is stated as structure rather than as measurement, and the difference is marked.

A log-structured store’s read cost depends on how the runs are organised, and there are two arrangements with different answers.

Tiering keeps up to T runs at each level and merges them only when the level is full. Writes are cheap — each key is written once per level — and reads are dear, because a key may be in any of the T runs at any of the levels.

Levelling keeps one run per level, merging each arriving run into it immediately. Reads are cheaper, because there is one run per level to consult; writes are dearer by a factor of about T, because merging into a large run rewrites the large run.

The same structure with the same parameters, arranged two ways, trades a factor of T between the two resources. Real engines mix them — tiering at the small levels where merging is cheap, levelling at the large ones where reads matter — and that hybrid is a policy in exactly the sense the practice phase’s library sorts are policies: a set of decisions with thresholds, whose interaction decides the behaviour and whose complexity class does not mention any of it.

What this site’s instrument can say about the read side is only that a Bloom filter’s false-positive rate is the probability of a wasted transfer, which a filter allowed to be wrong measures. What it cannot say is the number of transfers a mixed read/write workload costs, because that requires a workload — a distribution over operations arriving over time — and every measurement in this collection is of one algorithm on one input. Naming the boundary is the point of the paragraph, and it is the same boundary a tree with nodes the size of a block drew around the B-tree’s splitting.

The measurement, and what had to be fixed for it to be true #

The write-amplification figure came out of the instrument reporting zero the first time it ran.

The cause was in the code that decides which leaf a key lands in. A B-tree over 16,384 keys at fanout 64 has levels of 1, 4 and 256 nodes — the levels are not all full, because 64² = 4,096 does not divide the leaf count evenly — and the first version computed the child index from a power of the fanout rather than from the actual width of the level. Every insertion therefore landed in the same leaf, that leaf stayed resident, and it was written back exactly once.

The figures drawn from it would have been entirely plausible. A B-tree writing nothing looks like a structure with excellent locality rather than like a bug, and the number would have been quoted as a finding.

What caught it was the assertion, not the drawing: assertWriteAmplificationDiffers requires the in-place structure to write at least four times what the log-structured one writes, and zero is not four times two. A check written to confirm that a comparison is worth making refused a measurement in which one side had silently stopped happening.

That is the third time on this site an assertion has caught an input-generation defect rather than an algorithm defect — after the practice phase’s withRuns and the randomness phase’s treap priorities — and the pattern is now clear enough to state as a rule: the code that constructs the case is as likely to be wrong as the code being measured, and it is much less likely to be checked.

The amplification at three settings #

The number is elements written per key inserted, and it is a function of three things the model has: the size ratio, the block, and how many keys go in.

The third parameter is the one nobody tunes, because it is how much data arrives rather than a setting anybody chose.

What the B-tree can do about it, and why it is not enough #

An in-place tree is not defenceless, and the defences are worth listing because each one attacks a different term in the 49.3.

Batching. Buffer incoming keys and apply them in sorted order, so that several keys destined for the same leaf are applied while it is resident. That converts the amplification from B per key to B per batch of keys landing in one leaf, and with a large enough buffer it approaches the ideal. It is also the idea the log-structured design takes to its conclusion — the buffer is the memory level, and the levels below it are the buffer applied recursively.

Bigger memory. The 49.3 is what it is because 256 leaf blocks compete for 64 blocks of memory. Give the tree enough memory to hold every leaf and the amplification falls to nearly one, because nothing is evicted until the end. That is a real answer for a small table and no answer at all for a large one, and it is the same M ≥ n/B inequality that decides whether an index’s internal nodes stay resident.

Sequential keys. Insert in key order and every insertion lands in the leaf the last one did. The amplification falls to one and the structure is optimal, which is why an auto-incrementing primary key is the standard advice and why a random UUID as a primary key is the standard warning. The difference between the best and worst case here is the whole factor of B, decided entirely by the order the keys arrive in — the same sentence as one access, eight kilobytes’s, about a structure rather than about a loop.

The figure below is that last point measured rather than asserted.

The sixth counter’s clearest result #

Every counter added to this site was justified by a pair of things it could distinguish that nothing else could. This one has produced the widest gap of the six.

• 49.3 against 2.0, for the same 16,384 insertions of the same keys in the same order.
• Identical by the comparison count, which is dominated by the descent in one case and the sort in the other and comes out within a factor of two.
• Identical by the operation count: 16,384 keys stored either way.
• Identical by the auxiliary-space count at the granularity this site measures it.
• Invisible to the cache model, which counts misses and does not charge for the write-back.

A factor of 24 between two structures that every existing instrument here calls equivalent is the argument for the counter, and it is also the argument for the field: the difference is not a subtlety about constants, it is the reason a storage engine written after 2010 usually is not a B-tree.