The filter each run carries

A log-structured store makes a trade that the writes nobody counted measured in its favourable direction. It never updates a key in place. New keys go into a buffer in memory; a full buffer is written out as a sorted run; runs are merged into larger runs in levels that grow by a size ratio $T$. Every write is sequential and each key is rewritten only once per level it passes through, which is why the store moves two elements per key where an in-place B-tree dirties a whole block.

The other direction of the trade is lookups. A key might be in any level, and the newest version wins, so a lookup reads the levels from newest to oldest until it finds the key. A key that is present is found somewhere along the way. A key that is absent — the lookup that checks whether a user name is taken, or whether a row needs inserting — reads every level and finds nothing in any of them.

Every store of this kind answers that with a Bloom filter on each run, held in memory. A lookup asks the filter first and reads the run only if the filter says the key might be there. A filter that is allowed to be wrong is this collection’s measurement of what such a filter costs and how often it lies, and it never lies about a key it holds, which is the property that makes it safe here: a filter that says no is always right, so skipping the read is always correct.

That leaves one decision, and it is the subject of this page. The store has a fixed amount of memory for filters. How should it be divided among the levels?

The obvious division, and the store it is tried on #

The obvious division gives every key the same number of bits, whichever level it is in. Every filter is then sized for the same false-positive rate, and an absent key passes each level’s filter with the same probability $p$. With $L$ levels, an absent lookup wastes $L \cdot p$ reads on average.

The store measured here holds $n = 65{,}536$ keys. Its first run holds 1,024, and with a size ratio of four its levels hold 4,096, 16,384 and 45,056 keys — three levels, with the last holding more than twice as many keys as the other two together. Every level’s run carries a real Bloom filter built on its real keys, and every number below is counted over 6,000 lookups for keys that were never inserted and, separately, for keys that were.

The memory budget is stated in bits per key over the whole store, so five bits a key is $5 \times 65{,}536 = 327{,}680$ bits, or 40 KiB, however it is divided. That is the quantity held fixed on every plate: a division may move bits from one level to another, and it may not add any.

The same memory, divided two ways #

The first plate settles the question of whether the division matters. At every budget the sized division wastes fewer reads — about a quarter fewer at five bits a key, a third fewer at ten — for exactly the same number of bits.

What “sized” means comes from a small piece of arithmetic, and it is worth doing because the result is not the intuitive one.

A Bloom filter holding $n_i$ keys with a false-positive rate $p_i$ needs about $n_i \ln(1/p_i) / (\ln 2)^2$ bits. The wasted reads are $\sum_i p_i$. So the question is how to choose the rates to minimise $\sum_i p_i$ subject to $\sum_i n_i \ln(1/p_i)$ being fixed, and setting the derivatives equal gives the answer directly: the optimum has $p_i$ proportional to $n_i$. A level with four times as many keys should have four times the false-positive rate.

That is the opposite of what the phrase “more important levels get more bits” suggests. The largest level is the least efficient place to spend memory on, because lowering its rate by a given factor costs bits in proportion to its size — four times as many as the same improvement on a level a quarter its size — while buying the same reduction in wasted reads. So the sized division takes bits away from the biggest level and gives them to the small ones.

The measured rates bear the arithmetic out closely enough to be worth quoting. At five bits a key, the sized division’s three filters pass 1.2%, 4.3% and 13.5% of absent keys, smallest level first. Those successive ratios are 3.6 and 3.1, against level sizes that grow by 4 and then by 2.75, and the three rates add to about 0.19 — the 0.201 on the plate, within the noise of 6,000 lookups. The even division’s three filters each pass about 9.3%, which adds to the 0.279. So the sized division is not a heuristic someone tuned; it is the solution of a two-line optimisation, and the filters built to it land where the solution says.

Where the bits went #

The per-level view is where the argument becomes visible. Under the sized division the smallest level’s filter is nearly an order of magnitude more selective than under the even one, the middle level a few times more, and the largest level is substantially worse. A reader looking only at the largest level would conclude that the sized division had damaged the filter that matters most, since most keys live there.

