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 — 31% at 512 bits, gone by 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 11% 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 third of the remaining spread and does not lower the rate at any width. What stops it is the price of the first threshold, not the second, and that price 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.0653% against one threshold’s 0.0628%. The difference is inside the measurement’s noise, and it is not in the direction predicted. At 256 bits the second threshold is worse, 0.0963% against 0.0871%; at 1,024 and 2,048 bits the two designs agree to within 3%. The rate the prediction aimed at, one block four times as wide, is 0.0524% at 512 bits, and nothing with thresholds comes near 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 at every width: 0.1424% measured against 0.1362% computed at 256 bits, 0.0905% against 0.0860% at 512, 0.0634% against 0.0646% at 1,024 and 0.0524% against 0.0549% at 2,048. Differences of that size are what two million queries resolve, and they fall on both sides.

The widest column shows the other thing the earlier page found: at 2,048-bit blocks none of the designs is much better than one block, 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, and at 2,048 bits a block of 8,192 bits is no better than one of 2,048, since both are already near the rate the same bits give with no blocks at all.

That would be an unremarkable null 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.35 keys to 2.41, where one block’s is 5.72. 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. 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.0104% to 0.0064% at 512 bits, and its table raises the no-spread rate from 0.0524% to 0.0589%. The two nearly cancel. 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 about the same.

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.0051% of it. At 1,024 and 2,048 bits the tables are cheap, but there is little spread left to remove, and the two effects are both small.

The same decomposition says something about the first threshold that the earlier page did not measure. At 512 bits one threshold removes 0.0339% of spread cost against one block, and its table costs 0.0062% in load. At 256 bits it removes 0.0692% 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 or five bits, not eight. At 512-bit blocks one threshold of four bits measures 0.0587%, 9% under the eight-bit design’s 0.0644% in the same run. At 256 bits one of five bits measures 0.0789%, 11% under 0.0887%. 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 worse than eight.

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.0057% by which the four-bit design wins. The rest is spread: the four-bit design’s measured rate sits 0.0094% above its no-spread rate, the eight-bit design’s 0.0120%, and its load spread is 3.04 keys against 3.29.

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.6% overflow against 7.6%. 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 overload the blocks that are still open.

The two-threshold design at its own best width does no better than one threshold at its best: 0.0570% at three bits against 0.0587% at four at 512 bits, a difference of 3% where the measurement resolves about 1.5%, and 0.0820% against 0.0789% at 256 bits, the other way. One setting of the two-threshold design went badly wrong: two 4-bit thresholds on 256-bit blocks measured 0.1692%, twice its neighbours, with 9% of keys sent to a third block. With sixteen levels of ordering hash and 8,192 keys, each level is a tie group of about 512 keys. A group that overflows a block’s second threshold is refused as a whole, and at that width a whole group is dozens of blocks’ worth of keys. The reason for this one setting’s collapse was not traced further.

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 41. 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.4% 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, which is reported as no difference.

The tie groups. A threshold of $b$ bits divides keys into $2^b$ groups, closed as wholes. The one pathological setting is a case where a group is large compared to a block; a construction that broke ties by a second hash inside a group would remove it 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.