Loading...
Loading...
Space-efficient probabilistic data structure for set membership
Probabilistic Set Membership Test
You already know from the storage-engines module how log-structured stores flush sorted files called SSTables and check each one on a missing-key read, and from the caching module how a small piece of memory can absorb thousands of wasted disk trips. A Bloom filter, a small bit array plus a few hash functions that remembers which items were added without storing the items themselves, answers one question, have I seen this thing before, from a few bytes instead of a database trip. It is allowed one kind of mistake: sometimes saying yes when the truth is no. It never says no when the truth is yes.
Picture a bouncer with a smudged guest list, the one comparison we will use here. If your name is clearly absent he waves you past the long queue to the cheap check, and if your name might be there he sends you inside for a proper ID lookup. In the lab above, add a few hundred names, then test strangers and watch certain no answers skip the slow lookup while yes answers always pay for a second check, because a no is certain and a yes is only a maybe.
The deal, precisely: a no is certain, so skip the expensive check. A yes means go verify against the real store.
Suppose you run recommendations for a content site. Each reader has seen thousands of articles, and every recommendation pass must exclude the seen ones. The naive fix stores every seen id in a hash set (a table that keeps the actual values so lookup is exact). That works on a laptop and fails on ten million readers, because the memory bill arrives all at once, which is why we rejected exact sets for this pre-check despite their perfect accuracy. Run the arithmetic yourself.
In the lab above, raise the item count with fixed memory and watch the false yes rate climb, because more smudges overlap. That slope is the whole trade you are buying.
A bit array is a row of single 0-or-1 slots, all starting at 0. A hash function is a recipe that turns any input like an article id into a number, so hash modulo size picks one slot. Adding means computing a few such slots per item and flipping them to 1. Checking means recomputing the same slots: any 0 proves the item was never added, while all 1s only proves it might have been, because other items may have flipped those same slots.
def add(element):
for i in 1 to k:
position = hash_i(element) mod m
bit_array[position] = 1def contains(element):
for i in 1 to k:
position = hash_i(element) mod m
if bit_array[position] == 0:
return false # Definitely NOT in set
return true # Probably in setIf any slot is 0, the item was definitely never added. If all slots are 1, it might have been added or the slots were set by other items.
Try this shape in the lab: keep adding fruits and testing new ones until a stranger first reports yes. Small arrays collide fast, which is exactly the lesson the math below prices.
After inserting n items with k hash functions into m slots, the chance a given slot is still 0 is (1 - 1/m) raised to k×n, which is close to e raised to -k×n/m. A stranger reports yes only if all k of its slots are 1, so the false yes chance is that filled fraction raised to k. Two consequences follow: more slots per item lowers the rate, and for a fixed size there is one best k, found where the math bottoms out at k = (m/n) × 0.693.
After inserting n items using k hashes into m slots:
Work it: for a 1% target you need m/n near 9.6 slots per item, and k near 9.6 × 0.693 which rounds to 7 hashes. For 0.1% you need about 14.4 slots per item and about 10 hashes. In the lab, set slots per item to 10, sweep k from 2 to 12, and watch the measured false rate dip near 7 and rise on both sides, because too few hashes collide too easily and too many fill the array too fast.
Bloom filters need hashes that are fast and spread outputs evenly across the slots, meaning every slot is about equally likely, and behave as if independent, meaning knowing one slot tells you nothing about the next. Heavyweight cryptographic hashes (recipes designed to resist attackers, like SHA-256) waste time here because no attacker is being resisted. Simple non-cryptographic hashes (fast recipes with good spreading but no attack resistance) are the right tool, and in practice teams use just two of them to imitate k.
Compute two base hashes h1 and h2 once, then form slot i as h1 + i × h2. This trick, published as double hashing, behaves closely enough to k independent hashes for filters while costing only two hash evaluations. Storage engines that check filters on every read use it precisely because hash time sits on the hot path.
In the lab, compare k real hashes against two-hash derivation at the same m and n and watch the curves nearly overlap, which is why production code takes the cheaper path.
Standard limit: you cannot erase one item, because a 1 slot may be shared by several items and clearing it would create false no answers, the one error a Bloom filter promises never to make.
A counting Bloom filter replaces each bit with a small counter, usually 4 bits holding 0 to 15. Adding increments the k counters, erasing decrements them, and checking asks whether all k counters sit above 0. The edge case is overflow: a counter stuck at 15 never comes back down, so later erases under-count and the false yes rate drifts up. Size the counters so saturation stays rare, or accept the drift for workloads that mostly add.
class CountingBloomFilter:
def __init__(self, m, k, counter_bits=4):
self.m = m
self.k = k
self.max_count = (1 << counter_bits) - 1
self.counters = [0] * m
def add(self, element):
for pos in self._get_positions(element):
if self.counters[pos] < self.max_count:
self.counters[pos] += 1
def remove(self, element):
for pos in self._get_positions(element):
if self.counters[pos] > 0:
self.counters[pos] -= 1
def contains(self, element):
return all(self.counters[pos] > 0
for pos in self._get_positions(element))Log-structured stores (databases that buffer writes in memory and later flush sorted files to disk) attach one filter per file. Before touching disk for a missing key, the reader asks the filter, and a no avoids the whole read. Setting the target to 1% means about 9.6 bits per key, so a million keys cost just over a megabyte to save thousands of disk trips.
Delivery networks (servers spread near users that cache popular content) see many objects requested exactly once. The rule is simple: first sighting only flips filter bits and still serves from the far origin, while a filter yes on the second sighting earns a cache slot. One arithmetic check saves a cache full of orphans.
Data-parallel engines (systems that run one query across many machines) build a filter from the small table, mail a 200-kilobyte copy everywhere, and drop most of the big table before the expensive shuffle. Skipping 950 million of 1 billion rows turns a network-bound join into a local one, at the price of a few false yeses that the join itself discards.
Some relational databases offer a Bloom index that packs every column of a row into roughly 80 shared bits instead of maintaining many tree indexes. Multi-column equality searches share one small structure and accept rechecking the few false yeses against the real rows.
Ask the tiny lossy structure first and pay for certainty only on maybe. No is free and final, yes just means go check properly, and the lab above shows how memory buys fewer false yeses almost linearly. If your workload starts deleting items as fast as it adds them, how long can a structure that cannot erase stay useful before its yeses stop meaning anything?
Try this in the playground
Open a template and build it yourself — then take a quiz.