Bloom Filters Explained

Anyone working with caches eventually runs into this problem: a request arrives with a key that exists in neither the cache nor the database, yet every lookup punches straight through to the database. To block these requests, you first need a fast way to answer "does this key exist at all?" — and that's exactly what Bloom filters were built for.

Background

In a redis caching setup, if someone floods you with requests for keys that don't exist, the cache never hits and all the pressure lands on the database — the classic cache penetration problem. The naive way to intercept these requests is to store every valid key in a set and check it before querying. But once the key count grows large, holding the full key set in something like a HashSet costs far too much memory. A Bloom filter trades a tiny amount of space for an existence check that is "possibly imprecise but plenty fast" — landing exactly on this sweet spot.

The Bloom filter was proposed by Burton Bloom in 1970. It is essentially a very long binary vector combined with a series of random mapping functions. Bloom filters are typically used to prevent redis cache penetration: they save a great deal of space while quickly determining whether an element exists.

A Bloom filter hashes a key to locate indices in a bitmap (which is just a bit array). Each position in the array has only two states, 0 and 1, and occupies a single bit — 0 means no element is present, 1 means an element is present.

Concretely, when inserting an element, k different hash functions each compute a value for the key, producing k indices, and all k positions in the bitmap are set to 1. Lookups follow the same procedure: if any one of the k positions is 0, the key was definitely never inserted; only when all k positions are 1 does the filter answer "possibly present". The entire process involves nothing but hashing and bit operations, so the time complexity is O(k), independent of how many elements have been stored — which is why lookups are so fast.

Note: the indices produced by hashing two different keys may partially overlap. This overlap reduces memory usage, but it also creates the possibility of hash collisions — a key that was never inserted can hash to positions that all happen to be 1 in the bitmap.

From this behavior we can derive the two defining properties of a Bloom filter:

1. If a Bloom filter says an element exists, the element may exist.

2. If a Bloom filter says an element does not exist, the element definitely does not exist.

These two properties dictate how it should be used: it works well as a front-line gate that blocks requests for keys that definitely don't exist, but its "exists" verdict must never be taken at face value — after a positive answer, you still go to the cache or database for confirmation.

A Bloom filter always carries some false positive rate, because hash collisions can never be avoided completely. This misjudgment rate is called the False Positive Probability, or fpp for short.

The fpp is determined mainly by three factors: the bitmap length m, the number of hash functions k, and the number of elements already inserted, n. The more elements you insert, the more bits in the bitmap are set to 1, and the more likely it becomes that a stranger key's k positions "just happen to all be 1". This is why Bloom filter implementations (such as Guava's BloomFilter) typically ask for an estimated element count and a target fpp at creation time, and derive suitable values of m and k from them.

To reduce the fpp, you can enlarge the bitmap or hash more times to lower the collision probability — but a bigger bitmap needs more memory, and more hashing burns more CPU. Budget the resource costs accordingly and pick what fits. At its core this is a three-way trade-off between space, CPU, and accuracy; there is no free lunch.

What About Deleting a Key?

As we've seen, membership is determined by checking whether the corresponding index positions are 1. But you can't delete an element by simply flipping those 1s back to 0, because other elements may map to the same positions — which is why the original Bloom filter cannot support deletion. So what do we do if deletion is needed? The simplest approach is to add a counter: instead of storing just a 1, each position in the bit array stores the number of elements mapped there (0 if none). This raises an obvious cost — a plain 1 fits in a single bit, but storing an actual count like 2 needs 2 bits, so a Bloom filter with counters takes up more space.

This improved variant is generally called a Counting Bloom Filter: insertion increments the counters at all k positions by 1, deletion decrements them by 1, and only when a counter drops to 0 is that position truly empty. Beyond the space blow-up (each position grows from 1 bit to several bits), there's another hazard — if you mistakenly delete an element that was never inserted, counters get wrongly decremented, and elements that actually exist can be "deleted away", introducing false negatives. Deletion should therefore only ever be performed on elements you've confirmed were inserted.

If your business doesn't really need deletion, there's an even simpler route: don't delete at all. Periodically rebuild a fresh Bloom filter from the latest full dataset and swap it in for the old one. The old filter keeps serving during the rebuild, and the switch is atomic — many cache penetration setups work exactly this way.

Pitfalls and Caveats

1. Estimate capacity generously. Once a Bloom filter is created, its bitmap length is fixed. If insertions exceed the estimated scale, the fpp degrades sharply — and there's no online resize, only a full rebuild.

2. "Exists" doesn't mean it actually exists. Keys that slip through as false positives still hit the database. A Bloom filter greatly reduces penetration but never eliminates it entirely, so database-side safety nets (such as caching empty values) are still needed.

3. Hash functions must match the writer's. If multiple services share one Bloom filter (say, stored in redis), every client's hash implementation and parameters must be exactly identical, or the results will simply be wrong.

Wrapping Up

With one bitmap and k hash functions, a Bloom filter buys you a membership check with tiny space usage and O(k) lookups — at the cost of false positives and, in its original form, no deletion. Its two defining answers — "definitely not present" versus "only possibly present" — make it best suited as a front-line gate, with cache penetration prevention as the textbook use case. When deletion is needed, switch to a counting Bloom filter or just take the periodic-rebuild route; as for capacity estimates and the fpp setting, that's a calculation each business has to make for itself, balancing memory, CPU, and accuracy.