Scaling Systems with Bloom Filters: Characteristics, Use Cases, and C# Implementation

Bloom Filters are space-efficient, probabilistic data structures that have revolutionized how we handle large datasets and perform quick membership queries. Despite their simplicity, these powerful tools are used in many applications, from database systems to network security protocols.

Imagine being able to determine, with high certainty, whether an element is part of a massive set without storing the entire set in memory. Sounds too good to be true? That's the magic of Bloom Filters. They offer a unique trade-off between space efficiency and accuracy, allowing for lightning-fast lookups with a small but acceptable beforehand chance of false positives.

Understanding Bloom Filters: A Simple Analogy

Imagine you are a stamp collector with a vast collection of rare stamps. You want to quickly check whether a particular stamp is already in your collection without physically flipping through every album page.

To speed up the process, you create a checklist where each stamp is represented by several small characteristics, like color, size, and country of origin. You mark off each characteristic on your checklist for every stamp you own.

When you come across a new stamp, you compare its characteristics against your checklist. If all the corresponding characteristics are marked, you conclude that the stamp might already be in your collection. This cannot be said for sure and hence we call it out as false positive. Lets try and break it down:

• For each stamp in your collection, you check off certain characteristics on your checklist. For example, let’s say you mark a stamp with characteristics like “red,” “medium size,” and “from France.” These marks stay on the checklist for future reference.

• You now come across a new stamp, which you want to check to see if it’s already in your collection. This new stamp has its own characteristics, but coincidentally, it is also “red,” “medium size,” and “from France.”

• You compare the new stamp’s characteristics against your checklist. Since the characteristics “red,” “medium size,” and “from France” are already marked (because of a different stamp in your collection with the same characteristics), it seems like the new stamp might already be in your collection, but in reality, it isn’t! It just happens to share the same characteristics as another stamp, which creates a false positive.

• The checklist can’t distinguish between the two stamps because it only tracks a limited set of characteristics, not the actual full details of each stamp.

However, if even one of the three characteristic isn’t marked, you know for sure that the stamp isn’t in your collection.

The checklist is like a Bloom filter: it doesn’t hold the actual stamps (or data), but rather a series of indicators (hashes) that help you quickly check whether a stamp (item) might be in the set.

The Inner Workings of Bloom Filters: Mechanics Explained

Now that we've introduced the concept of Bloom filters, let's dive into the nuts and bolts of how they actually work.

At its core, a Bloom filter consists of two main components:

1. A bit array: This is a array of m bits, all initially set to 0.

2. A set of k hash functions: These functions map input elements to positions in the bit array.

When you add an element to a Bloom filter, here's what happens:

1. The element is passed through each of the k hash functions.

2. Each hash function produces an index in the range [0, m-1].

3. The bits at all k indices in the bit array are set to 1.

For example, lets say we want to track registered users email addresses in the system in our bloom filter. If we have 3 hash functions and an email "hello@gmail.com" produces indices 2, 4, and 7, we would set the bits at positions 2, 4, and 7 to 1.

To check if an element is in the set:

1. The element is passed through the same k hash functions.

2. The bits at the resulting k indices are checked.

3. If ALL of these bits are 1, the filter reports that the element is probably in the set.

4. If ANY of these bits are 0, the element is definitely not in the set.

Let's explore how a false positive can occur in a Bloom filter:

Imagine we add the email address "helloworld@gmail.com” to the filter, and it generates hash values corresponding to the indices 2, 4, 8, and 7, setting all these positions in the bit array to 1.

Now, suppose we check for the presence of "hellow@gmail.com” which was never added to the filter. If the hash values for "hellow@gmail.com" happen to correspond to indices 2, 4, and 7 (which were set to 1 by the previous email), the filter will incorrectly indicate that "hellow@gmail.com" is present, resulting in a false positive.

Key Characteristics: What Sets Them Apart

• Space-efficient: Uses much less space than conventional hash tables.

• Fast lookups: O(k) time complexity for both insertions and queries, where k is the number of hash functions used.

• No false negatives: If the filter says an element is not in the set, it definitely isn't.

• Possible false positives: The filter might incorrectly report that an element is in the set when it actually isn't.

• Cannot remove elements: Once added, elements cannot be removed without rebuilding the entire filter.

When to use Bloom Filters

• Caching: Quickly determine if an item is definitely not cached.

• Database queries: Avoid unnecessary disk lookups for non-existent data.

• Network routing: Efficiently route packets and avoid routing loops.

• Web crawling: Avoid revisiting already crawled URLs.

