For the Bluesky backend, we essentially do a SELECT * FROM blocks, mutes, list items, etc. every time one the processes starts, and add all the items to the bloom filter

If you’re constructing a bloom filter but not querying it yet, I think you can split that across many threads without contended locks or atomics, by having each thread have its own private bitmap and setting bits in that. Then when all threads have finished inserting items, you bitwise OR together all the bitmaps.

There’s also a real time atproto firehose consumer inserting items in to bloom filters (even during process startup), so there is a race condition if you’re not careful.

Add another bitmap for events that are showing up during process start and bitwise OR that in at the end, too.

Alternatively if you happen to have two bitmaps and no opportune time to merge them, you could keep querying both and returning 1 where either bitmap has a 1.

score 1 · canonical

The linked paper describes a “Standard Bloom Filter” as using k hash functions and a modulo.

If I was to build a simple Bloom filter:

• Size my bit array to a power of two so I can use a truncation / mask instead of a comparatively expensive modulo. (Obviously less flexible, but if you have a use case where the next lower power of two bit array size has too high a false positive rate and the next larger uses too much memory… your cache sizing is way more precise than anything I’ve worked on.)
• Shift and mask the output of one hash function to generate my “k” hashes. E.g. the lowest 16 bits are h1, next higher 16 are h2, etc. Can get three 21 bit numbers from a 64 but hash, and if that’s not enough, many hash functions can output 128 bits or more for no extra cost. For a good hash function, any positions should be as independent as different hash functions would be.

Perhaps those are mentioned later in the paper or in the references, but weren’t in the related work or the beginning of the design section before the math got too dense for me to skim on my phone.

While there might be other e.g. locality benefits to this scheme, making a “one hash Bloom filter” seems trivial. Is there something I’m missing where the simple scheme wouldn’t actually work?

score 1 · canonical