LRU Cache
What it is
A cache keeps a small set of values ready to use. LRU means least recently used. When the cache is full, it removes the key that has gone longest without use. Removing a stored item to make room is called eviction. Reading a key counts as use. Updating a key counts too.
The core idea
A hash map supports fast key lookup. A doubly linked list represents order of use. Together, they can support O(1) reads and updates on average because neither lookup nor a change in order needs a full scan. The cost is extra memory for links and more state to keep consistent. LRU works well when recent use predicts future use. A long scan of unrelated keys can still push useful entries out.
Example
A cache can hold two keys.
Put(1, 10), thenPut(2, 20)stores both.Get(1)returns 10 and makes key 1 the newest used key.Put(3, 30)removes key 2.Get(2)reports not found.
Where you meet this
- Redis can drop the least recently used keys when it reaches its memory limit (the
allkeys-lrusetting). It does not keep an exact order. It checks a few random keys and drops the oldest of them, because an exact order costs memory. (Redis key eviction) - Memcached splits the items of each size class into HOT, WARM, and COLD least recently used queues, and normally takes space back from the COLD one. (Memcached LRU notes)
- PostgreSQL keeps disk pages in a shared memory pool. It does not keep an exact order of use either. Each page has a small use counter, and a "clock hand" goes round the pool, lowers each counter, and reuses the first page whose counter is zero and that no one is using right now. (PostgreSQL buffer manager notes)
When to choose it: recent use is a good guess for the next use, like sessions of users who are online now, or pages people are reading today. The Redis docs call it a good default when a small part of the keys gets most of the reads.
When not to: one long scan over keys that are read only once, like a nightly report, pushes every useful key out. An exact order also costs memory and work on every read. The Redis docs give memory as the reason Redis uses an estimate.
If some keys stay popular for a long time, compare LFU Cache, which counts how often a key is used. Redis offers that rule too (allkeys-lfu).
Common bugs
- Removing the oldest added key, rather than the oldest used key.
- Returning a value without counting the read as recent use.
- Removing another key when updating an existing key.
- Leaving a removed key in the map.
- Treating zero or negative values as missing data.
- Keeping one key too many, or removing a key before the cache is full.
Keep it fast
Get and Put should take a small, fixed amount of work. Does each call do more work as the cache grows? A full scan or a full copy makes large caches slower.
Learn more
Compare LFU Cache to learn a different removal rule. Operating system books explain LRU and CLOCK for page replacement. Redis documentation explains how real caches can use approximate LRU.