A block the lookup can work out

Two blocks and the chances they add took the repair that tames a hash table’s worst bucket — offer each key two places and use the emptier — and gave it to a blocked Bloom filter. The load flattened: the busiest block of a filter at sixteen bits a key went from 55 keys to 38. The false-positive rate did not move, and at eight bits a key it doubled.

The reason is one sentence and it is the whole design problem. A lookup cannot know which of the two blocks the key went to, because that depended on which block was emptier at the moment of insertion, and a lookup has no access to insertion history. So it reads both blocks and answers yes if either matches. Two blocks is two chances to be wrong, and the doubled chance cancels the flatter load almost exactly.

That page ended by naming the way out. The block a key goes to does not have to depend on history. It can depend on the key and on a small number the block carries, and if a lookup can read that number it can work out where to look.

The lowest line is the one to keep in view. It was drawn on that page as a diagnostic — the load balance’s gain with the doubled chance taken out — and its caption said plainly that it is not a filter, because no lookup can do what it does. It sits at 1.09× the whole filter at sixteen bits a key where the real two-choice design sits at 2.28×. Everything below is an attempt to turn that line into a filter.

A threshold instead of a comparison #

Give each key an ordering hash $u(x)$ as well as its two candidate blocks. Give each block a threshold $\tau$: it accepts a key whose $u$ is below $\tau$ and sends the rest to their second block. A block starts with $\tau$ at its maximum, accepting everything, and lowers it when it reaches its design load.

A lookup computes $u(x)$ and the first block, reads that block’s threshold, and knows where the key must be. One threshold, one block, one chance.

Two things make it correct, and both are constraints on when such a filter can be built.

Keys are inserted in increasing order of $u$. Lowering a threshold after a key above the new threshold has already been placed would leave that key unreachable: the lookup would go to the second block and find nothing. Building in increasing $u$ means every key already in a block is below the threshold when it falls. That makes this a static filter, built from a known key set — which is what a filter over a run of a log-structured store is, and is not what a filter accepting a stream of insertions is.

A whole tied group of keys goes in or out together. The threshold is quantised, so with 2,048 keys and an eight-bit ordering hash about eight keys share each value. Closing a block at $u$ after accepting some of the keys at $u$ leaves those keys above their own block’s threshold and unreachable. Measured before the grouping was added: 134 stored keys denied, on a structure that is supposed to have no false negatives at all. The gate that caught it is the one that asks every stored key back.

The thresholds are paid for #

A table of thresholds is not free and it is not paid for out of nowhere. Each is a few bits and there is one per block, and those bits come out of the same budget as the filter.

They are paid for in blocks rather than in bits a block, and the difference is not cosmetic. Narrowing every block to 504 bits to make room was the second attempt: a block then no longer starts on a cache line, so a lookup that reads “one block” reads 1.82 lines and the design’s entire claim stops being true. Dropping one block keeps every block aligned and one line wide, and the cost lands where it belongs — 63 blocks instead of 64 for the same bits, so each holds 1.6% more keys.

The first attempt was worse and is worth recording because it failed silently. It shortened the bit array and left the block indices alone, so the last block ran past the end, every position there counted as set, and that block answered yes to everything. One block in sixty-four is a floor of 1/64 on the false-positive rate. The plate drew 1.6% against the one-choice filter’s 0.089% and read as the design being seventeen times worse, rather than as an index running off the end.

What it buys #

At sixteen bits a key the threshold design measures 0.0628% against one block’s 0.0954% and two blocks’ 0.100% — a third below either, at the same total bits, reading one block and one threshold. At twenty bits it is 0.0123% against 0.0231% and 0.0159%. At twenty-four it is 0.0021% against 0.0085% and 0.0029%.

At eight bits a key it loses, at 2.545% against one block’s 2.338%. Positions confined to one line measured where the block penalty comes from in the first place — a block that drew more than its share of keys is over its design load and the rate is convex in the load — and that page’s own numbers say the penalty grows from 1.11× the whole filter at eight bits a key to 7.0× at twenty-four. A repair aimed at the penalty should therefore be worth least where the penalty is smallest, and it is. That is the density where the block penalty is smallest — a loose filter’s blocks are all far from full, so their load spread costs little — and where a lost block costs most, because one block in thirty-one is 3% of the capacity rather than 1.6%. Both effects run the same way and the design is behind by 9%.

