Bloom filters

A Bloom filter is a small bit array that answers one question very cheaply: is this key definitely not in the set? It never says “no” to a key you added, but now and then it says “probably yes” to one you didn’t. With about 10 bits per key that mistake happens roughly 1% of the time, however long the keys are, so a filter for a billion keys fits in about 1.2 GB of RAM and lets you skip most of the expensive lookups that would have found nothing.

Picture it first: the parcel office pegboard

A railway parcel office keeps its parcels in a godown two kilometres away. All day people walk up and ask, “Is there a parcel for my mobile number?” Most of them have nothing waiting, and every trip to the godown takes twenty minutes.

So the clerk keeps a pegboard with 1,000 numbered holes. When a parcel arrives, he applies three fixed rules to the recipient’s number (say “last three digits”, “first three digits reversed” and “sum of the digits times 37”), gets three hole numbers, and puts a peg in each. When someone asks, he applies the same three rules and looks at those three holes:

• Any hole empty? No parcel for that number ever arrived. He says “no” on the spot, and he is always right.
• All three pegged? Probably a parcel, so he walks to the godown. Usually it is there. Occasionally the three pegs were put in by three other parcels, and the walk is wasted.

He also can’t pull pegs out when a parcel is collected, because each peg might be shared with a parcel that is still waiting.

Map it back: the godown is your disk, database or remote service; the pegboard is the bit array; the three rules are k hash functions; a wasted walk is a false positive; and the stuck pegs are why a plain Bloom filter can’t delete. The board is tiny compared with a list of numbers, and it never turns away a customer who really has a parcel.

How a Bloom filter works

A Bloom filter has two parts: an array of m bits, all starting at 0, and k hash functions, each mapping a key to a position from 0 to m − 1.

• Add a key: compute its k positions and set those bits to 1. A bit that is already 1 stays 1.
• Check a key: compute the same k positions. If any of them is 0, the key was definitely never added. If all are 1, the key is probably present.

That is the whole data structure. It stores no keys, no lengths and no pointers, so a 4-byte user ID and a 2 KB URL cost exactly the same k bits.

Why there are no false negatives. Bits only ever go from 0 to 1. Adding a key set all k of its bits and nothing clears them, so a later check of that key always finds k ones. Everything you build on a Bloom filter rests on this guarantee, which is why deleting is hard (more on that below).

Why there are false positives. A check can find all k bits set for a key that was never added, because other keys set those bits between them. The fuller the array, the likelier that is, and most of what follows is about keeping that probability where you want it.

The idea is older than most databases. Burton Bloom described it in 1970 for a hyphenation program: of about 500,000 words, roughly 450,000 could be hyphenated by simple rules and 50,000 needed a dictionary on disk. A filter of the 50,000 exceptions that allowed 1 error in 16 fitted in under 300,000 bits of core memory. Only the exceptions plus the false positives still went to disk, 50,000 + 450,000 / 16 ≈ 78,000 words, so disk accesses fell by about 84%. The shape of the trick hasn’t changed since: a small structure in memory guards a big, slow one.

The maths: false positives, k and m

Write n for the number of keys added, m for the number of bits, and k for the number of hash functions, and assume each hash picks a position uniformly at random.

One hash of one key misses a particular bit with probability 1 − 1/m. After n keys with k hashes each, that bit is still 0 with probability (1 − 1/m)^(kn) ≈ e^(−kn/m). A key that was never added is a false positive only if all k of its positions are 1, so:

false-positive rate     p ≈ (1 − e^(−kn/m))^k
best number of hashes   k = (m/n) · ln 2            ≈ 0.693 × bits per key
bits per key needed     m/n = −ln p / (ln 2)²       ≈ 1.44 × log2(1/p)

Two useful facts fall out of the middle line. At the best k, e^(−kn/m) = 1/2, so about half the bits are set when the filter holds its design load, and the false-positive rate is simply (1/2)^k. More hashes is not always better: too few and each check tests too little; too many and every key fills the array faster than it helps.