• Anywhere you need fast, memory-efficient set membership tests and can tolerate some false positives.

Read More: Efficient Database Lookups

Considerations and Limitations

• False Positive Rate: Increases as more elements are added to the filter.

• Size: Once created, the size of a Bloom filter is fixed. It can't be resized without rebuilding.

• Deletion: Standard Bloom filters don't support element deletion. Variants like Counting Bloom filters can support deletions but are more complex and require and additional set or array where the deleted items can be tracked.

• SQL Server Performance: Implementing Bloom filters directly in SQL Server might not be as efficient as using them in application code or as a separate service.

Delete Operation in Bloom Filters: Why It’s Tricky

One of the limitations of Bloom filters is their inability to support a direct delete operation. This is because Bloom filters rely on setting bits in a bit array when an item is added, but they don't track which bits were set by which item. This causes a fundamental challenge when trying to remove an item.

When you add an item to a Bloom filter, multiple hash functions set specific bits in the bit array to 1. However, these same bits may have been set to 1 by other items previously added to the filter. If we attempt to remove an item by simply setting its corresponding bits back to 0, we risk unintentionally removing bits that were set by other items, leading to false negatives (where an existing item incorrectly appears to be absent).

In many cases, Bloom filters are used in situations where items are only added but never deleted, such as in caching, database lookups, or large-scale distributed systems. If deletions are a key requirement, alternative data structures or variations like counting Bloom filters may be more suitable.

Decreasing the Chances of False Positives

There are several ways to decrease the chances of false positives in a Bloom filter:

• Increase the size of the bit array: A larger bit array reduces the probability of bit collisions.

• Optimize the number of hash functions: The optimal number of hash functions (k) is related to the size of the bit array (m) and the number of items to be inserted (n). The optimal k can be calculated as: k = (m/n) * ln(2)

• Limit the number of items: The more items you add to the filter, the higher the false positive rate. Design your system to limit the number of items or create a new filter when a certain threshold is reached.

You can read more about the mathematically optimized numbers against your dataset set size needed for a Bloom Filter here.

Scaling Bloom Filters

As Bloom filters fill up, their false positive rate increases but you cannot directly increase the size of a Bloom Filter. Since, the bit positions derived from the hash functions for the existing elements will change, because the bit positions are computed using the modulus operation based on the Bloom Filter size (m).

If you simply expand the bit array without adjusting for this, your existing bit positions will no longer map correctly, which could lead to incorrect results (i.e., false negatives).

Rebuilding from Scratch

This is the most straightforward approach but requires recalculating everything:

• Create a new Bloom Filter with a larger size (m1).

• Re-insert all the existing elements into the new Bloom Filter.

• The new size will allow the new hash values to distribute over a larger bit array, thus reducing the false positive rate.

Layering or Cascading

Instead of expanding the original Bloom Filter directly, you can add a new Bloom Filter alongside the existing one. This is known as a cascading Bloom Filter or a multi-level Bloom Filter.

• Leave the original Bloom Filter unchanged.

• Add a second Bloom Filter with a larger size to handle future insertions.

• For lookups, check both Bloom Filters:

• First, check the original Bloom Filter.

• If the element isn’t found, check the new Bloom Filter.

Choosing the Right Hash Function

When selecting hash functions for a Bloom filter, consider the following criteria:

• Speed: Hash functions should be fast to compute.

• Uniform distribution: The hash function should distribute items evenly across the bit array.

• Independence: Multiple hash functions should produce independent results.

Approach	Speed	Distribution	Independence	Implementation Complexity
Cryptographic (MD5, SHA-256)	Slow	Slow	Excellent	High
Non-cryptographic (MurmurHash, FNV)	Fast	Good	Moderate	Low
Double Hashing	Very Fast	Good	Moderate	Moderate

Practical Implementation in C-Sharp .Net

Lets now try and implement a simple Bloom Filter in C#. For the purpose of this demo we are going to use a Boolean Array instead of a Bit Array. But in real world use cases Bit should be used as they offer far more memory and time optimization.

namespace BloomFilter
{
    public class Bloom
    {
        private bool[] bitArray;
        private int size;

        private readonly Func<byte[], int>[] hashFunctions;


        public Bloom(int size)
        {
            this.size = size;
            this.bitArray = new bool[size];

            hashFunctions = new Func<byte[], int>[]
            {
            data => GetMd5Hash(data),
            data => GetSha1Hash(data),
            data => GetSha256Hash(data)
            };
        }
    }
}

• private bool[] bitArray;: A boolean array that represents the bit array of the Bloom filter. Each index of this array can be true or false.

