Two hashes that shared their low bits

A block the lookup can work out gave a blocked Bloom filter a threshold for each block. A key is placed in its first block while its ordering value, a second hash of the key, is below that block’s threshold, and in a second block otherwise. A lookup reads the threshold and knows which block to check. The bits a second threshold costs shrank the thresholds from eight bits to four, and a threshold knows only its own block tried sharing one among a group of blocks. Each of the last two pages recorded something it could not explain. The first measured two four-bit thresholds at 256-bit blocks at 0.169%, beside neighbours near 0.08%. The second centred itself on 512-bit blocks because at 256 bits one seed of four collapsed, and it said so.

The last of those pages closed by proposing to code the threshold table by its own distribution, which would save about a third of the table: half a per cent of a filter’s memory. A saving that size moves the false-positive rate by a few per cent at most, and an instability that doubles the rate on one seed in four would bury it. So the instability had to be traced before the saving could be measured. It traces to one line that every one of these filters shares, the line that turns a hash into a block number.

The reduction, and what it was defended on #

Every filter on these pages hashes a key with multiply-shift. The hash multiplies the key by an odd constant modulo $2^{32}$ and keeps the top 30 bits of the product. A block number is that 30-bit value modulo the number of blocks, and the ordering value is another such hash modulo sixteen. The modulo was chosen with an argument, and the argument was about bias: at these sizes it introduces a bias below one part in a million, since $2^{30}$ is so much larger than any block count, and none at all when the count is a power of two. That is true, and it answers the wrong question. Bias is about one value’s distribution, and the trouble here is two values’ dependence.

The low bits of a product depend only on the low bits of its factors. Bit $j$ of $a \cdot x \bmod 2^{32}$ is a function of bits 0 to $j$ of $a$ and of $x$, and nothing above. Keeping the top 30 bits drops the lowest two, so the lowest $j$ bits of the hash are a function of the key’s lowest $j+2$ bits. A modulo by sixteen keeps exactly the lowest four bits. A modulo by 992, which is 31 times 32, keeps among other things the value modulo 32, the lowest five bits. So a key’s ordering value and its first block modulo 32 are both functions of the key’s lowest seven bits, through two different multipliers. Among all keys they take at most 128 combinations of the 512 that independent values would reach.

A hash is a family, not a function showed a hash that takes the low bits of the key sending every multiple of the table size to one bucket. Multiply-shift fixes that for one value, by keeping the top bits of the product, which depend on every bit of the key. It does not fix it for the low bits of its own output, and no multiplier can, because carries only move upward.

Sixty-four cells of two hundred and fifty-six #

Taken by a modulo, a key’s ordering value and its first block modulo 16 reach 64 of the 256 combinations; taken from the hash’s top bits, all 256. Both values are functions of the key’s lowest six bits, and six bits have 64 values, so the grid on the left has exactly 64 cells filled and every one of them receives four times its share. Each residue of the block index sees only four of the sixteen ordering values. The top bits of a multiply-shift hash depend on every bit of the key, and the grid on the right is flat.

The same holds for a key’s two block choices. At 256 blocks the first and second block, each the lowest eight bits of a different multiply-shift hash, are both functions of the key’s lowest ten bits. So the pair takes 1,024 values of the 65,536 possible. Keys are not spread over all pairs of blocks; they come in 1,024 kinds, each kind sharing the same two blocks.

Where the collapse came from #

At 128-bit blocks the modulo filter’s rate runs from 0.185% to 0.645% across eight seeds; the same filter reading the hash’s top bits runs from 0.126% to 0.133%. The spread between seeds is a factor of 3.5 in one and 1.06 in the other, and the top-bit filter is better than the modulo filter’s best seed. At 256-bit blocks the modulo filter runs from 0.082% to 0.171%, which is the collapse the previous page saw on one seed of four, and the top-bit filter from 0.072% to 0.081%. At 512-bit blocks the two nearly agree, and at 64-bit blocks they agree to within the seeds’ own spread.

The block counts say why the widths differ. Sixteen bits a key over 8,192 keys is 131,072 bits, and with a four-bit threshold a block the filter holds 1,927 blocks of 64 bits, 992 of 128, 504 of 256 and 254 of 512. Those are an odd number, 31 times 32, 63 times 8 and 127 times 2. The dependence between the ordering value and the block needs a common power of two, and the larger the power of two in the block count, the more of the block index is tied to the key’s low bits. A count of 992 ties five bits of the block to the same seven key bits that set the ordering value. A count of 254 ties one bit, and the filter barely notices. An odd count ties nothing.

