Understanding Bloom Filters and Their Use in Preventing Cache Penetration

Cache penetration occurs when repeated queries for non‑existent keys bypass Redis and repeatedly hit the database, causing unnecessary load; a simple mitigation is to cache a placeholder value, but this fails when attackers use many different bogus keys.

To efficiently handle massive key spaces, the article presents an interview‑style question that leads to using a bitmap (bit array) combined with multiple hash functions, laying the groundwork for Bloom filters.

A Bloom filter stores elements in a fixed‑size bit array using several hash functions; when all corresponding bits are set, the element is considered possibly present, while a zero bit guarantees absence, resulting in false positives but no false negatives.

The Guava library provides a ready‑made Bloom filter implementation. Below is the Maven dependency required:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>21.0</version>
</dependency>

Example Java code using Guava to create a filter, insert one million random strings, and test 100 existing and 9,900 non‑existing elements demonstrates the false‑positive rate (≈2% when configured with fpp = 0.02 ).

private static final int insertions = 1000000;
private static final double fpp = 0.02;

public static void main(String[] args) {
    BloomFilter
bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions, fpp);
    Set
sets = new HashSet<>(insertions);
    List
lists = new ArrayList<>(insertions);
    for (int i = 0; i < insertions; i++) {
        String uuid = UUID.randomUUID().toString();
        bf.put(uuid);
        sets.add(uuid);
        lists.add(uuid);
    }
    int rightNum = 0, wrongNum = 0;
    for (int i = 0; i < 10000; i++) {
        String data = i % 100 == 0 ? lists.get(i / 100) : UUID.randomUUID().toString();
        if (bf.mightContain(data)) {
            if (sets.contains(data)) {
                rightNum++;
                continue;
            }
            wrongNum++;
        }
    }
    // output results
}

For distributed systems, the article shows how to implement a Bloom filter on top of Redis bitmap operations. The core helper class calculates optimal bit array size and hash count, and provides a method to obtain hash offsets:

public class BloomFilterHelper
{
    private int numHashFunctions;
    private int bitSize;
    private Funnel
funnel;
    // constructors and methods omitted for brevity
    public int[] murmurHashOffset(T value) { /* ... */ }
    private int optimalNumOfBits(long n, double p) { /* ... */ }
    private int optimalNumOfHashFunctions(long n, long m) { /* ... */ }
}

The RedisBloomFilter class uses Spring's RedisTemplate to set and query bits. It offers add , addList (pipeline for bulk inserts), and contains methods:

public class RedisBloomFilter
{
    @Autowired private RedisTemplate redisTemplate;
    public void add(BloomFilterHelper
helper, String key, T value) { /* set bits */ }
    public void addList(BloomFilterHelper
helper, String key, List
values) { /* pipeline */ }
    public boolean contains(BloomFilterHelper
helper, String key, T value) { /* check bits */ }
}

A test class demonstrates creating a filter for 1,000 expected insertions with a 10% false‑positive probability, adding 100 elements via addList , and verifying that all inserted elements are reported present while measuring any missed checks.

Finally, the article lists other common use cases for Bloom filters such as URL deduplication in web crawlers, spam detection, malicious URL filtering in browsers, recommendation systems, and reducing unnecessary lookups in storage engines like BigTable and Cassandra, concluding that Bloom filters are a practical tool for mitigating cache penetration and many other large‑scale membership‑query problems.