BloomCraft: twelve Bloom filter variants under one API, looking for feedback

Hey y'all, I published BloomCraft and wanted to share it here and get some eyes on the design before it goes much further.

Backstory (real quick): I started writing a small tech blog back in November and one of the things I wanted to cover was a classic CS paper. I ended up on Burton Bloom's original 1970 paper and I just got HOOKED(omg, it was interesting hehe), I'd never actually used a Bloom filter before that, didn't know much about them beyond the name either. One paper led to another (Kirsch-Mitzenmacher, the scalable filter paper, Lemire's range reduction stuff, to name a few) and at one point I was like, let's build this, it looks easy. Also, I was like, building one is better than just writing about them.
BloomCraft is what came out of this rabbit hole, 12 variants covering the different trade-offs those papers described, all behind one consistent BloomFilter trait.

A quick tour of what's in there:

• StandardBloomFilter - the classic space-optimal filter, AtomicU64 backed, supports union/intersect
• CountingBloomFilter - lets you delete stuff via per-slot counters, costs you 4-16x the memory though
• ScalableBloomFilter - auto-grows when it fills up, keeps a bounded FPR across the chain of slices
• PartitionedBloomFilter - splits the bit array so each hash stays cache-local
• RegisterBlockedBloomFilter - 512-bit register blocks, one cache-line touch per query, costs you some FPR for it
• TreeBloomFilter - hierarchical bins, good if you need to know where something might be, not just yes/no
• ShardedBloomFilter / StripedBloomFilter - two different takes on high-concurrency writes without a global lock
• AtomicScalableBloomFilter / AtomicPartitionedBloomFilter - lock-free versions of the two above, sitting behind a concurrent feature flag
• ClassicBitsFilter / ClassicHashFilter - implementations of Bloom's original 1970 paper, kept in mostly for reference and teaching, not meant for production (also because it felt wrong not to include it)

On concurrency specifically, there are three distinct models depending on the filter: plain &mut self with your own external lock, &self with atomic CAS operations directly on the bit words, and &self through interior mutability (sharding or striping). I didn't want to slap a Mutex onto everything and call it done, since the right locking strategy really depends on your read/write mix.

Config goes through type-state builders, so orgetting something like the expected item count blows up at compile time:

let (filter, meta) = StandardBloomFilterBuilder::new()
    .expected_items(100_000)
    .false_positive_rate(0.001)
    .hash_strategy(HashStrategy::EnhancedDouble)
    .build_with_metadata::<String>()?;

Hashing is pluggable too, SipHash by default, WyHash or XXH3 behind feature flags if you want the speed and don't need DoS resistance.

I benchmarked all twelve against each other (Criterion, single-threaded and concurrent runs, memory, tail latency, everything in between). I found: PartitionedBloomFilter beats StandardBloomFilter on insert throughput up to about a million items purely from staying cache-local, and StripedBloomFilter didn't scale at all past a couple of threads on my machine, RwLock stripe contention just ate whatever gains striping was supposed to give me. AtomicPartitionedBloomFilter actually got slower going from 1 to 2 threads, which I guess is a known anti-pattern (cache-line ping-pong on shared atomic words) but still weird to watch happen in real time.

Any unsafe in there is limited to SIMD intrinsics and manual allocation in the partitioned filter, trying to keep it that way, the public API itself is fully safe.

It's still early (0.1, MSRV 1.73) so I'd really appreciate feedback on the trait hierarchy and whether the whole API makes sense before I lock myself into stuff for a 1.0. If you've actually used Bloom filters for real and I'm missing a variant or trade-off, or something about the API just feels off, please lemme know.

• Crate: crates.io: Rust Package Registry
• Docs: bloomcraft - Rust
• Repo: GitHub - ZaudRehman/bloomcraft: Comprehensive probabilistic data structures library in Rust with 11+ filter variants, pluggable hash system, and SIMD acceleration. · GitHub

Happy to nerd out about any of the internals if anyone's curious.

P.S This is the logo:

1 post - 1 participant

Read full topic