The rate follows the power of two #

Varying the filter by a few keys at a time, the modulo filter’s rate spikes at exactly the block counts with a large power of two in them: 0.190% at 976 blocks, 0.146% at 984 and 0.197% at 992, against about 0.131% where the count is odd or twice an odd number. The top-bit filter has no spikes. Between 969 and 993 blocks its rate stays in a band from 0.124% to 0.138%, and it wanders the way a measured rate wanders over a million queries. A filter whose rate depends on whether its block count is divisible by sixteen has a defect in it, because nothing about a block’s capacity knows its index.

The previous pages could not have seen this. Each measured one block count at each width, since the count follows from the bits a key and the width. The rate at 256 bits looked like the rate at 256 bits, with an unlucky seed. It was the rate at 504 blocks.

Why a threshold suffers and a second choice does not #

The threshold design is hurt because its whole mechanism is the ordering value. Keys are placed in increasing order of that value, a tied batch at a time, and a block’s threshold closes at the first value where the block’s first-choice keys would overflow it. With independent values, a block sees keys arriving at all sixteen ordering values, about a sixteenth of its first-choice keys at each. It can close within a sixteenth of the ideal point. When the block’s index modulo 32 fixes which four of the sixteen values its keys can have, those keys arrive in four batches of a quarter each. The threshold can close only at those four points. A block that would have overflowed by one key closes a quarter of its keys out at once, and they go to second blocks chosen from the same few kinds. A four-bit threshold had become a two-bit one, with the two bits chosen differently for each residue class of blocks. The seeds then decide whether the classes’ closing points land well or badly, which is why the rate spread across seeds is a factor of 3.5.

The emptier-of-two filter, whose two block choices are dependent in the same way, loses nothing to it: 0.100% by modulo and 0.099% from the top bits at 256 blocks, where its pairs of blocks take 1,024 values of 65,536. Its mechanism does not use an ordering value. Each key goes to whichever of its two blocks holds fewer keys, and a kind of key, sharing its two blocks with a few others of its kind, still spreads between them. Choices that are not independent measured two choices drawn with a dependence built in on purpose and found the balance survived much of it, and this is a case of that. The one-block filter uses one hash, and one hash’s low bits are as uniform as its high ones on random keys, so it is untouched too.

So the defect is specific. It needs two values of one key, reduced by ranges that share a power of two, and a mechanism that depends on their joint distribution. The threshold filters have all three. A filter with eight-bit thresholds has them in a milder form, since its ordering value keeps eight bits and loses fewer of its levels to the dependence. On the widths the earlier pages measured, the eight-bit filter’s rate moves by at most 11% between the two reductions, in both directions, and as much at block counts that are odd, where the reduction cannot matter. That is one run’s noise, not the dependence.

What the published numbers become #

The pages this touches measured at 512-bit blocks mostly, where the block count carries one factor of two, and most of what they said survives. The claim that a threshold needs four or five bits and not eight survives in direction and shrinks in size: averaged over four seeds, a four-bit threshold beats an eight-bit one by 3% reading the top bits, and by 4% by modulo, against the 9% a single run of eight million queries reported. Three bits is still worse than four, by 6% from the top bits. Between four and eight bits the differences are within what four seeds resolve. At 256-bit blocks the modulo’s four-bit filter averages 0.118% over four seeds and the top bits’ 0.078%. Every width from three bits to six sits within 3% of that figure on the top bits.

The shared-threshold page’s ranking survives as well. Rebuilt from the top bits at 512-bit blocks, on the same million queries, one threshold a block measures 0.0605%, one shared by a pair 0.0705% and one shared by sixteen blocks 0.100%, against 0.0577%, 0.0650% and 0.0889% as published. Sharing loses at every group size either way. A run twice as long gives 0.0616%, 0.0699% and 0.0922% from the top bits and 0.0607%, 0.0730% and 0.0948% by modulo, so at 512 bits the difference between the reductions is no larger than the difference between one run and the next. The page’s centring on 512 bits turns out to have been the right instinct for the wrong reason: 512-bit blocks were steady because their block count is twice an odd number.

