LRU cache

TIL how a standard caching strategy, the Least Recently Used (LRU) cache, works.

What is it?

An LRU cache is a cache that maintains O(1) lookup time (otherwise it wouldn’t be much of a cache) and makes a determination about what should be removed from the cache when the cache is at capacity by finding the least recently used item and removing that.

How is it implemented?

One could think of adding items to / removing items from the cache in a FIFO order: The first item in the cache is the first item out of the cache (since it was least recently used). A queue would work well for implementing this characteristic: perform a dequeue to get the least recently used item out of the cache.

Random item lookups in a queue, though, are O(n)…since we generally only have reference to a queue’s head (if implemented as a linked list) and would need to traverse the list starting from the head to find a particular item. A hash table is often used to keep track of items in the queue in LRU implementation, which provides O(1) lookup time.

Anytime an item is accessed in the cache, it should be moved up in the queue to the “head” since it was most recently used. Re-ordering items in a queue, if implemented as a singly linked list, is also O(n), since we need to know the position of the item before the item in question in order to perform the re-order. This involves traversing the list from the head. A way to optimize for this requirement of the LRU cache is to implement the queue as a doubly linked list, which then makes re-ordering a constant time operation since we will have links to the previous node from the node in question.

Summary

So in summary:

1. Keep track of cache nodes in a doubly linked list, so moving items to the head of the list takes constant time.
2. Access items from cache via a hash table for O(1) access time. Keys hash values for the item in the cache, and point to items in the queue.
3. Whenever a item is accessed, move that item to the head of the queue.
4. When an item is added to the cache, and the cache is at capacity, remove the least recently used from the cache by dequeuing. The new item should be added to the hash table, and the dequeued item removed.