Note: as always, all my public writing is written by hand by me. Overview A bloom filter is a probabilistic data structure that allows you to quickly and cheaply answer the question "is key X in this set?" with either "definitely not" or "probably". You pick a false positive rate that is acceptable for your workload and hardware, add keys to the set, and check for their existence later on.
Bloom filters use a small amount of memory compared to the cardinality of the set, and are computationally very cheap. For these reasons, they're frequently used in high performance data systems. For example, a database might keep an in-memory bloom filter and check it before actually going to disk when looking up rows.
This saves substantial amounts of very slow disk IO. We also use them all over the place in the Bluesky backend. They allow us to save millions of queries per second against our Scylla database when looking up blocks, mutes, labels, and more.
For instance, we can often answer the question "does user X block user Y" without even hitting the database. Here's the last several days of some of our bloom filter positive hit rates: The above yellow line has a roughly 1% positive rate, which means that 99% of the time, we can completely skip querying our database. This has been critical in our ability to scale the site and operate the site cheaply.
Traditional Bloom Filters A bloom filter is an array of bits and k hash functions. You choose the size of the array and k before hand, and want to right-size it to your workload to achieve a specific false positive rate. To add a key to the set, run it through the k hash functions and set the bits at each of those locations.
To check if a a key is in the set, hash it k times and check each resulting location in the bit array. If any bits are zero, the key was never added. If all bits are set to one, it might be in the set.
Double Hashing 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! One Hash Can we go further? For Bluesky, the answer is no. Contention was our original problem, not the number of hash functions or other factors, thus by Amdahl's Law we did not receive any furthe...
Source: Hacker News · Summarized by HeadlinesBriefing