A penalty set by the block

A block the lookup can work out measured a repair for the penalty a blocked Bloom filter pays. Confining a key’s bit positions to one 512-bit block makes a lookup read one cache line, and costs false positives, because some blocks draw more keys than others and a Bloom filter’s error is convex in its load. Giving each key a second candidate block and each block a threshold on a hash of the key lets a lookup work out which block a key went to. That flattens the load and keeps a single block read. At sixteen bits a key on 2,048 keys it measured 0.0628% against one block’s 0.0954%, recovering about two thirds of what an oracle lookup could.

Its list of things not settled ended with the size of the filter. Everything had been measured at 2,048 keys, and the page argued that on a larger filter the advantage over one block should widen: the number of blocks grows with the keys, so the tail of the load distribution grows, and with it the penalty the threshold exists to repair. It said plainly that this was an argument and not a measurement.

This page measures it. The argument fails, the reason it fails is worth having, and the variable that actually decides the penalty turns out to be one the earlier pages held fixed.

The rate does not see the filter’s size #

The measurement is the earlier page’s three designs, built exactly as it built them, at sixteen bits a key and 512-bit blocks, on filters of 2,048, 8,192, 32,768 and 131,072 keys: a 64-fold range. Every point is two million lookups of absent keys, spread over as many filters as keep the measurement affordable. That is enough to resolve a rate near 0.06% to a few per cent. Beside the one-block rate is a computed one: Bloom’s formula applied inside a block, averaged over the block’s load, with the load drawn from a Poisson distribution whose mean is the keys a block holds, 32 here.

Nothing moves. One block’s rate wanders between 0.085% and 0.091% across a 64-fold range of sizes, around a computed value of 0.086% that does not depend on the size at all. The threshold design stays between 0.063% and 0.066%, 24% to 31% under one block at every size. The emptier-of-two design stays near 0.1%, its doubled chance of a false positive intact. Two blocks and the chances they add measured that doubling at 2,048 keys, and it is exactly as large at 131,072: a lookup that must ask two blocks is wrong twice as often however many blocks there are to ask, because the chance is set per lookup, not per filter. The advantage the earlier page predicted would widen is the same at 131,072 keys as at 2,048.

The computed line explains why. A lookup for an absent key lands in a block chosen by a hash, so every block is equally likely to be asked, and the filter’s rate is the mean of its blocks’ rates. Each block’s rate depends only on how many keys it holds. In a one-choice filter every block’s load has the same distribution — binomial, with a mean of the block’s width divided by the bits a key — whatever the number of blocks. More blocks means more samples from that distribution, not a different distribution, and a mean over more samples of the same thing is the same mean.

The tail grows and the rate does not follow it #

The earlier page’s argument was not wrong about the tail. It was wrong about what the rate is.

The busiest block does grow with the filter. Under one choice it holds 51 keys at 2,048 and 57 at 131,072 — the maximum of more draws from the same distribution, rising slowly, the way the second choice measured a hash table’s worst bucket rising. The threshold design’s busiest block grows less, from 42 to 43, and the emptier of two holds its busiest block at exactly 35 at every size. All three shapes are the balls-in-bins results already measured for hash tables.

But a false-positive rate is not a maximum. The busiest block at 131,072 keys is one block of 4,096, and a lookup reaches it once in 4,096 tries. Its rate is higher than the average, and it gets its share of the average, a share that falls exactly as fast as the tail rises. A worst case that grows with the number of blocks moves a quantity that averages over blocks by nothing. The earlier argument carried a statement about the maximum across to a quantity that is a mean. That is the same slip distributions, not averages keeps warning about, taken in the other direction: here the average is the question and the tail is the distraction.

The threshold design shows the same thing in a second way. Its advantage over one block comes from narrowing the whole load distribution, not from trimming the maximum. Its load spread is 3.4 keys against one block’s 5.6 at every size, and the spread of a distribution does not depend on how many samples are drawn from it.

Which quantities a filter’s size can move #

