Bloom Filters

TL;DR: Bloom filters (and friends) are a family of probabilistic data structures that answer the question "is this element in the set?" with no false negatives, a bounded false-positive rate, and a small memory footprint: about 14 bits per element at a 0.1% false-positive rate, no matter how long the elements are.

The problem

Let's say you are building an application with millions of users with unique usernames. You get a request with a username and want to check if it exists before allowing a response.

You could send a select query to the database, but that might not be reasonable if you don't want to overload it (and accessing disk is a bit slow).

What about storing the usernames in a hashset in memory (e.g. C++ unordered_set)? Now here comes the interesting part: hashsets use O(n) memory with a big constant. Storing 1 billion strings (don't ask me why you would have a billion users, just follow the example, it generalizes to other data) of 10-20 characters costs around 10 GB to 20 GB of memory, and that's ignoring the overhead of the data structure itself.

So the question is: can we do better on memory without sacrificing fast lookups?

The answer is yes, you can use a Bloom filter.

A Bloom filter answers this exact question with no false negatives (if it says the user doesn't exist, then they don't exist). If it says the user exists, there is a small probability that they actually don't, but we can accept that to save memory :D

How do they work?

A Bloom filter uses an array of m bits and k hash functions.

When an element is added, we hash it with each of the k hash functions and, for each result, set the bit at position hash % m to 1.

To look an element up, we do the same: hash it with each of the k hash functions and check that all k bits are 1. If they are, the element might be in the set. If any of them is 0, the element was definitely never added.

An example: say we have 3 hash functions and a 16-bit array, and we insert alice and bob. We run the 3 hash functions on each and set the corresponding bits (mod 16).

Now what if we want to query carol and dave? We run the same method and check the corresponding bits.

Carol has a bit that is 0, so she was definitely never added. All of dave's bits happen to be 1 (they were set by other names), so the filter says he might exist. That is exactly the false positive case Bloom filters can give you.

Sizing

Key formulas [1]:

• p = desired false-positive rate
• n = expected number of unique elements
• Bit array size: m = -(n * ln(p)) / (ln(2)^2)
• Number of hash functions: k = (m / n) * ln(2)
• Actual false-positive rate: p = (1 - e^(-kn/m))^k

What about some numbers? For the same example with 1 billion elements and a 0.1% false-positive rate, we use n = 10^9 and p = 0.001. That gives m ≈ 14.4 * 10^9 bits, which is about 1.8 GB (~1.7 GiB), with k ≈ 10 hash functions.

Compared with 10 to 20 GB for the hashset, this looks pretty good. Notice that the length of the strings doesn't matter to a Bloom filter, only the number of strings does. If we doubled the username length, the Bloom filter would use the same memory, while the hashset's footprint would roughly double.

Pros and cons

Pros:

• Small memory footprint (about 14 bits per element at 0.1%)
• Constant-time lookups (k hash computations)
• Zero false negatives
• Supports parallel operations

Cons:

1. False positives
2. Parameter sensitivity and hash function dependence
3. You can't remove an item from the filter

Traditional Bloom filters don't support deletion. You can't just set the hashed bits back to zero, because those bits may be shared with other elements, so you would effectively delete more than one element.

Counting Bloom filters

...But what if, instead of setting a bit to 1, we used more than one bit per entry (we call it a counter) and incremented the counter at position hash % m?

Well, you just created a counting Bloom filter. Now you increment the counters when inserting an item, and you can decrement them to delete it.

Here is an example of inserting alice and bob and then deleting alice, with 4-bit counters (they can reach 15) instead of 1 bit per entry.

Keep in mind: if a counter reaches its maximum (1111 with 4 bits), it becomes saturated and we stop changing it, neither incrementing nor decrementing.

Why? Let's imagine a very naive scenario. We use a single hash function and 2-bit counters (max value 3), and the hash function for some reason maps alice, bob, carol and dave to the same counter. After adding the first three names, the counter is 3 (11 in binary). Adding dave would overflow it, so we can't let it wrap around to 0, and we leave it at 3.

Now what if we remove alice, bob and carol? If we decremented the counter each time, it would reach 0, and querying dave would say he doesn't exist. That's a false negative, and we hate those.

The deeper problem is that once the counter reads 3, the filter can't tell whether 3, 4 or 100 names landed there, so any decrement is a guess. Leaving saturated counters untouched is the only safe choice. The cost is that such a counter may stay non-zero even after every item using it is gone, which can only cause extra false positives, never false negatives. (With 4-bit counters and a properly sized filter, reaching 15 is rare.)

Scalable Bloom filters

Another issue: notice how we fixed the array size and the number of hash functions based on the expected input size (or an assumption of our maximum input size)? Let's say that after 1 billion usernames it turns out you still need more.

You can't simply grow the bit array, because hashes are taken modulo the array size, so every existing element would now map to different bits. And you can't rehash either, because the filter never stored the original elements.

Luckily there is a variant that fixes this: scalable Bloom filters.

We start with a normal Bloom filter. Once it is full, we stack another filter on top of it, usually a bigger one, while keeping the overall false-positive rate bounded. New elements are inserted into the newest (active) filter, and when querying we have to check every layer of the stack.

Note: it is still worth starting the first layer with a good estimate of the input size. A low initial guess means many layers, and every lookup has to run the hash functions of each layer, which hurts performance.

Where they're used

1. Databases like Apache Cassandra use Bloom filters on SSTables (Sorted String Tables) to avoid reading data files that can't contain the requested key.
2. The MyRocks storage engine in MariaDB uses Bloom filters to speed up point lookups (queries that ask for a single key).
3. CDNs (content delivery networks) like Akamai use Bloom filters to handle "one-hit wonders". They don't want to cache objects that are only requested once, so when an object is requested and isn't in the Bloom filter, it isn't cached and is added to the filter. If it's requested again, it's found in the filter and gets cached.

If you found this interesting, there are more variants worth a look, like Cuckoo filters and Ribbon filters.

References

[1] https://bloomy.hexdocs.pm/Bloomy.Params.html
[2] https://redis.io/blog/bloom-filter/
[3] https://www.geeksforgeeks.org/system-design/bloom-filters-in-system-design/
[4] https://grindengineer.substack.com/p/bloom-filters-how-databases-skip-millions-of-disk-reads
[5] https://medium.com/@suresh.sk1691/bloom-filter-0d3ad654536c
[6] https://www.geeksforgeeks.org/python/bloom-filters-introduction-and-python-implementation/
[7] https://corte.si/posts/code/bloom-filter-rules-of-thumb/
[8] https://mariadb.com/docs/server/server-usage/storage-engines/myrocks/myrocks-and-bloom-filters
[9] https://medium.com/@nitishmehta3/optimize-lookups-with-bloom-filters-fast-cheap-and-almost-honest-dbec172f720f
[10]https://cassandra.apache.org/doc/latest/cassandra/managing/operating/bloom_filters.html