Bloom filters

A Bloom filter answers one question: "have I seen this item before?" It stores the answer in a few bits per item rather than the item itself. The trade is one-sided error. A "no" is always right. A "yes" is right most of the time, and wrong by a known, adjustable rate.

The big idea

A Bloom filter is a bit array of m bits, all zero at the start, plus k hash functions. Each hash maps an item to a position in the array.

• Insert: hash the item k times and set those k bits to 1.
• Query: hash the item k times and check those bits. If any bit is 0, the item was never inserted. If all bits are 1, it probably was. Other items may have set those same bits.

Walking through a query

Say m = 16 and the filter has already stored apple (bits 1, 4, 9) and pear (bits 4, 6, 12). Now query plum, which hashes to bits 1, 6 and 12.

bit:    1  4  6  9  12
state:  1  1  1  1   1     ← bits 1, 6 and 12 are all set
answer: "probably seen"    ← but plum was never inserted

Each bit was set by a different item, so the filter reports a false positive. A query that hits even one zero bit gets a definite "no".

You cannot delete from a plain Bloom filter. Clearing a bit may erase evidence of another item and create a false negative.

Sizing it

After inserting n items, the chance that a given bit is still 0 is about e^(−k·n/m). A false positive needs all k bits set:

FPR ≈ (1 − e^(−k·n/m))^k

For a target false positive rate p, the best choices are:

bits per item   m/n = −ln(p) / (ln 2)²       ≈ 1.44 × log₂(1/p)
hash functions  k   = (m/n) × ln 2

For p = 1%:

m/n = −ln(0.01) / (ln 2)² = 4.605 / 0.4805 = 9.59 bits per item
k   = 9.59 × 0.693 = 6.6, so 7 hash functions

Each tenfold drop in the error rate costs about 4.8 more bits per item.

For a crawler that has seen 1 billion URLs, a 1% filter takes 10⁹ × 9.59 bits ≈ 1.2 GB. An exact set of 1 billion URLs averaging 70 bytes needs at least 70 GB. The filter is about 60 times smaller. The price is that about 1 in 100 new URLs is wrongly skipped. For a crawler, that is usually fine. See designing a web crawler.

Code

This version uses double hashing. It derives all k positions from two hash values, h1 + i·h2. That gives the same false positive rate as k independent hashes and is how most production filters do it.

import hashlib, math

class BloomFilter:
    def __init__(self, n: int, fp_rate: float):
        self.m = math.ceil(-n * math.log(fp_rate) / math.log(2) ** 2)  # bits
        self.k = round(self.m / n * math.log(2))                       # hashes
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item: str):
        d = hashlib.blake2b(item.encode(), digest_size=16).digest()
        h1, h2 = int.from_bytes(d[:8], "big"), int.from_bytes(d[8:], "big")
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item: str):
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def __contains__(self, item: str) -> bool:
        return all(self.bits[p // 8] & (1 << (p % 8)) for p in self._positions(item))

bf = BloomFilter(n=1_000_000, fp_rate=0.01)
print(bf.m, bf.k)

Output:

9585059 7

Adding 1 million keys and then querying 100,000 keys that were never added gives a false positive rate of about 1.02%, which matches the formula.

Where Bloom filters run

• LSM-tree databases. RocksDB, LevelDB and Cassandra keep a filter per data file. A lookup checks the filter first and skips files that cannot hold the key. Many disk reads become one. RocksDB's usual setting of 10 bits per key gives about a 1% false positive rate. See LSM storage engines.
• CDNs. Akamai reported that roughly three-quarters of requested objects were requested only once. A Bloom filter lets a cache store an object only on its second request.
• Crawlers and feeds. "Have I seen this URL?" or "Have I shown this article to this user?"

Common mistakes

• Sizing for the average, not the maximum. Size for the largest n you expect.
• Expecting deletes. Use a counting filter or a cuckoo filter if items must be removed.
• Treating "yes" as proof. It means "probably". Confirm with the real lookup when the answer matters.

Check yourself

1. Why can a Bloom filter never miss an item that was inserted? Inserting sets all of the item's bits to 1, and bits are never cleared, so a later check always finds them set.
2. A filter for 1 million items at 1% error uses about 9.6 bits per item. What does a 0.1% target cost? About 14.4 bits per item, since each tenfold reduction adds about 4.8 bits.

Key takeaways

• A Bloom filter has no false negatives and a tunable false positive rate.
• Size it with m/n ≈ 1.44 × log₂(1/p) bits per item and k = (m/n) × ln 2 hashes.
• At 1% error, that is about 9.6 bits and 7 hashes per item.
• It fits in front of expensive lookups, such as disk reads in an LSM engine, where a rare false positive costs one extra read.

Further learning

Next, read the hub, probabilistic data structures, for the other structures and how to choose among them. Then read HyperLogLog for counting distinct items.