Now plug in numbers, using (ln 2)² ≈ 0.4805:

• 1%: ln 100 = 4.605, so m/n = 4.605 / 0.4805 ≈ 9.6 bits per key, and k = 9.6 × 0.693 ≈ 6.6, so 7 hashes.
• 0.1%: ln 1000 = 6.908, so m/n ≈ 14.4 bits per key and k ≈ 10.
• Each further 10× improvement costs another ln 10 / 0.4805 ≈ 4.8 bits per key.

These match the figures Redis documents for BF.RESERVE (9.585 bits and 7 hashes at 1%, 14.378 bits and 10 hashes at 0.1%) and RocksDB’s rule that about 10 bits per key gives roughly 1%.

The last column is just 100,000,000 × bits per key ÷ 8. Notice what is missing from the table: the key size. The filter’s memory depends only on how many keys you add and the error rate you accept.

Worked example: a billion usernames

A sign-up page wants to show “✓ available” as the user types. You have 1 billion existing handles averaging 16 bytes.

• An exact set in Redis: Redis’s documentation estimates about 192 bits (24 bytes) of overhead per set member plus the value, so 1e9 × (24 + 16) B ≈ 40 GB. That is a sharded cluster of its own.
• A Bloom filter at 1%: 1e9 × 9.6 bits ≈ 9.6e9 bits ≈ 1.2 GB, with 7 hashes. It fits in one process, or ships to every API server.
• At 0.1%: 1e9 × 14.4 bits ≈ 1.8 GB.

That is roughly 33× less memory at 1%. The flow: if the filter says “definitely not”, show “available” immediately with no database call; if it says “maybe”, ask the database, which is the only component allowed to say “taken”. The final sign-up still relies on a unique index (see database constraints), because the filter is a fast path, not a guarantee.

The same arithmetic for a crawler that has seen 100 million URLs averaging 80 bytes: a hash set needs about 1e8 × (24 + 80) B ≈ 10.4 GB, a 1% filter about 1e8 × 9.6 bits ≈ 120 MB. More of this kind of estimate is in back-of-envelope estimation.

Getting k hashes from two

Seven independent hash functions per lookup sounds expensive. In practice you compute one good hash and derive the rest. Adam Kirsch and Michael Mitzenmacher showed that positions of the form g_i(x) = h1(x) + i · h2(x) mod m, for i from 0 to k − 1, give the same asymptotic false-positive rate as k independent hashes. One 128-bit hash split into two 64-bit halves gives you h1 and h2.