The distinction is worth making general, because it decides in advance whether a measurement at one size says anything about another.

A quantity that is an average over lookups — a false-positive rate, an expected number of lines read, an expected number of probes — is a property of the distribution a single lookup meets. A lookup meets one block, chosen by a hash, and the load of that block has the same distribution in a filter of a thousand blocks as in a filter of a million. Every quantity of that kind is the same at every size, however it is computed. The same holds for a quantile over lookups: the 99.9th percentile of the load a lookup meets is a quantile of the same distribution, and it does not grow either.

A quantity that is a statement about every block is different. The fullest block, the chance that some block overflows, the capacity a design must reserve so that no block ever refuses a key — these are statements about a maximum, and the maximum of more samples grows. The second choice measured exactly that growth for a hash table’s worst bucket, and it is where the earlier page’s intuition came from. It applies wherever a structure fails at its fullest block. A bucketed table with a fixed number of slots a bucket is one: its capacity has to cover the busiest bucket or an insertion fails, and an insertion that can fail is what that failure looks like from the caller’s side. A Bloom filter never refuses a key, so it has no such quantity. Its busiest block simply answers yes a little more often, to the one lookup in thousands that reaches it.

So the question to ask of any blocked structure, before measuring it at a larger size, is which of the two kinds of quantity is being claimed. The bucket that fits a line sized its buckets to a cache line and had to find room for every key, which is a claim about the fullest bucket; a filter confined to a line only has to average well. The two designs share a shape and answer to different statistics.

What the width decides #

If the size does not decide the penalty, something else must, and the computed line says what: the mean load of a block, which is its width in bits divided by the bits a key. The earlier pages held it at 32 by fixing 512-bit blocks at sixteen bits a key. Sweeping the width moves it.

One block’s penalty falls steadily as the block widens, from 3.1 times an unblocked filter’s rate at 256 bits to 1.1 times at 4,096. The reason is the Poisson spread. A block holding $\lambda$ keys on average has a spread of $\sqrt{\lambda}$, so the spread as a share of the load is $1/\sqrt{\lambda}$: a quarter at 16 keys, an eighth at 64, a sixteenth at 256. A narrower relative spread means the convexity of Bloom’s formula has less to act on. The computed line follows the measurement at every width to within 6%, which is the resolution the queries allow.

The threshold’s advantage falls with it. It is 39% under one block at 256 bits, 31% at 512, 13% at 1,024, and gone at 2,048. The threshold repairs the spread, and there is less spread to repair when blocks are wide. At the widest two widths on this plate it is behind one block — 5% at 2,048 bits and 19% at 4,096 — and that part is not the width at all.

It is the price of the thresholds, paid in the currency the earlier page chose. To keep every block aligned to a cache line, the thresholds are paid for by dropping whole blocks, not by narrowing every block. At 4,096-bit blocks on 8,192 keys there are only 32 blocks, and a table of 32 eight-bit thresholds costs one of them, 3% of the filter’s capacity for 256 bits of table. On 131,072 keys there are 512 blocks and the table costs one block in 512. Measured there, the threshold design is 8% under one block at 2,048 bits (0.0505% against 0.0550%) and level at 4,096 (0.0495% against 0.0490%). So the filter’s size does enter, once, through the rounding of the table into whole blocks — and there it matters least exactly where the earlier page expected it to matter most.

A threshold is worth a doubling #

The width sweep says what a threshold buys. The question a designer asks is what it costs, and the cost of a blocked filter is the lines a lookup reads.

A threshold on a block of $w$ bits gives about the rate of one block of $2w$ bits, at the line count of the narrower block plus one. At 256 bits the threshold design measures 0.0871% against one 512-bit block’s 0.0905%. At 512 it measures 0.0628% against one 1,024-bit block’s 0.0634%. At 1,024 it measures 0.0554% against 2,048’s 0.0524%, and the rule starts to slip as the penalty runs out.

