Design an LRU cache
A least-recently-used cache with a linked list and a lookup table.
On this page
Constraints and assumptions#
- What are we caching?
- We are caching the results of web queries
- Can we assume inputs are valid or do we have to validate them?
- Assume they're valid
- Can we assume this fits memory?
- Yes
Solution#
class Node(object):
def __init__(self, results):
self.results = results
self.prev = None
self.next = None
class LinkedList(object):
def __init__(self):
self.head = None
self.tail = None
def move_to_front(self, node): # ...
def append_to_front(self, node): # ...
def remove_from_tail(self): # ...
class Cache(object):
def __init__(self, MAX_SIZE):
self.MAX_SIZE = MAX_SIZE
self.size = 0
self.lookup = {} # key: query, value: node
self.linked_list = LinkedList()
def get(self, query)
"""Get the stored query result from the cache.
Accessing a node updates its position to the front of the LRU list.
"""
node = self.lookup.get(query)
if node is None:
return None
self.linked_list.move_to_front(node)
return node.results
def set(self, results, query):
"""Set the result for the given query key in the cache.
When updating an entry, updates its position to the front of the LRU list.
If the entry is new and the cache is at capacity, removes the oldest entry
before the new entry is added.
"""
node = self.lookup.get(query)
if node is not None:
# Key exists in cache, update the value
node.results = results
self.linked_list.move_to_front(node)
else:
# Key does not exist in cache
if self.size == self.MAX_SIZE:
# Remove the oldest entry from the linked list and lookup
self.lookup.pop(self.linked_list.tail.query, None)
self.linked_list.remove_from_tail()
else:
self.size += 1
# Add the new key and value
new_node = Node(results)
self.linked_list.append_to_front(new_node)
self.lookup[query] = new_nodeAdded on this site
The one idea#
A cache that evicts the least recently used entry has to answer three questions fast: is this key here, which entry was touched longest ago, and how do I mark an entry as just used. A hash map answers the first in O(1). A list ordered by recency answers the other two, if you can move an entry to the front and remove the one at the back in O(1). That points to a doubly linked list beside the hash map: the map finds the node, and the list orders them.
How to get there in an interview#
- Pin down the behaviour. Fixed capacity.
getreturns the value, or nothing on a miss, and counts as a use.seton an existing key updates it and counts as a use.seton a new key when full removes the least recently used entry first. - Start with the obvious version and say what is wrong with it. A plain list of pairs makes every lookup O(n). A map plus a "last used" timestamp makes lookup fast, but evicting means scanning every entry for the oldest, which is O(n) again.
- Name what you need. O(1) lookup by key, O(1) "move this entry to the front", and O(1) "remove the entry at the back". Only a doubly linked list can unlink a node it was handed without searching for its neighbour. A singly linked list cannot, because deleting a node needs the node before it.
- Choose the classes. A
Nodethat stores the key as well as the value, because when the tail node is evicted you must also delete its key from the map. A cache class that owns the map and the two end markers. - Use sentinel nodes at both ends so you never have to special-case an empty list or a one-element list.
A working version#
This is complete and runs as written. Both operations are O(1).
class Node:
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
if capacity < 1:
raise ValueError('capacity must be at least 1')
self.capacity = capacity
self.lookup = {} # key -> Node
self.head = Node() # sentinel on the most recently used side
self.tail = Node() # sentinel on the least recently used side
self.head.next = self.tail
self.tail.prev = self.head
def _unlink(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _push_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
node = self.lookup.get(key)
if node is None:
return None
self._unlink(node)
self._push_front(node)
return node.value
def set(self, key, value):
node = self.lookup.get(key)
if node is not None: # existing key: update and mark as used
node.value = value
self._unlink(node)
self._push_front(node)
return
if len(self.lookup) == self.capacity: # full: drop the least recently used
oldest = self.tail.prev
self._unlink(oldest)
del self.lookup[oldest.key]
node = Node(key, value)
self.lookup[key] = node
self._push_front(node)Try it:
cache = LRUCache(2)
cache.set('a', 1)
cache.set('b', 2)
cache.get('a') # 'a' is now the most recently used
cache.set('c', 3) # the cache is full, so the least recently used ('b') goes
assert cache.get('b') is None
assert cache.get('a') == 1 and cache.get('c') == 3
cache.set('a', 10) # updating counts as a use
cache.set('d', 4) # evicts 'c', not 'a'
assert cache.get('c') is None and cache.get('a') == 10What is wrong with the sketch above#
The solution on this page is an outline, and some of it cannot run. Each of these was checked by running the code:
- The list methods are empty (
move_to_front,append_to_frontandremove_from_tailcontain onlypass). As soon as the cache is full,setfails withAttributeError: 'NoneType' object has no attribute 'query', because the list never recorded a tail. Nodehas no key.setreadstail.query, butNodeonly storesresults. Without the key you cannot remove the evicted entry from the map.self.next = nextstores Python's built-innextfunction, not a pointer to another node. It is a typo forNone.- There is no
prevpointer. Without one, removing the tail in O(1) is impossible, which is the reason the list is doubly linked. - The arguments are
set(results, query), which is the reverse of the usual (key, value) order and is easy to get wrong.
Spotting problems like these in a design you have been handed is itself a useful interview skill.
Questions to expect next#
- Thread safety. Two threads moving nodes at once corrupt the list. The simple answer is one lock around
getandset. Under heavy contention you can split the cache into several independent shards, each with its own lock. - Expiry. Store a deadline in each node and treat an expired entry as a miss, removing it lazily when it is touched.
- Size by bytes instead of by count. Track a running total and evict from the tail until the new entry fits.
- Is LRU the right policy? Not always. A one-off scan of cold data can flush your hot entries. See the cache eviction lab to compare it with LFU, FIFO and random on the same traffic.
- Across many servers. Each server holds its own LRU, and requests are routed by key with consistent hashing. The cache page covers where caches fit in a larger system.
- In Python you can build this in a few lines from
collections.OrderedDictwithmove_to_end. Interviewers usually want to see the linked-list-plus-map design, because it shows you understand why it is O(1).