Least Recently Used Cache Replacement Algorithm

The least recently used, or LRU, algorithm is a cache replacement policy that decides which item to remove from a full cache by discarding whichever stored item has gone the longest without being accessed. It works by keeping some record of how recently each cached item was last used, commonly an ordered list or age marker per entry, updating that record every time an item is accessed, and evicting the item at the stale end of that ordering whenever room must be made for a new one. The policy assumes that an item used recently is likely to be used again soon and an item left untouched for a long time is not, an assumption that holds well for many real workloads, such as repeated access patterns in a web cache or an operating system's page cache, though it can perform poorly against access patterns that defeat that assumption, such as a single pass through data larger than the cache. Because tracking exact recency for every cache line has a real bookkeeping cost, many practical systems implement an approximation of true LRU rather than the exact policy.