About Cache Eviction Algorithms

A cache eviction algorithm is a way of deciding which element to evict when the cache is full. In Ehcache , the memory store and the off-heap store might be limited in size. When these stores get full, elements are evicted. The eviction algorithms determine which elements are evicted. The default algorithm is Least Recently Used (LRU).

What happens on eviction depends on the cache configuration. If a disk store is configured, the evicted element is flushed to disk; otherwise it is removed. The disk store size by default is unbounded. But a maximum size can be set as described in “Sizing the Storage Tiers” in the Configuration Guide for Ehcache . If the disk store is full, then adding an element causes an existing element to be evicted.

Note: The disk store eviction algorithm is not configurable. It uses LFU.

 

Built-in Memory Store Eviction Algorithms

The idea here is, given a limit on the number of items to cache, how to choose the thing to evict that gives the best result.

In 1966 Laszlo Belady showed that the most efficient caching algorithm would be to always discard the information that will not be needed for the longest time in the future. This is a theoretical result that is unimplementable without domain knowledge. The Least Recently Used (LRU) algorithm is often used as a proxy. In general, it works well because of the locality of reference phenomenon and is the default in most caches.

A variation of LRU is the default eviction algorithm in Ehcache .

Ehcache provides three eviction algorithms to choose from for the memory store.

 

Least Recently Used (LRU)

This is the default and is a variation on the Least Frequently Used algorithm.

The oldest element is the Less Recently Used element. The last-used timestamp is updated when an element is put into the cache or an element is retrieved from the cache with a get call.

This algorithm takes a random sample of the Elements and evicts the smallest. Using the sample size of 15 elements, empirical testing shows that an Element in the lowest quartile of use is evicted 99% of the time.

If probabilistic eviction does not suit your application, a true Least Recently Used deterministic algorithm is available by setting java -Dnet.sf.ehcache.use.classic.lru=true.

Least Frequently Used (LFU)

For each get() call on the element, the number of hits is updated. When a put() call is made for a new element (and assuming that the max limit is reached), the element with least number of hits (the Least Frequently Used element) is evicted.

If cache-element usage follows a Pareto distribution, this algorithm might give better results than LRU.

LFU is an algorithm unique to the Ehcache API. It takes a random sample of the Elements and evicts the smallest. Using the sample size of 15 elements, empirical testing shows that an Element in the lowest quartile of use is evicted 99% of the time.

First In First Out (FIFO)

Elements are evicted in the same order as they come in. When a put call is made for a new element (and assuming that the max limit is reached for the memory store) the element that was placed first (first-in) in the store is the candidate for eviction first-out.

This algorithm is used if the use of an element makes it less likely to be used in the future. An example here would be an authentication cache.

It takes a random sample of the Elements and evicts the smallest. Using the sample size of 15 elements, empirical testing shows that an Element in the lowest quartile of use is evicted 99% of the time.

 

Plugging in Your own Eviction Algorithm

Ehcache allows you to plug in your own eviction algorithm using Cache.setMemoryStoreEvictionPolicy(Policy policy). You can utilize any Element metadata, which makes possible some very interesting approaches. For example, you might evict an element if it has been hit more than ten times.

/** * Sets the eviction policy strategy. The Cache will use a policy at startup. * There are three policies which can be configured: LRU, LFU and FIFO. However * many other policies are possible. That the policy has access to the whole * element enables policies based on the key, value, metadata, statistics, or a * combination of any of the above. * * It is safe to change the policy of a store at any time. The new policy takes * effect immediately. * * @param policy the new policy */ public void setMemoryStoreEvictionPolicy(Policy policy) { 　　memoryStore.setEvictionPolicy(policy); }

A Policy must implement the following interface:

/** * An eviction policy. * 
 * The Cache will use a policy at startup. There are three policy implementations provided in ehcache: * LRU, LFU and FIFO. However many other policies are possible. That the policy * has access to the whole element enables policies based on the key, value, metadata, statistics, or a combination of * any of the above. * * @author Greg Luck */public interface Policy {    /**     * @return the name of the Policy. Inbuilt examples are LRU, LFU and FIFO.     */    String getName();    /**     * Finds the best eviction candidate based on the sampled elements. What distinguishes     * this approach from the classic data structures approach is that an Element contains     * metadata (e.g. usage statistics) which can be used for making policy decisions,     * while generic data structures do not. It is expected that implementations will take     * advantage of that metadata.     *     * @param sampledElements this should be a random subset of the population     * @param justAdded       we probably never want to select the element just added.     * It is provided so that it can be ignored if selected. May be null.     * @return the selected Element     */    Element selectedBasedOnPolicy(Element[] sampledElements, Element justAdded);    /**     * Compares the desirableness for eviction of two elements     *     * @param element1 the element to compare against     * @param element2 the element to compare     * @return true if the second element is preferable for eviction to the first element     * under ths policy     */    boolean compare(Element element1, Element element2);}

 

Disk Store Eviction Algorithm

The disk store uses the Least Frequently Used algorithm to evict an element when the store it is full.