A cache replacement policies decides which resident item to remove when a cache is full and a new item needs space. That sounds like a small choice. In practice, the answer depends on what the cache stores, what the system can observe, and how expensive a miss is.
The same label can also hide different implementations. Redis uses sampled approximations for some eviction policies. A CPU cache may use a hardware-specific policy that its vendor does not disclose. A database may protect pages read during a scan instead of applying plain LRU to every access. So the useful question is not simply “Which policy is best?” It is “Which policy fits this cache, this workload, and this cost?”
Key takeaways
Click any topic to expand or collapseWhat a cache replacement policy does
A cache replacement policy is the rule that selects an existing cache entry for removal when a miss requires space and no unused slot is available. If a cache still has a free line or entry, the system can fill it without evicting anything. If the cache is full, it chooses from the eligible residents.
That definition applies broadly, but the “item” changes by layer. A processor cache stores lines in sets. An operating system reclaims memory pages under pressure. A database buffer pool holds database pages. A key-value store may evict keys; a CDN may evict objects. Their access signals, update costs, and miss penalties differ.
| Layer | Typical cached unit | What constrains the decision? |
|---|---|---|
| CPU cache | Cache line within a set | Hardware timing, associativity, metadata, and microarchitecture |
| Operating system | Memory page | System-wide memory pressure, file/anonymous pages, writeback, and kernel configuration |
| Database | Database page or block | Query access patterns, dirty pages, pinned buffers, and I/O cost |
| Application or key-value cache | Key, object, or computed result | Object size, popularity, expiration, memory budget, and request concurrency |
| CDN | Cached response or content object | Object popularity, freshness rules, cache capacity, and origin-fetch cost |
A CPU replacement rule cannot be assumed to describe a database buffer pool, and a CDN’s retention behavior does not tell you how the Linux kernel reclaims pages. Keep the layer visible throughout the comparison.
Replacement is not the same as admission or expiration
Replacement answers: Which current resident should leave? Admission answers: Should this new item enter the cache at all? Expiration or freshness answers: Is this item still valid to serve? Invalidation removes an item when it is no longer correct. Writeback controls when dirty data is sent to a lower layer. Request coalescing prevents many concurrent misses from triggering duplicate work.
These mechanisms can work together, but they solve different problems. The Arm cache-policy guide separates allocation, replacement, and write policies. In software caches, TinyLFU’s original paper describes an admission policy: it estimates whether a new candidate deserves space relative to a resident that might be removed.
The four-question filter: layer, signal, control, objective
Before choosing an algorithm, run through four questions. This framework prevents a common mistake: picking a policy name before defining the problem.
- Layer: What is the item, a cache line, page, database block, key, or object? What event creates pressure to remove it?
- Signal: Does recent access predict reuse? Does long-term popularity matter? Is the access pattern cyclic, bursty, or dominated by one-time scans?
- Control: Is the problem really eviction, or is it admission, expiration, invalidation, writeback, or concurrent miss coordination?
- Objective: Are you reducing request misses, bytes fetched, weighted I/O cost, tail latency, CPU overhead, or memory use? A higher hit rate does not automatically mean a faster system.
A cache that stores differently sized objects may care more about bytes saved than the number of hits. A CPU may accept a slightly less precise recency signal to keep access-time hardware simple. A response cache may need stale-while-revalidate or request coalescing even when its eviction policy is sound.
The core cache replacement policies
The policies below use different guesses about future reuse. The comparison is useful for learning the rules, not for declaring a winner across all implementations.
| Policy | Signal | Victim rule | What it can fit | Main limitation |
|---|---|---|---|---|
| LRU | Recency | Least recently accessed resident | Workloads where recent use predicts near-term reuse | A long one-time scan can displace useful residents |
| FIFO | Admission time | Resident admitted earliest | Simple queue-based baseline | Hits do not refresh its position; can show Bélády’s anomaly |
| LFU | Frequency history | Lowest-frequency resident, under the implementation’s scoring and tie rules | Popularity that remains useful over time | Old popularity can linger unless counts decay or reset |
| MRU | Most recent access | Most recently accessed resident | Some cyclic patterns where the just-used item is least likely to be needed next | Often poor when recent use predicts another near-term access |
| Random | No recency or frequency ranking | A randomly selected eligible resident | A simple baseline or roughly uniform access, depending on implementation | Does not protect a hot item from eviction |
| OPT / Bélády’s MIN | Future knowledge | Resident whose next use is farthest away, or never occurs | A lower-bound comparison for a fixed trace | Cannot be implemented online because future requests are unknown |
LRU assumes recent use is a good predictor of near-future use. LFU assumes repeated popularity matters more than the timing of the latest access. FIFO ignores hits when ordering residents. MRU makes the opposite choice from LRU. OPT knows the future and is therefore a benchmark, not a deployable algorithm. These definitions are standard in page-replacement teaching; Cornell’s page-replacement notes include the textbook policies and worked examples.
dLRU: useful when recency predicts reuse
LRU removes the resident that has gone the longest without an access. An implementation must keep enough information to distinguish the recency order, but that information can be represented in different ways: a list in software, per-way state, a pairwise ordering structure, or an approximation in hardware.
LRU is not “the default” for every cache. It is a useful conceptual baseline when temporal locality is plausible. A one-time scan can hurt it: each new item becomes the newest resident and pushes an older item toward eviction, even if the scanned data will not be revisited. The severity depends on scan length, cache capacity, insertion/admission rules, and what else the cache is serving.
LFU: frequency is not one fixed counter design
A textbook LFU policy removes the least-frequently accessed resident. That definition leaves important questions unanswered: do counts include an item’s entire history, only a recent window, or a decayed approximation? What happens on a tie? Does a newly admitted entry start at zero or one?
Without adaptation, a key that was popular yesterday can keep a high lifetime count after demand shifts. Real implementations often approximate frequency or decay old information. For example, Redis documents sampled LRU and LFU eviction; its LFU option uses compact probabilistic counters and a decay setting. Those are Redis-specific mechanics, not rules for all LFU caches.
“Aging” can also mean something else. In operating-systems teaching, aging commonly refers to a finite-width reference-history counter used to approximate LRU. That is different from LFU frequency decay. Name the mechanism instead of treating “aging” as one universal algorithm.
FIFO: simple, but not monotonic with capacity
FIFO evicts the resident that entered earliest, whether or not it has been accessed since. Its queue is easy to explain, but FIFO does not preserve a frequently reused item just because it has been hit.
The classic Bélády trace shows why more capacity does not guarantee fewer misses under every policy. Cornell’s page-replacement notes show this anomaly for FIFO. The result is specific: it does not mean every FIFO trace has an anomaly, or that every policy without the stack property must show one.
MRU: a counterexample, not a general scan rule
MRU removes the item accessed most recently. It can help when the access order is cyclic and the most recently used item will not be needed again until after other items. It can perform badly when recent use predicts imminent reuse.
The draft’s MRU sequence is internally consistent, but it does not prove that MRU is optimal for database scans. A project author in a torchcache discussion described using MRU for a repeated computer-vision training pattern; the author also noted that one performance claim was untested. Treat that as a project-specific experience, not a benchmark or database-industry rule.
Worked example: a scan can change the ranking
The following is an illustrative simulation, not a production benchmark. Begin with an empty cache of four equal-size entries. Use the trace below: a hot set is accessed twice, four one-time scan items arrive, then the hot set is requested again. For LFU, new entries start with frequency one, hits increment the count, counts do not decay, and equal counts use FIFO tie-breaking.
| Policy | Misses / 16 requests | What happens |
|---|---|---|
| LRU | 12 | The one-time scan replaces the original hot set; all four final requests miss. |
| FIFO | 12 | The scan entries arrive after the hot set and push it out in admission order. |
| MRU | 9 | The trace leaves three hot entries resident through the scan; the final D request misses. |
| LFU with FIFO ties | 9 | The repeated hot entries have higher counts than one-time scan entries under the stated rules. |
This example does not establish that MRU or LFU is generally better than LRU. It shows why the trace and policy rules matter. Change the sequence, tie-break, counter decay, or capacity and the result can change. The miss counts above are reproducible from the stated trace and rules; they are illustrative, not evidence of typical performance.
Bélády’s anomaly: a verified FIFO example
Use the twelve requests 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Start with empty frames and count each initial load as a miss. Under FIFO, three frames produce nine misses; four frames produce ten. On this trace, the larger cache has one more miss.
| Policy and capacity | Hit/miss sequence | Misses |
|---|---|---|
| FIFO, 3 frames | M M M M M M M H H M M H | 9 |
| FIFO, 4 frames | M M M M H H M M M M M M | 10 |
| LRU, 3 frames | M M M M M M M H H M M M | 10 |
| OPT, 3 frames | M M M M H H M H H M M H | 7 |
| OPT, 4 frames | M M M M H H M H H H M H | 6 |
In the page-replacement model, OPT (also called Bélády’s MIN) evicts the resident whose next request is farthest in the future. It gives a lower bound on misses for a fixed request string and capacity when entries are equal-size and the objective is minimizing misses. It cannot be implemented online because a real system does not know future requests.
The Cornell worked example reports the canonical FIFO counts and shows OPT’s role as a theoretical comparator. The stack-property explanation says stack policies such as LRU do not show Bélády’s anomaly in this model; that result does not extend to every replacement policy.
CPU caches: why pseudo-LRU exists, and what it does not prove
A set-associative CPU cache maps each address to a set and gives the replacement logic a choice among the ways in that set. Exact LRU needs to distinguish the recency ordering of those ways. The theoretical minimum state is five bits for a four-way set, sixteen for eight-way, and forty-five for sixteen-way. These are information counts per set, not a direct measurement of silicon area, power, update delay, or the encoding used by a real processor.
A common tree-PLRU design for power-of-two associativity stores direction bits in a binary tree. With the usual complete-tree layout, a four-way set needs three bits, an eight-way set seven, and a sixteen-way set fifteen. Each bit records which subtree is the next victim candidate. On a hit, the bits along the path are changed to point away from the accessed way. When replacement is needed, the tree follows its recorded victim directions. Because it stores only partial order, tree-PLRU can choose a different victim from exact LRU.
Do not turn that teaching model into a claim about every CPU. The Arm Cortex-A53 technical reference documents pseudo-random replacement for its L1 data cache. Hardware reverse-engineering research by Abel and colleagues found model-specific replacement behavior in the Intel processors they studied. A vendor may document cache size and associativity without publishing its replacement algorithm.
Another hardware option is RRIP, which predicts the approximate interval before a cache line is reused. The original ISCA 2010 RRIP paper studies scan-resistant variants for processor caches. Later research includes the proposed PACIPV design evaluated for instruction-heavy workloads in an ISCA 2025 paper; the authors’ Texas A&M publication record summarizes that work. These are research designs evaluated under stated workloads, not evidence that any given CPU uses them or that they win on every workload.
What real systems do: three implementation examples
The point of these examples is not to rank products. It is to show that real systems combine replacement with other rules, and often publish behavior that a generic algorithm label would hide. Redis and PostgreSQL links below point to current documentation or source reviewed on October 23, 2026; the MySQL example is version 8.4, and the Linux reference is kernel documentation v6.9.
Check the documentation for the exact release and configuration you run.
Constraint: Eviction occurs when the configured memory limit is reached and an evicting maxmemory-policy is active.
Implementation: Redis documents sampled approximate LRU and LFU options; LFU uses probabilistic counters and decay.
Lesson: “LRU” and “LFU” can name implementation-specific approximations. With noeviction, Redis rejects writes that need more memory; volatile policies also have no eligible keys if none have expirations.
Constraint: A large scan should not immediately promote every newly read page above a useful working set.
Implementation: InnoDB inserts newly read pages into the old portion near the LRU midpoint. MySQL 8.4 documents a default insertion point three-eighths from the tail and an innodb_old_blocks_pct default of 37. The default innodb_old_blocks_time window is 1,000 ms after first access; another access during that window does not promote the page to the front.
Lesson: Scan protection can modify LRU behavior; it does not require declaring MRU the general database policy.
Constraint: Database buffer management must handle shared pages, bulk access, and operating-system caching.
Implementation: PostgreSQL’s buffer-manager source documents clock-sweep victim selection and small rings for specific operations that read many pages only once.
Lesson: A database may protect its buffer pool with operation-specific paths. Check the source and version you actually run.
The Redis eviction reference is the right place to check policy names, sampling controls, and LFU settings. It also documents the noeviction behavior and the conditions under which volatile policies have no eligible keys. For InnoDB, consult MySQL’s scan-resistant buffer-pool documentation; its values are version-specific defaults, not universal tuning targets. For PostgreSQL, the buffer-manager README says normal victim selection uses clock sweep.
For large sequential scans it documents a 256 KB buffer ring; VACUUM uses a similar configurable ring, and the current resource-consumption documentation also covers the vacuum_buffer_usage_limit setting for VACUUM and ANALYZE. The docs also explain that shared_buffers exists alongside the operating-system cache.
Linux memory reclaim is another layer, not a user-space cache library. The Linux v6.9 Multi-Gen LRU documentation describes MGLRU as an alternative LRU implementation for page reclaim. Its availability depends on kernel configuration and runtime controls, so check the documentation and settings for the kernel you use; do not treat it as a Redis-style object-cache policy.
CDN retention also needs careful wording. Cloudflare’s retention-versus-freshness documentation separates the question of whether an object remains in cache from whether it is fresh under TTL and cache-control rules. It documents Cloudflare’s behavior; it does not prove that every CDN uses the same policy.
For a reader who wants the Linux memory-pressure context, Vertex Frontier’s guide to Linux VM swappiness and dirty ratios is a useful next step. LLM serving uses a different cache again: GPU KV-cache sizing and prefix reuse are covered in Vertex Frontier’s distributed-inference guide. Those topics should not be folded into a generic replacement-policy explanation.
Adaptive and scan-resistant policies
A fixed recency or frequency rule can struggle when workloads change. Several designs keep additional history or filter new entries:
- ARC tracks resident recency- and frequency-oriented lists plus “ghost” histories of recently evicted items. It adjusts its balance in response to hits in those histories. The original USENIX ARC paper reports evaluation on 23 traces from several domains; its detailed trace section also describes a synthetic storage-controller benchmark. Those results belong to the paper’s workloads and configurations, not every mixed workload.
- 2Q separates pages that have been seen once from items that demonstrate reuse and retains limited nonresident history. The original 2Q paper is a primary description; later derivatives may differ.
- CLOCK and CLOCK-Pro use reference-state and clock-hand ideas to reduce the need to maintain a fully ordered LRU list. CLOCK-Pro adds history about evicted pages; its paper’s evaluation used a specific older Linux implementation and workloads, so do not label current Linux as CLOCK-Pro by default. See the CLOCK-Pro paper.
- SLRU divides residents into probationary and protected regions. A second access can promote an item, while a protected victim may be demoted rather than immediately discarded.
- TinyLFU and W-TinyLFU separate admission from victim ordering. In W-TinyLFU, new arrivals first enter an LRU window; TinyLFU then helps decide whether the window’s eviction candidate should enter the SLRU main cache. The primary TinyLFU paper describes this design, and Caffeine’s design notes document one software-cache implementation whose window sizing can adapt to workload characteristics.
A 2023 HotOS paper, “FIFO can be Better than LRU”, is a useful reminder that implementation details matter: its designs use lazy promotion and quick demotion. It should not be paraphrased as “plain FIFO always beats LRU.”
A decision workflow you can actually use
A policy table is a starting point. A production decision needs a workload and an objective. Use this sequence:
- Name the unit and boundary. Record whether the cache stores lines, pages, keys, blocks, or objects, and when it is allowed to evict them.
- Describe the access pattern. Identify recent reuse, stable popularity, phase changes, bursts, one-time scans, cyclic access, and object-size skew. Do not infer the pattern from a policy’s name.
- Separate the controls. Check admission, TTL/freshness, invalidation, pinned/dirty items, prefetching, and request coalescing before changing victim selection.
- Choose what “better” means. Track miss count, bytes served, weighted I/O or origin cost, throughput, tail latency, CPU, metadata updates, lock contention, and writeback where relevant.
- Replay representative traces. Use the same warm-up, capacity, object-size assumptions, and admission rules. Include scan, cyclic, hot-key, burst, and phase-shift cases.
- Pin the implementation. Record product version, configuration, cache size, sampling/decay settings, and whether the behavior is measured, documented, or inferred.
- Compare with a simple baseline. LRU, FIFO, or random can be useful baselines. Include OPT only as an offline lower bound on a fixed trace.
- Test the operational path. A policy that improves hit ratio but increases contention or tail latency may be a bad fit. Test cache warm-up, expiry bursts, memory pressure, and failure recovery.
A before-and-after review should change the decision process, not just the algorithm label. Before: “The workload scans, so use MRU.” After: “The cache is a database buffer pool; measure whether the access is cyclic or one-pass, then compare the engine’s ring, admission, or promotion behavior against the actual trace.”
A cache stampede is not a replacement-policy failure
Suppose hundreds of requests arrive after the same cached response expires. If every request independently rebuilds the value, the origin database can be overloaded even if the eviction policy is excellent. The problem is duplicate work at a miss, not which resident should be removed.
In one Reddit Engineering account of the “Three Stooges” problem, the team described duplicate requests overwhelming downstream services during cache repopulation and reported using request coalescing and distributed coordination. This is a first-person engineering report, not a controlled benchmark. The post also claims an uptime improvement, but the reviewed text does not provide comparative benchmark methodology; this article does not rely on that outcome. Lock timeouts, stale-data rules, key correctness, and failure recovery need their own design and tests.
If the real problem is a burst at expiry, investigate request coalescing, jitter, prewarming, or serving stale data only after checking the consistency and failure requirements. Changing LRU to LFU will not make duplicate cache misses disappear.
Common mistakes to avoid
Treating one policy as universal
State the cache layer, item, and implementation.
Confusing recency with frequency
A recent single hit and a long history of past hits are different signals.
Presenting FIFO ties as part of LFU’s definition
Specify the tie-break only for the implementation or example being discussed.
Conflating OS aging with LFU decay
One approximates recency in a finite history; the other reduces old frequency influence.
Calling a one-pass scan a cyclic workload
MRU can help certain cycles; it is not a general database scan policy.
Treating TinyLFU as a victim-ordering rule
It is primarily about whether to admit a candidate.
Confusing TTL with eviction
TTL controls freshness/validity; eviction frees space. Cloudflare documents the distinction for its own cache.
Using “optimal,” “dominant,” or precise percentages without scope
A result needs a named policy, workload, capacity, metric, baseline, and source.
Assuming more memory always reduces misses under every policy
FIFO’s anomaly is possible, but not inevitable; the trace and policy matter.
Calling a static table interactive
If an article promises an interactive simulator, build, test, and label one accurately.
Advanced insights that change how you compare policies
State cost is not hardware cost
Theoretical state counts explain why tracking a complete recency order gets more demanding as associativity grows. They do not directly tell you the area, power, or timing cost of a shipping design. Encoding, update logic, access timing, and circuit organization matter. Likewise, the lower bit count of a tree-PLRU example does not prove its miss rate is close to LRU under every trace.
Capacity and policy interact
A scan that is harmless when the hot set fits comfortably may displace valuable entries when it exceeds the cache. MRU can win a carefully chosen cycle while losing badly on a different temporal-locality pattern. Report capacity and reference order alongside every toy result.
A higher hit ratio may not be the right objective
A one-kilobyte object and a multi-gigabyte database page should not automatically count as equal wins. A cached response that saves an expensive origin call may matter more than a cheap in-memory lookup. Measure the cost that the system is trying to reduce, then account for policy overhead and tail latency.
Conclusion
A cache replacement policy is a prediction about future reuse, made under a specific layer’s constraints. LRU bets on recent access, LFU on frequency, FIFO on admission order, and MRU on the possibility that the just-used item is the least useful one next. Hardware and software systems then add approximations, admission rules, scan protection, or feedback to fit their own limits.
The practical rule is simple: name the cache, state the workload, separate eviction from the other controls, and test the policy against representative traces. That is more reliable than declaring a universal winner from an algorithm label or an unsourced percentage.
FAQ: cache replacement policies
What is the purpose of a cache replacement policy?
It chooses which current cache entry to remove when the cache is full and a miss needs space. It does not, by itself, decide whether new data should be admitted, whether an item is fresh, or how to coordinate concurrent misses.
What is the difference between LRU and LFU?
LRU removes the resident that has gone longest without an access. LFU removes the resident with the lowest frequency under its implementation’s counting, decay, and tie-breaking rules. LRU responds quickly to recent changes; a decaying LFU can preserve longer-term popularity while adapting to phase changes.
What is the difference between LRU and pseudo-LRU?
Exact LRU preserves a complete order of recency among residents. A common tree-PLRU design stores a smaller set of direction bits and can choose a different victim. The metadata comparison depends on the variant and associativity; it does not imply a fixed hit-rate penalty.
When can LRU perform poorly?
LRU can lose useful entries when a one-time scan streams through a cache and newer scan items replace a working set. It can also thrash when the access pattern repeatedly exceeds capacity. The effect depends on the trace, capacity, admission rules, and competing workload.
Why can FIFO have more misses with more frames?
FIFO can exhibit Bélády’s anomaly: for a particular reference string, increasing capacity can increase the number of misses. The classic twelve-request example in this article produces nine FIFO misses with three frames and ten with four. This is possible, not inevitable for every trace.
What happens when a cache miss occurs?
The system fetches the missing item from a lower layer. If the cache has an unused slot, it can fill that slot; if it is full, the replacement policy selects an eligible resident. Depending on the system, the miss may also trigger writeback, prefetch, admission checks, or concurrent-request coordination.
Does a TTL replace an eviction policy?
No. A TTL or freshness rule determines when an item is no longer valid to serve. An eviction policy frees space when capacity is constrained. Some systems combine both, but one does not substitute for the other.
Which cache replacement policy is best?
There is no universal best policy. Start with the cache layer, workload trace, miss cost, capacity, and implementation constraints. Compare policies on representative traces and measure the objective that matters—such as latency, I/O, bytes saved, or CPU—not just a generic hit ratio.
Was this article helpful?
[…] only half the story: which file-backed pages actually get evicted is decided by the kernel’s cache replacement policy, the same recency-versus-frequency logic that repeats across CPU caches, database buffer pools, and […]
[…] an Adaptive Replacement Cache that balances recency against frequency when it picks a victim, and our cache replacement policies guide explains how ARC, LRU, and LFU make that decision in real […]