LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance

WC 273 / RT 2min


LIRS

LRU replacement policy has been commonly used in the buffer cache management, it is well known for its inability to cope with access patterns with weak locality.

LIRS effectively addresses the limits of LRU by using recency to evaluate Inter-Reference Recency (IRR) for making a replacement decision.

LRU inefficiency

The reason for LRU to behave poorly in these situations is that LRU makes a bold assumption – a block that has not been accessed the longest would wait for relatively longest time to be accessed again.

Implementation

IRR as the recorded history information of each block, where IRR of a block refers to the number of other blocks accessed between two consecutive references to the block.

Specifically, the recency refers to the number of other blocks accessed from last reference to the current time.

It is assumed that if the IRR of a block is large, the next IRR of the block is likely to be large again. Following this assumption, we select the blocks with large IRRs for replacement, because these blocks are highly possible to be evicted later by LRU before being referenced again under our assumption.

Notes

LIRS - low inter reference set

IRR - inter reference recency