How a Bloom Filter Stores 30 Million Items in Just 35 MB

Production Configuration

In a Java service a static class defines three parameters for a popup‑notification Bloom filter: a 6‑day expiration (EXPIRE), an expected size of 30,000,000 items (EXPECTED_SIZE), and a false‑positive probability of 1% (FALSE_PROBABILITY).

public static class PopupBloomFilterConfig {
    // popup lasts 5 days, filter expires = popup days + 1
    public static final long EXPIRE = 60 * 60 * 24 * 6;
    // expected number of members
    public static final long EXPECTED_SIZE = 30000000;
    // false positive rate 1%
    public static final double FALSE_PROBABILITY = 0.01;
}

Redisson creates the filter, initializes it if it does not exist, and sets the expiration:

RBloomFilter<Object> bloomFilter = redissonClient.getBloomFilter(key);
if (!bloomFilter.isExists()) {
    bloomFilter.tryInit(EXPECTED_SIZE, FALSE_PROBABILITY);
    bloomFilter.expire(EXPIRE, TimeUnit.SECONDS);
}

When a request arrives, the service checks the user ID against the filter. A false result means the user has not seen the popup, so the popup logic runs and the ID is added to the filter; a true result means the popup has already been shown and is skipped.

Why Not Use Other Solutions?

Storing 30 million IDs in a HashSet would require 700 MB–1 GB of heap memory because each Long object carries object‑header and node overhead; replicating this in a distributed Redis cache would be even larger.

Querying a relational database on every request would work functionally but would place tens of millions of queries on the DB in a short window, causing severe load.

A Redis bitmap uses 1 bit per user, so 30 million users need only about 3.58 MB, but it assumes user IDs are dense and sequential. In real systems IDs can be sparse (e.g., up to 1 billion), forcing the bitmap to allocate space for the entire range and wasting most of it.

The Bloom filter strikes a balance: it consumes memory comparable to a bitmap while providing a controllable false‑positive rate. With 30 million items and a 1% false‑positive setting, the filter occupies roughly 35 MB.

Bloom Filter Mechanics

A Bloom filter consists of a bit array and several hash functions. Insertion hashes the element with k functions and sets the corresponding bits to 1. Querying hashes the element again and checks whether all k bits are 1; if any bit is 0 the element is definitely absent, otherwise it is probably present.

This design guarantees no false negatives: an element that was inserted will always be reported as present. False positives occur when bits set by different elements overlap.

False‑Positive Impact

With a 1% false‑positive rate, about 1 in 100 non‑existent elements will be reported as present. In the popup scenario this means a few users who have not yet seen the popup may be mistakenly considered as already seen, resulting in a missed notification. Because missing a few popup alerts is acceptable, a 1% rate is considered tolerable.

Key Parameter Determination

The bit‑array size is calculated by the formula m = -n * ln(p) / (ln2)^2, where n is the expected insertions and p is the false‑positive probability. Redisson internally applies this formula.

Expected Insertions – Determines the length of the bit array; under‑estimating leads to higher actual false‑positive rates, so a safety margin (e.g., 1.2–1.5× the member count) is recommended.

False‑Positive Probability – Lower rates require larger bit arrays and more hash functions, increasing memory and CPU cost. Example trade‑offs:

1% → ~35 MB for 30 M items

0.1% → ~52 MB

0.01% → ~70 MB

Expiration – Bloom filters cannot delete individual elements, so an expiration time is set for the whole filter. In the example the popup lasts 5 days, so the filter expires after 6 days, allowing automatic recreation.

Hash Function Count

The optimal number of hash functions is k = -(ln(p) / ln2). A lower false‑positive rate increases k, which raises insertion overhead.

Deletion Limitation and Counting Bloom Filters

Standard Bloom filters cannot delete a single element because bits are shared among many elements; clearing a bit could invalidate other elements. A counting Bloom filter replaces each bit with a small counter (typically ≥4 bits). Insertion increments the counters, deletion decrements them, and query checks whether the counter is >0. This variant multiplies memory usage several‑fold (e.g., 35 MB → ~140 MB for the same parameters).

In most production cases the simple Bloom filter with an expiration policy is sufficient; counting variants are used only when true per‑element deletion is required and the extra memory cost is justified.

Capacity Limits

The bit array size is fixed at initialization. If the actual number of inserted elements far exceeds the expected size, the array becomes saturated, false‑positive rates soar, and the filter loses its usefulness. When capacity is exceeded, a new filter should be created and the old one discarded.

Practical Library Choices

Two popular Java implementations are:

Guava BloomFilter – Suitable for single‑node applications; creation is straightforward and the filter lives in the JVM heap.

Redisson RBloomFilter – Stores the bit array in Redis, enabling multiple service instances to share the same filter. This is the approach shown in the production code.

The choice depends on deployment: use Guava for standalone services, Redisson for distributed environments.

Summary

Bloom filters provide a memory‑efficient solution for massive existence checks: 30 million entries can be handled with only 35 MB while tolerating a 1% false‑positive rate. Understanding the three core aspects—bit array sizing, false‑positive probability, and expiration—allows engineers to size the filter correctly, avoid over‑ or under‑provisioning, and select the appropriate library for their architecture.

For interview preparation, be ready to explain the bit‑array structure, the role of multiple hash functions, and why false positives are one‑sided (no false negatives). Emphasize that accurate estimation of expected insertions is crucial for maintaining the desired false‑positive rate.