Cache replacement policies
Algorithms that decide what to remove from a full cache.
Cache replacement policies, also called cache algorithms, are instructions used by computer programs or hardware-managed structures to govern how a cache stores information. Caching improves performance by keeping recently or frequently accessed data in faster memory locations than the main storage. When the cache becomes full, the algorithm selects which items to discard to accommodate new data. The two primary measures of cache performance are latency—the time to return a requested item on a hit—and hit ratio, which indicates how often a sought item is found. More efficient policies track more usage information to improve hit rates, but this often increases latency; faster strategies track less information, sometimes none at all, reducing update time. Each policy represents a compromise between these factors.
Hit ratios vary by application; for instance, video and audio streaming often yield near-zero hit ratios because each data bit is read once and never reused. Some algorithms, particularly Least Recently Used (LRU), can allow streaming data to fill the cache, pushing out information that will soon be needed again—a phenomenon called cache pollution. Other considerations include data size, retrieval time, and expiration. In some cases, no eviction algorithm is needed if the cache is large enough. Algorithms also maintain cache coherence when multiple caches share the same data, such as with multiple database servers updating a shared file.
The theoretically optimal policy, Bélády’s algorithm, discards the item that will not be needed for the longest time, but it is impractical because future access patterns cannot be predicted. Random replacement selects an item at random, requiring no access history and enabling simple stochastic simulation; it has been used in ARM processors. Simple queue-based policies include First In First Out (FIFO), which evicts blocks in the order they were added, and Last In First Out (LIFO), which evicts the most recently added block first. The SIEVE algorithm, designed for web caches, uses lazy promotion and quick demotion: it does not update its global structure on cache hits, delaying updates until eviction, and quickly removes newly inserted objects because many are one-hit wonders. It employs a single FIFO queue with a moving hand that starts at the tail and progresses toward the head, evicting objects that have not bee
- field
- Computing
- known_for
- Managing cache memory by selecting which items to evict when full
- key_metrics
- Hit ratio and latency
- example_algorithms
- Bélády's optimal, LRU, MRU, FIFO, LIFO, Random, SIEVE, TLRU, SLRU
Lore & Background
Cache replacement policies are optimizing instructions that manage a cache of information, improving performance by keeping recent or often-used data in faster memory. When the cache is full, the algorithm must choose which items to discard to make room for new data. The average memory reference time is calculated as T = m × Tm + Th + E, where m is the miss ratio, Tm is main-memory access time on a miss, Th is cache latency, and E includes secondary effects like queuing in multiprocessor systems. Two primary figures of merit are latency and hit ratio; faster replacement strategies typically track less usage information, while more efficient ones track more to improve hit rate.
Reader's Guide
Cache replacement policies are fundamental to computer performance, as they directly affect the hit ratio and latency of a cache. The most efficient theoretical algorithm is Bélády's optimal algorithm, which discards information not needed for the longest time, but it is unfeasible in practice because future access patterns cannot be predicted. Practical algorithms include LRU, which discards least recently used items; MRU, which discards most recently used items; FIFO, which evicts in order of addition; and Random replacement, which requires no access history. Each represents a compromise between hit rate and latency. For example, LRU is a family of algorithms including 2Q and LRU/K, while MRU is best for looping sequential reference patterns. SIEVE is designed for web caches, using lazy promotion and quick demotion to handle high one-hit-wonder ratios. TLRU adds time-awareness for content with valid lifetimes. The choice of policy depends on the application: video and audio streaming often have near-zero hit ratios, and some algorithms like LRU can suffer from cache pollution by streaming data. Ultimately, no single policy is universally best, and effectiveness is measured against benchmark applications.
Did You Know?
- Bélády's optimal algorithm is also called the clairvoyant algorithm, but it is unfeasible in practice because future information needs cannot be predicted.
- Random replacement does not require keeping any access history and has been used in ARM processors due to its simplicity.
- SIEVE uses a single FIFO queue and a moving hand to evict objects, quickly removing newly inserted objects that are often one-hit wonders.
- MRU cache algorithms have more hits than LRU for random access patterns and repeated scans over large datasets.
Frequently Asked Questions
What is Cache replacement policies?
Cache replacement policies are decision-making algorithms that determine which data items to kick out of a full cache so that new ones can be stored. They operate in both software and hardware contexts to keep frequently needed information readily accessible.
What role does Cache replacement policies play?
Its core job is to select the least valuable cached entry for eviction whenever space runs out, ensuring the cache holds the most useful data. By making smart discard choices, it directly influences how quickly a system can serve repeated requests.
Which well-known algorithms are part of the Cache replacement policies cast?
The lineup includes classic entries like LRU, FIFO, and Random, as well as more sophisticated ones such as SIEVE, TLRU, and SLRU. Bélády's optimal algorithm serves as the theoretical benchmark no real policy can actually achieve.
How do fans measure whether Cache replacement policies is doing a good job?
Two key metrics define its performance: hit ratio (how often a requested item is already in the cache) and latency (how long it takes to retrieve or replace data). A good policy keeps the hit ratio high while keeping latency low.
Why is Cache replacement policies important in computing?
Without a smart eviction strategy, caches would fill up with stale or rarely used data, forcing the system to repeatedly fetch information from slower storage. Effective replacement policies are a foundational layer that keeps modern processors, databases, and web servers running at acceptable speeds.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record