BloomFilter.NetCore

BloomFilter.NetCore is a high-performance .NET library for Bloom filters—probabilistic data structures used to test element membership with minimal memory footprint. It provides $O(1)$ time complexity for both add and query operations.

Key characteristics:

• Space Efficient: Uses significantly less memory than a HashSet.
• Probabilistic: May return false positives (claiming an element is present when it is not) but never false negatives.
• Two Implementation Types:
  1. In-Memory (FilterMemory): Uses BitArray for single-process scenarios.
  2. Distributed (FilterRedis series): Uses Redis backends to share state across multiple application instances.

Common use cases include cache penetration protection, deduplication (URLs, IDs), recommendation systems, and web crawlers.

Select the backend mode based on your application architecture:

1. Prevent Cache Penetration

Use a BloomFilter as the first line of defense. If Contains(id) returns false, the item definitely does not exist, so you can return null immediately without querying the database or cache.

2. URL Deduplication (Web Crawlers)

Maintain a BloomFilter of visited URLs. Before crawling a new URL, check Contains(url). If it returns true, skip it; otherwise, add it to the filter and proceed.

3. Distributed Deduplication

In multi-instance microservices, use a Redis-backed BloomFilter. All instances check the same shared filter (e.g., ContainsAsync(messageId)) to ensure a specific message or event is only processed once across the entire cluster.

Memory usage is determined by the capacity (m) in bits. The formula for memory in bytes is:

Memory (bytes) = m / 8

You can inspect the Capacity property on a Filter instance to calculate usage.

// 10 million elements, 1% false positive rate
var bf = FilterBuilder.Build(10_000_000, 0.01);
var filter = (Filter)bf;

// Calculate memory usage
long bits = filter.Capacity;
long bytes = bits / 8;
double mb = bytes / (1024.0 * 1024.0);

Console.WriteLine($"Bit array size: {bits:N0} bits");
Console.WriteLine($"Memory usage: {bytes:N0} bytes ({mb:F2} MB)");
// Output: approximately 11.4 MB

BloomFilter.NetCore is thread-safe. You can safely perform Add and Contains operations across multiple threads concurrently.

var bf = FilterBuilder.Build(10_000_000, 0.01);

// Concurrent additions
Parallel.For(0, 1000, i =>
{
    bf.Add($"item:{i}");
});

// Concurrent checks
Parallel.For(0, 1000, i =>
{
    var exists = bf.Contains($"item:{i}");
});

Standard Bloom Filters do not support deleting elements. Deleting an element might inadvertently affect the detection of other elements because multiple elements can map to the same bits.

If your use case requires deletion, consider using a Counting Bloom Filter or a Cuckoo Filter.

Bloom filters are effective for several real-world scenarios:

Cache Penetration Protection

Use a Bloom filter as a first layer before querying a cache or database. If Contains(id) is false, the item definitely does not exist, allowing you to return early and protect downstream resources.

URL Deduplication

In web crawlers, use a Bloom filter to track visitedUrls. Before processing a URL, check Contains(url). If true, skip it; if false, add it and proceed.

Distributed Deduplication

When running multiple service instances, use a Redis-backed Bloom filter. This allows all instances to share a global state (e.g., GlobalDeduplication) to ensure a message or task is only processed once across the entire cluster.

BloomFilter.NetCore is thread-safe. You can perform Add and Contains operations concurrently from multiple threads (e.g., using Parallel.For) without external synchronization.

// Multi-threaded concurrent access
var bf = FilterBuilder.Build(10_000_000, 0.01);

Parallel.For(0, 1000, i =>
{
    bf.Add($"item:{i}"); // Thread-safe
});

Parallel.For(0, 1000, i =>
{
    var exists = bf.Contains($"item:{i}"); // Thread-safe
});

Select the backend based on your application architecture: