Cache Algorithms

Cache replacement policies determine which entries to evict when the cache is full. They have a direct impact on system performance. Here is an overview of common cache eviction algorithms.

Algorithm Overview

Algorithm	Full Name	Core Idea
Belady	Belady’s Algorithm	Evict the item not needed for the longest time in the future (theoretical optimum, not realizable)
LRU	Least Recently Used	Evict the least recently accessed item
MRU	Most Recently Used	Evict the most recently accessed item
PLRU	Pseudo-LRU	Approximate LRU using bitsets instead of linked lists for lower overhead
RR	Random Replacement	Random eviction
SLRU	Segmented LRU	Split cache into probation and protected segments
2-way	2-Way Set Associative	Each cache set has two slots
Direct-mapped	Direct-Mapped Cache	Each memory address maps to exactly one cache line
LFU	Least-Frequently Used	Evict the least frequently accessed item
LIRS	Low Inter-reference Recency Set	Distinguish hot/cold data by reuse distance, outperforms LRU in many workloads
ARC	Adaptive Replacement Cache	Dynamically balances between LRU (recency) and LFU (frequency)
CAR	Clock with Adaptive Replacement	Clock-based approximation of ARC
MQ	Multi Queue	Multi-level queue management, each with its own replacement policy

Least Recently Used (LRU)

LRU is the most widely used cache eviction strategy: when the cache is full and a new item must be inserted, evict the item that has gone the longest without being accessed.

Implementation Key Points

Get: Move the accessed key to the head of the list
Put: If the key doesn’t exist and space is insufficient, evict from the tail until space is available, then insert at the head

Common Implementations

LinkedHashMap: Java’s LinkedHashMap with accessOrder=true provides a ready-made LRU cache
Linked List + HashMap: Doubly-linked list + hash map for O(1) read/write
LruCache: Android’s LruCache<K, V> class

Trade-offs

Pros: Exploits temporal locality, simple to implement
Cons: Sequential/looping access patterns with a working set slightly larger than the cache cause thrashing

References

ARC (Adaptive Replacement Cache)

Proposed by IBM Research, ARC adaptively balances between recency (LRU) and frequency (LFU) to achieve better hit rates across diverse workloads.

LIRS (Low Inter-reference Recency Set)

LIRS distinguishes between “hot” and “cold” data using reuse distance rather than simple access time for eviction decisions, widely used in databases and storage systems.

Note: Originally written as study notes while learning cache algorithms. Content will be continuously improved.

Algorithm Overview#

Least Recently Used (LRU)#

Implementation Key Points#

Common Implementations#

Trade-offs#

References#

ARC (Adaptive Replacement Cache)#

LIRS (Low Inter-reference Recency Set)#