One Hash Bloom Filters

While much cheaper than going to disk, computing k independent hashes per key is still a bit expensive for very high performance systems.

In 2008, Kirsch and Mitzenmacher wrote a paper demonstrating that two hashes can get you the same output. The math is far over my head, but if you derive the i-th location as (hash_1 + i*hash_2) % n, then the false positive rate is effectively the same as using k independent hashes. Phew!

bits-and-blooms/bloom maintained by Daniel Lemire (a huge inspiration of mine, you should buy his book) is a fantastic double hash bloom filter implementation written in go. It runs 128-bit murmur3 twice to get four 64-bit values, then combines them to produce all k bit locations. We used this in production at Bluesky for a long time.

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. 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.

The problem with the bits-and-blooms library is that it's not internally thread-safe, so we needed to wrap all bloom filter access in a mutex lest we suffer a data race. pprof showed that mutex contention was actually the bottleneck in launching the process. A single deploy used to take 90 minutes to roll out fully because of this!

So my colleague Jasmine forked the library and created atomic-bloom, which uses atomic CPU instructions to do the same logic, but safely and without mutexes. This led to substantially less contention and was massively faster than the mutex-based approach. Our deploys dropped from 90 minutes to about 15, which enabled us to ship faster and with greater confidence. Awesome!