LIRS

Lirs commonly refers to the LIRS cache replacement policy, short for Low Inter-reference Recency Set. It is designed to improve on traditional LRU by more accurately distinguishing data that will be reused soon from data that will not, thereby increasing cache hit rates in a variety of workloads. The policy is especially effective for caches that experience a mix of long-lived and short-lived working sets, such as memory page caches, disk caches, and web or database caches.

The core idea of LIRS is to classify cache blocks into two categories: low inter-reference recency (LIR) blocks, which tend to be accessed repeatedly and are kept in the cache, and high inter-reference recency (HIR) blocks, which are more transient and may be evicted to make space for new references. Some HIR blocks can remain resident, while non-resident entries indicate data that has been evicted but may be reloaded on a future reference. The algorithm tracks recency information using a data structure that maintains the order of accesses and identifies which blocks should be designated as LIR or HIR.

Operationally, when a reference occurs, if the block is labeled as LIR it is promoted within the structure, potentially causing eviction of an HIR block with lower priority. If a non-resident LIR block is accessed, it is promoted to LIR, which may trigger further adjustments to maintain cache balance. The result is a cache replacement policy that seeks to preserve data with long-term reuse while still accommodating new or infrequently accessed items.

LIRS has been studied and implemented in various caching contexts, including operating system page caches, disk and memory caches, and web or database caches. It generally offers improved hit rates over LRU for workloads with mixed locality patterns, though it involves greater implementation complexity and runtime overhead.