The read a filter has no key for

The filter each run carries measured what a Bloom filter on every run of a log-structured store buys. Without filters, a lookup for a key the store does not hold reads a block at every level — three levels, three transfers, and nothing found. With five bits a key spread evenly, it wastes 0.279 reads; spread so that small levels get more bits and the large one fewer, 0.201. The level count, which is the whole read cost of a log-structured store, is bought back almost entirely.

A range query is a different question and gets no such answer. A filter tells a store whether a named key might be in a run. “Every key between $a$ and $b$” names no key, so there is nothing to ask, and every run whose interval overlaps the range has to be opened and read. The level count is paid in full, on every range query, however many bits the filters hold.

This page measures what that costs.

The two costs, against the size ratio #

A log-structured store’s level count falls as its size ratio rises: with runs of 4,096 keys and a million keys held, a ratio of two gives eight levels and a ratio of sixteen gives two. That is the dial one dial between two structures swept, and it is paid for in writes.

Two lines fall together and one of them is a fraction of a transfer.

At a size ratio of two the absent point lookup costs 0.72 transfers and the range query costs sixteen. Both numbers are the same eight levels, seen through different questions: the point lookup pays $L \times \text{false-positive rate}$ and the range pays $L$ seeks plus the rows. A store tuned to make its point lookups cheap has almost nothing left to gain there — 0.72 transfers to 0.18 is a saving of half a transfer — and the same change saves a range query eleven.

So the dial’s value depends entirely on which question is being asked, and the earlier page’s framing hid that by asking only one.

What the filter bits do, and do not #

The flat line is the page’s title. Ten times the memory spent on filters changes a range query’s cost by nothing at all, because the filter is being asked a question it cannot be asked.

That is worth separating from the ordinary observation that a Bloom filter has a false-positive rate. A filter with a rate of zero would still leave the range query at nine transfers. The limit is not the filter’s accuracy; it is its interface. A membership test over a set has no extension to an interval unless the structure indexes the interval, which a Bloom filter by construction does not.

It also means the two costs are separately tunable and are usually tuned together. A store’s memory budget buys filter bits, and filter bits buy point lookups; its size ratio buys levels, and levels buy both point lookups and ranges. A system with a memory budget and a range-heavy workload is spending its memory on the wrong axis, and would do better to spend the same bytes on a block cache, which helps both.

How long a range has to be before the levels stop mattering #

The level count is a fixed charge and the rows are not, so the overhead is a ratio that falls as the range grows. A range of one key — which is a point lookup asked the other way — costs four times what a single sorted run would; a range that reads a thousand keys costs 1.24 times; a range that reads a hundred thousand costs what any structure would, because by then the answer is the cost.

The crossing is at about a thousand keys, and that number is the one a system designer needs. It is not a property of the store’s size: it is the point at which the range’s own rows fill more blocks than the store has levels, so it depends on the level count and the block size and on nothing else. With four levels and sixty-four keys a block, a range of 256 keys reads as many blocks of data as it pays in seeks.

Below that crossing a log-structured store is answering range queries at a multiple of what a single sorted run would, and the multiple is the level count. The index that is not worth reading made the same kind of point about a different structure — that where a method turns is decided by the block size, a number the query does not contain and the schema does not mention — and the level count here is that number’s counterpart. Above it, the structure barely matters. A workload of short range scans — “the last ten events for this user”, which is the shape most key-value stores actually serve — sits entirely below the crossing.

The two questions a store is asked #

It is worth writing the two costs out, because they have the same $L$ in them and almost nothing else in common.

A point lookup for a key the store does not hold reads a block at every level whose filter says maybe. With $L$ levels and a false-positive rate $p$ that is $Lp$ transfers in expectation — eight levels at five bits a key is $8 \times 0.0905 = 0.72$. Every term is small and the product is a fraction of one transfer.

A range query reads one seek into each level plus the blocks holding that level’s share of the rows: $L + \sum_i \lceil r s_i / B \rceil$, where $r$ is the rows asked for and $s_i$ is level $i$’s share of the keys. With eight levels and a hundred rows over sixty-four-key blocks the second term is eight and the first is eight, so the levels are half the cost and the rows are the other half.

Set the two expressions beside each other and the difference is one factor. The point lookup multiplies $L$ by $p$; the range query does not multiply $L$ by anything. Everything in this page follows from that, including the flat line on the filter-bits plate, which is $p$ not appearing.

There is a second consequence that the plates show and the expressions make obvious. Spending memory on filters lowers $p$ and therefore lowers $Lp$; raising the size ratio lowers $L$ and therefore lowers both. The size ratio is the only parameter that helps both questions, which is why it is the one a mixed workload has to be tuned on, and it is the parameter whose cost is paid in writes rather than in memory.

What it costs to fix by turning the dial #

This is the frontier the store is actually on, and reading it against the earlier page’s changes the answer.

Judged on point lookups, raising the size ratio is nearly pointless. It takes 0.72 transfers to 0.18, a saving of half a transfer a query, and costs 3.8 times the write amplification. Almost no workload justifies that, which is why write-optimised stores are configured with small size ratios and many levels.

Judged on short range queries it is the main lever available. Sixteen transfers to five is a saving of eleven, and 3.8 times the writes for it is a trade a read-heavy workload can want. The writes nobody counted measured a B-tree writing 49.3 elements of block per key stored against a log-structured store’s 2.0; a store at a ratio of sixteen writes 30 units against a ratio of two’s 8, which is still far below the B-tree and is a large change within the family.

So the tuning question is not “how much memory for filters” and not “how write-optimised should this be”. It is what share of the queries name a key, and that share moves the best size ratio by a factor of eight in this sweep.

