How Bitmap, Bloom Filters, and Cache Strategies Solve Massive Data Lookups

Bitmap and Bloom Filter

When checking whether a large set of integers contains a specific value, a simple hash map can consume hundreds of megabytes or even gigabytes of memory for billions of entries. Bitmap uses one bit per possible value, dramatically reducing memory consumption.

For example, storing numbers up to 100 million requires only about 12 MB of memory (100 million bits). The following Java class implements a basic bitmap using a byte array and bitwise operations:

public class MyBitMap {
    private byte[] bytes;
    private int initSize;

    public MyBitMap(int size) {
        if (size <= 0) {
            return;
        }
        initSize = size / 8 + 1;
        bytes = new byte[initSize];
    }

    public void set(int number) {
        int index = number >> 3; // divide by 8
        int position = number & 0x07; // modulo 8
        bytes[index] |= 1 << position;
    }

    public boolean contain(int number) {
        int index = number >> 3;
        int position = number & 0x07;
        return (bytes[index] & (1 << position)) != 0;
    }

    public static void main(String[] args) {
        MyBitMap myBitMap = new MyBitMap(32);
        myBitMap.set(30);
        myBitMap.set(13);
        myBitMap.set(24);
        System.out.println(myBitMap.contain(2));
    }
}

While bitmap excels when the value range is limited, its memory cost grows with the range, making it unsuitable for sparse large ranges (e.g., 10 billion possible values would need ~120 MB).

Bloom Filter

To handle huge ranges with limited memory, a Bloom filter hashes each element into multiple positions in a bitmap, reducing false‑positive probability while accepting that some queries may incorrectly report existence. It cannot guarantee true negatives, but it can reliably indicate non‑existence.

High‑Concurrency Cache Design Strategies

Cache sits between CPU and memory (or between application and database) to alleviate latency differences. In high‑traffic systems, proper cache design is crucial to avoid bottlenecks.

Cache Consistency Patterns

Cache‑aside

Read‑through

Write‑through

Write‑behind

Cache Penetration

When requests query keys that never exist, they bypass the cache and hit the database, potentially overwhelming it. Two common mitigations are:

Store a placeholder (e.g., null) in the cache for missing keys to prevent repeated DB hits.

Use a Bloom filter in front of the cache to quickly filter out definitely‑absent keys.

Cache Avalanche

An avalanche occurs when many cached entries expire simultaneously, causing a surge of DB traffic. Mitigation techniques include:

Distribute expiration times (staggered TTLs) to avoid synchronized expiry.

Employ distributed locks so only one request repopulates a missing entry.

Pre‑warm cache with hot data.

Use high‑availability cache architectures (e.g., Redis master‑slave with Sentinel).