This article needs additional citations for verification .(May 2023) |
LIRS (Low Inter-reference Recency Set) is a page replacement algorithm with an improved performance over LRU (Least Recently Used) and many other newer replacement algorithms. [1] This is achieved by using "reuse distance" [2] as the locality metric for dynamically ranking accessed pages to make a replacement decision. This algorithm was developed by Song Jiang and Xiaodong Zhang.
While all page replacement algorithms rely on existence of reference locality to function, a major difference among different replacement algorithms is on how this locality is quantified. LIRS uses reuse distance of a page, or the number of distinct pages accessed between two consecutive references of the page, to quantify locality. Specifically, LIRS uses last and second-to-last references (if any) for this purpose. If a page is accessed for the first time, its reuse distance is infinite. In contrast, LRU uses recency of a page, which is the number of distinctive pages accessed after the reference of the page, to quantify locality. To take into account of up-to-date access history, the implementation of LIRS actually uses the larger of reuse distance and recency of a page as the metric to quantify its locality, denoted as RD-R. Assuming the cache has a capacity of C pages, the LIRS algorithm is to rank recently accessed pages according to their RD-R values and retain the C most highly ranked pages in the cache.
The concepts of reuse distance and recency can be visualized as below, in which T1 and T2 are page B’s second-to-last and last reference times, respectively, and T3 is the current time.
. . . B . . . B . . . . . . . . . . B . . . . . ^----Reuse Distance---^--Recency--^ T1 T2 T3
LIRS organizes metadata of cached pages and some uncached pages and conducts its replacement operations described as below, which are also illustrated with an example [3] in the graph.
LIRS has been deployed in MySQL since version 5.1, [4] and another reference by link. It is also adopted in Infinispan data grid platform. [5] An approximation of LIRS, CLOCK-Pro, [6] is adopted in NetBSD. [7] LIRS is adopted in Apache Jackrabbit, a Content Repository. An in-memory LIRS cache is developed in the Red Hat JBoss Data Virtualization System. LIRS is used in the H2 Database Engine, which is called a Scan Resistant Cache. Furthermore, LIRS is used in Apache Impala, a data processing with Hadoop.