The bits a second threshold costs

A blocked Bloom filter confines each key’s bits to one small block, a cache line or two, so a lookup reads one block instead of scattering over the whole array — the trade positions confined to one line priced at a few per cent of false positives for five fewer lines read. A block the lookup can work out gave each key two candidate blocks and the first block a threshold on an ordering hash: a key below its first block’s threshold lives there, and the rest go to their second block. Built in increasing order of the hash, with a block’s threshold lowered as it fills, that design balances the load between blocks almost as well as offering every key two choices, and a lookup reads one threshold and one block. A penalty set by the block measured it across block widths. A threshold on a block of $w$ bits gave about the rate of one block of $2w$, and its advantage shrank as blocks widened — 30% at 512 bits, 13% at 2,048.

That page’s closing section located what the threshold leaves behind. A full block stops accepting keys for which it is the first choice, and cannot refuse keys for which it is the second. So the 3 to 10% of keys that overflow land wherever their second hash sends them and can push a block past its design load. The proposal was a second threshold on second-choice keys, with a third candidate block for keys refused by both, and a lookup that reads two thresholds before one block. The prediction was that this would remove most of the remaining spread at 512 bits and reach the rate of a block four times as wide, not twice, and that it would not be worth doing at 1,024 or wider.

The second threshold removes a quarter of the remaining spread and lowers the rate at only one width of four. What stops it is the price of its table, and the price of the first table turns out to have been set too high all along.

The rate, four designs, four widths #

The filters are the earlier page’s: 8,192 keys at sixteen bits a key, eleven bit positions a key inside its block, blocks aligned to their own width. Every design spends the same total bits. The threshold tables are paid for in whole blocks, as before, so a design with tables has slightly fewer blocks and slightly more keys in each. The two-threshold design processes keys in increasing order of the ordering hash, a tied group at a time. It closes a block’s first threshold when its first-choice keys would overflow it and its second threshold when its second-choice keys would, and sends a key refused by both to a third block chosen by a third hash. Every stored key is looked up and found; two million absent keys a point measure the rate, which resolves a rate near 0.06% to about 3%.

At 512-bit blocks, thresholds on both blocks measure 0.0656% against one threshold’s 0.0621% — 6% worse, a little over the measurement’s noise, and not in the direction predicted. At 256 bits the second threshold is worse by 8%, 0.0955% against 0.0887%. At 1,024 bits it is 9% better, 0.0522% against 0.0575%, and at 2,048 it is 5% worse again. The rate the prediction aimed at, one block four times as wide, is 0.0573% at 512 bits, and nothing with thresholds comes within 8% of it.

The one-block rates are the check that the measurement is sound. A penalty set by the block computed one block’s rate exactly, as Bloom’s formula inside a block averaged over a Poisson load, and the rates here sit within 5% of it from 512 bits up: 0.0888% measured against 0.0860% computed at 512, 0.0665% against 0.0646% at 1,024 and 0.0573% against 0.0549% at 2,048. At 256 bits the measurement, 0.1482% against 0.1362%, sits 9% above, the gap that page found at sixteen keys a block across four seeds.

The widest column shows the other thing the earlier page found: at 2,048-bit blocks the designs are closest together, because a block of 128 keys has a spread of eleven keys against its mean, less than a tenth, and there is little to repair. The one-block-four-times-as-wide line flattens for the same reason: at 2,048 bits a block of 8,192 bits measures 0.0464%, within 1% of the rate the same bits give with no blocks at all.

That would be an unremarkable mixed result if the second threshold did nothing. It does a great deal, and the rate hides it.

The spread it removes #

The second threshold narrows the spread of block loads by 26% to 29% at every width — at 512 bits, from 3.40 keys to 2.52, where one block’s is 5.71. It does exactly what it was proposed to do. Keys a full block would have had to take as its second choice go to their third block, and only 2 to 6% of keys need a third choice at all, 4.5% at 512 bits. The prediction that it would remove most of the remaining spread was too strong, and the direction is right.

The lookup pays much less for this than predicted. A lookup reads its first block’s threshold, and only a key above it needs the second threshold. At 512 bits that is 7% of absent-key lookups, so the design reads 1.07 threshold entries a lookup on average, not two. The line count rises from 2.00 to 2.07. Neither the second table’s reads nor its lines is where the design loses.