Against the oracle from the plate above, the threshold design recovers most but not all of what was available. At sixteen bits a key the whole filter is 0.0440%, the oracle lookup is 0.0478%, one block is 0.0954% and the threshold design is 0.0628%. Of the 0.0476 points between one block and the oracle, the threshold recovers 0.0326 — about two thirds.

Where the remaining third is #

The threshold design does not flatten the load as well as a second choice does, and the reason is asymmetry. A block that fills stops accepting keys for which it is the first choice. It cannot stop accepting keys for which it is the second, because a key rejected by its first block has nowhere else to go — the second block is the fallback and has no say. So the overflow arrives wherever it arrives, and a block can be pushed past its design load by keys it never agreed to take.

At sixteen bits a key that overflow is 7.5% of the keys, and it is the whole of the remaining spread. A design in which both blocks could refuse would need somewhere for a doubly-refused key to go, which is a third block or a rebuild — and the bits given to the wrong keys priced what a rebuild costs a filter that cannot read its own keys back.

There is a second reason the two designs cannot be made equal, and it is about information rather than about structure. The second choice measured what two choices do to a hash table’s maximum load — a logarithm becomes a logarithm of a logarithm — and that result depends on the insertion being allowed to look at both loads. The threshold design’s insertion looks at one load and a threshold that was set by earlier keys, which is strictly less information. Getting 56% of the balance from strictly less information, and spending the saving on halving the chances, is the trade this page is about. The remaining 44% is not recoverable by tuning; it is the part that needed the comparison.

How accurate a threshold has to be #

Two bits of threshold gets most of the benefit. The rate is 0.0745% at two bits against 0.0636% at eight and 0.0707% at sixteen, and every one of them is below the 0.0870% of one block with no threshold. The curve is flat because a threshold does not have to be accurate: it has to say roughly where a block stopped accepting, and a key on the wrong side of a coarse threshold is not lost. It goes to its second block, which is a valid home.

That is the property that makes the design practical. A table of 63 two-bit thresholds is 126 bits — sixteen bytes, a quarter of a cache line, for a filter of four kilobytes — and it would sit permanently in the first level of a real machine’s cache whatever the filter did. The eight-bit table measured above is 1.54% of the budget and 63 bytes, still inside one line. The threshold is not a structure. It is an annotation.

The line count, counted honestly #

A design that reads “one block and a threshold” reads two things, and the plates here count distinct 512-bit lines rather than blocks. Counted that way the threshold design reads 2.00 lines on an absent key against one block’s 1.00 and two blocks’ 1.99 — the same as the design it was built to improve on.

That is the honest number and it is not the whole story, because the two second reads are not the same object. The two-choice design’s second read is another 512-bit block of a four-kilobyte filter, chosen by a hash, and it is a different block on every lookup. The threshold design’s second read is the same sixteen to sixty-three bytes on every lookup of every key. One is a random access into a structure that does not fit in a first-level cache; the other is a line that would never leave it. One access, eight kilobytes is the page that says why those are not the same cost, and nothing in that line counter can tell them apart.

So the claim this page can support is the narrow one: at the same total bits and the same number of block reads, the threshold design’s rate is a third lower. The claim it cannot support without the machine model is that it is faster.

The stored-key side is where the two-choice design has its own answer. Reading the second block only when the first says no costs 1.99 lines on an absent key and 1.32 on a stored one, because a stored key is usually found in the first block; the threshold design reads 2.00 either way. On a workload that is mostly hits rather than mostly misses, that difference runs the other way — and a filter whose workload is mostly hits is a filter that is not doing very much. A filter allowed to be wrong is where the shape of a filter’s workload was first priced, and the assumption throughout has been that absent keys dominate.

The capacity, and what happens either side of it #

The design has one free parameter beyond the threshold’s width, and it turns into each of its neighbours at the two ends of it.

