Editing Cache replacement policies (section)

=== {{anchor|Other cache replacement policies}}Other policies ===

==== Low inter-reference recency set (LIRS) ====
{{Further|LIRS caching algorithm}}
LIRS is a page replacement algorithm with better performance than LRU and other, newer replacement algorithms. Reuse distance is a metric for dynamically ranking accessed pages to make a replacement decision.<ref>{{cite journal | last1=Jiang | first1=Song | last2=Zhang | first2=Xiaodong | title=LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance | journal=ACM SIGMETRICS Performance Evaluation Review | publisher=Association for Computing Machinery | volume=30 | issue=1 | pages=31–42 | doi=10.1145/511399.511340 | issn=0163-5999 | date=June 2002 | url=http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-02-6.pdf}}</ref> LIRS addresses the limits of LRU by using recency to evaluate inter-reference recency (IRR) to make a replacement decision.

[[File:LIRSalgoworking.png|center|alt=Diagram of the LIRS algorithm]]

In the diagram, X indicates that a block is accessed at a particular time. If block A1 is accessed at time 1, its recency will be 0; this is the first-accessed block and the IRR will be 1, since it predicts that A1 will be accessed again in time 3. In time 2, since A4 is accessed, the recency will become 0 for A4 and 1 for A1; A4 is the most recently accessed object, and the IRR will become 4. At time 10, the LIRS algorithm will have two sets: an LIR set = {A1, A2} and an HIR set = {A3, A4, A5}. At time 10, if there is access to A4 a miss occurs; LIRS will  evict A5 instead of A2 because of its greater recency.

==== {{anchor|Adaptive replacement cache (ARC)}}Adaptive replacement cache ====
[[Adaptive replacement cache]] (ARC) constantly balances between LRU and LFU to improve the combined result.<ref name=megiddo>[[Nimrod Megiddo]] and Dharmendra S. Modha. [http://www.usenix.org/events/fast03/tech/full_papers/megiddo/megiddo.pdf ARC: A Self-Tuning, Low Overhead Replacement Cache.] FAST, 2003.</ref> It improves SLRU by using information about recently-evicted cache items to adjust the size of the protected and probationary segments to make the best use of available cache space.<ref>{{cite web |url=http://www.c0t0d0s0.org/archives/5329-Some-insight-into-the-read-cache-of-ZFS-or-The-ARC.html |url-status=dead |archive-url=https://web.archive.org/web/20090224074209/http://www.c0t0d0s0.org/archives/5329-Some-insight-into-the-read-cache-of-ZFS-or-The-ARC.html |archive-date=24 February 2009 |title=Some insight into the read cache of ZFS - or: The ARC - c0t0d0s0.org}}</ref>

==== {{anchor|Clock with adaptive replacement (CAR)}}Clock with adaptive replacement ====
[[Page replacement algorithm#Variants of clock|Clock with adaptive replacement]] (CAR) combines the advantages of ARC and [[Page replacement algorithm#Clock|Clock]]. CAR performs comparably to ARC, and outperforms LRU and Clock. Like ARC, CAR is self-tuning and requires no user-specified parameters.

==== {{anchor|Multi queue (MQ)}}Multi-queue ====
The multi-queue replacement (MQ) algorithm was developed to improve the performance of a second-level buffer cache, such as a server buffer cache, and was introduced in a paper by Zhou, Philbin, and Li.<ref name="zhou">[[Yuanyuan Zhou]], James Philbin, and Kai Li. [http://static.usenix.org/event/usenix01/zhou.html The Multi-Queue Replacement Algorithm for Second Level Buffer Caches.] USENIX, 2002.</ref> The MQ cache contains an ''m'' number of LRU queues: Q<sub>0</sub>, Q<sub>1</sub>, ..., Q<sub>''m''-1</sub>. The value of ''m'' represents a hierarchy based on the lifetime of all blocks in that queue.<ref>Eduardo Pinheiro, Ricardo Bianchini, Energy conservation techniques for disk array-based servers, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France</ref>

[[File:MultiQueueReplacementAlgortithm.jpg|center|alt=Diagram of the multi-queue replacement algorithm]]

==== {{anchor|Pannier: Container-based caching algorithm for compound objects}}Pannier ====
Pannier<ref name="Li">Cheng Li, Philip Shilane, Fred Douglis and Grant Wallace. [http://dl.acm.org/citation.cfm?id=2814734 Pannier: A Container-based Flash Cache for Compound Objects.] ACM/IFIP/USENIX Middleware, 2015.</ref> is a container-based flash caching mechanism which identifies containers whose blocks have variable access patterns. Pannier has a priority-queue-based survival-queue structure to rank containers based on their survival time, which is proportional to live data in the container.