One query in ten. That is the whole of the practical finding, and it is worth stating as a warning rather than as a recommendation: a store configured on a pure point-lookup benchmark is configured for a workload that almost nothing has, and the configuration changes as soon as a tenth of the traffic scans anything.

The charge on the insertion is the one number on that plate that was chosen rather than counted, and the choice is conservative. A write-amplification unit is charged as one key’s worth of block, so an insertion at a ratio of sixteen costs 30/64 of a transfer. A system that charged writes more dearly — a device whose writes cost several times its reads, which is the read ratio what insurance against an estimate costs sweeps — would keep the small ratio longer, and the crossing would move right rather than disappear.

Setting that plate beside this page’s is the clearest statement of the problem. The earlier page’s whole finding — a real improvement, correctly measured, worth having — moves a cost from 0.279 transfers to 0.201. The level count it is optimising around costs a short range query eleven transfers. The two pages are optimising the same structural quantity at scales two orders of magnitude apart, and only one of them is where a range-serving store’s time goes.

Why this is the shape of a whole family of mistakes #

The general form is worth naming, because a reader who has this one will spot the others.

A structure has several costs; an optimisation removes one of them; the removed cost is the one the structure was most often measured on; and the structure’s design parameters are then tuned as though the other costs did not exist. Here: filters remove the level count from point lookups, point lookups are how key-value stores are benchmarked, and the size ratio gets tuned for write amplification and point lookups alone.

The filter that feeds the table is the same device in a different structure, and it has the same blind spot — it can decline a probe for a named key and cannot decline a scan. A filter has a selectivity is the standing statement that a filter’s value is a ratio between two costs; what this page adds is that the denominator can be a cost the filter cannot touch, in which case the ratio is one however good the filter is.

And the honest summary of what a filter is follows from it. A Bloom filter is not a way of making a store faster; it is a way of removing one specific read — a read for a key that is not there — and everything it is worth is the share of a workload made of those reads.

That share is larger than it sounds, which is why the device is everywhere. A key-value store behind a cache sees mostly misses, because the hits were served by the cache; a store sharded across machines sees a lookup for every shard and finds the key on one; a store used as a set sees membership tests by definition. In all three the absent point lookup is most of the traffic and the filter is the whole design. The mistake is not building it. The mistake is letting the parameter it optimised — the level count seen through $p$ — stand in for the parameter it did not.

And the two can be separated by a measurement any running store can make, which is the practical form of this page. A store that counts its queries by kind knows the range share; the level count is in its own configuration; the block size and the mean range length are in its logs. Those four numbers are the whole of the plate above, and none of them requires an experiment.

What is not measured here #

One seek a level, charged as one transfer. A range query is modelled as one transfer to find the range’s start in each level’s index, then the blocks holding that level’s share of the rows. A real store’s index is itself blocks and a seek into a large level costs more than one; the plate therefore understates the range query’s cost, and the understatement grows with the level count — which is the direction that would make this page’s case stronger.

Levelled, not tiered. Each level is one sorted run. A tiered store keeps several runs a level and a range query reads all of them, so the level count in every number here becomes a run count, several times larger. That is the arrangement most write-optimised stores actually use.

Ranges that overlap every level. Every run’s key interval is assumed to overlap the range, which is exact for a store whose levels each hold a uniform sample of the key space and pessimistic for one whose recent levels hold a narrow range of recent keys. A store with time-ordered keys has levels that mostly do not overlap a given range, and a per-run minimum and maximum key — which every real store keeps — prunes them for free.

Closed forms, not a simulation. The point-lookup costs here are the closed forms rather than the built-and-measured filters of the earlier page, because this page’s sweeps are over stores too large to build once for each point. The earlier page’s simulation agreed with these forms at the sizes it could reach, which is the only reason to trust them here.

No comparison with a B-tree. The obvious rival for a range-heavy workload is the structure a log-structured store was built to avoid, and the writes nobody counted priced the two on insertions. A B-tree answers a range in one seek plus the rows, which is this page’s “one sorted run” line, and pays 49.3 elements of block per key stored to do it. The crossing between the two families on a mixed workload is a plate this page does not draw, and it is the plate a system designer actually wants. One dial between two structures is the argument that they are one design at two settings, so the crossing is a point on a curve rather than a choice between two things.

No compaction cost per query. Write amplification is reported as the classical $(T-1)L$ rather than measured, and the reads compaction itself performs are not charged to any query.

One block size and one key size. Sixty-four keys to a block throughout, which sets where the crossing on the length plate falls. A store of wide rows fits fewer to a block, so the range’s own data costs more blocks and the level count is a smaller share of it — the crossing moves left and the whole finding weakens. A store of narrow keys moves it right.

Still open: the filter a range query could use #

A Bloom filter cannot be asked about an interval, and there is a structure that can. A prefix filter — a Bloom filter over the prefixes of keys rather than over keys — can be asked “does this run hold any key beginning with $p$”, which is a range query when the range is a prefix. Real stores ship them, and their value is bounded by how well the query’s ranges line up with the prefixes the filter was built on.

The measurement that follows builds a store whose runs each carry a filter over $b$-bit key prefixes, sweeps $b$ from one to the key’s full width, and asks how many levels a range query can skip at each prefix length: short prefixes match everything and skip nothing, long prefixes match almost nothing but cover only ranges narrower than a prefix. The prediction from this page is that the useful band is narrow and that its position is set by the range length rather than by the store — so a store serving ranges of mixed lengths would need several such filters, and the memory that buys them is memory not spent on the point-lookup filters that are already there.