That conclusion confuses where the keys are with where the reads are. Every absent lookup consults every level exactly once. The largest level holding most of the keys makes its filter expensive; it does not make its false positives more costly than anyone else’s. So the reads are divided evenly among the levels, the bits are not, and the sized division simply puts bits where they buy the most reads per bit.

What a wasted read is worth #

A tenth of a read sounds like nothing, and whether it is depends on what a read costs — which is the question the estimate a plan rests on found deciding a planner’s behaviour. A read of a run’s block for a key that turns out not to be there is a scattered read: the lookup has no reason to have that block nearby, and on a device where a scattered read costs many sequential ones it is the most expensive kind of transfer the store performs.

The fair comparison is with the structure the log-structured store replaces. A tree with nodes the size of a block answers any lookup, present or absent, in one read per level of the tree, and on a real system the upper levels are cached, so a lookup costs about one scattered read. The store measured here, with sized filters at five bits a key, answers a present lookup in 1.045 reads and an absent one in 0.201. So for absent keys it is cheaper than the tree, by a factor of five; for present keys it is within five per cent; and the price was 40 KiB of memory and the writes the filters take to rebuild at every merge.

That reverses the usual summary of the trade, which says a log-structured store is fast to write and slow to read. It is slow to read without filters, by a factor of the number of levels. With filters sized to its levels it reads about as fast as a tree for present keys and faster for absent ones, and what it gave up is memory. The cliff where the data stops fitting is the reminder of what happens if that memory is not there: a filter that must itself be read from storage turns a saved read into a spent one.

At a generous budget the numbers shrink and the pattern holds. The proportional gain is if anything larger, which the arithmetic predicts: the even division’s waste is $L$ times one rate, while the sized division’s is dominated by the largest level’s rate and scaled by a factor that does not depend on the budget.

Sized filters stop the waste from growing with the levels #

That factor is the finding worth carrying away, and it can be written down. Under the sized division the rates form a geometric series, largest level first, with ratio $1/T$. So the total waste is the largest level’s rate times $1 + 1/T + 1/T^2 + \cdots$, which is at most $T/(T-1)$ — a third more than the largest level’s own rate at $T = 4$, and nothing to do with how many levels there are.

Under the even division the waste is $L$ times a single rate. Adding a level adds a full rate’s worth of waste.

The plate is the prediction checked. Growing the store from three levels to four raised the even division’s waste by about a third and left the sized division’s almost unchanged: 0.201 to 0.209. A store that keeps growing adds a level every time it grows by the size ratio, so under an even division every absent lookup gets slower as the data grows, and under a sized division it essentially does not.

This is the same distinction a filter has a selectivity keeps returning to — a filter’s usefulness is a rate, and a rate compounds over every place it is consulted — and it is sharper here than usual, because the number of places grows with the data.

Raising the size ratio is the other way to reduce the number of levels, and it confirms the account from the other side: with only two levels, and the larger one holding most of the keys, the sized and even divisions are closer together, because an even division’s penalty is proportional to the number of levels it spreads its bits across. The size ratio is also the dial one dial between two structures swept, where it traded write cost against read cost; filters change where the read side of that dial sits, and sized filters change it most for the settings with the most levels.

Why the even division is the one that gets configured #

If the sized division is better at every budget and the arithmetic is two lines long, it is fair to ask why stores are so often configured with a single bits-per-key setting. There are three honest reasons, and none of them is that the even division is better.

It is one number. A single setting is easy to state, easy to reason about and easy to change, and a per-level setting is a vector that must be recomputed whenever the size ratio or the number of levels changes. The plates show the price of that simplicity is a quarter to a half of the absent-lookup waste, which at a generous budget is a very small absolute number.

A run’s level is known only when it is written. A filter is built when its run is built, and a run is built by a flush or a merge that knows which level the output belongs to — so the information is available, but it has to be threaded through to the filter builder. A store whose filter construction predates the idea has no reason to ask.

