Understanding Redis LRU and LFU: How Memory Eviction Works

Redis 4.0 introduced eight memory eviction policies, four of which are based on LRU and LFU algorithms. This article focuses on the LRU and LFU mechanisms used inside Redis.

LRU Algorithm

LRU (Least Recently Used) follows the "recently used" principle: objects accessed more recently have higher retention priority, while those not accessed for a while are likely to be evicted when the cache is full. Redis implements an approximate LRU by randomly sampling a subset of keys instead of scanning all keys, trading some accuracy for performance.

Redis does not maintain a dedicated doubly‑linked list for LRU. Instead, each key stores a timestamp in an extra field, and a global LRU clock (an incrementing integer) records access order. When a key is accessed, its timestamp is updated to the current clock value. During eviction, Redis selects the key with the smallest timestamp among the sampled keys.

#define LRU_BITS 24
typedef struct redisObject {
  unsigned type:4;
  unsigned encoding:4;
  unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                           * LFU data (least significant 8 bits frequency
                           * and most significant 16 bits access time). */
  int refcount;
  void *ptr;
} robj;

The lru field in redisObject records the last access time for each key; it is updated on every read or write.

LFU Algorithm

LFU (Least Frequently Used) follows the "least frequently used" principle: objects with the lowest access count receive the lowest retention priority. When the cache is full, Redis evicts the keys with the smallest access frequency. Like LRU, Redis samples a random subset of keys for eviction.

Redis records both the access count and a timestamp using the same 24‑bit lru field. The high 16 bits store the Last Decrement Time (ldt), acting as a timestamp, while the low 8 bits store a logistic counter (logc) that tracks access frequency.

In the LRU algorithm, the 24‑bit lru field stores the key's access timestamp.

In the LFU algorithm, the 24‑bit lru field is split: the high 16 bits store ldt (timestamp), and the low 8 bits store logc (frequency counter).

Practical guidance: if workload access patterns are relatively uniform, LRU usually satisfies operational needs. For workloads with strong temporal spikes—such as promotional events that create sudden hot data—LFU is recommended to retain frequently accessed items.