Bloom filters are probabilistic data structures used to determine if an item exists within a set. They are highly efficient for high-performance systems because they use minimal memory and provide a 'definitely not' or 'probably' answer, allowing systems to skip expensive operations like disk I/O. For example, the Bluesky backend uses them to filter millions of queries per second against its Scylla database, successfully skipping database hits for approximately 99% of requests.
This figure illustrates the fundamental logic of Bloom filters where a single zero bit provides a definitive 'not present' result.
This figure demonstrates the probabilistic nature of Bloom filters, where a set of 'one' bits suggests an item might be present.
Traditional Bloom filters rely on an array of bits and $k$ different hash functions. To check for a key, the system hashes the key $k$ times and checks the corresponding bit locations. While effective, computing multiple independent hashes can be computationally expensive. To mitigate this, developers often use 'double hashing,' where two hashes are used to derive $k$ locations. However, Calabro notes that even this can lead to performance bottlenecks, such as mutex contention in multi-threaded environments. Bluesky addressed this by moving to an atomic-based implementation, which replaced mutexes with atomic CPU instructions, significantly reducing deployment times from 90 minutes to 15 minutes.
To further optimize, Calabro implemented a 'One Hash Bloom Filter' (OHBF) based on research by Lu et al. This method splits a large bit array into $k$ partitions of pairwise coprime sizes. A single hash of a key is used to determine a bit position in each partition. This approach eliminates the need for multiple hash calculations. The implementation also incorporates low-level optimizations, such as aligning 64-byte blocks to CPU cache lines to ensure that lookups result in at most one cache miss. While this method offers significant speedups, it involves a trade-off in space efficiency; partitioning can lead to uneven occupancy across segments, potentially requiring a larger overall filter size to maintain a low false-positive rate.
This diagram explains the One Hash Bloom Filter (OHBF) method of using a single hash to determine bit positions across coprime partitions.
One final optimization involves replacing the modulo operation—which requires an expensive division instruction—with a single multiplication (MUL) instruction to select the block to check. By combining these techniques—one-hash logic, cache alignment, and multiplication-based indexing—the system achieves high-throughput lookups that minimize both CPU cycles and memory latency. The OHBF implementation is currently live in the Bluesky backend and its high-performance sync service, Jetstream.