一哈希布隆过滤器优化Bluesky后端性能

Bluesky团队开发了基于单一哈希函数的布隆过滤器实现gloom，已在后端生产环境运行9个月1。该实现通过缓存对齐和原子指令等优化技术，将查询性能提升至单次缓存失误的水平1。

一哈希布隆过滤器基于Lu等人的研究论文，采用k个互质大小的分区数组，通过单次哈希运算获得k个位置1。gloom实现通过64字节块大小匹配CPU缓存行，并使用unsafe确保缓存对齐，保证最坏情况下仅一次缓存失误1。此外，ShardedAtomicFilter将写操作分散到多个过滤器分片，减少核心间的数据竞争1。

该优化方案带来了显著的性能改进。Bluesky后端布隆过滤器正命中率约为1%，意味着99%的时间可以完全跳过数据库查询1。基于互斥锁的bits-and-blooms库实现导致单次部署耗时90分钟，而采用原子指令的atomic-bloom实现将其降低至15分钟1。

An optimized bloom filter implementation called gloom has been running in production on Bluesky's backend for nine months, demonstrating significant performance improvements over traditional approaches 1. The implementation achieves a positive match rate of approximately 1% on Bluesky's backend bloom filters, meaning the system can skip database queries entirely 99% of the time 1.

The gloom implementation addresses both throughput and latency challenges by employing single-hash optimization based on research by Lu et al. 1. Rather than using multiple independent hash functions, the approach utilizes k partitioned arrays of coprime sizes, deriving all k bit positions from a single hash computation 1. The implementation aligns 64-byte blocks to match CPU cache line sizes and leverages unsafe code to guarantee cache alignment, ensuring at most one cache miss in the worst case 1. Additionally, ShardedAtomicFilter distributes write operations across multiple filter shards to reduce inter-core contention 1.

Performance gains compared to existing solutions are substantial. The bits-and-blooms library, which relies on mutex locks, requires 90 minutes for a single deployment, while the atomic-bloom implementation reduces this to 15 minutes 1.