Bloom Filters & Probabilistic Data Structures
A Bloom filter answers one question: "Is this element possibly in the set, or definitely not?" It does this using dramatically less memory than storing the actual set, at the cost of a small, tunable probability of false positives. It never produces false negatives — if the filter says "no," the element is guaranteed absent.
This trade-off turns out to be extraordinarily useful. Every query you run against a database, every URL your browser checks against a phishing list, every key lookup in an LSM-tree storage engine — all of these use Bloom filters or their descendants to avoid expensive operations that would almost certainly return "not found."
How Bloom Filters Work
The Data Structure
A Bloom filter is a bit array of bits, initially all set to 0, combined with independent hash functions, each mapping an element to one of the bit positions.
Initial state (m = 16 bits):
[0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Insert Operation
To insert an element, compute all hash functions and set the corresponding bits to 1:
Insert "alice" with k=3 hash functions:
h1("alice") = 2
h2("alice") = 7
h3("alice") = 13
[0][0][1][0][0][0][0][1][0][0][0][0][0][1][0][0]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^ ^ ^
Insert "bob":
h1("bob") = 4
h2("bob") = 7 ← already set by "alice"
h3("bob") = 11
[0][0][1][0][1][0][0][1][0][0][0][1][0][1][0][0]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Lookup Operation
To check membership, compute all hash functions and check if all corresponding bits are 1:
Lookup "alice": bits 2, 7, 13 → all 1 → "possibly present" ✓
Lookup "charlie": bits 1, 5, 9 → bit 1 is 0 → "definitely not present" ✗
Lookup "dave": bits 2, 4, 11 → all 1 → "possibly present" (FALSE POSITIVE!)
False Positives Are Fundamental
A Bloom filter can report an element as present when it is not (false positive). This happens because other insertions set the same bit positions. A Bloom filter can never report an element as absent when it is actually present (false negative). You cannot delete elements from a standard Bloom filter because clearing a bit might affect other elements.
The False Positive Math
The probability that a specific bit is still 0 after inserting elements with hash functions into an -bit array:
The false positive probability — the chance that all bits for a non-member are set to 1:
Deriving the Formula Step by Step
The derivation is short and lets you reason about any variant. It treats the hashes as independent and uniform, which good hashes approximate well.
Step 1: one bit, one hash. A single hash of a single element picks one of positions uniformly. The chance that it does not pick a given bit is .
Step 2: all the hashes of all the elements. Inserting elements with hashes each makes independent picks. The bit stays 0 only if every pick misses it:
Step 3: the exponential approximation. Using for large :
Call this fraction of zero bits . The fraction of one bits is .
Step 4: the query. A non-member is reported present only if all of its positions are 1. Treating those positions as independent draws from a bit array in which a fraction are set:
Step 4 is not quite exact, because the bits are slightly correlated. Bose and others showed in 2008 that the formula slightly underestimates the true rate for small filters; for realistic sizes the difference is negligible.
Two things fall out of the formula immediately:
- The rate depends only on the ratio (bits per element) and on . A 10-bit-per-element filter has the same false-positive rate at a thousand elements as at a billion.
- The rate depends on the actual number of elements inserted, not the number you planned for. Overfill a filter and the rate climbs fast (worked example below).
Optimal Number of Hash Functions
The false positive rate is minimized when:
With the optimal , the false positive rate simplifies to:
Why ? There is a tension in choosing . More hashes means each query checks more bits, which makes a false positive harder. But more hashes also set more bits, which makes each check more likely to hit a 1. To find the balance, minimise the logarithm of the rate:
Substitute , so :
The expression is symmetric in and , so its extreme is at . Then gives . The intuition is pleasant: the best filter is one where exactly half the bits are set. A filter with far fewer than half its bits set is wasting space, and one with far more is saturated. With half the bits set, each of the checks has a one-in-two chance of hitting a 1, which is where comes from.
The minimum is flat. With , the best is 6.6, and the rates around it are:
| 3 | 5 | 7 | 9 | 11 | |
|---|---|---|---|---|---|
| FPR | 1.94% | 1.11% | 1.00% | 1.15% | 1.50% |
So rounding , or choosing a smaller to save CPU, costs little.
Sizing a Bloom Filter
Given a desired false positive rate and expected number of elements :
| False positive rate | Bits per element () | Hash functions () |
|---|---|---|
| 10% | 4.79 | 3 |
| 1% | 9.58 | 7 |
| 0.1% | 14.38 | 10 |
| 0.01% | 19.17 | 13 |
Memory Efficiency
A Bloom filter with a 1% false positive rate uses only 9.6 bits per element — regardless of element size. Storing 1 billion URLs (average 50 bytes each) as a set would take ~50 GB. A Bloom filter for the same set with 1% FP rate takes ~1.2 GB — a 40x reduction.
Worked Examples
Example 1: sizing from requirements. A service must answer "have we seen this order id before?" for 1 million ids, with at most 1% false positives.
1.2 MB for a million ids, of any length. A hash set of the same ids as 36-character UUID strings would be well over 50 MB once you count per-entry overhead.
Example 2: what overfilling does. The same filter (9.585 million bits, ) is used past its design point.
| Elements inserted | Bits per element | FPR |
|---|---|---|
| 1.0 million (design) | 9.6 | 1.0% |
| 1.5 million | 6.4 | 5.8% |
| 2.0 million | 4.8 | 15.7% |
Doubling the load makes false positives about sixteen times more common. This is the most common production failure with Bloom filters: someone sizes a filter for last year's data. Either size for growth, rebuild periodically, or use a scalable filter (below).
Example 3: is the filter paying for itself? An LSM store has 7 levels, each SSTable lookup costs one random SSD read of about 100 µs, and a filter check costs about 100 ns from memory. Without filters, a lookup for a missing key reads every level: 7 × 100 µs = 700 µs. With 1% filters, the expected number of wasted reads is , so the average cost is about 7 µs plus 0.7 µs of filter checks. The filters make negative lookups about a hundred times faster.
How Close to Optimal Is a Bloom Filter?
Any structure that answers membership with false-positive rate and no false negatives needs at least bits per element (an information-theoretic lower bound). A Bloom filter uses bits, so it is about 44% above the lower bound. That gap is what newer filters (cuckoo, xor, ribbon) attack.
| Target FPR | Lower bound (bits/elem) | Bloom (bits/elem) | Cuckoo, semi-sorted, 95% full (bits/elem) |
|---|---|---|---|
| 3% | 5.1 | 7.3 | 7.4 |
| 1% | 6.6 | 9.6 | 9.1 |
| 0.1% | 10.0 | 14.4 | 12.5 |
Implementation
import math
import mmh3 # MurmurHash3
from bitarray import bitarray
class BloomFilter:
def __init__(self, expected_items: int, fp_rate: float = 0.01):
self.fp_rate = fp_rate
self.size = self._optimal_size(expected_items, fp_rate)
self.num_hashes = self._optimal_hashes(self.size, expected_items)
self.bit_array = bitarray(self.size)
self.bit_array.setall(0)
self.count = 0
@staticmethod
def _optimal_size(n: int, p: float) -> int:
"""Calculate optimal bit array size."""
m = -(n * math.log(p)) / (math.log(2) ** 2)
return int(math.ceil(m))
@staticmethod
def _optimal_hashes(m: int, n: int) -> int:
"""Calculate optimal number of hash functions."""
k = (m / n) * math.log(2)
return int(math.ceil(k))
def _get_hash_indices(self, item: str) -> list[int]:
"""Generate k hash indices using double hashing."""
h1 = mmh3.hash(item, seed=0) % self.size
h2 = mmh3.hash(item, seed=42) % self.size
return [(h1 + i * h2) % self.size for i in range(self.num_hashes)]
def add(self, item: str) -> None:
for idx in self._get_hash_indices(item):
self.bit_array[idx] = 1
self.count += 1
def might_contain(self, item: str) -> bool:
"""Returns True if item might be in the set, False if definitely not."""
return all(self.bit_array[idx] for idx in self._get_hash_indices(item))
@property
def current_fp_rate(self) -> float:
"""Estimate current false positive rate."""
bits_set = self.bit_array.count(1)
return (bits_set / self.size) ** self.num_hashes
# Usage
bf = BloomFilter(expected_items=1_000_000, fp_rate=0.001)
bf.add("user:12345")
bf.add("user:67890")
print(bf.might_contain("user:12345")) # True (correct)
print(bf.might_contain("user:99999")) # False (or very rarely True)
Choosing k and m in Practice
The formulas give real-valued answers. Production implementations add a few engineering decisions.
Two hashes are enough
Computing independent hashes is wasteful. Kirsch and Mitzenmacher ("Less Hashing, Same Performance", 2006) proved that deriving all positions from two hashes, as , gives the same asymptotic false-positive rate. The implementation above uses this "double hashing" trick, as do Guava, RocksDB, Cassandra and most others. In practice one 128-bit hash (for example MurmurHash3 x64-128, or xxHash's 128-bit variant) is split into two 64-bit halves.
One detail matters: if , every is the same position, and the element sets only one bit. Implementations force to be odd (and a power of two), or add a small fix-up, to avoid this.
Blocked Bloom filters for speed
A classic filter's probes land on random cache lines, so a lookup in a filter larger than the CPU cache costs cache misses. A blocked (or "cache-line") Bloom filter first hashes the element to one 64-byte block, then sets all bits inside that block. A lookup costs one cache miss, at the price of a slightly higher false-positive rate for the same memory, because blocks fill unevenly.
Practical sizing rules
| Decision | Rule |
|---|---|
| Bits per element | Pick from the target rate: about 4.8 for 10%, 9.6 for 1%, 14.4 for 0.1%. Each extra 4.8 bits divides the rate by 10. |
| Number of hashes | , and rounding down by one is fine if CPU matters |
| Expected | Plan for the largest before the next rebuild, not today's |
| Hash function | A fast non-cryptographic hash (Murmur3, xxHash). Use a keyed hash (SipHash) if attackers choose the input. |
| Persistence | Store , , the hash function and its seed alongside the bits, or the filter cannot be read back |
Operations on filters
Two filters with the same , and hash functions can be combined with bitwise operations:
- Union: bitwise OR gives exactly the filter you would have built by inserting both sets. This is what makes Bloom filters easy to merge across shards or time windows.
- Intersection: bitwise AND gives a filter that contains the intersection, but with a higher false-positive rate than one built from the intersection directly.
- Estimating size: from the set bits, handy for monitoring fullness.
Counting Bloom Filters
Standard Bloom filters do not support deletion — you cannot unset a bit without potentially removing other elements. Counting Bloom filters replace each bit with a counter:
Standard: [0][1][0][1][1][0][0][1] ← 1 bit per position
Counting: [0][2][0][1][3][0][0][1] ← n bits (usually 4) per position
class CountingBloomFilter:
def __init__(self, expected_items: int, fp_rate: float = 0.01):
self.size = self._optimal_size(expected_items, fp_rate)
self.num_hashes = self._optimal_hashes(self.size, expected_items)
self.counters = [0] * self.size
def add(self, item: str) -> None:
for idx in self._get_hash_indices(item):
self.counters[idx] += 1
def remove(self, item: str) -> None:
"""Remove an element. Only call if the element was previously added."""
if not self.might_contain(item):
raise ValueError("Cannot remove element not in filter")
for idx in self._get_hash_indices(item):
self.counters[idx] = max(0, self.counters[idx] - 1)
def might_contain(self, item: str) -> bool:
return all(self.counters[idx] > 0
for idx in self._get_hash_indices(item))
Counter Overflow
With 4-bit counters, the maximum count is 15. If a counter overflows, it stays at the maximum value and deletion becomes unsafe. The probability of overflow is negligible for well-sized filters, but monitor it in production.
Trade-off: Counting Bloom filters use 3-4x more memory than standard Bloom filters (4 bits per counter vs 1 bit).
Why 4 bits is enough: Fan, Cao, Almeida and Broder, who introduced counting Bloom filters for web cache sharing (the "Summary Cache" paper, 2000), showed that with the optimal , the chance of any counter reaching 16 is on the order of times . A filter of a billion counters is still very unlikely to overflow.
Two other caveats make counting filters less useful than they look:
- Deleting a false positive corrupts the filter. If you delete an element that was never inserted but which the filter reported as present, you decrement counters that belong to other elements, and can create false negatives. Only delete elements you know were inserted, which usually means keeping the real set somewhere else.
- The memory cost buys less than a cuckoo filter. At 4 bits per counter, a counting filter at 1% uses about 38 bits per element. A cuckoo filter supports deletion at about 9 to 13 bits.
Scalable Bloom Filters
A plain Bloom filter must be sized up front, and Example 2 showed what happens when it is overfilled. When you do not know how many elements will arrive, Almeida, Baquero, Preguiça and Hutchison's scalable Bloom filter (2007) grows as needed while keeping a bound on the overall false-positive rate.
The idea:
- Start with one filter sized for elements at false-positive rate .
- When it fills up (its estimated count reaches capacity), add a new filter that is times larger (growth factor, typically 2 or 4) with a tighter rate , where is the tightening ratio (typically 0.8 or 0.9).
- Insert only into the newest filter. Query all of them, and report "present" if any says so.
The overall false-positive rate is bounded by the sum of a geometric series:
So to guarantee 1% overall with , start with . The cost is that each lookup checks every layer, but because layers grow geometrically, a filter that has grown a thousand-fold has only about ten layers.
import math
class ScalableBloomFilter:
"""Grows by adding larger, stricter BloomFilter layers.
Overall false-positive rate stays below target_fp."""
def __init__(self, initial_capacity=1000, target_fp=0.01,
growth=2, tightening=0.9):
self.growth = growth
self.r = tightening
self.p0 = target_fp * (1 - tightening) # so that sum <= target_fp
self.layers: list[tuple[BloomFilter, int]] = [] # (filter, capacity)
self._add_layer(initial_capacity)
def _add_layer(self, capacity: int) -> None:
p = self.p0 * (self.r ** len(self.layers))
self.layers.append((BloomFilter(capacity, p), capacity))
def add(self, item: str) -> None:
if self.might_contain(item):
return # avoid double-counting
bf, cap = self.layers[-1]
if bf.count >= cap:
self._add_layer(cap * self.growth)
bf, cap = self.layers[-1]
bf.add(item)
def might_contain(self, item: str) -> bool:
return any(bf.might_contain(item) for bf, _ in self.layers)
sbf = ScalableBloomFilter(initial_capacity=1_000, target_fp=0.01)
for i in range(100_000):
sbf.add(f"id-{i}")
false_hits = sum(sbf.might_contain(f"other-{i}") for i in range(100_000))
assert all(sbf.might_contain(f"id-{i}") for i in range(100_000)) # no false negatives
assert false_hits / 100_000 < 0.01, false_hits
print(len(sbf.layers), "layers, measured FPR", false_hits / 100_000)
RedisBloom's BF.RESERVE creates a scalable filter of this kind by default: when a filter fills up, a new sub-filter is stacked on top with an EXPANSION factor that defaults to 2. Passing NONSCALING turns this off and makes inserts fail once the filter is full.
Cuckoo Filters
Cuckoo filters are a modern alternative that support deletion, use less space than counting Bloom filters, and often have better lookup performance.
graph TD
A["Element x"] --> B["Fingerprint: f = fingerprint(x)"]
B --> C["Bucket 1: h1(x)"]
B --> D["Bucket 2: h1(x) XOR h(f)"]
C --> E{Empty slot?}
D --> F{Empty slot?}
E -->|Yes| G["Insert in Bucket 1"]
E -->|No| F
F -->|Yes| H["Insert in Bucket 2"]
F -->|No| I["Kick existing entry<br/>to its alternate bucket"]
I --> J["Repeat (max 500 kicks)"]
The key insight: each element has exactly two possible bucket locations, and you can compute one from the other using only the fingerprint (not the original element):
This XOR property means you can relocate entries without knowing the original elements.
import hashlib
import struct
from typing import Optional
class CuckooFilter:
def __init__(self, capacity: int, bucket_size: int = 4,
fingerprint_bits: int = 8, max_kicks: int = 500):
self.capacity = capacity
self.bucket_size = bucket_size
self.fp_bits = fingerprint_bits
self.max_kicks = max_kicks
self.buckets: list[list[int]] = [[] for _ in range(capacity)]
self.count = 0
def _fingerprint(self, item: str) -> int:
h = int(hashlib.sha256(item.encode()).hexdigest(), 16)
fp = h % ((1 << self.fp_bits) - 1) + 1 # Never 0
return fp
def _hash1(self, item: str) -> int:
h = int(hashlib.md5(item.encode()).hexdigest(), 16)
return h % self.capacity
def _hash2(self, index: int, fingerprint: int) -> int:
return (index ^ hash(fingerprint)) % self.capacity
def insert(self, item: str) -> bool:
fp = self._fingerprint(item)
i1 = self._hash1(item)
i2 = self._hash2(i1, fp)
if len(self.buckets[i1]) < self.bucket_size:
self.buckets[i1].append(fp)
self.count += 1
return True
if len(self.buckets[i2]) < self.bucket_size:
self.buckets[i2].append(fp)
self.count += 1
return True
# Must kick existing entries
import random
i = random.choice([i1, i2])
for _ in range(self.max_kicks):
j = random.randrange(len(self.buckets[i]))
fp, self.buckets[i][j] = self.buckets[i][j], fp
i = self._hash2(i, fp)
if len(self.buckets[i]) < self.bucket_size:
self.buckets[i].append(fp)
self.count += 1
return True
return False # Filter is too full
def lookup(self, item: str) -> bool:
fp = self._fingerprint(item)
i1 = self._hash1(item)
i2 = self._hash2(i1, fp)
return fp in self.buckets[i1] or fp in self.buckets[i2]
def delete(self, item: str) -> bool:
fp = self._fingerprint(item)
i1 = self._hash1(item)
i2 = self._hash2(i1, fp)
for bucket_idx in [i1, i2]:
if fp in self.buckets[bucket_idx]:
self.buckets[bucket_idx].remove(fp)
self.count -= 1
return True
return False
Bloom Filter vs Cuckoo Filter
| Feature | Bloom Filter | Cuckoo Filter |
|---|---|---|
| Deletion | Not supported | Supported |
| Space (at <3% FP) | Less efficient | More efficient |
| Space (at >3% FP) | More efficient | Less efficient |
| Lookup speed | hash probes | 2 hash probes |
| Insert speed | hash probes | Amortized |
| Load factor | N/A | Typically ~95% |
Correction
The two "Space" rows of this table were previously swapped. Fan et al. report that cuckoo filters (with semi-sorted buckets) use less space than Bloom filters when the target false-positive rate is below about 3%, and Bloom filters win above that. The worked numbers in the "How Close to Optimal" table earlier on this page show the crossover.
About the Python cuckoo code above
The XOR trick only works if going from bucket 1 to bucket 2 and back again returns to bucket 1. That requires the number of buckets to be a power of two, with the index computed as (index ^ h(fp)) & (capacity - 1). With an arbitrary capacity and % capacity, the alternate of the alternate can be a third bucket, and lookups then miss relocated entries, which gives false negatives. Also, Python's hash() of a small integer is the integer itself, so the "hash of the fingerprint" adds no mixing. A real implementation should run the fingerprint through a proper hash. The sketch is fine for following the algorithm, but fix both points before using it.
Cuckoo Filter Sizing and Caveats
A cuckoo filter has three parameters: the fingerprint length bits, the bucket size (entries per bucket, usually 4), and the load factor it can reach before inserts start failing (about 95% with ).
A lookup compares the query's fingerprint with up to stored fingerprints (two buckets of each). Each comparison matches by chance with probability , so:
Bits per element are then . For 1% with : bits, and bits per element. The paper's "semi-sorting" trick, which sorts the 4-bit prefixes of fingerprints within a bucket and encodes them more compactly, saves one bit per entry, which gives the numbers in the table above.
Caveats that matter in production:
- Inserts can fail. Once the filter is near its maximum load, an insert can exhaust its kick budget. You need a plan: rebuild bigger, or chain a second filter (the scalable idea again).
- Deletes need care. Deleting an item that was never inserted can remove a different item with the same fingerprint in the same bucket, which creates a false negative. As with counting Bloom filters, only delete what you inserted.
- Duplicates are limited. Inserting the same item repeatedly stores its fingerprint repeatedly, and after copies both buckets are full of it. Check before inserting if duplicates are possible.
- Unions are not free. Unlike Bloom filters, two cuckoo filters cannot be merged with a bitwise OR.
Newer Filters: XOR and Ribbon
Two more recent designs get even closer to the lower bound for static sets (built once, never updated):
- XOR filters (Graf and Lemire, 2020) use about bits per element and answer queries with exactly three memory accesses.
- Ribbon filters (Dillinger and Walzer, 2021) solve a linear system over GF(2) at build time and get much closer to the lower bound than Bloom filters do. RocksDB offers Ribbon for SST filters, reporting about 30% less filter memory than Bloom at the same rate, for more CPU at build time.
HyperLogLog
HyperLogLog (HLL) answers a different question: "How many distinct elements are in this set?" It does so using memory — for 1 billion distinct elements, it uses only ~1.5 KB of memory with ~2% error.
The Intuition
If you hash elements uniformly, the maximum number of leading zeros in any hash tells you roughly how many distinct elements you have seen. If the longest run of leading zeros is , the estimated cardinality is .
hash("alice") = 00101... → 2 leading zeros
hash("bob") = 10011... → 0 leading zeros
hash("charlie") = 00001... → 3 leading zeros
hash("dave") = 01100... → 1 leading zero
Max leading zeros = 3 → estimate ≈ 2^3 = 8 distinct elements
This estimate has high variance. HyperLogLog reduces variance by splitting elements into buckets using the first few bits, and taking the harmonic mean of the estimates:
where is the maximum number of leading zeros seen in bucket , and is a bias correction constant.
import hashlib
import math
class HyperLogLog:
def __init__(self, precision: int = 14):
"""precision p: uses 2^p registers, ~1.04/sqrt(2^p) standard error."""
self.p = precision
self.m = 1 << precision # Number of registers
self.registers = [0] * self.m
self.alpha = self._compute_alpha(self.m)
@staticmethod
def _compute_alpha(m: int) -> float:
if m == 16:
return 0.673
elif m == 32:
return 0.697
elif m == 64:
return 0.709
else:
return 0.7213 / (1 + 1.079 / m)
def _hash(self, item: str) -> int:
h = hashlib.sha1(item.encode()).hexdigest()
return int(h[:16], 16) # 64-bit hash
def add(self, item: str) -> None:
h = self._hash(item)
# First p bits → register index
idx = h >> (64 - self.p)
# Remaining bits → count leading zeros
remaining = h & ((1 << (64 - self.p)) - 1)
leading_zeros = (64 - self.p) - remaining.bit_length() + 1
self.registers[idx] = max(self.registers[idx], leading_zeros)
def estimate(self) -> int:
"""Return estimated cardinality."""
raw = self.alpha * self.m ** 2 * (
sum(2 ** (-r) for r in self.registers) ** -1
)
# Small range correction
if raw <= 2.5 * self.m:
zeros = self.registers.count(0)
if zeros > 0:
return int(self.m * math.log(self.m / zeros))
return int(raw)
def merge(self, other: 'HyperLogLog') -> 'HyperLogLog':
"""Merge two HLLs (e.g., from different servers)."""
assert self.p == other.p
result = HyperLogLog(self.p)
result.registers = [
max(a, b) for a, b in zip(self.registers, other.registers)
]
return result
Standard error of HyperLogLog:
| Precision () | Registers () | Memory | Standard Error |
|---|---|---|---|
| 10 | 1,024 | 1 KB | 3.25% |
| 14 | 16,384 | 12 KB | 0.81% |
| 16 | 65,536 | 48 KB | 0.41% |
Redis uses HyperLogLog natively with the PFADD and PFCOUNT commands — 12 KB per counter, ~0.81% error.
Why the Estimate Works
The intuition above can be made precise. For a uniform hash, the chance that a value starts with at least zero bits is . Seeing a value with leading zeros is therefore a "one in " event, and after distinct items the largest you would expect to have seen is about . Duplicates do not matter at all: the same item always hashes to the same value, so it cannot raise the maximum twice. That is what makes the structure count distinct items.
A single maximum is a terrible estimator, though, because one lucky hash with 30 leading zeros makes the estimate jump to a billion. HyperLogLog fixes this with stochastic averaging: use the first bits of the hash to pick one of registers, keep a separate maximum per register, and combine them with the harmonic mean. The harmonic mean is dominated by the small values, so one outlier register barely moves it. The constant corrects a systematic bias in this estimator.
Each register needs to hold a number up to about 64, so 6 bits is enough. That is where the memory figures come from: registers × 6 bits = 12 KB. Memory grows with only because the register width needs bits. The register count is set by the accuracy you want, not by .
Worked Example: Unique Visitors
A site wants daily unique visitors per page for 2 million pages, with about 1% error.
- Exact sets at 1,000 visitors per page and 16 bytes per id: 32 GB per day, far more for popular pages.
- HyperLogLog at : at most 12 KB per page, and Redis keeps small HLLs in a sparse run-length encoding of a few hundred bytes until they pass
hll-sparse-max-bytes(3,000 by default), so most pages cost far less. - A page with 8 million real visitors is reported within about ±65,000 (one standard error, ) roughly two-thirds of the time, and within about ±130,000 about 95% of the time.
Weekly uniques do not need a recount. Because merging two HLLs is just a per-register max, the weekly count is PFMERGE week day1 day2 ... day7 followed by PFCOUNT week. Each visitor is counted once even if they came every day. This works across machines too: each server keeps its own HLL, and a central job merges them. That property (sketches that combine without loss) is why HLL is everywhere in distributed analytics: Redis, Presto/Trino's approx_distinct, BigQuery's APPROX_COUNT_DISTINCT, Druid, and Elasticsearch's cardinality aggregation all use HyperLogLog or a variant.
HyperLogLog++
Google's 2013 paper "HyperLogLog in Practice" (Heule, Nunkesser and Hall) introduced the improvements most modern implementations use: a 64-bit hash (so accuracy does not degrade near items), empirical bias correction for small and medium cardinalities, and a sparse representation that stores only non-zero registers while sets are small.
What HLL cannot do well: intersections. You can estimate from three HLL estimates, but the error is relative to the size of the union, so the intersection of two large, barely overlapping sets is dominated by noise. Use MinHash or theta sketches if you need set intersections.
Count-Min Sketch
A Count-Min Sketch (CMS) estimates the frequency of elements in a stream using sub-linear memory. Unlike a Bloom filter (which answers "is this in the set?"), a CMS answers "approximately how many times has this element appeared?"
graph TD
A["Element x"] --> H1["h1(x) = 2"]
A --> H2["h2(x) = 5"]
A --> H3["h3(x) = 1"]
subgraph "Count-Min Sketch (d=3 rows, w=8 columns)"
R1["Row 1: [0][0][3][0][0][1][0][0]"]
R2["Row 2: [0][0][0][0][0][2][0][0]"]
R3["Row 3: [0][4][0][0][0][0][0][0]"]
end
H1 --> R1
H2 --> R2
H3 --> R3
B["Estimate = min(3, 2, 4) = 2"]
import hashlib
import sys
class CountMinSketch:
def __init__(self, width: int, depth: int):
"""
width (w): number of columns. Determines accuracy: error ≤ e*N/w
depth (d): number of rows/hash functions. Determines confidence: 1 - 1/e^d
"""
self.w = width
self.d = depth
self.table = [[0] * width for _ in range(depth)]
self.total = 0
def _hash(self, item: str, i: int) -> int:
h = hashlib.md5(f"{i}:{item}".encode()).hexdigest()
return int(h, 16) % self.w
def add(self, item: str, count: int = 1) -> None:
self.total += count
for i in range(self.d):
j = self._hash(item, i)
self.table[i][j] += count
def estimate(self, item: str) -> int:
"""Returns an overestimate of the true count."""
return min(
self.table[i][self._hash(item, i)]
for i in range(self.d)
)
@staticmethod
def from_error_bounds(epsilon: float, delta: float) -> 'CountMinSketch':
"""Create CMS with error ≤ epsilon*N with probability ≥ 1-delta."""
import math
w = int(math.ceil(math.e / epsilon))
d = int(math.ceil(math.log(1 / delta)))
return CountMinSketch(w, d)
The error guarantee: for any element, the estimated count satisfies:
with probability , where is the total number of insertions.
Correction
This bound previously read , which divides by the width twice. The Cormode–Muthukrishnan guarantee is an additive error of when the width is . Equivalently, for a given width the error is at most , which matches the docstring in the code above.
Why the Minimum Works
Each row is a small hash table of counters with collisions. Item 's counter in row holds 's true count plus the counts of every other item that hashed to the same column. Collisions only ever add, so every row overestimates, and the least-overestimated row (the minimum) is the best guess. In one row, the expected collision mass is , and by Markov's inequality the chance that it exceeds is at most . The rows use independent hashes, so the chance that all rows exceed it is at most . That is the whole proof, and it explains the two knobs: width controls how big the error is, depth controls how often you exceed it.
Worked Sizing
Find the heavy hitters among 1 billion requests per hour, with error at most 0.1% of traffic (, so 1 million requests) and 99% confidence ():
- columns
- rows
- Memory: bytes KB
53 KB tracks approximate counts for every key in a billion-event stream. The error is absolute (up to a million here), so the sketch is excellent for large counts and useless for small ones: an item seen 50 times might be reported as 900,000. That is fine for heavy hitters, where you only care about items near the top.
Conservative Update and Top-K
Two practical improvements:
- Conservative update. When adding to item , only raise each of its counters to , instead of adding to all of them. Counters that are already larger than 's new estimate are left alone. This reduces overestimation a lot in practice, but it no longer supports decrements.
- Heavy hitters. A sketch answers "how many times did appear?" but cannot list the frequent items by itself. Pair it with a min-heap of size : on each update, if the item's estimate exceeds the smallest heap entry, put it in the heap. RedisBloom offers a
CMSsketch, and a separateTOPKstructure based on the HeavyKeeper algorithm.
Like HLL, sketches with the same width, depth and hash functions merge by adding the tables element-wise, so each node can sketch its own traffic and a coordinator can sum them. That is how distributed rate limiters and network monitors find the top talkers across a fleet without shipping every event.
Real-World Usage
LSM-Tree Storage Engines (LevelDB, RocksDB, Cassandra)
Before reading an SSTable from disk, check a Bloom filter to see if the key could be there. This avoids unnecessary disk I/O for keys that do not exist in that level.
Query for key "user:123":
Level 0 Bloom filter → "maybe" → read SSTable → not found
Level 1 Bloom filter → "no" → skip (saved disk read!)
Level 2 Bloom filter → "maybe" → read SSTable → found!
See Storage Engines for how this fits into the LSM-tree architecture.
How the major engines expose it:
| Engine | Filter | Default and tuning |
|---|---|---|
| LevelDB | Optional, per table file | NewBloomFilterPolicy(10), 10 bits per key, about 1% FPR. Off unless you set a filter policy. |
| RocksDB | Bloom (legacy and "full" formats), Ribbon | bits_per_key commonly 10. Option to skip filters on the last level (optimize_filters_for_hits) where most data lives and most lookups hit. Prefix Bloom filters for range scans that share a prefix. |
| Cassandra | Bloom filter per SSTable, off-heap | Table option bloom_filter_fp_chance. Commonly 0.01, and 0.1 for leveled compaction, which has fewer SSTables per read. Setting it to 1.0 disables the filter. |
| HBase | Per HFile block, row or row+column | BLOOMFILTER => 'ROW' by default in recent versions |
The RocksDB optimize_filters_for_hits option is a nice example of reasoning about filters. In a leveled LSM-tree about 90% of the data is in the last level, so that level's filters are about 90% of filter memory. If your workload mostly looks up keys that exist, the last level is where the lookup succeeds anyway, and its filter almost never saves a read. Dropping it saves most of the filter memory at little cost.
Cassandra's Read Path
In Cassandra a read for a partition key goes to each SSTable that might hold it. For each one, the node checks, in order: the Bloom filter (in memory, off-heap), then the partition key cache, then the partition summary and index on disk, and finally the data file. The Bloom filter is the step that lets a read skip SSTables entirely. With size-tiered compaction a partition can be spread across many SSTables, so the filter decides whether a read touches 2 files or 20.
nodetool tablestats reports each table's Bloom filter false ratio and memory. Filter memory scales with the number of partitions, so tables with billions of tiny partitions can spend gigabytes per node on filters, a common reason to raise bloom_filter_fp_chance on write-heavy tables rarely read by key. A changed setting applies only to SSTables written afterwards.
Google Chrome Safe Browsing
Chrome checks URLs against a Bloom filter of known malicious URLs stored locally. Only if the Bloom filter says "maybe" does it make a network call to verify.
Correction
This describes Chrome's original Safe Browsing design. Chrome replaced the Bloom filter in the early 2010s with a compact sorted set of short hash prefixes (its "PrefixSet"), and the Safe Browsing protocol today works with hash prefixes: the client checks a local list of 4-byte (or longer) SHA-256 prefixes and asks the server for full hashes only on a prefix match. The principle is the same (a compact local structure with false positives, confirmed remotely), but it is no longer a Bloom filter.
Content Delivery Networks
CDNs use Bloom filters to decide which objects to cache. Only cache an object after it has been requested more than once (the first request adds it to the filter; subsequent requests that hit the filter trigger caching).
This is documented for Akamai in Maggs and Sitaraman's "Algorithmic Nuggets in Content Delivery" (2015). They report that about three-quarters of the objects requested from their servers were "one-hit wonders", requested once and never again in the measurement window. Caching those wastes disk writes and evicts useful content. With a Bloom filter of recently requested URLs, an object is cached only on its second request. They report that this "cache on second hit" rule cut disk writes roughly in half and improved hit rates, because the cache was no longer churned by one-off objects. A filter like this has to be reset periodically or it fills up; a common way to avoid forgetting everything at once is to rotate two filters, the current period's and the previous one's, and check both.
Database Query Optimization
PostgreSQL uses Bloom filters for join optimization, and Cassandra uses them to avoid reading SSTables that cannot contain a partition key.
Correction
The PostgreSQL part of the sentence above is not accurate for core PostgreSQL. PostgreSQL ships Bloom filters as the bloom contrib extension (a Bloom-filter index type useful for equality queries on many columns) and, since version 14, as bloom operator classes for BRIN indexes. Its hash joins do not build Bloom filters. Bloom filters for joins, often called runtime filters or semi-join reduction, are used by distributed and analytic engines such as Apache Impala and Spark (runtime Bloom filters, added in 3.3). The Cassandra part is correct and is described above.
The distributed-join use deserves a sentence of explanation, because it is a classic distributed-systems trick. To join a small filtered table with a huge one spread over many nodes, build a Bloom filter of the small side's join keys, send that compact filter to every node holding the large side, and let each node discard rows whose key is definitely not in the filter before shipping anything over the network. False positives only cost a little extra network traffic. The real join removes them.
Bitcoin Light Clients (a Cautionary Tale)
BIP 37 (2012) let lightweight Bitcoin wallets send a Bloom filter of their addresses to full nodes, which would then forward only matching transactions. False positives were meant to hide which addresses were the wallet's, but analysis showed the filters leaked far more than intended. Bitcoin Core stopped serving them by default in version 0.19 (2019), and BIP 157/158 "compact block filters" reverse the direction: nodes publish a filter per block and clients test them locally. The lesson generalises: a Bloom filter's false positives are not a privacy mechanism.
Stream Processing
Count-Min Sketch is used in network monitoring to detect heavy hitters (IPs sending the most traffic) and in advertising to track approximate impression counts.
Comparison of Probabilistic Data Structures
| Structure | Question Answered | Memory | Error Type |
|---|---|---|---|
| Bloom Filter | "Is x in the set?" | bits | False positives |
| Cuckoo Filter | "Is x in the set?" (with delete) | bits | False positives |
| HyperLogLog | "How many distinct elements?" | Estimation error | |
| Count-Min Sketch | "How often does x appear?" | Overestimates | |
| MinHash | "How similar are sets A and B?" | Estimation error | |
| Top-K (Space-Saving) | "What are the most frequent elements?" | May miss elements |
Count-Min's full memory cost is counters; the in the table is the width of one row.
Choosing a Structure
flowchart TD
Q["What do you need to know?"] --> M{"Is x in the set?"}
Q --> C{"How many distinct?"}
Q --> F{"How often does x appear?"}
M --> D{"Need deletes?"}
D -->|"No, set is static"| X["Xor or Ribbon filter"]
D -->|"No, set grows"| B["Bloom, scalable if size unknown"]
D -->|"Yes"| CF["Cuckoo filter"]
C --> H["HyperLogLog, merge per shard"]
F --> S["Count-Min Sketch, plus heap for top-K"]
Failure Modes in Production
| Failure | Symptom | Fix |
|---|---|---|
| Filter sized for old data | False-positive rate creeps up, backend load rises slowly | Monitor set-bit fraction or estimated . Rebuild or use a scalable filter. |
| Weak or correlated hash | FPR far above the formula, often for structured keys like sequential ids | Use a well-mixed hash (Murmur3, xxHash). Never use x mod m on raw integers. |
| Attacker-chosen inputs | Adversary crafts keys that collide, saturating bits or flooding the backend | Keyed hash (SipHash) with a secret seed |
| Format mismatch across services | A filter built in Java reports nonsense in Go | Pin and document the hash function, seed, bit order, and . Version the format. |
| Deleting from a counting or cuckoo filter what was never added | False negatives appear, the one thing a filter must never do | Only delete confirmed members |
| Treating "maybe" as "yes" | Business logic acts on a false positive (blocks a username, rejects a payment) | A positive answer must always be confirmed against the source of truth unless false positives are harmless |
War Story (illustrative)
A team put a Bloom filter in front of a user database to answer "is this username taken?" during sign-up, sized for 50 million users at 1%. Three years later the site had 140 million users. Nobody had looked at the filter since launch. At almost three times its design load, the filter's false-positive rate was nearly 40%, so more than a third of new usernames were reported as taken. That alone would only have cost database reads, but the sign-up code treated the filter's "maybe" as a definitive "taken" to save a query, so new users saw "username unavailable" for perfectly free names. Sign-up conversion fell for months before anyone connected it to the filter. The fix was to confirm every positive against the database, add a metric for the filter's estimated element count against its capacity, and rebuild it nightly at twice the current user count.
Interview Questions
1. Derive the false-positive rate of a Bloom filter.
A bit stays 0 after uniform picks with probability . A non-member is a false positive if all of its bits are 1, which happens with probability about .
2. Why is the optimal equal to , and what does that mean physically?
Minimising gives : the best filter has exactly half its bits set. Then each probe hits a 1 with probability one half, and the rate is .
3. You need 100 million keys at 0.1% false positives. How much memory?
About 14.4 bits per key, so 1.44 billion bits, about 180 MB, with .
4. Why can't you delete from a Bloom filter, and what are the alternatives?
A bit may be shared by several elements, so clearing it can create false negatives. Counting Bloom filters (4-bit counters, about 4× memory) and cuckoo filters (fingerprints in buckets, close to Bloom's size) support deletion, but only of elements that were really inserted.
5. When does a cuckoo filter beat a Bloom filter?
When you need deletion, when the target false-positive rate is below about 3% (it uses less space there), and when you want lookups to touch only two buckets. Bloom filters win at higher rates, on union by OR, and on never failing an insert.
6. How does HyperLogLog count distinct items in 12 KB, and how do you get weekly uniques from daily counters?
It hashes each item, uses the first bits to pick one of 16,384 registers, and records in each register the longest run of leading zeros seen. The harmonic mean of across registers estimates the count with a standard error of about 0.81%. Weekly uniques come from merging the seven daily HLLs with a per-register max, then counting.
7. Size a Count-Min Sketch for 0.1% error at 99% confidence. What can it not do?
Width , depth , about 53 KB of 32-bit counters. It never underestimates, but its error is absolute (), so counts of rare items are meaningless, and it cannot list frequent items without a companion heap.
8. How do LSM-tree engines use Bloom filters, and why might you turn off the last level's filter?
Each SSTable has a filter checked before the file is read, so missing keys cost memory lookups, not disk reads. The last level holds most data and filter memory; if most lookups hit existing keys, they read it anyway, so its filter saves little.
9. A filter in front of a database is suddenly letting 20% of non-existent keys through. What do you check?
Whether the element count has outgrown the design capacity (estimate it from the set-bit fraction), and whether the hash function, seed or parameters changed between writer and readers.
Further Reading
- Storage Engines — How Bloom filters are used in LSM-trees
- Redis Internals — Redis native HyperLogLog and Bloom filter modules
- Consistent Hashing — Another hash-based distributed systems primitive
- Distributed Locking — Probabilistic approaches to distributed coordination
- Burton H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors" (1970)
- Philippe Flajolet et al., "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" (2007)
- Bin Fan et al., "Cuckoo Filter: Practically Better Than Bloom" (2014)
- Graham Cormode and S. Muthukrishnan, "An improved data stream summary: the count-min sketch and its applications" (2005)