Two blocks and the chances they add

Positions confined to one line found that a blocked Bloom filter’s penalty is not about hashing at all. A block of 512 bits holds however many keys happened to choose it, the false-positive rate is convex in that load, and the overloaded blocks cost more than the underloaded ones save. At eight bits a key the penalty was 7%. At sixteen it was 91%, because a tight filter has the most to lose.

That is a balls-in-bins problem, and the standard repair for one has already been measured. The second choice offered each key two buckets and sent it to the emptier, and the maximum load fell from a logarithm to the logarithm of a logarithm. So the natural question is whether a filter can do the same thing: offer each key two blocks, put its bits in the emptier, and flatten the load that the block penalty comes from.

It can do the insertion. The trouble is the lookup.

The load, flattened #

The repair works exactly as it does for a hash table.

The spread falls by more than a factor of three and the busiest block goes from 72% over the mean to 19% over. That is the balls-in-bins result again. A second choice leaves each block’s load close to the mean, because a key never adds to the busier of its two candidates.

If the false-positive rate depended only on load, this would fix the block penalty. It depends on something else as well.

Two blocks to ask #

A lookup for a key has to answer whether the key might be stored. With one block choice there is one block to check. With two, the lookup does not know which block the key was sent to. The emptier block at insertion time depended on every key inserted before it, and the filter does not record which one won. So the lookup must check both blocks and answer yes if either holds all of the key’s positions.

For a stored key that costs nothing in correctness: its bits are in one of the two, so one of them matches. For an absent key it is two tries at a false positive. Each block’s rate is lower because the blocks are flatter. But the lookup succeeds if either block produces a false match, so the rate it reports is close to the sum of the two blocks’ rates.

The result has two regimes and a crossing.

At low density the second choice nearly doubles the rate. At eight bits a key one block measures 2.338% and two choices 4.335%. The block penalty there was only 11% over the whole filter, so flattening the load could save at most that. Asking two blocks costs nearly 100%.

At high density it wins. At 24 bits a key one block measures 0.0085% and two choices 0.0029%. The block penalty there is seven times the whole filter’s rate, because the rate is so steeply convex in load that an overloaded block dominates. Flattening removes most of that, and doubling what is left still comes out ahead.

The two cross at about sixteen bits a key, where one block measures 0.0954% and two choices 0.100%. Below that density the second choice is a loss. Above it the second choice gains, and the gain grows with density.

Seen as a multiple of the whole filter, the second choice’s penalty is roughly flat at a little over two. The factor of two is the doubled chance. What remains above two is the load that flattening did not remove. One block’s penalty climbs from 1.11 to 7.0, because it is all load. The design that is best at every density on this plate is neither of them. It is a single block of 1,024 bits.

The fourth line is the one that explains the rest. Asking only the first candidate is not something a real lookup can do, because a stored key sent to its second block would be denied. But on absent keys it measures exactly what one block’s false-positive rate becomes once the load has been flattened. Flattening alone removes almost the whole block penalty: at sixteen bits a key one ordinary block is 2.17 times the whole filter and a flattened block is 1.09 times. At 24 bits the figures are 7.00 and 1.14. The balls-in-bins repair does what it did for the hash table, nearly completely.

The usable two-choice filter then sits at almost exactly twice the flattened block’s rate at every density: 2.06 against 1.06, 2.01 against 1.00, 2.28 against 1.09. The doubling is not a side effect that happens to be large. It is the whole remaining cost, and it follows from a lookup asking two blocks. The repair works and the lookup gives the gain back.

The block that was twice as wide all along #

A single 1,024-bit block has twice the room of a 512-bit block, and it spreads the same keys over half as many blocks, so each block’s load is closer to its mean in relative terms. It needs no choice and no second lookup, and it matches or beats two 512-bit choices at every density measured. At twenty bits a key it measures 0.0145% against 0.0159%. At 24 the two are 0.0026% and 0.0029%, a difference that rests on about thirty false positives each and cannot be told apart.

The comparison is fair only if both designs cost the same to read, and they do. A 1,024-bit block spans two 512-bit cache lines. Two 512-bit blocks span two lines as well. The quantity a blocked filter exists to reduce is the lines a lookup reads, so the real comparison is between designs at the same number of lines.

At one line there is only one kind of design, and the 512-bit block is the best of it. At two lines three designs sit together: one block of 1,024 bits at 0.0145%, two choices of 512 at 0.0160%, and two choices of 256 at 0.0181%. The single wide block is lowest. At four lines one block of 2,048 bits, 0.0099%, beats two choices of 1,024, 0.0149%, by a third.

For the same lines read, giving a key one wider block beats giving it a choice of two narrower ones. The choice flattens the load, and so does width. Width does not double the chances of a false match, because a lookup asks one block. The choice is a way of spending a second line, and on this measurement it is a worse way than spending the line on a bigger block.

Reading the second block only after a no #

There is an obvious refinement, and positions confined to one line predicted it would help: read the first block, answer yes at once if it matches, and read the second only if the first says no. Answers are identical, since yes from either block means yes. Lines should fall.

It helps stored keys and does nothing for absent ones. A stored key that went to its first block, 68% of them at this density, is found after one block and reads one line, so stored-key lookups average 1.31. An absent key is almost never matched by its first block. That match would itself be a false positive, 0.05% of the time at this density, so the lookup almost always goes on to read the second block and averages 1.99 lines. The refinement is free on true negatives only in the sense that it costs nothing extra. It saves nothing either, because a negative lookup is exactly the case where the first block cannot end the search.

