A cheap "no"
A database stores a billion keys on disk. A request arrives for a key that does not exist. To find that out the hard way, the database reads the disk, finds nothing, and has wasted a slow operation.
What if a tiny structure in memory could say, almost for free, "that key is definitely not here, do not bother looking"?
That is a Bloom filter. It answers one question, "is this item in the set?", and it gives one of two answers:
- Definitely not. Always correct.
- Probably yes. Usually correct, occasionally wrong.
It never stores the items themselves. A billion keys can be covered in a little over a gigabyte, with about 1 wrong "probably yes" in 100.
How it works
Start with a row of bits, all 0
Just bits. No keys, no values.
To add an item, hash it several ways
Use three different hash functions. Each one gives a position in the row.
Set those bits to 1
That is the whole of "adding". The item itself is thrown away.
To check an item, hash it the same way and look at those bits
If any of them is 0, the item was never added. If all of them are 1, it probably was.
Start. 16 bits, all 0. The filter never stores the words themselves, only these bits.
- Bits set
- 0 / 16
- Answer
- –
Why "no" is certain and "yes" is not
A 0 bit is proof. Adding an item sets all of its bits, and nothing ever sets a bit back to 0. So if one of an item's bits is 0, that item cannot have been added.
All 1s is only a hint. Bits are shared. Other items may have set those same positions between them. In the last check of the animation, a word that was never added passes, because the words that were added happen to cover all three of its bits. This is a false positive.
There are no false negatives. An item that was added always passes.
Example
Using both answers
A request arrives for key user:981. Ask the filter first.
"Definitely not": answer "not found" immediately. No disk read.
"Probably yes": do the real lookup. Most of the time the key is there. Once in a while it is not, and you have wasted one read, which is what you would have done anyway without the filter.
class BloomFilter:
def __init__(self, size, hash_count):
self.bits = [False] * size
self.hash_count = hash_count
def _positions(self, item):
return [hash((i, item)) % len(self.bits) for i in range(self.hash_count)]
def add(self, item):
for position in self._positions(item):
self.bits[position] = True
def might_contain(self, item):
return all(self.bits[position] for position in self._positions(item))Tuning it
The more bits are 1, the more likely a random item finds all of its bits set. So the false positive rate depends on how full the filter is.
| You change | Effect |
|---|---|
| More bits | Fewer false positives, more memory |
| More items added | More false positives |
| More hash functions | Better up to a point, then worse, because each item fills more bits |
A common rule of thumb: about 10 bits per item with 7 hash functions gives roughly a 1% false positive rate.
Good at
- Tiny: a few bits per item, whatever the size of the items
- Adding and checking take the same short time however many items there are
- A "no" is always right
Where it bites
- A "yes" can be wrong
- You cannot list the items or get one back
- You cannot remove an item: clearing its bits could break other items
Where you will meet it
- Databases keep one per file on disk, to skip files that cannot contain a key.
- Caches use one to avoid asking for keys that were never stored.
- Sign-up forms can check "is this username taken?" against millions of names without a database query for most misses.
Key takeaways
- A Bloom filter is a row of bits that remembers which items were added, without storing them.
- Adding an item sets a few bits. Checking an item looks at the same bits.
- Any 0 bit means definitely not. All 1s means probably yes.
- False positives happen because items share bits. False negatives never happen.
- It is used in front of something slow, to skip lookups that would find nothing.