Eviction: LRU, LFU and maxmemory

Caching and Redis Mid-level Python 3.13+ PostgreSQL 17+ Reviewed 31 Oct 2026 By Best Latest Apps

Predict the output

Capacity 2. After put a, put b, get a, put c, which keys remain?

Python 3.13

from collections import OrderedDict


class LRU:
    def __init__(self, capacity: int) -> None:
        self.cap = capacity
        self.data: OrderedDict[str, str] = OrderedDict()

    def get(self, key: str) -> str | None:
        if key not in self.data:
            return None
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key: str, value: str) -> None:
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.cap:
            self.data.popitem(last=False)


c = LRU(2)
c.put("a", "1")
c.put("b", "2")
c.get("a")
c.put("c", "3")
print(list(c.data))

Options['a', 'c']['b', 'c']['a', 'b']['a', 'b', 'c']

Hint 1 of 1

Which key was touched least recently?

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A ['a', 'c']

Correct. Reading a made b the least recently used, so b was evicted.

LRU evicts the entry that was used longest ago. The get moved a to the most-recent end, so when c pushed the cache past 2 entries, b was the oldest and went.

Why not the others?

B ['b', 'c']. a was used more recently than b.
C ['a', 'b']. Adding c over capacity evicts one key.
D ['a', 'b', 'c']. Capacity is 2.

30-second answer

With maxmemory set, Redis applies maxmemory-policy. allkeys-lru evicts the least recently used keys, a good default for a pure cache. allkeys-lfu evicts the least frequently used, better when a few keys stay popular over time. The volatile-* variants only evict keys with a TTL, and noeviction (the default) returns errors on writes, which suits Redis used as a primary store.

Practise saying it · 30 s. No recording, just a timer

Explain eviction policies.

Say your answer out loud, then check which of these points you covered:

maxmemory + policy
allkeys-lru for caches
LFU for stable popularity
noeviction for stores
Monitor evictions

Deep dive

Redis's LRU and LFU are approximations that sample keys (maxmemory-samples, default 5).

Watch evicted_keys and hit rate in INFO stats; constant eviction means the cache is too small.

Mixing cache data and must-keep data in one instance with volatile-lru is fragile; use separate instances.

Big values hurt: one 50 MB value evicts many small useful keys.

A tiny LRU with OrderedDict Ran on Python 3.13.5 · mypy --strict

Python 3.13

from collections import OrderedDict


class LRU:
    def __init__(self, capacity: int) -> None:
        self.cap = capacity
        self.data: OrderedDict[str, str] = OrderedDict()

    def get(self, key: str) -> str | None:
        if key not in self.data:
            return None
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key: str, value: str) -> None:
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.cap:
            self.data.popitem(last=False)


c = LRU(2)
c.put("a", "1")
c.put("b", "2")
c.get("a")
c.put("c", "3")
print(list(c.data))

Common mistakes

Leaving noeviction on a cache and getting write errors at peak.
No maxmemory at all, so the OS kills Redis.
Storing sessions and cache in one instance with allkeys-lru.

Senior take & follow-ups

Name the policies, say which suits a pure cache, and how you'd monitor it.

Follow-up questions

Think of your answer first, then open the hint.

Exact LRU in Redis?
Show hint
No: it samples keys and evicts the best candidate.
When pick LFU?
Show hint
When popularity is stable and a scan of cold keys would push hot ones out under LRU.

Compare on iOS: A thread-safe LRU cache The same LRU idea; here it's Redis's sampled policy across a fleet instead of an in-app structure.

Suggest a fix if something here is wrong or out of date.