Set the capacity well above the mean load and the thresholds never fall: no key overflows, every key is in its first block, and the design is the one-choice filter — measured at 0.0962% against one block’s 0.0870%, the difference being the lost block. Set it well below and most keys are pushed into second blocks that have no threshold of their own and take whatever arrives, which reintroduces the spread the threshold was for: 34.7% overflow at a capacity of 0.7.

The optimum is at or just below the design load, and it is worth noticing that this is the one value that needs no tuning. A block’s capacity is the mean keys a block holds, which the filter’s own parameters give. There is no constant to choose.

What is settled and what is not #

Settled, on 2,048 keys in 512-bit blocks at the same total bits, over 24 filters and tens of thousands of absent queries a point: a blocked filter whose first block carries a threshold measures 0.386%, 0.0628%, 0.0123% and 0.0021% at 12, 16, 20 and 24 bits a key, against one block’s 0.417%, 0.0954%, 0.0231% and 0.0085% and the emptier-of-two design’s 0.640%, 0.100%, 0.0159% and 0.0029%. At eight bits a key it loses to one block, 2.545% against 2.338%.

Settled: it reads one block and one threshold line, where the two-choice design reads two blocks. Its load spread is 3.48 keys at sixteen bits a key against one block’s 5.72 and two blocks’ 1.75 — 56% of the way between them — and the gap is the 7.5% of keys that overflow into a second block which cannot refuse them.

Settled: the threshold’s width barely matters. Two bits gives 0.0745% and sixteen gives 0.0707%, both below the no-threshold 0.0870%, so the table is 0.38% of the budget if it needs to be.

Not settled:

Insertion in a stream. The construction needs the keys in increasing order of the ordering hash, so this is a filter built once from a known set. A design that accepts insertions in arrival order would have to raise thresholds rather than lower them, or keep a key’s position stable under a falling threshold, and neither is measured here.

Whether both blocks can refuse. The remaining spread is entirely the overflow into blocks that have no say. Giving the second block a threshold too needs a home for a doubly-refused key, and that is a different structure rather than a parameter.

Larger filters. Everything is 2,048 keys. The number of blocks grows with the key count at a fixed block width, so the table of thresholds grows in proportion and its share of the budget does not — but the tail of the load distribution does grow, and the block penalty with it, so the advantage over one block should widen. That is an argument and not a measurement.

The seed. Every filter here is built from a stated seed, and the ordering hash is one more function an adversary who knows it can invert. The adversary who knows the seed sets out what that costs in general; the specific hazard here is new, because $u(x)$ decides where a key is stored and is published in the thresholds. A key chosen so that its $u$ falls just below a full block’s threshold is a key placed deliberately, and a set of them is a block pushed past its load on purpose.

Deletion. None of these designs deletes. A filter that grows by moving a bit is the page where the fixed set stops being a fair assumption, and a threshold that has fallen cannot rise again without moving the keys it excluded.

Still open: the threshold as the only thing that is stored #

Every design on this page stores a threshold and a Bloom block, and the threshold is used only to choose the block. That is a strange division of labour: the threshold is already a statement about the key — $u(x)$ is below $\tau_a$ or it is not — and a filter is a structure for making statements about keys.

A filter made of thresholds alone is a known object under a different name. If the only thing stored for block $a$ is $\tau_a$, then “is $x$ in the set?” can be answered as “is $u(x)$ below $\tau_a$?” — which is wrong for most keys but wrong in a stated direction, and the rate is $\tau_a$ itself. A block that accepted a third of its candidates has a threshold of a third and a false-positive rate of a third: hopeless alone, and it costs two bits.

The measurement that follows asks what happens when those two bits are spent the other way. A filter of the same total bits with no thresholds and slightly wider blocks is the baseline the plates here already carry; the question is whether a third structure — the threshold used as a filter in its own right, ahead of the block, rejecting a fraction of absent keys before the block is read — pays for itself in lines rather than in bits. A key whose $u$ is above every threshold it could be under is absent for certain, and a lookup that can say so has answered without reading a block at all. What fraction of absent keys that catches, and whether it is worth the branch, is the number this page does not have.