Where the gain goes #

A narrower spread should lower the rate, because a Bloom filter’s false-positive rate rises steeply with the load of the block a lookup lands in, and a spread load puts some lookups in overloaded blocks. The rate of a blocked design can be split into two parts. The first is the rate it would have if every block held exactly its mean load: that depends only on how many blocks the design’s tables leave. The second is everything the spread adds.

The second threshold cuts what the spread costs from 0.0097% to 0.0067% at 512 bits, and its table raises the no-spread rate from 0.0524% to 0.0589%. The table costs more than the spread saves, 0.0065% against 0.0030%. The second table, 248 thresholds of eight bits, is 1,984 bits. Paid for in blocks it removes four of them, and every remaining block carries 33.0 keys instead of 32.5. In a filter at sixteen bits a key with eleven bit positions, half a key more in every block raises the rate by 12%. The narrower spread is worth less than half that.

At 256-bit blocks the table is twice as costly relative to a block and the loss is plain: the no-spread rate rises from 0.0605% to 0.0748%, and the narrower spread takes back only 0.0075% of it. At 1,024 and 2,048 bits the tables are cheap and there is little spread left to remove. At 1,024 the two effects fall the second threshold’s way — its no-spread rate rises by 0.0029% and its spread cost falls by 0.0082%, almost to nothing — and at 2,048 the other way, by a margin inside two runs’ difference.

The same decomposition says something about the first threshold that the earlier page did not measure. At 512 bits one threshold removes 0.0329% of spread cost against one block, and its table costs 0.0062% in load. At 256 bits it removes 0.0734% and costs 0.0139%. The first threshold is a large net gain, and the reason is that it attacks the fat tail of a Poisson load, which is where most of one block’s excess is. The second choice showed how much of that tail a single alternative removes when keys are balls thrown into bins, and choices that are not independent what becomes of it when the alternatives are computed from one another rather than drawn separately. The second attacks what is left, a spread already close to the minimum that sixteen keys’ worth of randomness allows, and it pays the same price per table for much less.

The bits a threshold is stored in #

If a threshold table’s cost is its bits, the obvious question is how many bits a threshold needs. The earlier pages used 8, 256 levels for an ordering hash, and never varied it.

A threshold needs four to six bits, not eight. At 512-bit blocks one threshold of four bits measures 0.0595% and one of six 0.0592%, 10% under the eight-bit design’s 0.0660% in the same run. At 256 bits one of four bits measures 0.0771%, 12% under 0.0881%. Fewer bits cost fewer blocks, and a coarser threshold balances nearly as well. With sixteen levels a block’s threshold can still close within a sixteenth of the ordering hash’s range of where it would ideally close, and the keys that close costs it are a few, while the blocks it saves carry every key. Below four bits the threshold becomes too coarse to balance and the rate climbs again: two bits, four levels, is no better than eight. These are single runs of eight million queries; two hashes that shared their low bits averaged four seeds of a smaller filter and found the four-bit advantage nearer 3%, so the direction is settled and its size is not.

The same split into a no-spread rate and a spread cost says where the four-bit threshold’s advantage comes from, and it comes from both sides. At 512-bit blocks the eight-bit table leaves 252 blocks at a mean of 32.5 keys and a no-spread rate of 0.0524%; the four-bit table leaves 254 at 32.25 and 0.0493%. That is 0.0031% of the 0.0065% by which the four-bit design wins. The rest is spread: the four-bit design’s measured rate sits 0.0102% above its no-spread rate, the eight-bit design’s 0.0136%, and its load spread is 3.12 keys against 3.48.

That second half is not what a coarser threshold was expected to do, and it has a plain cause. A threshold closes a block when the next group of tied keys would overfill it, and with four bits each group is 512 keys spread over all the blocks — two to a block on average — where with eight bits it is 32 keys, one block in eight getting one. A coarse threshold therefore closes each block a little below its capacity rather than exactly at it, and sends slightly more keys on to their second choice: 10.7% overflow against 7.8%. Those second-choice keys land in blocks chosen at random, and at 512 bits random blocks are mostly under their capacity. The design spreads its surplus more widely and ends up more even. Two bits carries the same effect too far: blocks close at a quarter of their range, 16% of keys overflow, and the second choices begin to overload the blocks that are still open.

