LRUk

LRUk, sometimes written as LRU-k, is a family of cache replacement policies that generalize the basic least-recently-used (LRU) strategy by incorporating information about the k-th most recent access to a cache item. The goal is to improve cache hit rates by modeling temporal locality more accurately than standard LRU, especially for workloads with diverse access patterns.

Mechanism and principles: For each cached item, LRUk maintains the timestamps of its last k references. Evictions are based on the age of the k-th most recent reference: the item whose k-th last reference is oldest is considered least likely to be used soon. When a page is accessed, its history is updated accordingly. If k = 1, LRUk reduces to the traditional LRU policy. With larger k, the policy can distinguish between items that have a very recent single reference and those with repeated references spread over a longer window, potentially reducing misses for certain workloads.

Implementation considerations: Implementing LRUk requires storing multiple reference timestamps per cached item and maintaining a data structure to select eviction candidates according to the k-th reference age. This introduces higher per-item overhead compared to LRU. In practice, systems may choose small values of k, use approximate or aging techniques, or adopt hybrid strategies to balance accuracy with overhead. LRUk has been explored in contexts ranging from CPU caches to database buffer pools and web caches.

Variants and evaluation: Studies compare LRUk with LRU, LFU, and other policies across synthetic and real workloads, noting that the effectiveness of a given k depends on workload characteristics. Adaptive variants that adjust k or combine LRUk with other strategies have been proposed to improve robustness.

See also: LRU, LFU, cache replacement policies, ARC.