What is cache stampede and cache penetration? How to deal with them?

Cache stampede — a situation where many requests simultaneously try to retrieve data from the cache, but the cache is empty or outdated, and all these requests start accessing the slow data source (e.g., database) at the same time, creating a load.

Cache penetration — a situation where requests constantly access the cache with keys that are not present (e.g., due to missing data in the database), and each such request leads to a database query, which can cause overload.

How to fight:

Cache stampede:

• Use a locking mechanism (mutex) when updating the cache: the first request updates the cache, others wait.
• Apply the "early recomputation" strategy — update the cache before the expiration time.
• Use "probabilistic early expiration" — update the cache with a certain probability before TTL expires.

Cache penetration:

• Cache negative results (e.g., empty or null values) with a short TTL to avoid repeated database access.
• Validate input data to prevent requests with incorrect keys.
• Use filters (e.g., Bloom filter) for preliminary checking of key existence in the database.

Example in Java using locking for cache stampede:

private final ConcurrentHashMap<String, Object> cache = new ConcurrentHashMap<>();
private final ConcurrentHashMap<String, ReentrantLock> locks = new ConcurrentHashMap<>();

public Object getData(String key) {
    Object value = cache.get(key);
    if (value != null) return value;

    ReentrantLock lock = locks.computeIfAbsent(key, k -> new ReentrantLock());
    lock.lock();
    try {
        // re-check after acquiring lock
        value = cache.get(key);
        if (value == null) {
            value = loadFromDb(key); // slow operation
            cache.put(key, value != null ? value : NULL_PLACEHOLDER);
        }
        return value == NULL_PLACEHOLDER ? null : value;
    } finally {
        lock.unlock();
    }
}

This approach helps avoid simultaneous database access when the cache is missing.