Cristi Cretan has a very nice post on using Bloom filters to reduce system load. The TL;DR is that his team had a system that used a database to determine if they had seen a certain file before. That’s pretty straightforward but the requests were bursty and even though they had some front ends mediating the requests, it sometimes overloaded the database.
When Cretan looked at the requests, he discovered that the answer was almost always that the file was unknown. That suggested filtering the requests to avoid the expensive database lookup if the file didn’t exist. That’s a perfect case for the application of a Bloom filter. The idea is that that you hash the file identifier with a set of hash functions and set a corresponding bit for each function. On lookup, if the corresponding bit for each hash function is set, it’s likely that the value is in the set. More to the point, if any of the hash values come up with an unset bit, it’s a sure sign that the value is not in the set.
The salient point is that if any hash function comes up with an unset bit, it’s absolutely certain that the value is not in the set and the expensive database search can be avoided. You can see the details in Cretan’s post.
As I said, this is a nice application of Bloom filters but I have a couple of observations. First, Cretan got push back from his colleagues on the grounds that Bloom filters are probabilistic and the application demanded certainty. That push back speaks poorly of his colleagues as it reveals their lack of understanding of how Bloom filters work in the negative case.
Second, it’s not clear to me that a Bloom filter is needed here. To a first approximation, a single hash function should be sufficient here since we’re only interested in the negative case. It might be that a single hash function would have too many false positives and that multiple hash functions reduces that problem.
Regardless, the application of Blooms filters is just what this problem needed and it did, indeed, reduce system requirements.