LRU Cache
A Least Recently Used (LRU) cache evicts the least recently used items. It does this when the cache is full.
LRU Cache isn't timestamp based
I always thought an LRU cache used timestamps. But it doesn't. It only keeps an order of entries. It updates that order whenever an entry is used or added.
- It always adds/moves the accessed/added entry to the front of the order.
- When the cache exceeds its capacity, it evicts the entry at the end of the order
Implementation Details
- Uses a doubly linked list of cache items to maintain the order of usage.
- Uses a hash map to store the key and its corresponding node in the linked list for O(1) access.
Concurrency Problems
The biggest bottleneck is keeping the entry order in a concurrent setup. Moving an entry to the front is an O(1) operation. Still, it needs a lock on the whole cache for thread safety.
Linked list corruption
If many threads access the cache, the LRU code updates the linked list order at the same time. This corrupts the linked list.
Some solutions for the concurrency problem are:
- 2-Random - This method uses no linked list. Each entry holds a counter or timestamp for its usage. To evict, the cache picks two entries at random. It evicts the less recently used one, by the counter or timestamp.
- Segmented LRU - The cache is split into many segments. Each segment keeps its own LRU order and eviction policy. When an entry is used, it moves to the front of its segment. To evict, the cache picks the segment with the overall least recently used entry. It evicts that entry.
- Bulk Updates - The cache doesn't update the order on every access. Instead, it keeps a separate structure to track usage. It updates the order in bulk at set intervals, or when the cache hits a threshold.