Cache replacement policies
A cache replacement policy is an algorithm that selects the resident item removed when a cache must admit a new item and lacks sufficient unused capacity. Replacement is necessary because the cache contains fewer storage locations than the addressable backing store, while requests generally exhibit nonuniform patterns of temporal locality and spatial locality. The policy attempts to retain items whose presence will reduce the cost of future accesses.
Replacement policies are used in processor caches, virtual memory, database buffer pools, operating-system page caches, and distributed storage systems. These environments differ in access latency, admission cost, write behavior, and available metadata. Consequently, no implementable policy minimizes misses for every workload.
Formal model
In the classical paging model, a cache of capacity (k) receives a request sequence
[ \sigma = (r_1,r_2,\ldots,r_n), ]
where each (r_i) identifies a page or object. A request is a hit when the requested item is resident. Otherwise, the request produces a miss and the item is fetched from a lower storage level. If the cache already contains (k) items, the replacement policy chooses a victim before or during admission.
For a cache in which every object occupies one unit and every miss has the same cost, policy performance is commonly expressed by the miss count
[ M_P(\sigma,k), ]
where (P) denotes the replacement policy. The corresponding hit ratio is
[ H_P(\sigma,k)=1-\frac{M_P(\sigma,k)}{n}. ]
This model isolates replacement from other mechanisms, but actual systems often violate both assumptions. Cached objects can have unequal sizes, and fetching one object can be substantially more expensive than fetching another. A cost-sensitive formulation therefore minimizes aggregate retrieval cost rather than raw miss count. In storage systems, the objective can also include write-back traffic, queuing delay, or interference with concurrent requests.
Replacement is distinct from cache admission. A replacement rule chooses which resident item loses its allocation, whereas an admission rule determines whether the incoming item receives an allocation at all. The two decisions are frequently combined because admitting a low-value object can evict a resident object with a higher expected reuse value.
Information limits and optimal replacement
László Bélády established the standard offline optimum, commonly called Bélády's algorithm or MIN. On each miss, MIN evicts the resident item whose next request occurs furthest in the future. An item that is never requested again is treated as having an infinite forward distance. An exchange argument shows that no other policy can produce fewer misses for the same request sequence and cache capacity.
MIN is not directly implementable in an online system because it requires complete knowledge of future requests. Its principal function is therefore analytical. Trace-based studies use it as a lower bound on the miss count attainable by any replacement policy under the same cache model.
The absence of future information also creates a fundamental limitation for online algorithms. For a cache containing (k) pages, deterministic online paging algorithms can be forced to incur a miss count up to a factor of (k) above the offline optimum, apart from an additive constant. Least recently used and first-in, first-out both attain this deterministic competitive bound in the standard uniform paging model, although their practical behavior differs substantially.
Recency-based replacement
Least recently used
Least recently used replacement evicts the item whose most recent reference is earliest in time. Its model of future reuse rests on temporal locality: a recently accessed item is treated as more likely to be accessed again than an item whose last access occurred further in the past.
Exact LRU can be represented by an ordered stack. Every hit moves the referenced item to the top, while every miss inserts the incoming item at the top and removes the bottom item when the stack exceeds capacity. This representation gives LRU the stack property: the contents of an LRU cache of capacity (k) form a subset of the contents produced by the same request sequence at capacity (k+1). Increasing cache capacity therefore cannot increase the LRU miss count.
Richard Mattson, Jan Gecsei, Donald Slutz, and Irving Traiger formalized stack algorithms and showed how a single trace could be used to derive miss ratios across multiple cache capacities. Their method relates cache behavior to reuse distance, also called stack distance, which measures the number of distinct items referenced between consecutive accesses to the same item. A reference hits in a fully associative LRU cache precisely when its reuse distance is smaller than the cache capacity.
Exact LRU requires enough metadata to maintain a total ordering of resident items. That cost is manageable in many software caches but becomes significant in highly associative processor caches, where replacement decisions operate under strict latency and area constraints. Hardware implementations therefore commonly use approximations based on a limited number of state bits.
CLOCK and recency approximation
The CLOCK algorithm arranges resident pages in a circular order and associates each page with a reference bit. A moving hand examines pages in sequence. A page whose bit is set receives a second chance through bit clearing, whereas a page whose bit is already clear becomes eligible for replacement.
CLOCK does not reproduce the complete LRU ordering. It instead records whether a page has been accessed since a previous examination, substantially reducing metadata and update costs. Its behavior depends on the speed with which the hand traverses the resident set and on the rate at which references reset page state.
Song Jiang and Xiaodong Zhang introduced CLOCK-Pro as a refinement that combines CLOCK-style implementation with reuse information derived from both resident pages and recently evicted pages. The policy distinguishes references that survive over longer reuse intervals from pages whose accesses are concentrated within a short scan. This design addresses a recurrent weakness of plain recency policies: a sequential traversal larger than the cache can displace frequently reused data.
Frequency and mixed-history policies
Least frequently used replacement assigns value according to accumulated reference frequency. In its basic form, LFU evicts the resident object with the smallest access count. This treatment preserves repeatedly referenced objects even when they have not been used recently.
Unbounded frequency counts can encode obsolete history. An object that was popular during an earlier phase may remain protected after its request rate declines, while a newly popular object begins with a comparatively small count. Aging mechanisms reduce this effect by discounting older observations. Such mechanisms transform raw frequency into an estimate whose effective time horizon depends on the discount schedule.
Policies combining recency with frequency divide the cache or its metadata into regions representing different forms of evidence. The 2Q algorithm uses separate queues to prevent a single recent access from receiving the same status as a repeated access. Theodore Johnson and Dennis Shasha introduced the underlying queue organization, in which first-time references pass through a probationary structure before recurrent references enter the principal cache.
You Watanabe's 1995 analysis of 2Q established the relationship between the length of its nonresident history queue and the reuse intervals recognized as recurrent. The resulting formulation separated the history mechanism from the number of data pages assigned to the main queue, allowing the policy's behavior to be described in terms of measurable reuse-distance distributions rather than queue position alone.
Nimrod Megiddo and Dharmendra Modha later introduced adaptive replacement cache, which maintains recency-oriented and frequency-oriented resident lists together with nonresident history lists. ARC changes the target balance between the resident lists in response to hits in the corresponding histories. The adaptation operates from observed requests and does not require a fixed division chosen before execution.
Anomalies and workload structure
First-in, first-out replacement removes the item that has been resident for the longest time, independently of subsequent accesses. Its state can be maintained as an insertion-ordered queue, but the policy does not possess the stack property. As a result, FIFO can exhibit Bélády's anomaly, in which increasing cache capacity increases the number of misses for a particular request sequence.
The anomaly is not a general consequence of larger caches. It results from the way a non-stack policy changes its replacement trajectory when capacity changes. LRU and MIN cannot exhibit the anomaly because their resident sets are nested across capacities.
Workload structure determines which historical signal is informative. Looping traversals with a working set slightly larger than the cache can defeat LRU by evicting each item shortly before its next access. Long scans can similarly pollute a recency-ordered cache even when the scanned data is accessed only once. Frequency-sensitive policies resist those patterns, although delayed adaptation can impair their response to phase changes.
Peter Denning's working-set model describes locality through the distinct pages referenced during a recent execution interval. A process whose active working set fits in available memory can execute with a relatively low fault rate. When aggregate working sets exceed physical memory, repeated eviction and retrieval can produce thrashing. Replacement policy influences the onset and severity of this behavior, while capacity allocation and scheduling determine how much memory each process can retain.
Associativity and implementation
Replacement occurs within the set of locations in which an item is permitted to reside. A fully associative cache allows an incoming item to replace any resident item. A set-associative cache restricts the choice to a small set selected by the address mapping. A direct-mapped cache has only one candidate location and therefore has no independent replacement choice.
Limited associativity introduces conflict misses that a fully associative cache of the same total capacity would avoid. Replacement metadata is also maintained separately for each set, so the policy observes only a restricted portion of the global access history. Exact global LRU and per-set LRU consequently represent different algorithms even when both use recency ordering.
Hardware approximations frequently encode a partial recency order rather than a complete permutation. Tree-based pseudo-LRU associates direction bits with an internal binary tree and follows those bits to select a victim. A hit updates the path associated with the referenced way. The resulting state requires fewer bits than exact LRU, although two distinct access histories can map to the same replacement state.
Random replacement selects a victim without maintaining recency or frequency order. Its expected behavior is insensitive to adversarial ordering that specifically targets deterministic metadata states, but it discards information that can be useful under stable locality. The relevant comparison is therefore not metadata-free simplicity in isolation, but the interaction between implementation cost and the predictive value of accessible history.
Writes and heterogeneous costs
A replacement decision can trigger operations beyond fetching the incoming item. In a write-back cache, a modified victim must be written to the next storage level before its location can be reused. A clean victim does not require that transfer. Policies for storage caches may therefore incorporate dirty state when estimating eviction cost.
Evicting the cheapest item is not generally equivalent to minimizing total long-run cost. A dirty page can still be the appropriate victim when its expected reuse is sufficiently remote, while preserving it can cause several additional misses among more active pages. Cost-aware replacement consequently combines an estimate of future reuse with the immediate expense associated with eviction and retrieval.
Variable-sized objects create a related distinction between object hit ratio and byte hit ratio. Replacing one large object can free enough capacity for several smaller objects, but those objects may have different request frequencies and retrieval costs. Generalized caching models therefore assign value relative to occupied capacity, while preserving the temporal dimension needed to prevent stale historical estimates from dominating current behavior.
Evaluation
Replacement policies are evaluated with request traces, analytical models, or controlled execution of complete systems. Trace replay provides reproducibility and permits direct comparison with MIN, but a fixed trace can omit feedback between caching and application behavior. Full-system measurements include that feedback while also incorporating effects from prefetching, concurrency, and storage scheduling.
A miss-ratio curve expresses the miss fraction as a function of cache capacity. For stack policies, reuse-distance methods can derive the curve efficiently from one pass over a trace. Non-stack policies generally require additional state because their cache contents at one capacity do not determine their contents at another.
Hit ratio alone does not determine system performance. A miss on a remote object can have a different latency from a miss served by local memory, and write-back congestion can dominate average retrieval time. Evaluation therefore relates replacement outcomes to the cost structure of the cache hierarchy rather than treating all misses as interchangeable events.