At a generous budget the difference is small in absolute terms. Ten bits a key leaves an absent lookup wasting 0.027 reads under an even division and 0.018 under a sized one, a difference of one read in a hundred lookups. A system whose lookups are dominated by present keys, or whose storage makes a scattered read cheap, can reasonably decide that the vector is not worth the configuration. The case for the sized division is strongest exactly where the budget is tight and the levels are many — a large store short of memory — which is also where an operator is least likely to have tuned anything.

A filter has a selectivity is the right frame for the choice. The sized division does not make any filter better; it rearranges which filters are selective so that the product of selectivities along a lookup is smallest, and whether that is worth doing depends on how many filters a lookup passes through.

The lookups that find their key #

Absent lookups were the motivation, but a sized division that made present lookups worse would be a hard sell. It does the opposite, and the reason is the same arithmetic run backwards.

A present key in the largest level — which is where most present keys are — pays for false positives in every smaller level above it, and never for the largest level’s own filter, since that level holds the key and the read there is not wasted. The sized division made exactly those smaller filters more selective. So the typical present lookup gains the most, and the keys in the smallest level lose nothing at all, since a lookup for them stops at that level before it reaches the looser filters below.

What the filters cost, and what they do not buy #

It is worth being exact about the budget, because a filter is memory taken from something else.

Five bits a key is 40 KiB for this store, against keys that are each far larger than five bits. Spent on caching blocks instead, the same memory would hold a small fraction of the data, and a cache can only avoid the reads of the blocks it holds — while the filters avoid more than nine tenths of the absent reads on every level at once. The formula everybody sizes filters with measured how well the textbook rate predicts a real filter, and at the loads used here it predicts well; the per-level rates above are measured, not computed, and they land where the formula says.

The filters also do nothing for three things.

A range query must read every level whose key range overlaps the query, because a Bloom filter answers only “is this exact key here”. No division of filter memory changes that cost at all.

Deletions in a log-structured store are writes of a tombstone, which is itself a key that the filter holds. A lookup for a deleted key therefore passes the filter of the level with the tombstone and reads it, correctly, to find the deletion. The evidence a filter cannot remove is the reason the store cannot simply clear the key’s bits instead.

And merges throw the filters away. Every merge that produces a new run must build that run’s filter from scratch, since two Bloom filters of different sizes cannot be combined into a filter of their merged set at the right rate. The filters’ construction cost is a write-side cost that the writes nobody counted did not include and that grows with the number of merges.

What the model leaves out #

The filter memory is assumed to be in memory. A store whose filters do not fit must read them, and a filter read is a transfer; that inverts the arithmetic, since a small level’s filter may then cost as much to consult as its run.

The levels are assumed to have one run each. A tiered store keeps several runs per level, each with its own filter, and the sized division then applies across runs rather than levels. The geometric-series argument survives with a different ratio.

Lookups are uniform over absent keys. A workload that repeatedly looks up the same absent keys can cache the answers, and a workload skewed towards recent keys consults the small levels far more often than the large ones — which changes the weights in the optimisation and moves the right division towards the small levels even further.

Where this ladder goes next: the query a filter cannot answer #

Everything on this page is a point lookup, and the section above named the query type that no division of filter memory helps.

A range query over a log-structured store reads every level whose run overlaps the range, and in a store with $L$ levels that is up to $L$ seeks for a short range where a B-tree pays one. That is the other half of the trade the two structures make, and it has not been priced on this ladder. The measurement is direct: sweep the length of a range from one key to a whole run, count transfers for a B-tree and for the store at the size ratios above, and find where the store’s extra seeks stop mattering against the cost of reading the range itself.

There is also a structure aimed squarely at the gap. A filter over key prefixes, rather than whole keys, can answer “might any key in this range be here” for ranges aligned with a prefix, at a false-positive rate that depends on how many prefixes the run contains. How much of the range cost such a filter recovers, and what it costs in memory against the point filters above, is a trade with a number in it — and it is the natural next rung, because it is the first place on this ladder where the thing being filtered is not a key.