The two figures the earlier pages left unexplained are both explained. The 0.169% for two four-bit thresholds at 256-bit blocks was measured at 496 blocks, a multiple of sixteen. Over four seeds that design measures 0.097% to 0.176% by modulo and 0.076% to 0.080% from the top bits. The shared-threshold page’s collapse at 256 bits was the same filter at 504 blocks.

The repair and its cost #

Reading a multiply-shift hash into a range means taking its top bits, which is how the family is defined: a hash into $2^\ell$ buckets keeps the top $\ell$ bits of the product. For a range that is not a power of two, the top-bit reading is $\lfloor h \cdot r / 2^{30} \rfloor$, one multiplication and one shift, and it spreads the hash’s 30 bits over the range as evenly as the modulo does. It costs no more than the modulo and on most machines less, since a division is slower than a multiplication.

What it costs here is the published numbers. The pages that built blocked filters with thresholds all measured with the modulo, and their figures and their text still agree with each other, because both were made from it. Rebuilt from the top bits, their numbers move by a few per cent at 512-bit blocks and by a third or more at 128 and 256. A penalty set by the block checked its one-block rates against Bloom’s formula averaged over a Poisson load and found them within 5%. That check passed because a one-block filter uses one hash. The threshold filters had no such check, since no formula gives their rate, and they are where the dependence was.

Why a single run could not show it #

Each of the earlier pages did what a measurement here is asked to do. It built real filters, counted real false positives over millions of queries, checked that no stored key was ever denied, and compared designs on the same keys. The dependence passed all of that. A filter with a dependent ordering value is still a correct filter: it denies no stored key, and its rate is a real rate, measured honestly, for that block count. What it is not is the rate of the design the page describes, which assumes the key’s values are independent. No check on one filter’s answers can see the difference, because the answers are right.

What exposes it is a comparison the pages did not make: the same design at neighbouring sizes. A design’s rate should change smoothly with the number of blocks, since nothing about a block cares what its index is. A rate that jumps by half when the count gains a factor of two is measuring the indices. The second choice measured two hashes drawn from one seeded family and found each exactly as good as the other on its own; what the pair buys is in how the two combine. The threshold pages relied on that combination too, for an ordering value and a block rather than for two blocks, and a family that behaves for one value at a time need not behave for two values read from the same low bits.

A sweep of block counts, with a second reduction to compare against, costs one extra plate. It would have caught this where the four-bit threshold was first measured.

What this does not settle #

Random keys only. Every key here is a uniformly random 32-bit integer. Keys that are themselves structured in their low bits — consecutive integers, aligned addresses — would make the modulo’s dependence worse, and would test the top-bit reading, which is only as good as the multiplier’s mixing. The independence an estimator spends caught multiply-shift failing a pairwise test decisively on keys built from its own arithmetic, and none of those probes is used here.

One hash family. The dependence is multiply-shift’s, and a family whose low output bits depend on all of the key would not have it. The fix measured here keeps the family and changes the reading, which is the smaller change.

The rebuilt numbers are single runs where the published ones were. The shared-threshold figures from the top bits are one run of two million queries, as the published ones were. The threshold widths are four seeds of two million queries each, and the ranking of three bits against four and of four against eight is resolved by them. The differences between four, five and six bits are not.

Still open: the table coded by where thresholds close, on a hash that can be trusted #

The measurement the previous page proposed can now be made. On the top-bit filter, at every width, a threshold’s closing distribution is the filter’s own and not an artefact of its block count. At 512-bit blocks two blocks in five never close, and the rest close in the upper half of the ordering hash’s range, which gives the table an entropy well under its four bits. A code built from that distribution would hold the table in about two thirds of the bits.

The prediction is that the coded table matches the four-bit rate on under three bits a block, and that the question worth asking is how it is laid out. A variable-length code cannot be indexed directly. If the table is packed end to end with an index of where each chunk begins, a lookup reads the index and then the table, the second read the threshold design was built to avoid. If each cache line holds a fixed number of thresholds, a lookup finds its threshold in one line with no index. The line then has to fit its worst run of long code words, and that worst case, not the entropy, sets the table’s size. The prize is small, a third of the table at half a per cent of the filter. On a filter whose rate now holds still from one seed to the next, a saving that size is measurable, and the page that measures it will say whether a code can be read in one line.