The equivalence on line counts is exact at the width that matters most. A threshold on a 512-bit block reads two lines, and so does one block of 1,024 bits: a 1,024-bit block spans two lines and a lookup’s eleven bit positions almost always touch both. The two designs have the same rate and the same line count, and the lines are different objects. The 1,024-bit block’s two lines are both random lines of a large filter. The threshold design’s second line is the table of thresholds, a few dozen bytes read by every lookup, which on any real machine would sit permanently in the first-level cache. One access, eight kilobytes is the page on why a line that is always hot is not the same cost as a line that is not.

The plate also shows the ceiling on the whole idea. Positions confined to one line confined a key to one line to make a lookup cost one line, and every repair since has spent a little of that back. A threshold spends a line that is nearly free to buy a doubling of the width. Beyond that, a wider block is simply a less blocked filter, and at 4,096 bits the design is reading six lines for a rate 9% above the unblocked filter’s — whose lookup reads eleven. The design space between one line and no blocking at all is one doubling wide, and a threshold covers it.

Where the repair goes as the block widens #

The threshold design flattens the load by a nearly constant share at every width: its spread is 54% to 63% of one block’s. What changes is what that flattening is worth. At 256 bits a block’s spread is a quarter of its load, and removing four tenths of it removes most of the penalty. At 4,096 bits the spread is a sixteenth, and removing four tenths of it removes four tenths of almost nothing. The overflow into second blocks falls as blocks widen too, because a wide block rarely reaches its capacity. The keys it does send are still the 3 to 11% that land in blocks with no say, which a block the lookup can work out identified as the whole of the remaining spread.

So the earlier page’s question has its answer in a different variable. It asked whether the threshold would be worth more on a larger filter. The answer is no, because the size does not change the load distribution. It is worth more on a narrower block, because the width does. A designer who wants the threshold’s benefit should look at the keys a block holds: 16 to 64 is where it pays, and 128 or more is where it has nothing left to do.

What was measured and what was not #

Sixteen bits a key throughout. The mean load is width divided by bits a key, so a denser filter is equivalent to a wider block. At eight bits a key a 512-bit block holds 64 keys, and the earlier page’s finding that the threshold loses at eight bits a key is this page’s 1,024-bit column seen from the other side.

The computed line assumes a Poisson load. A one-choice filter’s load is binomial, and the Poisson distribution is its limit when blocks are many. At 16 blocks the two differ in the tail, which is why the plates build filters of at least 2,048 keys. Every measured one-block point is within 6% of the computed one, and that agreement is the evidence that nothing except the load distribution is at work.

The threshold design’s table is paid in whole blocks. That choice belongs to the earlier page and keeps every block on a line. On small filters with wide blocks it costs more than the table’s bits, and the 5% and 19% losses at 2,048 and 4,096 bits on 8,192 keys are that rounding, not the design. The 131,072-key measurements, 8% ahead and level, are the design.

Random keys. Every filter here holds keys drawn from a seeded random source, and every lookup is for a key drawn the same way. The adversary who knows the seed is the page on what happens when the keys are chosen, and a blocked filter’s weakest point is the block an adversary can fill.

Still open: a threshold on both blocks #

Everything the threshold design leaves on the table is the overflow. A block that fills stops accepting keys for which it is the first choice. It cannot refuse keys for which it is the second, so the 3 to 11% of keys that overflow land wherever their second hash sends them, and a block can be pushed past its design load by keys it never agreed to take. On every width here the design’s load spread stays at more than half of one block’s, and the overflow is why.

The obvious repair has a cost the earlier page named: a key refused by both of its blocks needs somewhere to go. The measurement that follows gives each key a third candidate and every block a threshold on both first- and second-choice keys, sends a doubly refused key to the third, and has the lookup read two thresholds before it reads a block. It asks how much of the remaining spread that removes, what the second threshold line costs, and whether the design then reaches the rate of a block four times its width rather than two. The prediction is that it removes most of the remaining spread at 512 bits, and that it is not worth doing at 1,024 or wider, because by then the penalty it would repair is 13% and the second threshold costs another line.