Cache Penetration

Concept

Cache penetration occurs when querying data that does not exist in the database. The typical cache flow works as follows: data retrieval first checks the cache. If the key does not exist or has expired, the query proceeds to the database, and the retrieved object is stored in the cache. If the database returns null, the value is not cached.

Its important to distinguish this from cache breakdown. Cache breakdown refers to a scenario where the cache does not contain specific data, but the database does, and a particular key experiences extremely high traffic. When this key expires (typically due to cache TTL), concurrent requests bypass the cache and directly hit the database, creating a hole in the protective barrier.

Solutions

Bloom Filter

A Bloom filter is a probabilistic data structure using a bit vector or bit array. To map a value to a Bloom filter, multiple hash functions generate multiple hash values, each pointing to a bit position that is set to 1.

Working Principle: For a given key, apply k hash functions to generate k values, set these k positions to 1 in the bit array. During lookup, if all specified positions are 1, the Bloom filter indicates the key might exist.

Different keys may map to the same bit position. When many keys are stored, most bits become 1, causing false positives. If the filter indicates a key does not exist, it definitely does not exist. If it indicates the key might exist, the data may not actually exist.

Redis bitmap supports 2^32 size, occupying approximately 512MB of memory. With a false positive rate of 0.01%, it can store around 200 million keys while maintaining high performance and minimal space usage, eliminating numerous ineffective database connections.

Implementation:

Add the dependency:

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

Code example:

public class CacheFilterTest {
    private static int expectedItems = 1000000;
    private static double falsePositiveRate = 0.01;
    private static BloomFilter<Integer> bloomFilter = 
        BloomFilter.create(Funnels.integerFunnel(), expectedItems, falsePositiveRate);

    public static void main(String[] args) {
        for (int i = 0; i < 1000000; i++) {
            bloomFilter.put(i);
        }
        int falsePositives = 0;
        for (int i = 1000000; i < 2000000; i++) {
            if (bloomFilter.mightContain(i)) {
                falsePositives++;
                System.out.println(i + " returned false positive");
            }
        }
        System.out.println("Total false positives: " + falsePositives);
    }
}

Practical Application:

@Cacheable(value="productData")
public String fetch(String key) {
    String cached = redis.get(key);
    if (cached == null) {
        if (!bloomFilter.mightContain(key)) {
            return null;
        }
        cached = database.query(key);
        redis.set(key, cached);
    }
    return cached;
}

Caching Null Values

When the storage layer returns null, cache the null value with an expiry time. Subsequent requests for this key will retrieve the null from cache, protecting the database.

However, this approach has two drawbacks:

• Caching null values requires additional memory for storing these keys, potentially many null entries
• Even with TTL设置, a time window exists where cached and stored data may be inconsistent, affecting businesses requiring strong consistency

Cache Avalanche

Concept

Cache avalanche refers to massive data expiration in the cache, combined with large query volumes causing database overload or failure. Unlike cache breakdown (which targets a single key), cache avalanche affects multiple different keys expiring simultaneously, resulting in numerous cache misses hitting the database.

Causes

Consider a flash sale scenario: products are cached with a 1-hour TTL. When these缓存 expire at 2 AM, all product queries direct to the database, creating periodic pressure spikes.

Solutions

1. Staggered Cache Expiration

Apply different expiration periods for product categories, adding random factors within categories. This disperses cache expiration times. Popular categories receive longer cache durations while niche categories have shorter ones, optimizing cache resource utilization.

2. Distributed Cache Distribution

When using distributed cache deployments, distribute hot data evenly across different cache instances.

3. Never Expire Hot Data

Set critical hot data to never expire, updating it through background processes or programmatic eviction.

4. Rate Limiting with Locks

Implement rate limiting and locking mechanisms to control concurrent access during expiration events.

Cache Breakdown

Concept

Cache breakdown occurs when specific data exists in the database but not in the cache, and that particular key experiences extremely high concurrent access. When the key expires, sustained high concurrency breaks through the cache directly to the database.

Solutions

1. Never Expire Hot Data

Set extremely hot keys to never expire or use background refresh mechanisms.

2. Mutex Locking

A common approach uses mutex locks. When the cache misses (value is null), instead of immediately loading from database, attempt to set a mutex key using cache tools with atomic operations (like Redis SETNX or Memcache ADD). Only after successful lock acquisition, load from database and populate cache. Otherwise, retry the entire cache retrieval process.

SETNX means "SET if Not eXists", enabling lock functionality.

public String retrieve(String key) {
    String cached = redis.get(key);
    if (cached == null) {
        if (redis.setNx(lockKey, 1, 180) == 1) {
            try {
                cached = database.query(key);
                redis.set(key, cached, expireTime);
            } finally {
                redis.delete(lockKey);
            }
        } else {
            Thread.sleep(50);
            return retrieve(key);
        }
    }
    return cached;
}