Loading...
Loading...
Probabilistic testing of set membership to save database lookups
Fanout 3 converges 3,000 gossiping nodes in about 6 seconds, yet every Cassandra read still walks 10 SSTables to prove a key is absent. Your read path checks Cassandra, a wide-column store, for every user key. Most keys do not exist, but the store must read SSTables, meaning immutable sorted files on disk, to prove absence. A Bloom filter, meaning a bit array plus hashes that answers definitely-absent or probably-present, sits in RAM and rejects misses in microseconds. It never says absent when the item exists, which is the no-false-negatives guarantee, and sometimes says present when it does not, which is the tunable false-positive rate. Like a restaurant host who knows instantly which names are not on tonight's list but double-checks the book for names that might be, a no skips the store while a yes always confirms.
Guarantee: No false negatives, possible false positives. If filter says no, skip the store. If it says yes, go to store and confirm.
The naive exact set stores every key, costing gigabytes plus garbage collection for miss-heavy workloads. The Bloom fix stores m bits starting zero: hashing, meaning mapping a key to positions deterministically, each item with k functions yields k positions set to 1, and re-adding changes nothing. Checking hashes identically: any 0 means definitely absent since no insert touched it, while all 1s mean probably present pending store confirmation.
m bits, all 0.k functions → k positions.m=10 bits: 0 0 0 0 0 0 0 0 0 0
add "ada" → h1=2 h2=5 h3=8
0 0 1 0 0 1 0 0 1 0k functions.check "bob" → h=2,5,9 bits at 2,5 =1 but 9=0 → definitely not in set → skip DB
For n items, m bits, k hashes, optimal k equals (m/n) times ln 2 and p, meaning false-positive probability, approximates (1 minus e to the minus kn/m) to the k. The naive sizing guesses bits and hopes; the working sizing inverts the formula for target p with m equal to minus n ln(p) over (ln 2) squared. More bits per item lowers p, more hashes lower p only to the optimum before extra sets fill the filter faster, and fuller filters raise p, so size for lifetime maximum n rather than today.
optimal k = (m/n) * ln 2
p ≈ (1 - e^{-kn/m})^k
Example: n=1M, want p=1% → m ≈ 9.6 * n ≈ 9.6M bits ≈ 1.2 MB, k ≈ 7Classic Bloom fits cache-before-database and SSTable skipping where deletes never happen. Counting Bloom, meaning counters replacing bits, adds deletes near 4x memory with overflow risk past small counters. Cuckoo filters, meaning fingerprint tables supporting deletion, delete natively with fewer bits near p equal to 1%. Never force classic Bloom onto revocation workloads: clearing shared bits corrupts unrelated keys.
| Structure | Delete? | Error | Use when |
|---|---|---|---|
| Bloom | No | Tunable false positive | Cache-before-DB, SSTable skip |
| Counting Bloom | Yes (counter) | Same p, 4× memory | Membership with deletes |
| Cuckoo filter | Yes | Similar, supports delete, lower bits for p≈1% | Modern replacement if deletes needed |
A million users at 1% false positives must fit RAM, and the arithmetic is one division plus one multiplication. Natural log of 0.01 equals minus 4.605, divided by (ln 2) squared near 0.4804, gives 9.585 bits per item, hence 9.585M bits or 1.2MB with k near 6.6 rounded to 7 hashes. The ladder memorizes as 9.6 bits for 1% and 14.4 for 0.1%: 10M users near 12MB at 1%, 100M URLs near 180MB at 0.1%.
Given: n items, target p. m = -n * ln(p) / (ln 2)^2, k = (m/n) * ln 2
Rule of thumb: m/n ≈ 9.6 bits for p=1%, ≈ 14.4 bits for p=0.1%
Worked: n = 1,000,000, p = 0.01
ln(0.01) = -4.605 → m = 1M × 4.605 / 0.4804 ≈ 9,585,000 bits
m ≈ 9.6M bits ≈ 1.2 MB, k = 9.585 × 0.693 ≈ 6.6 → 7 hashes
Check: 10M users at p=1% → ~12MB. 100M URLs at p=0.1% → ~180MB; still RAM.
Too few bits (m/n=4, k=3): p ≈ (1-e^{-3/4})^3 ≈ (0.53)^3 ≈ 15%; useless.
Too many hashes past optimum: you set extra bits per insert → fills faster → p rises.Production shortcut: hash once with a 64-bit function such as xxHash or Murmur, both fast non-cryptographic hashes, and derive k positions by double-hashing rather than k independent calls. Same distribution, one pass over the key.
A filter sized for a million keys hums at target, then six months later holds four million in identical bits and its rate quietly tripled, so every maybe-present hits disk and the I/O saver causes I/O. Filters saturate rather than age: bits-set ratio past 50% degrades steeply. Size for lifetime maximum or shard by time with one filter per day, rebuild on compaction, and graduate to Cuckoo or Xor where deletes or minimal static memory govern.
RedisBloom, now Redis query-engine Bloom/Cuckoo commands in the in-memory store, sizes with BF.RESERVE and scales with BF.SCANDUMP on growth. A filter outgrowing its reservation rebuilds rather than resizing in place, so set capacity plus error rate at creation and monitor expansion.
A Cassandra read for a missing key walks partition-key cache, then one Bloom per SSTable, then indexes, then at most one data read per false positive. With 10 SSTables at 1% each, expected false hits equal 10 times 0.01 or 0.1 disk reads per miss versus 10 without filters: roughly 100x fewer seeks on miss-heavy workloads such as caches, timelines, and graphs. Chrome Safe Browsing mirrors the shape: servers hold full malicious-URL lists and ship prefix Blooms refreshed every 30min, browsers proceed on miss and ask for full hashes only on hit.
GET missing key, 10 SSTables, p=1% per SSTable filter: no filters: 10 SSTable index+data reads → ~10 disk seeks per miss with Bloom: expected false hits = 10 × 0.01 = 0.1 → ~0.1 disk reads per miss savings: ~100x fewer seeks on miss-heavy workloads (caches, timelines, graphs) Chrome Safe Browsing mirror image: server holds full malicious-URL list → ships Bloom of 32-bit prefixes to browser browser: prefix miss → proceed (no network). prefix hit → ask server for full hashes. filter update every ~30min replaces the whole structure; deletes via rebuild.
Each SSTable sizes its filter for its own key count at creation, so total memory tracks total keys. Rebuilding on compaction keeps the rate honest as data churns; a filter inherited across three compactions sizes for a dataset that no longer exists.
Revoked tokens or removed URLs needing deletes suit Cuckoo natively with fewer bits near p equal to 1%. Static shipped blocklists suit Xor filters, meaning immutable minimal-memory structures built once, reading 30% smaller. Classic Bloom stays default only where neither constraint bites.
Formulas assume uniform hashes and exactly n keys, while production has neither. Measure empirically: insert the real sample, probe 100k holdout keys provably absent such as freshly minted UUIDs, meaning random identifiers, then divide hits by probes. A 1% design reading 0.8 to 1.2% is healthy; 3 to 5% means oversubscription from doubled n or hash clustering. Track bits-set ratio and rebuild before 50% full. Never probe inserted keys to test, since true positives reveal nothing about false positives.
Canary protocol: holdout: 100k keys never inserted → probe all → hits/100k = empirical p healthy: empirical ≈ theoretical (1% design → 0.8–1.2% measured) sick: empirical 3–5% → set outgrew sizing (n doubled?) or hash clustering alarm: track bits-set ratio; at >50% full the rate degrades steeply; rebuild BEFORE. Never probe with inserted keys to "test"; true positives tell you nothing about p. canary keys must be absent by construction (UUIDs minted for the test, then discarded).
Asking whether a password sits in a 4-billion-entry breach list cannot ship the list to browsers nor send the password anywhere. K-anonymity prefix ranges, meaning sending only the first 5 hash characters so the server cannot tell which password you typed, solve it: hash locally, send the prefix, receive all matching suffixes near 4k entries or 150KB, compare locally. The anonymity set near 4k passwords sharing a prefix bounds server knowledge. Rejected alternative: ship a Bloom of the full corpus to every browser. At p equal to 0.1% over 4B entries it needs 720MB, too fat for bundles but fine inline, which is why browsers use prefix APIs and servers use filters.
breach corpus: 4B SHA-1 hashes → 5-char prefix = 1M buckets ≈ 4k suffixes each client sends "5BAA6" → server returns ~4k suffixes (~150KB) → local match? anonymity set ≈ 4k passwords share the prefix; server cannot tell which you typed Bloom alternative on-device: 4B entries at p=0.1% ≈ 720MB; too fat for the bundle, so the prefix-range API wins for browsers; a server-side Bloom wins for inline checks.
Tenants share one Bloom filter sized for their combined keys, then one tenant ingests 10x its allotment and the shared false-positive rate triples for everyone. The naive response sizes bigger next quarter, which the same tenant outgrows again. The working isolation shards filters by tenant or by time, so each tenant's growth degrades only its own rate, with per-filter canaries, meaning holdout probes measuring empirical false positives, paging the owner rather than the platform. Cassandra's per-SSTable filters, meaning one filter per immutable sorted file, already follow this shape: each file's filter sizes to its own keys, so one huge SSTable cannot poison its neighbors' rates.
Shared: 10 tenants × 1M keys, m sized 96M bits → p=1% for all tenant X ingests 10M (10x): shared n=19M in 96M bits → m/n≈5 → p≈9% for EVERYONE sharded: 10 filters × 9.6M bits each → X degrades to ~9% alone, 9 tenants stay 1% canary per filter: 10k holdout probes each; X pages tenant X at >2%, platform sleeps. rule: share nothing that saturates; filters are per-owner or per-day, never global.
A 1.2MB filter rejects 10-SSTable misses at 1% with 7 hashes, but it only answers present or absent. What estimates top 100 URLs over 100M events in 5KB when the dashboard needs how-many, not is-it-there?