Bloom Filter Membership Testing

A Bloom filter answers "have I seen this key?" in a fixed amount of memory with two possible answers: definitely not or probably yes. It never gives false negatives. The false-positive rate (FPR) is something you choose at design time and pay for in bits.

Where it shows up

• LSM storage engines (RocksDB, Cassandra, HBase, LevelDB): each SSTable has a filter, so a point read skips files that can't contain the key and avoids a disk seek.
• Caches and CDNs: "one-hit-wonder" filters admit an object into cache only on its second request (Akamai's Maggs & Sitaraman, 2015).
• Recommendation / feed dedup: "has this user already seen this post?" (see the lesson seen-filtering-bloom-vs-exact-sets).
• Distributed joins: Spark and Impala runtime filters send a small Bloom filter from the build side to the probe side so non-matching rows are dropped early.

Design

add("user:42")
  h1 = murmur3(bytes, seedA)          h2 = murmur3(bytes, seedB) | 1
  g_i = (h1 + i*h2) mod m   for i = 0..k-1       <- Kirsch–Mitzenmacher
  set bit g_i in Uint8Array               byte = g >> 3, mask = 1 << (g & 7)
has(x): all k bits set?  -> "probably"   any bit clear? -> "definitely not"

Sizing. For n expected items and target FPR p:

m = ceil( -n * ln(p) / (ln 2)^2 )      bits
k = round( (m / n) * ln 2 )            hash functions
FPR(n) = (1 - e^(-k n / m))^k          after inserting n distinct items

At the optimal k about half the bits are set. Each 10x reduction in p costs log2(10)/ln 2 ≈ 4.79 more bits per item. For 1% that works out to 9.59 bits/item and k = 7. The demo checks these numbers.

Double hashing. Kirsch & Mitzenmacher (2006) showed that g_i = h1 + i*h2 gives the same asymptotic FPR as k independent hashes, so you only need two hash computations per operation. h2 is forced odd so the stride is never zero. If it were, all k probes would land on one bit.

Invariants.

1. No false negatives. A bit is never cleared in the plain filter.
2. Bits past m in the last byte are always zero. deserialize checks this.
3. union only works for filters with the same (m, k) and the same hash seeds. It is a bitwise OR, and the result is exactly the filter you would get by building from both sets at once.

Measured vs theoretical. expectedFpr() uses the formula above with the insert count. currentFpr() uses the actual fill ratio (X/m)^k. The demo checks both against 200k real non-member probes. They agree to within a few percent of each other.

Serialization. A 16-byte big-endian header (magic "BLM1" | k | m | count) followed by the raw bit array. This is enough to mmap or ship over the wire. Hash seeds are fixed constants, so any reader using this module computes the same positions.

Counting variant. CountingBloomFilter replaces each bit with a 4-bit counter, packed two per byte, to support remove(). Fan et al. ("Summary Cache", 2000) showed that 4 bits overflow with negligible probability at optimal load. A counter that reaches 15 becomes sticky and is never decremented, because its true value is unknown. toBloomFilter() collapses it to a plain filter for read-only consumers.

Complexity

Failure modes and trade-offs

• Overfilling. At 2x design load a 1% filter gets about 16% FPR. At 4x it gets about 68% (see demo step 3). The filter cannot grow, so rebuild it or use a scalable Bloom filter: a chain of filters with tightening FPRs.
• Counting-filter misuse. Calling remove(x) for an x that was never added, but tests positive, decrements counters that belong to other keys and introduces false negatives. This implementation refuses removes that test negative, but it cannot detect a false-positive remove. Only remove keys you know you inserted.
• Cache misses. Probes are random across m bits, so each lookup can touch k cache lines. Blocked and cache-local filters (RocksDB's FastLocalBloom) keep all k probes in one 64-byte line and pay a small FPR penalty.
• Hash quality. A weak or adversarially known hash lets attackers craft keys that collide. Use a keyed hash (e.g. SipHash) if inputs are hostile.
• Deletes vs space. Counting filters cost 4x the memory. Cuckoo filters support deletes at about the same space as a Bloom filter when FPR < ~3%.

How production systems do it

• Cassandra: one Bloom filter per SSTable, kept off-heap. It is tuned per table with bloom_filter_fp_chance (default 0.01, and 0.1 for LeveledCompactionStrategy). It uses Murmur3 128-bit with the same h1 + i*h2 double hashing.
• RocksDB: per-SST "full" filters, or partitioned filters for very large files. Configured with bits_per_key (commonly 10, about 1% FPR). format_version=5 introduced the cache-local FastLocalBloom. The Ribbon filter (NewRibbonFilterPolicy) saves about 30% of the space for more build CPU.
• Google Guava: BloomFilter.create(funnel, n, p) uses the same m/k formulas and the MURMUR128_MITZ_64 strategy (Kirsch–Mitzenmacher on 128-bit Murmur3).
• Redis Stack (RedisBloom): BF.RESERVE key error_rate capacity [EXPANSION n] creates a scalable Bloom filter that stacks sub-filters as it fills. CF.* commands provide cuckoo filters with delete.
• HBase: per-HFile ROW or ROWCOL Bloom filters, chosen per column family.

Extension exercises

1. Implement a blocked Bloom filter. Pick one 512-bit block with h1, then set all k bits inside it. Measure the FPR penalty against this filter at 8, 10 and 16 bits/item.
2. Build a scalable Bloom filter (Almeida et al. 2007). When the fill ratio passes 50%, add a new filter with double the capacity and FPR multiplied by r = 0.5. Check that the compound FPR stays below the target.
3. Replace MurmurHash3 with keyed SipHash-2-4 via crypto.createHmac or a hand implementation, and explain which attack this prevents.
4. Add a BloomFilter.intersectionEstimate(a, b) using |A∩B| ≈ |A| + |B| - |A∪B| from the cardinality estimator, and test how accurate it is.
5. Implement a cuckoo filter with the same interface and compare bits/item at p = 0.1%, 1% and 3%.