/ˌɛl ɑː ˈjuː/
noun — "evict the item not used for the longest time."
LRU, short for Least Recently Used, is a cache replacement and resource management policy that discards the item whose last access occurred farthest in the past when space is needed. It is based on the assumption that data accessed recently is more likely to be accessed again soon, while data not accessed for a long time is less likely to be reused. This principle aligns closely with temporal locality, a common property of real-world workloads.
Technically, LRU defines an ordering over cached items based on recency of access. Every read or write operation updates the position of the accessed item to mark it as most recently used. When the cache reaches capacity and a new item must be inserted, the item at the opposite end of this ordering, the least recently accessed one, is selected for eviction. The challenge in implementing LRU lies not in the policy itself, but in maintaining this ordering efficiently under frequent access.
Common implementations of LRU combine a hash table with a doubly linked list. The hash table provides constant-time lookup to locate cached entries, while the linked list maintains the usage order. On access, an entry is moved to the head of the list. On eviction, the tail of the list is removed. This approach achieves O(1) time complexity for insert, delete, and access operations, at the cost of additional memory overhead for pointers and bookkeeping.
In systems where strict LRU tracking is too expensive, approximations are often used. Operating systems, databases, and hardware caches may implement variants such as clock algorithms or segmented LRU, which reduce overhead while preserving similar behavior. For example, page replacement in virtual memory systems frequently uses an LRU-like strategy to decide which memory pages to swap out when physical memory is exhausted.
Operationally, LRU appears across many layers of computing. Web browsers use it to manage in-memory caches of images and scripts. Databases use it for buffer pools that cache disk pages. Filesystems apply it to inode or block caches. CPU cache hierarchies rely on approximations of LRU to decide which cache lines to evict. In each case, the goal is the same: keep the working set resident and minimize expensive fetches from slower storage.
A simplified conceptual implementation looks like this:
# access(key):
# if key exists:
# move key to front of list
# else:
# if cache is full:
# evict key at end of list
# insert key at front of list
This model highlights the essential behavior without committing to a specific data structure or language. Real implementations must also handle concurrency, memory constraints, and consistency guarantees.
In practice, LRU performs well for workloads with strong temporal locality but can degrade under access patterns that cycle through large working sets slightly larger than the cache capacity. In such cases, frequently accessed items may still be evicted, leading to cache thrashing. For this reason, LRU is often combined with admission policies, frequency tracking, or workload-specific tuning.
Conceptually, LRU is like clearing space on a desk by removing the item you have not touched in the longest time, on the assumption that what you used most recently is what you are most likely to need again.
See Cache, FIFO, Page Replacement.