Cache replacement policies
In computing, cache replacement policies (also known as cache replacement algorithms or cache algorithms) are optimizing instructions or algorithms which a computer program or hardware-maintained structure can utilize to manage a cache of…
≈ 11 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computing, cache replacement policies (also known as cache replacement algorithms or cache algorithms) are optimizing instructions or algorithms which a computer program or hardware-maintained structure can utilize to manage a cache of information. Caching improves performance by keeping recent or often-used data items in memory locations which are faster, or computationally cheaper to access, than normal memory stores.
When the cache is full, the algorithm must choose which items to discard to make room for new data.
Overview
The average memory reference time is T = m \times T_m + T_h + E where m = miss ratio = 1 - (hit ratio) T_m = time to make main-memory access when there is a miss (or, with a multi-level cache, average memory reference time for the next-lower cache) T_h = latency: time to reference the cache (should be the same for hits and misses) E = secondary effects, such as queuing effects in multiprocessor systems A cache has two primary figures of merit: latency and hit ratio. A number of secondary factors also affect cache performance.
The hit ratio of a cache describes how often a searched-for item is found. More efficient replacement strategies track more usage information to improve the hit rate for a given cache size. The latency of a cache describes how long after requesting a desired item the cache can return that item when there is a hit.
Faster replacement strategies typically track less usage information—or, with a direct-mapped cache, no information—to reduce the time required to update the information. Each replacement strategy is a compromise between hit rate and latency. Hit-rate measurements are typically performed on benchmark applications, and the hit ratio varies by application.
Video and audio streaming applications often have a hit ratio near zero, because each bit of data in the stream is read once (a compulsory miss), used, and then never read or written again. Many cache algorithms (particularly LRU) allow streaming data to fill the cache, pushing out information which will soon be used again (cache pollution).
Other factors may be size, length of time to obtain, and expiration. Depending on cache size, no further caching algorithm to discard items may be needed. Algorithms also maintain cache coherence when several caches are used for the same data, such as multiple database servers updating a shared data file.
Random replacement (RR)
Random replacement selects an item and discards it to make space when necessary. This algorithm does not require keeping any access history. It has been used in ARM processors due to its simplicity, and it allows efficient stochastic simulation.
Least Recently Used (LRU)
Discards least recently used items first. This algorithm requires keeping track of what was used and when, which is cumbersome. It requires "age bits" for cache lines, and tracks the least recently used cache line based on these age bits.
When a cache line is used, the age of the other cache lines changes. LRU is a family of caching algorithms, that includes 2Q by Theodore Johnson and Dennis Shasha and LRU/K by Pat O'Neil, Betty O'Neil and Gerhard Weikum.
The access sequence for the example is A B C D E D F: When A B C D is installed in the blocks with sequence numbers (increment 1 for each new access) and E is accessed, it is a miss and must be installed in a block. With the LRU algorithm, E will replace A because A has the lowest rank (A(0)). In the next-to-last step, D is accessed and the sequence number is updated.
F is then accessed, replacing B which had the lowest rank, (B(1)).
Time-Aware, Least Recently Used (TLRU)
Time-aware, least recently used (TLRU) is a variant of LRU designed for when the contents of a cache have a valid lifetime. The algorithm is suitable for network cache applications such as information-centric networking (ICN), content delivery networks (CDNs) and distributed networks in general.
TLRU introduces a term: TTU (time to use), a timestamp of content (or a page) that stipulates the usability time for the content based on its locality and the content publisher. TTU provides more control to a local administrator in regulating network storage. When content subject to TLRU arrives, a cache node calculates the local TTU based on the TTU assigned by the content publisher.
The local TTU value is calculated with a locally defined function. When the local TTU value is calculated, content replacement is performed on a subset of the total content of the cache node. TLRU ensures that less-popular and short-lived content is replaced with incoming content.
Most Recently Used (MRU)
Unlike LRU, MRU discards the most recently used items first. At the 11th VLDB conference, Chou and DeWitt said: "When a file is being repeatedly scanned in a [looping sequential] reference pattern, MRU is the best replacement algorithm."
Researchers presenting at the 22nd VLDB conference noted that for random access patterns and repeated scans over large datasets (also known as cyclic access patterns), MRU cache algorithms have more hits than LRU due to their tendency to retain older data. MRU algorithms are most useful in situations where the older an item is, the more likely it is to be accessed.
The access sequence for the example is A B C D E C D B: A B C D are placed in the cache, since there is space available. At the fifth access (E), the block which held D is replaced with E since this block was used most recently. At the next access (to D), C is replaced since it was the block accessed just before D.
Segmented LRU (SLRU)
An SLRU cache is divided into two segments: probationary and protected. Lines in each segment are ordered from most- to least-recently accessed. Data from misses is added to the cache at the most-recently accessed end of the probationary segment.
Hits are removed from where they reside and added to the most-recently accessed end of the protected segment; lines in the protected segment have been accessed at least twice. The protected segment is finite; migration of a line from the probationary segment to the protected segment may force the migration of the LRU line in the protected segment to the most-recently used end of the probationary segment, giving this line another chance to be accessed before being replaced.
The size limit of the protected segment is an SLRU parameter which varies according to I/O workload patterns. When data must be discarded from the cache, lines are obtained from the LRU end of the probationary segment.
LRU approximations
LRU may be expensive in caches with higher associativity. Practical hardware usually employs an approximation to achieve similar performance at a lower hardware cost.
Clock-Pro
The LRU algorithm cannot be implemented in the critical path of computer systems, such as operating systems, due to its high overhead; Clock, an approximation of LRU, is commonly used instead. Clock-Pro is an approximation of LIRS for low-cost implementation in systems. Clock-Pro has the basic Clock framework, with three advantages.
It has three "clock hands" (unlike Clock's single "hand"), and can approximately measure the reuse distance of data accesses. Like LIRS, it can quickly evict one-time-access or low-locality data items. Clock-Pro is as complex as Clock, and is easy to implement at low cost.
The buffer-cache replacement implementation in the 2017 version of Linux combines LRU and Clock-Pro.
Least frequently used (LFU)
The LFU algorithm counts how often an item is needed; those used less often are discarded first. This is similar to LRU, except that how many times a block was accessed is stored instead of how recently. While running an access sequence, the block which was used the fewest times will be removed from the cache.
On a cache miss, the line with an RRPV equal to the maximum possible RRPV is evicted; with 3-bit values, a line with an RRPV of 2 3 - 1 = 7 is evicted. If no lines have this value, all RRPVs in the set are increased by 1 until one reaches it. A tie-breaker is needed, and usually, it is the first line on the left.
The increase is needed to ensure that older lines are aged properly and will be evicted if they are not reused.
Policies approximating Bélády's algorithm
Bélády's algorithm is the optimal cache replacement policy, but it requires knowledge of the future to evict lines that will be reused farthest in the future. A number of replacement policies have been proposed which attempt to predict future reuse distances from past access patterns, allowing them to approximate the optimal replacement policy.
Some of the best-performing cache replacement policies attempt to imitate Bélády's algorithm. Mockingjay keeps a sampled cache of unique accesses, the PCs that produced them, and their timestamps. When a line in the sampled cache is accessed again, the time difference will be sent to the reuse distance predictor.
The RDP uses temporal difference learning, where the new RDP value will be increased or decreased by a small number to compensate for outliers; the number is calculated as w = \min\left(1, \frac{\text{timestamp difference}}{16}\right) . If the value has not been initialized, the observed reuse distance is inserted directly.
If the sampled cache is full and a line needs to be discarded, the RDP is instructed that the PC that last accessed it produces streaming accesses. On an access or insertion, the estimated time of reuse (ETR) for this line is updated to reflect the predicted reuse distance. On a cache miss, the line with the highest ETR value is evicted.
Mockingjay has results which are close to the optimal Bélády's algorithm.
Machine-learning policies
A number of policies have attempted to use perceptrons, markov chains or other types of machine learning to predict which line to evict. Learning augmented algorithms also exist for cache replacement.
Other policies
In the diagram, X indicates that a block is accessed at a particular time. If block A1 is accessed at time 1, its recency will be 0; this is the first-accessed block and the IRR will be 1, since it predicts that A1 will be accessed again in time 3.
In time 2, since A4 is accessed, the recency will become 0 for A4 and 1 for A1; A4 is the most recently accessed object, and the IRR will become 4. At time 10, the LIRS algorithm will have two sets: an LIR set = {A1, A2} and an HIR set = {A3, A4, A5}. At time 10, if there is access to A4 a miss occurs; LIRS will evict A5 instead of A2 because of its greater recency.
Adaptive replacement cache
Adaptive replacement cache (ARC) constantly balances between LRU and LFU to improve the combined result. It improves SLRU by using information about recently evicted cache items to adjust the size of the protected and probationary segments to make the best use of available cache space.
Clock with adaptive replacement
Clock with adaptive replacement (CAR) combines the advantages of ARC and Clock. CAR performs comparably to ARC, and outperforms LRU and Clock. Like ARC, CAR is self-tuning and requires no user-specified parameters.
Multi-queue
The multi-queue replacement (MQ) algorithm was developed to improve the performance of a second-level buffer cache, such as a server buffer cache, and was introduced in a paper by Zhou, Philbin, and Li. The MQ cache contains an m number of LRU queues: Q 0 , Q 1 , ..., Q m-1 . The value of m represents a hierarchy based on the lifetime of all blocks in that queue.
Pannier
Pannier is a container-based flash caching mechanism which identifies containers whose blocks have variable access patterns. Pannier has a priority-queue-based survival-queue structure to rank containers based on their survival time, which is proportional to live data in the container.
Static analysis
Static analysis determines which accesses are cache hits or misses to indicate the worst-case execution time of a program. An approach to analyzing properties of LRU caches is to give each block in the cache an "age" (0 for the most recently used) and compute intervals for possible ages.
This analysis can be refined to distinguish cases where the same program point is accessible by paths that result in misses or hits. An efficient analysis may be obtained by abstracting sets of cache states by antichains which are represented by compact binary decision diagrams. LRU static analysis does not extend to pseudo-LRU policies.
According to computational complexity theory, static-analysis problems posed by pseudo-LRU and FIFO are in higher complexity classes than those for LRU.
See also
Cache-oblivious algorithm Distributed cache
External links
Definitions of various cache algorithms Caching algorithm for flash/SSDs zh:快取文件置換機制
Text derived from https://en.wikipedia.org/w/index.php?oldid=1376205644 under CC BY-SA 4.0; modifications have been made.