LRU in the Real World

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.

Further reading

• Cache replacement policies (Wikipedia)
• functools.lru_cache (Python docs)
• collections.OrderedDict (Python docs)
• LinkedHashMap (Java SE docs)
• Key eviction (Redis docs)
• Map (MDN)