Bloom Filters in the Wild

You’ve seen how Bloom filters work wonders in terms of saving memory. Because of this, Bloom filters are ubiquitous in the real world. In addition to the use case of a blacklist of web traffic sources we looked at earlier, the following sections highlight some further applications where Bloom filters are used.

Reducing Database Lookups

Many database engines use Bloom filters to help reduce lookup time. Looking up an item in the database usually involves reading information from the disk and, therefore, takes a significant amount of time relative to looking something up in main memory.

Now, this time lag takes place upon each lookup, no matter whether the item we’re looking up is in the database or not. As such, it’s kind of a waste of time to execute a database lookup to find an item that’s not there. After all, there’s no actual information we need to extract from the database in such a case. Wouldn’t it be nice if we could know in advance that the item doesn’t exist so we can avoid the lookup cost?

This is where Bloom filters can help tremendously. Each time an item is added to a database, that same item is also inserted into a Bloom filter that lives in main memory. We don’t have to insert all the item’s information into the Bloom filter; we can simply insert the item’s name (or whatever its primary ID is).

The Bloom filter can then be used as a kind of index telling us what values can be found in the database. Each time we perform a lookup, we first check the Bloom filter to see if our desired item is in the database. Because the Bloom filter lives in main memory, this check happens extremely quickly. Only when the Bloom filter tells us that the item is present do we then perform the more expensive operation of looking it up in the database. On the other hand, if the Bloom filter tells us that the item is not in the database, we get to skip the expensive database lookup.

As to the issue of the Bloom filter’s possibility of error, there’s not much downside, and here’s why: If the Bloom filter tells us that the item doesn’t exist, we can be absolutely sure that this is true since there can never be a false negative.

Now, there’s a small chance for a false positive, meaning the Bloom filter will tell us that the item is present even though it isn’t. However, the worst thing that could happen is that we perform an unnecessary database lookup. And this is not a big deal, especially considering that if we didn’t use a Bloom filter at all, we’d be performing way more unnecessary database lookups! In other words, although a Bloom filter may not completely eliminate all unnecessary lookups, it will nevertheless still greatly reduce their frequency.

Again, a hash table can be used in this case instead of a Bloom filter, but the hash table would take up more space. And so, this is why many database engines use Bloom filters in practice to reduce database lookups.

Caches

In Chapter 4, , you learned all about caching. One of the primary lessons was that because caches only hold a limited amount of data, we only keep data that will be requested again in the future. On the flip side, we evict data that will never be asked for again.

The ultimate item we don’t want to cache is something often called a “one-hit wonder.” A one-hit wonder is a piece of data that is only being requested once in history; no one will ever request it again.

Now, there are some applications where most requests are indeed one-hit wonders. If, say, 75 percent of requests are for one-hit wonders, then we only want to cache the other 25 percent of requests.

Of course, we can’t know for sure whether a given request is a one-hit wonder, since we can’t see into the future to know for certain that it’ll never be requested again. However, we can use a Bloom filter to help prevent inserting one-hit wonders into our cache.

The strategy here is to only cache data from a request we know has been asked for more than once. That is, if this is the first time we ever had such a request, we suspect that perhaps this is a one-hit wonder. However, if this is already at least the second time we encounter this request, then we know it’s certainly not a one-hit wonder; after all, it’s now been requested twice! And so, we’ll cache the data, with the guesstimate that this request may be made yet again in the future.

Specifically, we’ll use a Bloom filter to keep track of what requests have ever been made previously. Whenever a request is made, we insert the requested value into our Bloom filter. This will indicate to us in the future that this request has been made once so far. Then, going forward, each time a request is made, we first check the Bloom filter to see whether the request has been made before. If it was never made before, we suspect that this may be a one-hit wonder and do not cache the data. But if the Bloom filter tells us that this request has been made before, then we do cache the data.

Now, when the Bloom filter tells us that the request has never been made before, we can 100 percent believe this to be true. On the other hand, if the Bloom filter tells us that this request has been made before, there’s a small chance that this isn’t true.

However, the worst thing that can happen is that we cache a one-hit wonder. This is no travesty, though, especially given that this will happen only occasionally. And again, without the Bloom filter, we’d be caching all one-hit wonders! Although a hash table would be more accurate (that is, 100 percent accurate), it may take up too much space to be worth it. The Bloom filter is a much more compact data structure.

Variants

Besides the classic Bloom filter, there are plenty of other variants out there as well. These include Bloomier filters (yep, that’s their name), Spatial Bloom filters, Scalable Bloom filters, Layered Bloom filters, and more. Each of these deals with specialized use cases, and you may enjoy researching them to see how the general Bloom filtering strategy can be used for so many different types of applications.

We’ve also seen that a Bloom filter is a Monte Carlo data structure. But it’s certainly not the only one. While I don’t have the space to cover other Monte Carlo data structures in this volume, I encourage you to check them out. Some of these include skip lists, quotient filters, cuckoo filters (totally!), count-min sketches, and HyperLogLogs.