import hashlib, math

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

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

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

    def might_contain(self, key):
        return all(self.bits[pos // 8] >> (pos % 8) & 1
                   for pos in self._positions(key))

BloomFilter(n=1_000_000, p=0.01) allocates 9,585,059 bits (about 1.2 MB) and picks k = 7. After adding a million keys, checking 200,000 keys that were never added gave a measured false-positive rate of 0.97%, right on the formula.

Production filters add two refinements. Squid’s cache digests got k = 4 by cutting a single 128-bit MD5 hash into four 32-bit pieces. And RocksDB keeps all k probes for a key inside one CPU cache line (512 bits), so a check costs one cache miss instead of up to k; at 10 bits per key this raises the false-positive rate only from about 0.84% to 0.95%, which RocksDB considers acceptable for the speed-up.

Where Bloom filters earn their keep

The pattern is always the same: a cheap in-memory check in front of an expensive operation that usually finds nothing.

LSM-tree reads: Bigtable, Cassandra and RocksDB

Log-structured merge (LSM) trees never update data files in place. Writes go to an in-memory memtable, which is flushed to immutable sorted files called SSTables, and background compaction merges them later (the full read and write paths are in Reads and writes: how databases store and fetch data). A point read checks the memtable and then every SSTable that might hold the key, newest first. Without help, a read for a key that doesn’t exist touches every file.

So each SSTable carries a Bloom filter of its keys, held in memory, and a read asks each filter before it opens the file.

• Bigtable (2006) let clients turn on Bloom filters per locality group. The paper reports that a small amount of tablet-server memory spent on filters drastically cut disk seeks, and that most lookups for rows or columns that don’t exist never touched disk.
• Cassandra builds a filter per SSTable, keeps it off the Java heap, and lets you tune bloom_filter_fp_chance per table. The default is 0.01, or 0.1 for tables using LeveledCompactionStrategy. Its docs advise lower values when you have spare RAM and slow disks, and much higher ones for analytics tables that only ever scan.
• RocksDB embeds a filter in every SST file, commonly at about 10 bits per key (NewBloomFilterPolicy(10)), and builds a fresh filter whenever compaction writes a new file. Its wiki notes that SST filters commonly use around 10% of a machine’s RAM.

The arithmetic is why they are worth it. A missing key checked against 8 SSTables costs 8 random reads without filters; with 1% filters it costs 8 × 0.01 = 0.08 reads on average. One limit: filters help point lookups only. A range scan has no single key to test, though RocksDB offers prefix filters for prefix seeks.

CDNs: don’t cache one-hit wonders

Akamai engineers analysed two days of logs from one 45-server cluster: about 74% of roughly 400 million objects were requested only once. Caching those “one-hit wonders” wastes disk space and disk writes, and pushes popular objects out. Their fix is a cache-on-second-hit rule. On a miss, the server checks a Bloom filter of recently requested URLs. If the URL is not there, it serves the object without caching it and adds the URL to the filter; if it is there, this is the second request, so it caches the object.

In a production trial on about 47 servers, turning the filter on lifted the byte hit rate from about 74% to 83% and cut disk writes from 10,209 to 5,738 per second, a 44% drop. A false positive only means an object gets cached one request early, which is harmless. This sits alongside the cache eviction policy rather than replacing it: the filter decides what gets in, eviction decides what leaves. More on edge caches in content delivery network (CDN).

Web crawlers: “have I seen this URL?”

A crawler discovers far more links than it can fetch, and most are repeats. A filter of every URL already queued answers “definitely new” from memory. Here a false positive means a genuinely new URL is skipped, which at 1% is usually fine for a broad crawl; for sites that must be complete, re-check the “maybe” against the URL store. The full design is in Design a web crawler.

Front doors for lookups that usually miss

• Availability checks: usernames, coupon codes, and the random codes a URL shortener generates. “Definitely free” returns at once; “maybe taken” goes to the database.
• Cache penetration: requests for IDs that don’t exist miss the cache every time and land on the database, sometimes deliberately. A filter of valid IDs in front of the cache turns them away (see hot keys, cache stampede and invalidation).
• Blocklists: a mail gateway or client app keeps a local filter of known-bad URL or file hashes. “Definitely not” proceeds with no network call; “maybe” asks the full service.
• Cache summaries between servers: in the Summary Cache design, and in Squid’s cache digests, proxies exchange Bloom filters of what they hold, so a proxy asks a peer for an object only when that peer’s filter says “maybe”.

Deleting: counting Bloom and cuckoo filters

You can’t delete from a plain Bloom filter by clearing a key’s k bits, because other keys may share them. Clear a shared bit and a key you still hold now reads as “definitely not”, a false negative, which breaks the one guarantee you had. Two structures fix this.

Counting Bloom filter. Replace each bit with a small counter. Adding increments the key’s k counters, deleting decrements them, and a check asks whether all k are non-zero. Broder and Mitzenmacher’s survey shows that 4-bit counters suffice for most uses (the chance that any counter ever reaches 16 is at most 1.37 × 10⁻¹⁵ × m), but that is still 4× the memory of a plain filter: about 38 bits per key for 1%. And you must only delete keys you actually added; deleting a stranger decrements other keys’ counters.

Cuckoo filter. Bin Fan, David Andersen, Michael Kaminsky and Michael Mitzenmacher proposed it in 2014. Instead of bits, it stores a short fingerprint of each key (around 10 bits for 1%) in a table of buckets with 4 slots each. Every key has two candidate buckets, i1 = hash(x) and i2 = i1 ⊕ hash(fingerprint). The XOR means either bucket can be computed from the other plus the fingerprint, so when a new key finds both buckets full, it can evict (“kick”) a resident fingerprint to that fingerprint’s other bucket without knowing the original key. A check reads just two buckets; a delete removes one matching fingerprint from one of them.

What you gain with a cuckoo filter: deletes, at most two bucket reads per check, and less memory than a Bloom filter when you want low error. The paper’s tables fill to about 95% with 4-slot buckets, and with its “semi-sorting” trick a cuckoo filter needs fewer bits per key than a space-optimised Bloom filter whenever the target rate is below about 3%. What you pay: inserts can fail when the table is nearly full (the paper gives up after 500 kicks), so you must size it or rebuild it; the same key inserted more than 8 times (2 buckets × 4 slots) overflows; and, as with counting filters, you may only delete keys you inserted. Redis sums up the practical split: Bloom filters are faster for inserts, cuckoo filters are quicker for checks and allow deletions.

When the filter fills up

A Bloom filter has no “full” state. You can keep adding keys forever; it just gets worse. The false-positive rate depends on how many keys are in it at the moment you check, so a filter sized for a million keys at 1% slides quickly once you go past a million.

Watch the fill ratio (keys added against capacity, or the fraction of bits set) and act before it drifts. You have four options:

• Size for the future. If you know the growth, reserve 2–3× the capacity up front. Memory grows linearly with capacity, so headroom is cheap.
• Rebuild. Build a new, bigger filter from the source of truth (the SSTable’s keys, the users table) and swap it in. You can’t grow a filter from its own bits, because it doesn’t store the keys. You can halve one whose size is a power of two by OR-ing its two halves, which is handy for shipping it over a network.
• Stack filters. Scalable Bloom filters, from Paulo Sérgio Almeida and colleagues (2007), chain plain filters: when one reaches its fill limit, add a new, larger one with a tighter error target, and check all of them. If each new filter’s error target is r times the previous one (0 < r < 1), the compound rate stays below P0 / (1 − r) however many you add.
• Rotate by time. For “seen recently” questions, keep two filters, current and previous. New keys go into the current one, checks consult both, and when the current one fills, it becomes the previous one and the old previous one is thrown away. This is how the CDN rule above forgets URLs nobody has asked for lately.

Bloom filters in Redis

Redis Open Source includes probabilistic types (Bloom and cuckoo filters, count-min sketch and others). You give a Bloom filter its error rate and capacity, and Redis does the sizing maths:

# 50M handles at 0.1%: 50e6 × 14.4 bits ≈ 90 MB, 10 hash functions
BF.RESERVE handles 0.001 50000000
BF.ADD     handles "asha_k"          # (integer) 1 → newly added
BF.ADD     handles "asha_k"          # (integer) 0 → may already be there
BF.EXISTS  handles "asha_k"          # (integer) 1 → probably present
BF.EXISTS  handles "meera_99"        # (integer) 0 → definitely absent
BF.MADD    handles "ravi" "kiran"    # several adds in one round trip

By default a Redis Bloom filter scales: when it reaches capacity it stacks a new sub-filter, EXPANSION times larger than the last (default 2), with extra hash functions so the overall error stays near the target. Adds stay fast, but a check for a missing key must test every sub-filter, so read latency grows with the number of layers. If you know your size, reserve it; NONSCALING makes the filter return an error at capacity instead of growing.

Three practical notes:

• One filter is one key, so it lives on one shard of a Redis cluster and every check for it lands on that node. For a filter too large or too hot for one node, split the key space: route each key by hash to one of N filters, each sized for n / N keys. RocksDB’s documentation points out that this doesn’t change the overall false-positive rate as long as each filter is sized for the keys it receives.
• A server-side filter costs a round trip per check. For the hottest paths (every request through a gateway, every database read), keep a copy in process memory and refresh it, or let the storage engine do it, as Cassandra and RocksDB do.
• Filters merge by OR. Two filters with the same size and hash functions can be OR-ed bit by bit, and the result is exactly the filter of the union. Shards can build their own and a coordinator can combine them.

Choosing a membership structure

Going deeper: limits and failure modes

Bloom filters are simple, not optimal

Any structure with false-positive rate p needs at least log2(1/p) bits per key; a Bloom filter needs 1.44 × log2(1/p), about 44% more. Newer designs close part of the gap. RocksDB’s Ribbon filter reaches the same 1% with about 7 bits per key instead of 9.9, roughly 30% less memory, but spends 3–4× more CPU, mostly while building filters during compaction. RocksDB argues that is a good trade when filters take around 10% of RAM and well under 1% of CPU.

Bad hashes break the maths

The formulas assume positions behave randomly. A weak hash that maps similar keys (sequential IDs, URLs with a shared prefix) to nearby positions sets fewer distinct bits than expected, and the real error rate drifts away from the formula. Use a well-mixed non-cryptographic hash such as MurmurHash3 or xxHash. And if attackers choose the keys and know your hash function, they can craft keys that land on bits that are already set; a secret per-deployment seed makes that impractical.

Wrong question, wrong tool

• Mostly hits: if 95% of lookups are for keys that exist, the filter says “maybe” almost every time and saves almost nothing. RocksDB can skip filters on the last level (optimize_filters_for_hits) for workloads where lookups usually find their key.
• Ranges: a filter tests exact keys; it can’t tell you whether any key between A and M exists.
• Counting: a Bloom filter can’t tell you how often a key appeared or how many distinct keys there are. Those are jobs for the count-min sketch and HyperLogLog, covered in Count-min sketch and HyperLogLog.

Budget the memory like a cache

Filters are RAM you must plan for. A Cassandra node holding 2 billion partition keys across its SSTables at the default 0.01 needs about 2e9 × 9.6 bits ≈ 2.4 GB of off-heap memory for filters, more if the same key appears in several SSTables. Raising bloom_filter_fp_chance to 0.1 roughly halves that (4.8 bits instead of 9.6), at the price of ten times as many wasted reads.

Cheat sheet

How to say it in the interview

“Most lookups here are for keys that don’t exist, so I’ll put a Bloom filter in front of the store. It’s a bit array with k hash functions: adding a key sets k bits, checking tests them, and any zero means the key is definitely absent, so we skip the disk or database call. A yes can be a false positive, so a yes still goes to the store, which has the final word. At about 10 bits per key we get roughly 1% false positives: for 100 million keys that’s 120 MB instead of around 10 GB for a hash set. I’ll size it for expected growth, alert on the fill ratio, and rebuild or rotate it rather than let the error climb. If we need deletes, I’d use a cuckoo filter instead.”

Why not just use a hash set? A hash set stores the keys, so its memory grows with key length: about 40 bytes per 16-byte key in Redis, around 10 GB for 100 million URLs. A Bloom filter needs about 10 bits per key regardless of length, so it fits on every server. Use the hash set when the set is small or you need exact answers or the stored values.

How do you delete from a Bloom filter? You can’t clear bits, because they are shared and you’d create false negatives. Use a counting Bloom filter (4-bit counters, 4× the memory) or a cuckoo filter (fingerprints in one of two buckets; a delete removes one copy), and only delete keys you actually added. Or rebuild the filter periodically from the source of truth.

How do you size it? Pick the expected number of keys n and the false-positive rate p you can tolerate, then m = −n · ln p / (ln 2)² bits and k = (m/n) · ln 2. Rule of thumb: 1% costs 9.6 bits per key and 7 hashes, and every 10× improvement costs 4.8 more bits.

What happens when it fills up? It never refuses a write; the false-positive rate climbs, to about 16% at twice the design load. Size for growth, monitor the fraction of bits set, and either rebuild a bigger one or use a scalable filter that stacks larger sub-filters (Redis does this by default) at the cost of slower checks. For “seen recently” data, rotate two filters.

How would you build a distributed Bloom filter? For read-mostly data, build it once and ship a copy to every node (it’s small), so checks stay local. For a filter too big or too hot for one machine, partition keys by hash across N filters, each sized for its share; the false-positive rate doesn’t change. Filters with identical size and hash functions can be OR-ed into the filter of the union, so shards can build their own and merge them.

Where to go next

• Count-min sketch and HyperLogLog: the sibling sketches that estimate how often and how many.
• Reads and writes: how databases store and fetch data: the LSM read path that Bloom filters speed up.
• Cassandra and DynamoDB: where bloom_filter_fp_chance is tuned in production.
• Design a key-value store: SSTables, compaction and filters in a complete design.
• Design a web crawler: the URL-seen test at billions of URLs.
• Caching 101: where admission rules such as cache-on-second-hit fit in a caching strategy.
• Redis: Bloom filters and HyperLogLog alongside the core data structures.

References and further reading

1. Space/Time Trade-offs in Hash Coding with Allowable Errors (Bloom, CACM 1970)dl.acm.orgThe original paper: trading a small error rate for a much smaller in-memory hash area, and the 500,000-word hyphenation example.
2. Network Applications of Bloom Filters: A Survey (Broder and Mitzenmacher, Internet Mathematics, 2004)eecs.harvard.eduThe false-positive derivation, optimal k = ln 2 · m/n, union by OR, halving, and why 4-bit counters suffice for counting filters.
3. Less Hashing, Same Performance: Building a Better Bloom Filter (Kirsch and Mitzenmacher, 2008)eecs.harvard.eduProof that two hash functions combined as h1 + i·h2 give the same asymptotic false-positive rate as k independent ones.
4. Cuckoo Filter: Practically Better Than Bloom (Fan, Andersen, Kaminsky and Mitzenmacher, CoNEXT 2014)cs.cmu.eduPartial-key cuckoo hashing, 95% load with 4-slot buckets, deletion rules, and the under-3% crossover against Bloom filters.
5. Scalable Bloom Filters (Almeida, Baquero, Preguiça and Hutchison, 2007)gsd.di.uminho.ptStacking filters with geometrically tighter error targets so the compound false-positive rate stays bounded as the set grows.
6. Algorithmic Nuggets in Content Delivery (Maggs and Sitaraman, ACM SIGCOMM CCR, 2015)users.cs.duke.eduAkamai’s one-hit-wonder data, the cache-on-second-hit rule with rotating Bloom filters, and the measured hit-rate and disk-write changes.
7. Bigtable: A Distributed Storage System for Structured Data (Chang et al., OSDI 2006)static.googleusercontent.comPer-locality-group Bloom filters that let most lookups for missing rows skip disk.
8. Apache Cassandra documentation: Bloom filterscassandra.apache.orgPer-SSTable filters stored off-heap and the bloom_filter_fp_chance defaults and tuning advice.
9. RocksDB wiki: RocksDB Bloom Filtergithub.comBits per key versus false-positive rate, cache-line-local filters, Ribbon filters and sharding filters without changing the error rate.
10. Redis documentation: Bloom filterredis.ioBF.RESERVE / BF.ADD / BF.EXISTS, the sizing formulas, sub-filter scaling with EXPANSION and NONSCALING, and set memory for comparison.