LRUlike

LRUlike is a term used in cache design to describe a family of eviction policies that approximate Least Recently Used (LRU) behavior without enforcing strict LRU ordering. It covers strategies that retain recently accessed items in a cache while managing metadata overhead and adapting to varying workloads. It is not a single standard algorithm.

LRUlike schemes typically rely on a notion of recency but implement it with different structures or update patterns. A common approach uses a hash map for fast access and a doubly linked list or priority queue to reflect usage order. Some variants update an item's position on every access, others move only a subset of items or apply aging counters to slowly forget past recency.

Various algorithms are described as LRUlike in the literature. LRU-k tracks the k-th most recent access rather than only the last, providing a broader view of usage. Other approaches such as 2Q, Adaptive Replacement Cache (ARC), and CLOCK-Pro use multiple queues or aging to separate hot data from cold data and to adapt to workload shifts. The common thread is balancing recency with scalability and metadata costs.

LRUlike methods are commonly used in processor and database buffer pools, web caches, and distributed caches where workload characteristics vary. They can outperform strict LRU under certain patterns but introduce extra metadata and complexity. The choice of whether to employ an LRUlike policy depends on expected access locality, hit-rate goals, and the acceptable overhead.