Bloom Filters
In short: a Bloom filter is m bits plus k hash functions. Inserting a key sets
its k positions; querying checks them, and if any is still 0 the key was
definitely never inserted, while all-1s means "maybe". Insert and query both cost O(k)
time, and the whole filter costs O(m) space, about 10 bits per key for a 1%
false-positive rate — far less than storing the keys themselves. It can never produce a
false negative, because nothing ever clears a bit, but it can be fooled into a false
positive once enough other keys have filled in the same positions.
Quarry writes records into segment files on disk. Looking a record up means asking each segment "do you have it?", and each question costs a disk read. That's fine when the answer is yes. It's pure waste when the answer is no, and most answers are no: a key lives in one segment, not in the twenty others you'd have to rule out.
What Quarry wants is a tiny in-memory summary per segment that can say "definitely not here" without touching the disk. It's allowed to sometimes say "maybe" wrongly, since that only costs a wasted read, but it must never say "not here" about a key that is there, because that would lose data. A Bloom filter is exactly that. It's a row of bits plus a few hash functions, and it costs about 10 bits per key for a 1% false-positive rate, however long the keys are.
How it works
A Bloom filter is an array of m bits, all 0 at the start, and k hash functions that
each map a key to a position in 0 … m − 1.
- Insert a key: compute its
kpositions and set those bits. - Query a key: compute the same
kpositions. If any of those bits is 0, the key was never inserted. That's a certain "no". If all are 1, the answer is "maybe". The bits might have been set by other keys.
Step through a 16-bit filter with k = 3. Three records go in, then two lookups
happen, one of which is fooled:
Inserts only ever set bits. A query stops at the first 0 it finds, and it can be fooled only when other keys have set every one of its bits.
Insert rec-11. Its three hashes land on 4, 3 and 2, so those bits are set. 16 cells.
Two facts fall out of this picture:
- No false negatives. An inserted key's bits were set, and nothing ever clears a bit, so its query always finds all ones.
- False positives grow as the filter fills. The more bits are 1, the likelier a
random key's
kprobes all land on ones.
bits = 0
for p in (3, 9, 3):
bits |= 1 << p
print(bin(bits).count("1"), bits >> 9 & 1)Hashing you can put on disk
Python's built-in hash() of a string is salted per process. Run the same program
twice and hash("rec-11") is different, which is a deliberate defence against attacks
on dicts. A filter saved to disk next to its segment has to give the same positions
tomorrow, so Quarry uses a fixed hash. Here it's a 32-bit FNV-1a, a simple hash made
of XOR, multiply and mask, followed by one XOR-shift that folds the well-mixed high
bits into the weak low ones:
The mask & 0xFFFFFFFF is the fixed-width rule from lesson 1. It makes Python's
unbounded multiply behave like a 32-bit register.
You don't need k independent hash functions. Two hashes h1 and h2 are enough,
because position i can be (h1 + i·h2) % m. That's double hashing, and it's proven
to give essentially the same false-positive rate as k independent hashes. Forcing h2
odd stops it from getting stuck on a few positions when m is a power of two.
Storing the bits
For a small m, a Python int is a perfectly good bitset: bits |= 1 << p sets a bit
and bits >> p & 1 tests one. A real filter has millions of bits and lives in a
bytearray. Bit p is bit p & 7 of byte p >> 3, which is the same shift-and-mask
arithmetic as lesson 2, one level down:
A query has to check all k bits. This one gets it the wrong way round:
It prints [True, True, False]. rec-6 was never inserted, but one of its bits happens to be set, and one set bit is enough for this version to say maybe.
Build one yourself. Every insert and every query below is drawn. Change M and K,
or add more keys, and watch the filter fill up and start saying maybe to strangers:
Your filter. Inserts set k bits, and a query stops at its first 0 or says maybe when every probe finds a 1.
How wrong is "maybe"?
After inserting n keys into m bits with k hashes, a given bit is still 0 with
probability about e^(−kn/m). A false positive needs all k probes to hit ones, so
p ≈ (1 − e^(−kn/m))^k
Only the ratio m/n, bits per key, matters. More hashes set more bits, which
fills the filter faster but also means a query has more chances to hit a 0. So there's
a best k. Quarry gives each segment's filter 10 bits per key:
hashes k |
false-positive rate at 10 bits per key |
|---|---|
| 2 | 3.29% |
| 4 | 1.18% |
| 6 | 0.84% |
| 8 | 0.85% |
| 10 | 1.02% |
The lowest rate sits between 6 and 8. The best k is (m/n)·ln 2 ≈ 0.69 × 10 = 6.9, the point where about half the bits end up set. A filter that's half ones carries the most information per bit.
import math
print(round((1 - math.exp(-7 * 1 / 10)) ** 7, 4))Interview corner — sizing a filter
A dedupe service must remember 50 million seen ids and may wrongly report "seen" at most
1% of the time. How much memory does it need, and how many hash functions? Invert the
formula. Bits per key is −ln p / (ln 2)², and k = (m/n) · ln 2:
That's 57 MB, where a Python set of 50 million ints would take several gigabytes. The
filter never stores the ids themselves, only a smear of bits. That's also why it can't
list its contents, can't count exactly, and can't forget a key. The explain exercise
takes that last point further.
Quick practice
bits = 0
for p in (2, 5, 9):
bits |= 1 << p
print(all((bits >> p) & 1 for p in (2, 5, 9)), all((bits >> p) & 1 for p in (2, 5, 6)))It prints 1 — all four probes land on the same bit. Fix positions so a key always gets k different positions.
🎯 Your turn
Write bloom_lookup(stored, queries, m, k). Build an m-bit filter from the keys in
stored using the lesson's positions(key, m, k) (it's in the starter). Return a list
of booleans, one per query: True for "maybe" and False for "definitely not".
bloom_lookup(["rec-11", "rec-42", "rec-97"], ["rec-42", "rec-6", "rec-67"], 16, 3)→[True, False, True], where the last one is the false positive from the picture
Hint — set bits with bits |= 1 << p for every position of every stored key. A
query is True only if bits >> p & 1 for all its positions.
Then press ▶ Run, try the Live App chips, and hit ✓ Check. ✅