2.7 Cache Replacement

only for RuBoard - do not distribute or recompile

2.7 Cache Replacement

Cache replacement refers to the process that takes place when the cache becomes full and old objects must be removed to make space for new ones. Usually, a cache assigns some kind of value to each object and removes the least valuable ones. The actual meaning of " valuable " may vary from one cache to another. Typically, an object's value is related to the probability that it will be requested again, thus attempting to maximize the hit ratio. Caching researchers and developers have proposed and evaluated numerous replacement algorithms, some of which are described here.

2.7.1 Least Recently Used (LRU)

LRU is certainly the most popular replacement algorithm used by web caches. The algorithm is quite simple to understand and implement, and it gives very good performance in almost all situations. As the name implies, LRU removes the objects that have not been accessed for the longest time. This algorithm can be implemented with a simple list. Every time an object is accessed, it is moved to the top of the list. The least recently used objects then automatically migrate to the bottom of the list.

A strict interpretation of LRU would consider time-since-reference as the only parameter. In practice, web caches almost always use a variant known as LRU-Threshold, where "threshold" refers to object size. Objects larger than the threshold size are simply not cached. This prevents one very large object from ejecting many smaller ones. This highlights the biggest problem with LRU: it doesn't consider object sizes. Would you rather have one large object in your cache or many smaller ones? Your answer probably depends on what you wish to optimize. If saving bandwidth is important, you want the large object. However, caching numerous small objects results in a higher hit ratio.

2.7.2 First In, First Out (FIFO)

A FIFO replacement algorithm is even simpler to implement than LRU. Objects are purged in the same order they were added. This technique does not account for object popularity and gives lower hit ratios than LRU. FIFO is rarely, if ever, used for caching proxies.

2.7.3 Least Frequently Used (LFU)

LFU is similar to LRU, but instead of selecting based on time since access, the significant parameter is the number of accesses . LFU replaces objects with small access counts and keeps objects with high access counts. If the algorithm does not take time since last access into account, the cache tends to fill up with frequently accessed but old objects. If the least frequently used object in the cache was accessed twice, a new object (which is accessed only once) can never be added. LFU implementations are sometimes used in caching products, but not very often.

2.7.4 Size

A size-based algorithm uses the object size as the primary removal criteria. The largest objects in the cache are removed first. The algorithm really needs an aging mechanism as well. That is, old objects must be removed eventually, otherwise the cache fills up with only very small objects. Simulations show that, compared to LRU, a size-based algorithm provides better cache hit ratios but significantly worse byte hit ratios.

2.7.5 GreedyDual-Size (GDS)

The previously mentioned algorithms tend to optimize one extreme or another. For example, LRU tends to have the highest byte hit ratios, while Size usually has higher document hit ratios. If you're looking for a middle ground, GreedyDual-Size is a good alternative.

GDS assigns value to cached objects based on the cost of a cache miss and the size of the object. GDS does not specify exactly what "cost" means. This offers a lot of flexibility to optimize just what you want. For example, cost might be latency ”the time it takes to receive the response. Cost might also be the number of packets transmitted over the network or the number of hops between the origin server and the cache. I'll give a brief explanation of the algorithm here, but for full details on GDS, see [Cao and Irani, 1997].

The GreedyDual-Size algorithm associates a value, H , with each object in the cache. When an object is initially brought into the cache, its H value is set to the cost of retrieving the object, divided by its size. When the cache is full, the object with the smallest H value ( H _min ) is removed. Then, the H values of all remaining objects are decreased by H _min . When a cache hit occurs, the object's H value is reset to its initial value, as though it were being added for the first time.

Implementation of the algorithm as described is problematic . It's impractical to perform a subtraction for every cache object each time an object is removed. It works just as well to add an "inflation" value to H for new objects and cache hits. The inflation value is simply set to H _min each time an object is removed.

2.7.6 Other Algorithms

Numerous other replacement algorithms have been proposed by web caching researchers. Many of these are combinations of the algorithms already mentioned. For example, LRU-size uses size as the primary criteria and LRU as the secondary criteria. The LRU-MIN algorithm attempts to remove an old object of approximately the same size as the new object. This prevents a new, small object from replacing a large object. Further details are not given here because these algorithms are not known to be used in caching products available today. Refer to [Williams, Standridge, Abdulla and Fox, 1996] for more information.

One reason for the relative popularity of the LRU algorithm is its simplicity. Some of the other algorithms proposed over the years are difficult to implement efficiently . Some require computing a metric for every cached object each time the replacement procedure runs. This is not practical for really large caches. Other algorithms require keeping extra metadata for each object. Since memory is usually a scarce resource, programmers are more likely to implement simpler algorithms.

only for RuBoard - do not distribute or recompile