A Close Study of Redis's LFU Memory Eviction Policy

Redis’s LFU (Least Frequently Used) eviction policy is an “upgraded” approximate algorithm built on top of LRU. It reuses the same 24-bit lru field in the object header and, through clever encoding and logarithmic counting, achieves an approximate tracking of access frequency at a tiny memory cost.

Below we examine it point by point: from the storage structure, to counter increment/decrement, to the eviction decision, to parameter configuration.

1. The bit layout of the 24-bit field

Every Redis object has an lru attribute (24 bits). In LFU mode it no longer holds a second-level timestamp but is split into two parts:

 High 16 bits: Last Decay Time (in minutes)
 Low   8 bits: Logarithmic Counter (range 0–255)

• High 16 bits: store (server.unixtime / 60) & 0xFFFF, i.e. the low 16 bits of the current minute timestamp. It can represent about 45 days at most — enough to cover eviction scenarios — and even with wraparound, as long as the interval doesn’t exceed 45 days, the difference can be computed correctly.
• Low 8 bits: a frequency counter from 0–255, but it is not a direct accumulation of access counts; it’s a logarithmically smoothed “approximate frequency.”

When a key is accessed, Redis calls updateLFU(): it first decays the counter based on the elapsed time, then probabilistically increments the counter, and finally re-encodes the new minute timestamp and counter back into lru.

2. Counter increment: logarithmic growth

To let the 8-bit counter (0–255) represent both low and high frequencies, distinguish between them, and avoid hot keys quickly maxing out, Redis uses probabilistic increment.

The increment formula (at the source level):

double p = 1.0 / ((counter - LFU_INIT_VAL) * server.lfu_log_factor + 1);
if ((random() & 0xFFFF) < p * 0xFFFF) counter++;

• LFU_INIT_VAL defaults to 5; a new key’s counter starts at 5.
• lfu_log_factor is a configurable logarithmic factor, default 10.
• As counter grows, p gets smaller and smaller, making increments harder and harder.

Example (with factor = 10, typical access counts vs. counter values):

As you can see, the counter grows fast early and extremely slowly later — this lets new keys quickly shed their “initial low score” while letting extremely hot keys be effectively distinguished within the 8-bit space.

3. Counter decay: linear decrease over time

LFU’s core is “frequency,” but a key that goes unused for a long time should have its frequency drop. The decay logic runs on every key access and during eviction evaluation.

The decay computation:

// current minute timestamp (16 bits)
now = LFUGetTimeInMinutes();      // (server.unixtime/60) & 65535
ldt = o->lru >> 8;               // last decay time
time_diff = now - ldt;           // unsigned difference (handles wraparound automatically)

num_periods = time_diff / server.lfu_decay_time;  // number of decay periods
counter = counter - num_periods;  // if negative, set to 0

• lfu_decay_time is a config item, default 1 (minute).
• Meaning: every 1 minute, the counter decreases by 1.
• If lfu_decay_time = 2, it decreases by 1 only every 2 minutes, so decay is slower.

Because this decay “makes up for all the historical elapsed time at once,” for example a key whose counter is now 20 and was last accessed 10 minutes ago, with decay_time = 1, the moment it’s accessed (or during eviction evaluation) the counter is reduced by 10 straight to 10. A key untouched for a long time drops to 0 and is very easily evicted.

4. Protecting new keys: the initial value

A newly created key doesn’t start at 0 but is directly given the initial counter LFU_INIT_VAL (default 5).
The benefit: it avoids a new key being “wrongly killed” in sampled eviction before it has accumulated enough accesses.

The field encoding at initialization:

o->lru = (LFUGetTimeInMinutes() << 8) | LFU_INIT_VAL;

5. Eviction decision: sampled approximate LFU

Redis does not maintain a global frequency ranking (too costly); instead it uses sampled approximation:

1. Each time eviction is needed, it randomly picks maxmemory-samples keys from the database (default 5).
2. For each sampled key, it calls LFUDecrAndReturn(o) to get the latest counter value after decay.
3. It sorts the samples by counter from small to large and puts them into the eviction candidate pool.
4. Finally it evicts the key with the smallest counter from the pool.

So even if a key’s raw counter is very high, as long as it hasn’t been accessed in a long time, its post-decay value shrinks sharply and it’s still removed first at eviction. This is exactly the combined effect of “frequency + time.”

6. Summary of the key config parameters

Tuning directions:

• If access frequencies vary greatly, you can raise lfu-log-factor (e.g. 20) so the 8-bit counter can distinguish higher-frequency keys.
• If you want cold data to age faster, lower lfu-decay-time (even 0, but 0 means it decays to nearly 0 on every access — not recommended); conversely, to keep hot data “warm” longer, raise the value.
• Raising maxmemory-samples makes eviction more accurate; keeping it under 10 is recommended to avoid a noticeable performance drop.

7. Caveats and limitations

• Wraparound: the 16-bit minute timestamp wraps around roughly every 45 days. As long as a key’s idle time is under 45 days (almost always true in eviction scenarios), the unsigned difference computation is correct.
• Large writes in a short time: new keys start at 5; if a flood of new keys arrives in a short time, they may evict each other via sampling, but because their initial values are the same, it degrades to near-random eviction. It can be mitigated by raising the initial value (requires source changes) or combining with another policy.
• Counter overflow: because logarithmic growth is extremely slow, the 8 bits are almost impossible to max out; even for a hot key with millions of requests per second, it would take an astronomical number of accesses to reach 255 — no concern in real production.
• Version differences: LFU was introduced in Redis 4.0 and the mechanism has stayed stable since; the above details apply to mainstream versions from 4.0 through 7.x/8.x.

To sum up, Redis’s LFU cleverly achieves approximate frequency-based eviction at a constant memory and CPU cost through logarithmic counting + minute-level decay + sampled eviction — very well suited to scenarios with stable hot spots where you don’t want periodic key scanning to cause mistaken evictions.