The two-threshold design at its own best width ties one threshold at its best at 512 bits: 0.0586% at three bits against 0.0592% at six, a difference of 1% where the measurement resolves about 1.5%. At 256 bits it wins, 0.0731% at three bits against 0.0771% at four, a 5% margin, and narrow thresholds are where it wins: at two and three bits the second table is cheap enough to pay. A two-threshold setting that once measured 0.1692% at four bits on 256-bit blocks, twice its neighbours, measures 0.0791% read from the top bits of its hashes; the collapse was the modulo’s, which two hashes that shared their low bits traced to 496 blocks being a multiple of sixteen.

The loads themselves #

The histograms show both halves of the trade at once. One block’s loads are a Poisson spread, with a long right tail running past 50 keys in a block meant for 32. The threshold cuts that tail off: no block holds more than 42. The second threshold pulls the distribution tighter still — its upper tail stops at 40 — and the whole distribution sits half a key to the right, where the second table’s blocks went. Two blocks and the chances they add found the same kind of exchange for offering every key a second block: better balance, paid for in a currency the balance cannot buy back.

The rate is an average over lookups, and a lookup lands in a block at random. So it is driven by the whole distribution of loads, not just its tail, and it can be lowered only by moving the whole distribution left or by squeezing the tail. The first threshold squeezes a fat tail. The second squeezes a thin one and moves everything right. A design that wanted the second threshold’s balance without its shift would have to find its bits somewhere other than the blocks, and the only other place in a filter of fixed size is the thresholds themselves — which is where the four-bit result says the bits were being wasted.

What was measured and what was not #

Sixteen bits a key, 8,192 keys. At other densities a block of a given width holds a different number of keys, and a penalty set by the block showed that the width and the bits a key act together through the mean load. The conclusions are about mean loads of 16 to 128 keys a block.

Absent keys, and present keys only for correctness. Every rate is measured on keys the filter does not hold, and every stored key is looked up only to check it is found. A lookup for a present key reads the second threshold whenever the key lives in its second or third block, 9.5% of keys at 512 bits, against 7% of absent-key lookups; a workload of mostly present keys would pay the second table’s read slightly more often and nothing else.

Independent positions inside a block. Each key’s eleven positions inside its block come from independent hashes, not from the two-value scheme two hash values and the keys they copy found costly in small filters. A production filter using that scheme inside a 512-bit block would pay its penalty on top of every rate here.

One construction order. Both threshold designs are built from a known key set in order of the ordering hash, which makes them static filters — the kind a run of a log-structured store carries. The day a filter cannot grow is where a filter that must grow is priced.

Rates to about 3% at two million queries, 1.5% at eight million. Every comparison the essay draws a conclusion from is larger than that, except the two-threshold design against the one-threshold design at their best widths on 512-bit blocks, which is reported as no difference. Every block and ordering value is read from the top bits of a multiply-shift hash.

The tie groups. A threshold of $b$ bits divides keys into $2^b$ groups, closed as wholes, and at two bits a group is a quarter of the keys. A construction that broke ties by a second hash inside a group would let a narrow threshold close a block precisely and was not built.

Still open: a threshold narrower than its block’s share #

The four-bit threshold beats the eight-bit one because a table’s bits cost the filter more than the table’s resolution is worth. That suggests going further in a different direction: not fewer bits a threshold, but fewer thresholds. A block’s threshold matters only for keys that name it as a first choice, and the table holds one for every block. Blocks could share thresholds in pairs or fours — one threshold for a group of blocks, closed when the group’s busiest block fills — and the table would shrink by that factor.

The measurement that follows gives one threshold of four bits to each group of $g$ blocks, for $g$ from one to eight, at 256- and 512-bit blocks, and measures the rate, the spread and the no-spread floor. The prediction is that sharing a threshold between two blocks loses little balance, since the busier of two blocks closes the pair only slightly early, and saves half the table. The design should then come within a few per cent of the rate of one block twice as wide with no table at all, which is the ceiling a threshold design can reach. At eight blocks a group the shared threshold should close too early for most of its blocks, and the balance should be lost faster than the table’s bits are saved.