One Hash Bloom Filters

This describes a practical exploration of bloom filters focused on reducing CPU and contention overhead in high-throughput systems. It starts from standard bloom filters and the common double-hashing optimization (Kirsch & Mitzenmacher), then recounts a real-world production problem: a mutex-protected bloom library caused severe startup contention, and replacing it with an atomic implementation cut deploy time from about 90 minutes to 15 while maintaining a ~1% positive rate that avoids millions of database queries. That work underlines that contention, not hashing cost, was the dominant bottleneck for this deployment.

The core innovation examined is a one-hash bloom filter (OHBF) technique: split the bit array into k partitions with pairwise coprime sizes, compute a single 128-bit hash, and derive one bit index per partition as hash % size_p. An implementation (gloom) uses xxh3 128-bit hashing (high 64 bits to pick a block, low 64 for positions), arranges 64-byte cache-aligned blocks via controlled allocation and unsafe pointers to guarantee a single cache miss, applies Daniel Lemire’s multiply trick to avoid division, and offers sharded atomic filters to reduce write contention. Deployed in production services for nine months, OHBF proved practical, though further speedups were limited by Amdahl’s law once contention was addressed.