LRU cache guide · 6/6

LRU in the Real World

LRU, or something close to it, runs at every layer of a computer system. This chapter tours those layers, shows the library versions you should reach for, and lists the pitfalls that cause most caching bugs.

Hardware, operating systems and databases

CPU caches pick a victim within a small set of lines. True LRU needs too much state in hardware, so CPUs usually implement pseudo-LRU variants such as tree-PLRU.
OS page cache: Linux keeps file pages on active and inactive lists. A page must be touched twice to be promoted, which protects hot pages from one-time scans. It is an LRU approximation in the spirit of 2Q and CLOCK.
Database buffer pools: MySQL InnoDB uses an LRU list with midpoint insertion, so new pages enter the "old" part first and a full table scan cannot flush the hot part. PostgreSQL uses clock-sweep, another approximation.

Redis eviction policies

When Redis reaches maxmemory, the maxmemory-policy setting decides what to evict. The long-standing options are noeviction, allkeys-lru, volatile-lru, allkeys-lfu, volatile-lfu, allkeys-random, volatile-random or volatile-ttl. The volatile- policies only consider keys that have an expiry set. Redis approximates LRU by sampling a few keys (maxmemory-samples, default 5) and evicting the oldest among them, which avoids a global linked list.

redis-cli CONFIG SET maxmemory 256mb
redis-cli CONFIG SET maxmemory-policy allkeys-lru

CDNs and browsers

CDN edge servers have limited disk and memory, so objects that are rarely requested are evicted, usually by LRU-like policies combined with the TTL from Cache-Control: max-age. Browsers do the same with their HTTP cache: when the disk quota is reached, least recently used entries go first.

Library versions

Python's functools.lru_cache memoizes a function with an LRU bound. Use maxsize=None (or functools.cache) for an unbounded cache, typed=True to cache 1 and 1.0 separately, and cache_clear() to invalidate.

Java's LinkedHashMap becomes an LRU cache with two changes: pass accessOrder = true so that get moves an entry to the end, and override removeEldestEntry.

import java.util.LinkedHashMap;
import java.util.Map;

class LruMap<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LruMap(int capacity) {
        super(16, 0.75f, true);            // true = access order
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;          // evict after each insert
    }
}

For production Java services, libraries such as Caffeine (W-TinyLFU, with expiry and concurrency built in) are usually a better choice. In Node.js the lru-cache package plays the same role.

Thread safety

In an LRU cache even a read is a write: get reorders the list. Two threads touching nodes at the same time can corrupt the pointers, so a read-write lock does not help. The simplest fix is one lock around every operation; under heavy contention, split the cache into shards with a lock each.

import threading
from collections import OrderedDict

class ThreadSafeLRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()
        self.lock = threading.Lock()

    def get(self, key, default=None):
        with self.lock:
            if key not in self.data:
                return default
            self.data.move_to_end(key)
            return self.data[key]

    def put(self, key, value):
        with self.lock:
            self.data[key] = value
            self.data.move_to_end(key)
            if len(self.data) > self.capacity:
                self.data.popitem(last=False)

functools.lru_cache keeps its internal structure consistent across threads, but it may call the wrapped function more than once for the same key when calls race.

Cache invalidation pitfalls

Stale data: after updating the source, delete or update the cached copy, or give entries a TTL so mistakes heal on their own.
Cache stampede: when a hot key expires, many requests miss together and hit the database. Use a per-key lock, request coalescing or slightly randomized TTLs.
Mutable cached values: returning the same list or dict to every caller lets one caller change what others see.
Incomplete keys: if the result depends on the user, locale or a flag, that value must be part of the key.
Unbounded caches: a dict "cache" without eviction is a memory leak. lru_cache on a method also keeps self alive.

from functools import lru_cache

@lru_cache(maxsize=128)
def settings(user_id):
    return {"theme": "light", "user": user_id}

s = settings(1)
s["theme"] = "dark"                 # mutates the cached object
print(settings(1)["theme"])         # dark, a surprise for every caller

@lru_cache(maxsize=128)
def settings_safe(user_id):
    return ("light", user_id)       # immutable value

Summary

LRU and its approximations (pseudo-LRU, CLOCK, sampling, midpoint insertion) run in CPUs, kernels, databases, Redis, CDNs and browsers.
Prefer library implementations: OrderedDict, lru_cache, LinkedHashMap, Caffeine, lru-cache.
Lock every operation, including reads, and plan invalidation from the start.