When Bloom filters don't bloom

What this post added

This post details the author's experience using Bloom filters for large-scale data deduplication, addressing performance issues encountered with traditional tools like 'sort' and 'uniq'. It explains the principles of Bloom filters, their parameters (n, m, k, p), and the trade-offs involved. The author developed a tool 'mmuniq-bloom' and encountered performance bottlenecks due to random memory access and cache misses, even with an optimized Bloom filter implementation. The analysis highlights the significant cost of memory fetches and the impact of cache misses on performance, suggesting that reducing memory accesses is crucial for optimizing such data structures.