LRU cache simulator
A least recently used (LRU) cache keeps a fixed number of entries and, when it is full, throws out the one that has gone unused the longest. It is built from a hash map and a doubly linked list, so every operation takes constant time. Step through it below. Further down are a worked example, code in Python and Java, and the follow-up questions interviewers ask.
0 of 4 entries in use.
Each key is hashed to a bucket, and the entry there points to that key's node in the list. Finding a node therefore takes one hash lookup instead of a walk through the list.
Press a key or play a pattern. Each get is explained step by step here.
After some gets, this compares LRU with Belady's optimal policy on the same sequence.
How to use the simulator
Press a key, or type one and press Get. The cache works as a read-through cache: if the key is present it is a hit; if not, it is a miss, the value is loaded from the slower store behind the cache and added. The list shows the entries from most recently used (left) to least recently used (right), and the panel lists every step the cache took, including each pointer change.
Try these:
- Press A, B, C, D, then A again. A moves to the front. Now press E: the cache is full, so B, the least recently used, is evicted.
- Play Loop one too big, which cycles through one more key than the cache holds. Every get misses, because each key is evicted just before it comes round again. Compare with the optimal policy in the panel.
- Play A one-off scan: two keys are used repeatedly, then a run of keys used only once pushes them out, and they miss when they come back.
What is an LRU cache?
A cache keeps copies of data in a small, fast store so that repeated requests do not have to go to a larger, slower one. Because the cache is small, it eventually fills up, and to add something new it must remove something old. The rule that chooses what to remove is the replacement policy, or eviction policy.
Least recently used (LRU) removes the entry that has gone the longest without being read or written. It relies on temporal locality: data used recently is likely to be used again soon, and data untouched for a long time probably is not. That holds for many real workloads, which is why LRU and close approximations of it are found in CPU caches, operating system page caches, databases and application caches.
How it works
An LRU cache needs to do three things quickly: find an entry by key, mark an entry as just used, and find the least recently used entry. No single basic structure does all three, so the usual design combines two:
- A doubly linked list holds the entries in order of use, the most recently used at the front and the least recently used at the back. Moving a node to the front, or removing the node at the back, only changes a few pointers.
- A hash map maps each key to its node in the list, so a node can be found without walking the list.
A get looks the key up in the hash map. On a hit, it unlinks the node from its place in the list and inserts it at the front. A put of a new key creates a node at the front and adds it to the map; if the cache is already full, it first removes the node at the back of the list and deletes that key from the map. All of these steps take constant time, so get and put are O(1).
The list must be doubly linked. To unlink a node in constant time you need its previous node as well as its next one; a singly linked list would have to be searched from the start to find it. Implementations often add two dummy nodes, a head and a tail, so that inserting and removing never has to handle an empty list or an end of the list as a special case.
LRU cache example
A cache with room for three entries receives requests for A, B, C, A, D, B, E and A, in that order. On a miss the value is loaded and put at the front; when the cache is full, the entry at the back goes. The list is written most recently used first.
| Request | Result | List after the request |
|---|---|---|
| A | Miss | A |
| B | Miss | B A |
| C | Miss | C B A |
| A | Hit: A moves to the front | A C B |
| D | Miss, evicts B | D A C |
| B | Miss, evicts C | B D A |
| E | Miss, evicts A | E B D |
| A | Miss, evicts D | A E B |
LRU gets one hit out of eight requests. It evicted B two requests before B came back, and A one request before A came back. Bélády’s optimal policy, which looks ahead, gets three hits on the same requests: when D arrives it evicts C, which is never requested again, and keeps A and B. Type the same keys into the simulator to watch each pointer change; its panel shows the optimal count alongside.
LRU cache implementation
Many languages provide the combination ready-made. In Python, collections.OrderedDict keeps keys in order and has move_to_end, and functools.lru_cache caches a function's results. In Java, a LinkedHashMap created with access order set to true keeps entries in order of use, and overriding removeEldestEntry turns it into an LRU cache. Building it by hand from a hash map and a list is a common interview question (LeetCode problem 146).
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.items = OrderedDict() # keys in order of use, oldest first
def get(self, key):
if key not in self.items:
return None # miss
self.items.move_to_end(key) # now the most recently used
return self.items[key]
def put(self, key, value):
if key in self.items:
self.items.move_to_end(key)
self.items[key] = value
if len(self.items) > self.capacity:
self.items.popitem(last=False) # evict the least recently used Without OrderedDict
In an interview you are usually asked to build the list yourself. Two dummy nodes at the ends mean that unlinking and inserting never have to check for an empty list.
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.map = {} # key -> node
self.head, self.tail = Node(), Node() # dummy ends: head.next is newest
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
node = self.map.get(key)
if node is None:
return None # miss
self._unlink(node)
self._push_front(node) # now the most recently used
return node.value
def put(self, key, value):
node = self.map.get(key)
if node:
node.value = value
self._unlink(node)
else:
if len(self.map) == self.capacity:
oldest = self.tail.prev # least recently used
self._unlink(oldest)
del self.map[oldest.key]
node = Node(key, value)
self.map[key] = node
self._push_front(node) In Java
A LinkedHashMap already keeps a doubly linked list through its entries. Passing true as the third constructor argument orders that list by access instead of insertion, and removeEldestEntry is called after every insert.
import java.util.LinkedHashMap;
import java.util.Map;
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
LRUCache(int capacity) {
super(16, 0.75f, true); // true: iterate in order of access, not insertion
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity; // drop the least recently used once over capacity
}
} The hand-written Python version was checked against the OrderedDict one on random sequences of gets and puts. Neither the Python nor the Java version is safe to share between threads without a lock.
When LRU works and when it fails
LRU does well when the data in active use, the working set, fits in the cache, and when popular items are requested often enough to stay near the front. It does badly in two common situations.
Loops slightly larger than the cache
If a program cycles through n + 1 items with a cache of n, each item is evicted just before it is needed again, and every access misses. A policy that simply never evicted some of the items would get most of them as hits. The simulator's "Loop one too big" pattern shows this, and the comparison with the optimal policy shows how much is lost.
Scans
A single pass over a large amount of data, such as a database table scan, a backup or a batch job, brings in many items that will never be used again. Under LRU each one goes to the front, and together they push out the frequently used items. This is called cache pollution.
LRU also ignores frequency: an item used a thousand times and one used once are treated the same once both have been idle for the same time. Policies that also count frequency handle these cases better (see below).
The optimal policy
In 1966 László Bélády described the best possible policy: evict the item whose next use is furthest in the future. It cannot be used in practice because it needs to know future requests, but it gives an upper limit for comparing real policies, which is how the simulator uses it.
Approximations of LRU
Exact LRU changes the list on every read, which is costly in hardware and creates contention when many threads share one cache, because each hit needs a lock. Many systems therefore use cheaper approximations.
- CLOCK (second chance) keeps entries in a circle with one "referenced" bit each. A read only sets the bit. To evict, a hand moves round the circle, clearing set bits and evicting the first entry whose bit is already clear. It was used for page replacement in the Multics operating system in the late 1960s, and variants are still used by operating systems and databases.
- Sampling. Redis does not keep a list. When it must evict under an LRU policy, it samples a few keys (5 by default, set by maxmemory-samples) and evicts the one idle longest.
- Pseudo-LRU in CPU caches tracks approximate recency for the few lines in each set with a handful of bits.
Other policies
| Policy | Introduced | Idea |
|---|---|---|
| FIFO | Evict the oldest entry, however recently it was used. Simple, but usually worse than LRU. | |
| LFU | Evict the least frequently used entry. Keeps popular items, but old popular items can stay forever. | |
| LRU-K | O'Neil, O'Neil and Weikum, 1993 | Rank entries by the time of their K-th most recent use, so one-off accesses rank low. |
| 2Q | Johnson and Shasha, 1994 | New entries enter a probation queue and move to the main LRU list only if used again, which keeps scans out. |
| ARC | Megiddo and Modha (IBM), 2003 | Balances a recency list and a frequency list, adjusting their sizes to the workload. |
| W-TinyLFU | Einziger, Friedman and Manes, 2017 | Admits a new entry only if a compact frequency count says it is more popular than the entry it would replace. Used by the Caffeine library for Java. |
The cache eviction simulator runs several of these on the same requests.
In practice
- Linux page cache. Keeps two lists, active and inactive. Pages enter the inactive list and are promoted only if used again, a scan-resistant design related to 2Q.
- MySQL InnoDB buffer pool. Uses an LRU list with a midpoint: new pages enter the "old" part, about three eighths of the list by default, and move to the "new" part only when accessed again after a short delay, so a table scan does not flush the pool.
- Memcached. Evicts by LRU within each slab class; since version 1.5 it uses a segmented LRU with hot, warm and cold sections.
- Redis. Offers approximate LRU and LFU eviction policies, such as allkeys-lru, based on sampling.
- Application code. In-process caches such as Python's functools.lru_cache, Java's Caffeine and Go's groupcache use LRU or policies derived from it.
LRU cache interview follow-ups
“Design an LRU cache” (LeetCode 146) is one of the most common coding interview questions. Once the hash map and list are working, interviewers tend to push in one of these directions:
- Thread safety. A get reorders the list, so reads write shared state. One lock around both operations is correct; splitting the cache into shards, each with its own lock, reduces contention. Caffeine records reads in buffers and replays them under the lock in batches.
- Expiry. Add a time to live per entry and treat an expired entry as a miss on get. Expired entries that are never read still need removing, either by a background sweep or when they reach the back of the list.
- Size in bytes. When values differ in size, keep a running total and evict from the back until the new entry fits, which may remove several entries.
- LFU instead. LeetCode 460 asks for an LFU cache, usually built with one list per use count and a pointer to the lowest count.
- Across machines. In a system design question the cache is often Redis or Memcached. Redis with maxmemory-policy allkeys-lru evicts by sampled, approximate LRU; keys are spread over nodes with consistent hashing or hash slots.
History
Replacement policies were first studied for virtual memory in the 1960s, when operating systems had to decide which pages of memory to move to slower storage. László Bélády's 1966 paper "A study of replacement algorithms for a virtual-storage computer" in the IBM Systems Journal compared several policies and described the optimal one. LRU became the standard reference policy, and CLOCK, an approximation that is cheap enough for hardware and kernels, was used in Multics.
Database researchers in the 1990s found that LRU handled scans and mixed workloads poorly, which led to LRU-K, 2Q and later ARC. More recent work, such as TinyLFU, combines recency with compact frequency counts.
LRU cache questions and answers
What is an LRU cache?
An LRU (least recently used) cache holds a fixed number of entries. When it is full and a new entry must be added, it removes the entry that has gone longest without being used. The idea is that data used recently is likely to be used again soon.
How do you implement an LRU cache with O(1) operations?
Combine a hash map with a doubly linked list. The list keeps entries in order of use, most recent at the front; the hash map maps each key to its node in the list. A get looks the key up in the map and moves its node to the front; a put adds a node at the front and, if the cache is full, removes the node at the back. Each step takes constant time.
What is the time complexity of an LRU cache?
Get and put both take O(1) time: one hash map lookup, which is constant on average, and a fixed number of pointer changes in the list. The cache uses O(capacity) space, for one map entry and one list node per cached key.
Why does an LRU cache need a doubly linked list?
To move or remove a node in constant time you need its previous node as well as its next one, so that the neighbours can be joined. A singly linked list would have to be searched from the start to find the previous node.
How do you implement an LRU cache in Java?
Extend LinkedHashMap, call the constructor with accessOrder set to true so that entries are kept in order of use, and override removeEldestEntry to return true when size() is greater than the capacity. The result is not thread-safe; for shared caches, use a library such as Caffeine.
Is an LRU cache thread-safe?
Not unless it is built to be. Every get changes the order of the list, so even reads modify shared state, and a read-write lock does not let reads run in parallel. The simple fix is one lock around get and put. Libraries such as Caffeine avoid that bottleneck by recording reads in buffers and applying them to the list in batches.
What is the difference between LRU and LFU?
LRU evicts the entry that has gone longest without being used; LFU evicts the entry that has been used the fewest times. LRU adapts quickly when the popular keys change but can be flushed by a one-off scan. LFU keeps popular keys through scans but can hold on to keys that were popular long ago unless the counts decay.
When does LRU perform badly?
LRU does badly when a program loops over slightly more data than the cache holds: each entry is evicted just before it is needed again, so every access misses. A single scan through a large amount of data also pushes out entries that are used often. Policies such as 2Q, ARC and W-TinyLFU were designed to handle these cases.
Further reading
- Bélády, 1966A Study of Replacement Algorithms for a Virtual-Storage ComputerThe study that introduced the optimal policy.
- Megiddo and Modha, 2003ARC: A Self-Tuning, Low Overhead Replacement CacheA policy that adapts between recency and frequency.
- Einziger, Friedman and Manes, 2017TinyLFU: A Highly Efficient Cache Admission PolicyThe admission policy behind Caffeine.
- Redis documentationKey evictionHow Redis approximates LRU and LFU by sampling.
- MySQL documentationInnoDB buffer poolThe midpoint insertion variant of LRU.
- Python documentationfunctools.lru_cacheLRU caching of function results in the standard library.
- SemicolonyHow caching worksCaches across a web stack, and how to keep them correct.