• private int size;: Stores the size of the bit array.

• private readonly Func<byte[], int>[] hashFunctions;: An array of functions that will be used as hash functions for the Bloom filter. Each function takes a byte array as input and returns an integer.

• As discussed earlier, hash functions are crucial for Bloom filters. They determine the positions in the bit array where bits are set. Multiple hash functions are used to minimize the chances of collisions and reduce the probability of false positives.

• Here we are defaulting to three hash functions MD5, SHA-1, and SHA-256 for the ease of implementation

public void Add(string item)
{
    byte[] itemData = Encoding.UTF8.GetBytes(item);  

    foreach (var func in hashFunctions)
    {
        int hash = func(itemData);
        bitArray[hash % size] = true;
    }
}

• The string item is converted to a byte array because hash functions operate on byte arrays.

• Each hash function from the hashFunctions array is applied to the byte array.

• The hash value is used to determine an index in the bitArray by taking the modulus with the size of the array. The corresponding bit in the bitArray is set to true. This marks the presence of the item.

  • Hash functions like MD5, SHA-1, and SHA-256 produce large hash values (e.g., MD5 produces 128-bit hashes).

  • These large values need to be reduced to fit within the array's bounds. For instance, if the hash value is 123456789, and the size of the bitArray is 100, then 123456789 % 100 results in 89. This reduces the large hash value to a valid index within the range of 0 to 99.

private static int GetMd5Hash(byte[] data)
{
    using (var md5 = MD5.Create())
    {
        byte[] hashBytes = md5.ComputeHash(data);
        return Math.Abs(BitConverter.ToInt32(hashBytes, 0));  
    }
}

private static int GetSha1Hash(byte[] data)
{
    using (var sha1 = SHA1.Create())
    {
        byte[] hashBytes = sha1.ComputeHash(data);
        return Math.Abs(BitConverter.ToInt32(hashBytes, 0));  
    }
}

private static int GetSha256Hash(byte[] data)
{
    using (var sha256 = SHA256.Create())
    {
        byte[] hashBytes = sha256.ComputeHash(data);
        return Math.Abs(BitConverter.ToInt32(hashBytes, 0));  
    }
}

• The three hash functions that computes the hash for the given input

• Math.Abs(...) ensures the integer is non-negative

public bool MightContain(string item)
{
    byte[] itemData = Encoding.UTF8.GetBytes(item);

    foreach(var func in hashFunctions) 
    {
        int hash = func(itemData);
        int index = hash % size;
        if (!bitArray[index])
        {
            return false;
        }
    }

    return true;
}

• Converts the input string to a byte array for hashing

• Applies the same three hash functions to the input

• Computes the bit array index using the hash value and modulus operation

• Checks if the bit at the computed index is false. If any bit is false, the item is definitely not in the Bloom filter, so return false

• If all checked bits are true, return true, indicating that the item might be in the Bloom filter. This is a probabilistic result; the item could still be absent, but the filter cannot conclusively say so

namespace BloomFilter
{
    public class BulkEmailGenerator
    {
        public static List<string> GenerateRandomEmailList(int count)
        {
            List<string> emailList = new List<string>();

            Random random = new Random();

            for (int i = 0; i < count; i++)
            {
                string username = GenerateRandomString(random, 8);  
                string domain = "fakemail.net";  
                string email = $"{username}@{domain}";
                emailList.Add(email);
            }

            return emailList;
        }

        public static string GenerateRandomString(Random random, int length)
        {
            const string chars = "abcdefghijklmnopqrstuvwxyz0123456789";
            char[] stringChars = new char[length];

            for (int i = 0; i < length; i++)
            {
                stringChars[i] = chars[random.Next(chars.Length)];
            }

            return new string(stringChars);
        }
    }
}

This code snippet just generates random email address which we can then add to our bloom filter and test it out.

The entire code is available on the GitHub repository for reference.

Conclusion: Embracing Bloom Filters for Modern Data Solutions

In today’s data heavy applications, tools like Bloom filters are increasingly relevant and represent a shift in thinking, from exact, resource-intensive solutions to probabilistic, efficient approaches that are "good enough" for many real-world scenarios.

The implementation we explored in C# is just the beginning. As you integrate Bloom filters into your projects, you'll likely discover new and innovative ways to leverage their strengths.

Whether you're optimizing a database, building a cache, or tackling any problem involving set membership queries, consider whether a Bloom filter might offer the perfect balance of speed, space efficiency, and accuracy for your needs.

Happy coding, and may your false positives be few and your lookups lightning-fast!