Hot Key Cache Eviction

partial

Summary

When Redis evicts a heavily-accessed cache key due to memory pressure under the allkeys-lru eviction policy, all concurrent requests for that key simultaneously miss the cache and issue identical queries to the backing database. Unlike TTL-based thundering herd, this eviction is triggered by memory pressure rather than expiry : meaning it can affect recently-accessed keys and occurs unpredictably as memory utilization crosses eviction thresholds, not at a predictable scheduled time.

Description

Redis allkeys-lru eviction works by maintaining an approximation of recently-used order and evicting the least-recently-used keys when memory reaches maxmemory. The LRU approximation (configurable via maxmemory-samples, default 5) randomly samples N keys and evicts the least-recently-used among them. This means a hot key can be evicted if it is not among the N sampled candidates: the probability increases as the hot key pool grows relative to the total key count.

The dangerous scenario: a hot key serving 500 requests/second is cached alongside 100,000 other keys. Memory pressure forces eviction. Redis samples 5 keys; the hot key is not among them. A moderately warm key is evicted. 10 ms later, memory pressure is still present; the hot key IS sampled and is the least-recently-used among its sample (because the sample included even hotter keys). The hot key is evicted. All 500 in-flight requests for it simultaneously miss the cache and query the database. This looks identical to thundering herd from the database perspective, but the eviction is silent: no TTL countdown, no scheduled expiry, no operator-predictable timing.

The failure is self-amplifying through a feedback loop. The hot key eviction causes a database load spike. The database query latency increases. Cache repopulation is delayed because the query takes longer. During this extended miss window (2-10x longer than normal query time), more cache misses accumulate. Each miss attempts another query. The database connection pool begins to queue. Queue depth grows. Timeout errors begin. In systems with circuit breakers, the circuit may open, blocking all requests to the backend for the entire circuit recovery window.

The problem is specific to allkeys-lru and allkeys-lfu policies, which can evict any key. Systems using volatile-lru (only evict keys with TTL set) are immune to hot key eviction on keys without a TTL. However, many production deployments use allkeys-lru to handle cases where applications set keys without TTLs, trading eviction safety for operational simplicity.

Characteristics

Propagationfeedback loop

Time to detect15–60 seconds via Redis keyspace_misses spike + database QPS spike correlation. Without combined Redis and database monitoring, the failure appears as a sudden database error rate increase with no obvious cause, taking 2–5 minutes to diagnose correctly.

Blast radiusThe database bears the full simultaneous load of all requests that were hitting the evicted key. If the key was absorbing 500 req/s and the database query takes 200ms, the initial stampede delivers up to 100 concurrent queries. If the connection pool exhausts, all requests requiring database access fail, not just those for the evicted key. In systems where Redis also serves as a session store or rate limiter, memory pressure that causes evictions can also corrupt session data or reset rate limit counters.

Triggers

·Redis memory utilization exceeds maxmemory threshold, triggering eviction
·Sudden traffic spike increases total key footprint (new users, new feature launch) until memory saturates
·Large value keys inserted that consume a disproportionate share of memory, forcing aggressive eviction of small hot keys
·maxmemory-samples set to 5 (default), making LRU approximation coarse enough to occasionally evict hot keys

Detection Signals

error rate spikelatency spikememory pressurealert

Mitigation Strategies

Protect hot keys from eviction using volatile policy with manual TTL managementpreventscomplexity: medium

Switch Redis eviction policy to volatile-lru and ensure that hot keys are NOT given a TTL. Keys without a TTL are never evicted under volatile-lru (only keys with TTL are candidates for eviction). Hot keys that must not be evicted are set with SET key value (no EX/PX). This requires discipline in application code to distinguish hot durable keys from warm expendable keys, but completely prevents hot key eviction.

Mutex on cache miss (lock-based repopulation)complexity: medium

On a cache miss for any key serving >50 req/s, acquire a short-lived Redis lock (SETNX hot_key_lock 1 PX 5000) before querying the database. Only the lock holder executes the database query and repopulates the cache. All other concurrent misses for the same key poll the lock and wait. This limits N simultaneous database queries to 1, regardless of whether the miss was caused by eviction or TTL expiry. Reduces stampede impact by 99% for hot keys.

Increase maxmemory-samples for better LRU approximationcomplexity: low

Increase maxmemory-samples from 5 to 10 or 20. Higher sample counts make the LRU approximation more accurate, significantly reducing the probability that a recently-accessed hot key is incorrectly selected for eviction. At maxmemory-samples=10, eviction quality approaches true LRU. The CPU cost increase is less than 10% on typical workloads. This does not prevent eviction under extreme memory pressure but reduces the probability of hot key eviction substantially.

Recovery Steps

1.Check Redis keyspace_misses in INFO stats: a sudden increase confirms a cache miss event
2.Identify the evicted key by correlating database slow query log with the cache miss timestamp
3.Manually re-populate the evicted key by running the backing query once and setting the result in Redis
4.If database is under stampede load, execute pg_terminate_backend for duplicate inflight queries before repopulating
5.After recovery, monitor Redis memory utilization: if consistently >90%, either increase Redis maxmemory or reduce the cache key footprint

Estimated recovery time: 30–90 seconds after manual cache repopulation. Database load normalizes within 30 seconds of the hot key being restored. If connection pool was exhausted, allow an additional 30–60 seconds for the pool to drain queued requests.

Affected Systems

Patterns

cache asideread replica

Technologies

redismemcachedpostgresqlmysql

Basis

Redis LRU eviction mechanics are precisely documented in Redis source code and official documentation; maxmemory-samples behavior is empirically verified; the hot key eviction pattern is a known production failure mode distinct from TTL-based thundering herd