A cache eviction algorithm is a way of deciding which element to evict when the cache is full. In Ehcache, the MemoryStore may be limited in size. When the store gets full, elements are evicted. The eviction algorithms in Ehcache determine which elements are evicted. The default is LRU.
What happens on eviction depends on the cache configuration. If a DiskStore is configured, the evicted element will overflow to disk (is flushed to disk); otherwise it will be removed. The DiskStore size by default is unbounded. But a maximum size can be set (see Sizing Caches for more information). If the DiskStore is full, then adding an element will cause one to be evicted unless it is unbounded. The DiskStore eviction algorithm is not configurable. It uses LFU.
Notes for distributed caches: There is no user selection of eviction algorithms with clustered caches. The attribute MemoryStoreEvictionPolicy is ignored (a clock eviction policy is used instead), and if allowed to remain in a clustered cache configuration, the MemoryStoreEvictionPolicy may cause an exception. In addition, the local DiskStore is not used in distributed cache, which relies on the Terracotta Server Array for storage.
Provided MemoryStore 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. It works pretty 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.
Altogether Ehcache provides three eviction algorithms to choose from for the MemoryStore.
Least Recently Used (LRU)
This is the default and is a variation on Least Frequently Used.
The oldest element is the Less Recently Used (LRU) 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 use follows a Pareto distribution, this algorithm may give better results than LRU.
LFU is an algorithm unique to Ehcache. 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 1.6 and higher allows you to plugin in your own eviction algorithm. You can utilise any Element metadata which makes possible some very interesting approaches. For example, evict an Element if it has been hit more than 10 times.
A Policy must implement the following interface:
DiskStore Eviction Algorithms
The DiskStore uses the Least Frequently Used algorithm to evict an element when it is full.