Skip to content

Certainly Absent

Edit source

A filter that says no in three reads, and is wrong about yes once in 256.

Part 32 of 38ofFamiliars
  1. 1Session Zero
  2. 2Rolling for a Name
  3. 3The Haunted Handler
  4. 4The Sparse Wheel
  5. 5The Fork in the Path
  6. 6The Planet as a Prefix
  7. 7The Long Division
  8. 8The Line You Usually Cancel
  9. 9Sixteen Bytes Too Far
  10. 10Packing a UUID
  11. 11Bytes You Can Type
  12. 12The Shunting Yard
  13. 13Interchangeable Parts
  14. 14One Loop Per Core
  15. 15The Seam
  16. 16Append Only
  17. 17Who Owns the Tree
  18. 18Down the Flume
  19. 19The Syscalls That Lie
  20. 20Asking the Machine
  21. 21The Earth Is Not a Ball
  22. 22Smith and Schmidt
  23. 23Many Ways to Be Similar
  24. 24Built to Disappear
  25. 25Sometimes a Mutex Is Right
  26. 26Work, Not Threads
  27. 27Before the Program Runs
  28. 28No Collisions, Ever
  29. 29The Names Enums Throw Away
  30. 30The Bag of Holding
  31. 31A Map of Blocks
  32. 32Certainly Absent
  33. 33A Tree Made of Types
  34. 34Everything but the Views
  35. 35Who Owns the Wheel
  36. 36A Guest on the Loop
  37. 37Acknowledged Means Durable
  38. 38Sorted as Bytes

Part of Familiars: the small, sharp libraries around Xapiand. This one is new, written for the engine underneath it, and it stands at the door of every dictionary: fusefilter.

Picture a library with fifty reading rooms, each with its own card catalog. You want one book, and it is in exactly one room. What you want is a cheap sign on each door that says either “definitely not here” or “maybe here, go check”.

A search engine has the same problem. Its data lives in many segments, chunks of the index written once and never changed, and each segment has a dictionary, a sorted list of the keys it holds. Looking up a document asks segment after segment, and in all but one the answer is no. Reading a dictionary to learn that costs real work every time. So in front of each one, the engine puts a filter: a tiny summary of the keys that answers “certainly not” (always true) or “maybe” (true except about one time in 256). Only a maybe goes on to the dictionary.

The classic sign on the door is a Bloom filter. It is a long row of bits; each key flips a handful of them on, and a query checks whether all of its bits are on. It accepts new keys at any time, and that flexibility costs space. To be wrong only 1 time in 256, a Bloom filter needs 11.54 bits per key (that is what Boost.Bloom sizes it to), when the theoretical floor is 8.

A segment never changes, so the engine does not need that flexibility. Thomas Mueller Graf and Daniel Lemire designed a filter for exactly this case, first the xor filter and then its refinement in “Binary Fuse Filters: Fast and Smaller Than Xor Filters” (2022). The idea below is theirs; fusefilter is my C++ version of it.

The filter is an array of bytes. Each key is scrambled by a hash function (a recipe that turns a key into a random-looking 64-bit number), and that number picks three positions in the array plus one byte called the key’s fingerprint. The array is filled so that, for every stored key, its three bytes combined with XOR (a bitwise “add without carrying”) give exactly its fingerprint.

Checking a key means reading three bytes and comparing. A stored key always matches, so the filter never says “not here” about a key that is there. A missing key reads three bytes that were set for other keys, and they happen to match its fingerprint by pure chance: one time in 256, or 0.39%. The array has about 1.125 bytes per key, which is where the 9 bits per key come from.

Filling that array is the clever part, and it works like solving a puzzle from its easiest square. Find a byte that only one key uses. That key can be settled last: whatever its other two bytes end up holding, this one is free to make the sum come out right. Set the key aside, which may leave another byte with only one key, and keep going. Like untying a knot by always pulling the loose end, this is called peeling. If every key comes off, put them back in reverse order, setting each key’s free byte as you go.

Sometimes a few keys tangle into a knot with no loose end. Then the build tries again with a different seed, a number mixed into the hash so every key lands somewhere new.

The first surprise was a set of 11,509 perfectly ordinary random keys that refused to build. At that size, the table the paper’s formula picks was just a little too tight, and all 100 seeds failed. The fix gives the table one more stretch of bytes after 100 failures, up to 8 times.

The second was duplicates. Two copies of the same key land on the same three bytes, so neither ever becomes a loose end, and no seed can ever work. The first version sorted every key up front to remove copies. Later, to cut the engine’s memory use during merges, the build learned to take over the caller’s list and sort it in place instead of copying it, which dropped its working memory from about 46 to 24 bytes per key.

Staring at that sort exposed the real waste: most sets have no duplicates, and they paid for a full sort to find none. The build now peels the keys as given and only looks for copies if the first attempt fails, checking just the few keys left in the knot, the only place a copy can hide. That, plus reading memory in a friendlier order, made the build 3.9 times faster: 37.2 to 9.6 nanoseconds per key at a million keys on an Apple M4 Pro.

Here is fusefilter beside the paper authors’ own C implementation (xor_singleheader) and a Bloom filter tuned to the same error rate, at one million random keys on an Apple M4 Pro. Times are in nanoseconds, lookups for a key that is present; fusefilter matches the authors on lookups and uses 22% fewer bits than the Bloom filter.

FilterBits per keyWrong “maybe”Build, per keyLookup
fusefilter9.040.39%9.71.6
xor_singleheader9.040.39%18.81.5
Bloom filter11.540.39%6.24.2

The Bloom filter builds faster, since adding a key is one quick step with no puzzle to solve. For a segment built once and read millions of times, that is a fine trade. Every row, a second machine and ten million keys are in the repo’s comparators page.

The tests check that no stored key is ever reported missing at sizes from zero up to a million keys, and that the error rate stays near 1 in 256. A second test builds sets in every awkward shape (half duplicates, all keys equal, keys picked to break a seed) and checks each against the old, slower build: the same seed and size, no missing key, and the same bytes whatever order the keys came in. A script breaks the build in 16 deliberate ways and requires a test to catch each one. A fuzzer (a tool that generates random input) fed 227 million byte strings to the loader, and every one was either read safely or rejected.

Reach for fusefilter in front of a slow lookup over a set that never changes: index segments, on-disk tables, anything written once and asked about often, mostly for things that are not there. It is one header file with no dependencies. Skip it if your set changes, since every change means a rebuild (a Bloom filter takes additions), or if you need fewer than 1 in 256 wrong answers.