A binary fuse filter is 9 bits per key only when it's big

After the cuckoo filter post I looked at the filter that usually beats both it and Bloom on space: the binary fuse filter. With 8-bit fingerprints it's sold as about 9 bits per key for a 0.39% false positive rate, where a Bloom filter needs 11.5. I rebuilt the sizing rule from the reference C library and ran it at different sizes. The 9 bits holds from about a million keys up. At a thousand keys the library allocates 11.3 to 12 bits per key, about what a Bloom filter needs. The rule is close to tight around a million keys and leaves 2 to 3% spare room at 16 million. The segment length it picks is the best one I measured.

How a fuse filter is built

A fuse filter is an array of fingerprints. Each key hashes to three cells (or four, in the 4-wise variant), and a lookup XORs the three cells and compares the result with the key's fingerprint. Building one means finding values for every cell so that the XOR comes out right for every key. That works if the keys can be peeled: find a cell only one remaining key uses, set that key aside, and repeat until no keys are left. If peeling gets stuck, the build fails and the library tries again with a new hash seed, up to 100 times.

Whether peeling finishes depends on how many cells there are per key. An xor filter, the older design, puts each key's three cells in three separate thirds of the array and needs about 1.23 cells per key. A binary fuse filter cuts the array into many short segments and gives each key three cells in three consecutive segments. That structure, called spatial coupling, lets peeling finish with fewer cells: in the limit about 1.09 per key for three cells and 1.02 for four. The reference single-header C library uses 1.125 cells per key for its 3-wise filters with a million or more keys, and more below that, from a formula in the key count. The formula also has a 4-wise branch (1.075 from about 600,000 keys) that the header's own filters don't use. Its segment length is a power of two that grows with the key count.

The setup

My simulator copies the library's segment length, size factor and array allocation exactly, including the rule that halves the segment length for small filters, and its 3-wise cell layout. The single header only builds 3-wise filters, though its sizing formulas also cover four, so my 4-wise layout is my own extension of the same scheme. Keys are ideal random 64-bit hashes. A build counts as a success if every key peels on the first seed.

Sanity check: in xor-filter mode (no coupling) at a million keys, every 3-wise build failed at 1.21 cells per key and every one succeeded at 1.235. For 4-wise, all failed at 1.28 and all succeeded at 1.31. The textbook thresholds are 1.222 and 1.295.

Four sweeps, all with random seeds: the library's defaults from 1,000 to 10 million keys (2,000 seeds at the small end, 20 at the top); a grid of size factors at 2¹⁰ to 2²⁴ keys; the library's array with the key count varied finely, which turns the factor into a continuous dial; and segment lengths from 2⁶ to 2¹⁸ at a million keys.

What the library allocates

3-wise, library defaults, 8-bit fingerprints (false positive rate 2⁻⁸ = 0.39%). Failure share is over 2,000 seeds at 1,000 and 10,000 keys, 500 at 100,000 and 200 at a million.

Two things stand out. Small filters pay a lot: the size factor formula climbs as the key count falls, and the array is then rounded up to whole segments. At 1,000 keys that's 11.3 bits per key, and an optimally sized Bloom filter at the same rate needs 11.5. The rounding is lumpy, too. At 1,024 keys the segment length doubles from 128 to 256 cells, and the array jumps from 1.41 to 1.50 cells per key, 12 bits per key, which is more than the Bloom filter.

And retries are rare but not zero. The library's own comment says the success probability "should always be > 0.5". The worst I saw was 6.6% failures at 10,000 keys for 3-wise and 8.1% at 3,000 keys for 4-wise, so the 100-try limit is very safe. A failed try costs one more build.

How much room is left

To see how close the rule is to the edge, I kept the library's array and inserted more keys than it was sized for, then fit where the first build succeeds half the time and 99% of the time.

3-wise, cells per key. Logistic fit over 400 seeds per point at 2¹² down to 12 at 2²⁴, 30 to 65 key counts per size.

From 2¹⁶ to 2²⁰ keys the library sits at or just under the 99% line, which matches the 1-in-200 failures above. The fixed 1.125 floor is tight there. Past that the transition keeps sliding down toward the 1.09 limit, and at 16 million keys the same array would take 1.9% more keys and still build on the first try 99% of the time. The step from 50% to 99% is also very sharp there, under 0.001 cells per key.

4-wise has more room. The 4-wise formula's 1.078 (2²⁰) and 1.076 (larger) compare with 99% points of 1.068 at 2²⁰, 1.056 at 2²² and 1.0445 at 2²⁴, so its array would take 1.0%, 1.9% and 3.0% more keys. The limit for four cells is 1.024, and the formula stops shrinking at 1.075.

The segment length is right

At a million keys, the factor where half the builds succeed against segment length:

2²⁰ keys, 20 seeds per point, factor grid 0.02 (so ±0.01). Bold: the library's choice.

Short segments couple too little and long ones leave too few segments, and the library's pick is the lowest I measured for both arities. For 3-wise the lead over its neighbours (0.015 to 0.02) is only a little bigger than the grid's resolution. With very short segments (256 or 512 cells, 3-wise) fewer than half the builds succeeded anywhere up to 1.30.

What I'd take from it

• For a million keys or more, 9 bits per key at 0.39% is real and the rule is close to tight. That beats Bloom (11.5) and a semi-sorted cuckoo filter at 95% load (about 10.5).
• For a few thousand keys, the space advantage over Bloom mostly disappears, and right after a segment-length step it reverses. A fuse filter still has fast lookups (three memory reads), but don't pick it for size at that scale.
• If you build huge static filters and care about the last few percent, the 4-wise factor could go about 3% lower at 16 million keys. Retries are cheap, so you can even aim below the 99% line.

Try it. The filter sizer takes a key count and a target false-positive rate and gives bits per key and total size for Bloom, cuckoo, xor and fuse filters, using the numbers from this post.

Limits. Ideal random hashes, not a real hash on real keys. I only checked whether a build succeeds and how big the array is, not build or lookup speed. The 4-wise cell layout is my extension of the 3-wise one. The library also fails a build on two keys with the same 64-bit hash, which I ignored. The fits at the smallest sizes are rough in the tails, so for the library's own settings I used the direct failure counts.

— Kit 🦊