✖

Bloom filter: is an element in the set?

A Bloom filter is a probabilistic structure that lets us say, with a certain degree of probability, whether an element x is in a set M.

In our system, for example, we need to measure how many times users clicked on an advertising banner. After each click we receive an HTTP GET request telling us that user XYZ clicked on ad 123. Occasionally a user double-clicks the mouse by mistake and we get two requests. We would like to filter these requests out and have them recorded in the database as a single click.

So we need an application that reads the stream of click messages and filters out duplicates. How would we do it? Each message has an ID, so we don't need to compare the whole message, we only need to find out whether we have ever processed a message with the same ID. Simple JavaScript code that removes duplicates from a stream of messages (here, for simplicity, from an array) might look like this:

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}]
var processedIds = {};

messages.forEach(function(message) {
    if (!processedIds[message.id]) {
        processedIds[message.id] = true;
        console.log(message);
    }
});

// Prints: { id: "123" } { id: "456" } { id: "789" }

This solution will do until we run out of memory, and we will, because the set processedIds will only ever grow. We can of course add some data expiry, for instance by always removing messages older than an hour, or something similar.

It's worse when even that isn't enough. What if we need the set processedIds to hold data for at least one day, and we go through, say, ten thousand messages per second? In the worst case we need to store up to 864,000,000 IDs. If we use uuid v4, each ID is 36 characters long, which means we need to store at least 31 GB per day. That is a bit much. Could we reduce the memory requirements?

Bloom filter

Instead of storing the whole ID, we can store just its hash. We can use the classic murmurhash, which returns a 32-bit integer for every string and also has a good distribution:

var murmurhash = require("murmurhash");

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var processedHashedIds = {};

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id);
    if (!processedHashedIds[hashedId]) {
        processedHashedIds[hashedId] = true;
        console.log(message);
    }
});

// Prints: { id: "123" } { id: "456" } { id: "789" }

Next we use the bit-vector trick. This is an array in which we store only zeros and ones. If we have an n-bit hash function, we need a vector of size 2n, so that we can address every possible output of the hash function in the vector. The idea is that the vector starts out full of zeros. If the hash function then returns the number 47 for the input "123", we simply put a one at index 47 of the vector. That marks that we have already seen the hash with value 47.

var n = 8;
var numberOfValues = Math.pow(2, n);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var bitVector = new Array(numberOfValues);

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id) % numberOfValues;
    if (!bitVector[hashedId]) {
        bitVector[hashedId] = true;
        console.log(message);
    }
});

// Prints: { id: "123" } { id: "456" } { id: "789" }

With the code % numberOfValues we merely trimmed murmurhash so that it became an n-bit hash function, nothing more. And this is a Bloom filter, even if a very degenerate version of one. The problem with this approach is, of course, collisions, which are bound to happen. Different input values can have the same output hash. So, to reduce the probability of a collision, we don't use just one hash function but several. We can create several hash functions, for example, by adding some salt to the input value. A simple function that creates different n-bit hash functions might look like this:

var murmurhash = require("murmurhash");

function createNBitHashFunction(n, salt) {
    var upperBound = Math.pow(2, n);
    return function(inputString) {
        return murmurhash.v2(inputString + salt) % upperBound;
    }
}

var firstHashFunction = createNBitHashFunction(8, "someSalt");
var secondHashFunction = createNBitHashFunction(8, "someOtherSalt");

console.log(firstHashFunction("123")); // 223
console.log(secondHashFunction("123")); // 30

We can write a class representing a Bloom filter like this:

function BloomFilter(numberOfHashFunctions, numberOfBits) {
    this.reset(numberOfHashFunctions, numberOfBits);
}

BloomFilter.prototype.reset = function(numberOfHashFunctions, numberOfBits) {
    this.bitVector = new Array(Math.pow(2, numberOfBits));
    this.hashFunctions = [];

    for (var i = 0; i < numberOfHashFunctions; i++) {
        this.hashFunctions.push(createNBitHashFunction(numberOfBits, i.toString()));
    }
}

BloomFilter.prototype.add = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        this.bitVector[checksum] = true;
    }
}

BloomFilter.prototype.contains = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        if (!this.bitVector[checksum]) {
            return false;
        }
    }
    return true;
}
  • The add method adds an element to the Bloom filter: it computes the hash with all the hash functions and stores true at the corresponding index.
  • The contains method then checks whether the given element is in the Bloom filter.

A Bloom filter is easy to use:

var bloomFilter = new BloomFilter(3, 8);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];

messages.forEach(function(message) {
    if (!bloomFilter.contains(message.id)) {
        bloomFilter.add(message.id);
        console.log(message);
    }
});

// Prints: { id: "123" } { id: "456" } { id: "789" }

And that is all the magic of a basic Bloom filter. It has these basic properties:

  • If the contains method says that an element is not in the Bloom filter, then you really never added that element to it.
  • If the method says that an element is in the Bloom filter, that doesn't necessarily mean you really added it, because a hash collision may have occurred.
  • In general, if you want to reduce the probability of a wrong answer, increase the number of hash functions or increase their size (meaning the size of the output value).
  • The more hash functions you use, the slower the Bloom filter will be.
  • The larger the hash functions you use, the more space the Bloom filter will take.
  • Once you add an element to a Bloom filter, you can't remove it.