Whether that matters depends on which lookups dominate. A filter exists to answer “no” cheaply for keys that are not there. A filter allowed to be wrong measured filters whose job is almost entirely negative lookups, standing in front of a slower store. For that workload the second choice is two lines a lookup, and a single 1,024-bit block is two lines with a lower rate. For a workload of mostly present keys, the refinement brings two choices to 1.31 lines. That is a real saving over a 1,024-bit block’s two lines, at a rate 54% higher than the wide block’s at sixteen bits a key and 10% higher at twenty.

Where the second choice’s hashes come from #

Every key here computes three hashes: one per candidate block and one for its positions inside a block. That is the independent version, and it is the one where the second choice does best.

A filter built for speed would not spend three hashes. Choices that are not independent measured what happens when a hash table’s two choices come from one hash split in two or from $h_1$ and $h_1 + h_2$, and found that the correlation between choices gives back part of the load balance. Two hash values and the keys they copy measured the same kind of shortcut inside a filter’s positions and found a penalty that grows as the space the positions share shrinks. A two-choice blocked filter built cheaply would pay both at once: less flattening from correlated choices, and positions made from two values inside a block of 512 bits. Neither is measured here, and both would move the crossing at sixteen bits a key towards higher densities, where the second choice already struggles to beat a wide block.

The block size the design is compared against has its own history. The bucket that fits a line chose a hash table’s bucket size by the cache line, and blocked filters inherited 512 bits for the same reason. This measurement suggests the line is the wrong unit to fix. What a lookup pays is lines read, and a block of two lines read once beats two blocks of one line each read together.

The densities filters are actually built at #

The crossing at sixteen bits a key matters because of where it falls. A floor on the bits measured an ordinary Bloom filter at 9.59 bits a key for a 1% false-positive rate. Rates of a few per cent to a tenth of a per cent, eight to fifteen bits a key, are what filters in front of a store are commonly sized for. Each halving of the rate costs about 1.44 more bits a key, and the reads a lower rate saves are only the reads of absent keys that would have been wrongly let through, so the memory for a much tighter filter usually does more good spent elsewhere. That whole common range lies below the crossing.

At twelve bits a key, near the middle of it, the numbers on the first plate are 0.318% for the whole filter, 0.417% for one 512-bit block, 0.351% for one 1,024-bit block and 0.640% for two choices. The second choice costs twice the whole filter’s rate and 1.8 times the wide block’s, at the same two lines a lookup as the wide block. Only a filter tuned to one false positive in several thousand, at twenty bits a key or more, reaches the regime where the choice beats a single narrow block. Even there it only ties with a wide one.

So the practical reading is short. For a blocked filter at an ordinary density, a second block choice is a loss on every absent-key lookup. The block penalty it was meant to remove was small at that density to begin with: 31% at twelve bits a key, against the 100% the doubled chance adds. The penalty only becomes large where the filter is tight, which is where the choice starts to help. By then a wider block has also started to help, and it costs no second lookup.

Why a table and a filter differ here #

The second choice pays in a hash table and not in a filter because the two structures ask different questions at lookup.

A hash table stores the key itself. A lookup in either of two buckets compares keys, and a key that is not there matches nothing in either bucket. Checking a second bucket costs a second probe and cannot produce a wrong answer. The load balance is pure gain, paid for in probes.

A filter stores only bits, and any block can match an absent key by accident. Checking a second block is a second chance of an accidental match. The load balance still helps each block, but the lookup gives back part of the gain the moment it asks two blocks. It gives back almost all of it when the filter is loose, and a factor of two when it is tight. The second choice measured the table’s version with no second chance to pay for. The filter’s version has the same insertion and a lookup that pays for two.

What is settled and what is not #

Settled by measurement over 24 filters of 2,048 keys: a second block choice cuts the spread of keys a block by more than half at every density, cuts the busiest block at sixteen bits a key from 55 keys to 38, doubles the rate at eight bits a key and cuts it by two thirds at 24. Its rate is about twice the whole filter’s at every density, while a flattened block asked alone measures between 1.00 and 1.39 times the whole filter’s rate, so the doubling is the entire remaining cost. A single block of 1,024 bits reads the same two lines and is as good or better at every density measured. Reading the second block only after a no leaves absent-key lookups at 1.99 lines and brings stored-key lookups to 1.31.

Not settled:

The tight end. At 20 and 24 bits a key the rates come from 30 to 230 false positives a design. The ordering of one 1,024-bit block against two 512-bit choices there is within that noise, and the claim is only that the choice does not beat the wider block.

Other block counts. 2,048 keys at these densities means 32 to 96 blocks. With far more blocks the load spread in relative terms is the same, but the rate of an overloaded block interacts with the number of positions, and nothing here varies the key count.

A filter that records the choice. The lookup reads both blocks because it cannot know which was used. A design that spends a few bits a block to say which keys chose it, or that makes the choice depend only on the key, would be a different structure with a different trade.

Still open: a choice the lookup can recompute #

The whole difficulty is that the emptier block depends on insertion history the lookup cannot see. There is a family of designs where it does not. Let each key’s two candidate blocks be ordered by a hash of the key, and let the insertion rule depend only on a threshold carried with each block, not on which block is currently emptier. For example, a block accepts keys whose ordering hash is below its current threshold, and it lowers the threshold when it fills. A lookup reads the thresholds and knows which block the key must be in. That is one line of thresholds plus one block.

The measurement that follows builds that filter, with thresholds in a small array read before the block, and measures its load spread, its rate and its lines against one wide block at the same total bits. The thresholds cost bits a block that could instead have gone into the block. The question is whether a lookup that knows where to look can keep the load balance and lose the doubled chance, and at what density the bits spent on thresholds are repaid.