Cache Eviction

In many scenarios the total amount of data is greater then the available amount of memory. When a cache is full and a new element is added. The cache must evict one of its element in order to make room for the new element. The algorithm that determines which entry that should be evicted is called a cache replacement policy (or sometimes just a replacement policy).

A naive replacement policy might just select a random element and remove it. However, a common observation is that elements that have been accessed recently have a tendency to be accessed again in the near future. This concept is known as temporal locality. This is probably best embodied in the Least Recently Used (LRU) replacement policy which is commonly used in many computer systems.
While LRU works great for many workloads the naive randomized implementation might work better for other workloads. Selecting the right replacement policy can often be very difficult. But this page might offer some useful advice.

Overview

The eviction service is located in the org.coconut.cache.service.eviction package. It consists of the following three classes

Cache size and cache volume

Before looking there two important concepts that must be discussed cache size and cache volume.

• size is the number of elements that is contained in the cache (also the number returned by java.util.Map#size()). Adding an element to the cache will increase the size of the cache by 1, removing an element will decrease the size of the cache by 1.
• volume is the total sum of individual element sizes in the cache. For example, if one element uses 1 MB of memory and another element uses 4 MB, the current volume of the cache is 5 MB. Adding an element to the cache will increase the volume of the cache by the size of the element, removing an element will decrease the volume of the cache by the size of the element.

Usually the user will configure a limit on either of these two properties. Note, that the limits imposed are hard limits and will be checked whenever a new element is added. And if there is a limit imposed on the volume this will also be checked whenever an element is updated.

Configuring the eviction service

By default, there are no limits on either the cache size or volume. Instead, the cache must be configured to do so.
Example: A cache where the maximum size is 1000, and the maximum volume is 10000000.

Cache Replacement Policy

All replacement policy used in
Coconut Cache must implement the [ReplacementPolicy] interface.

A list of all the supported policies can be seen at the end of this page

Normally, users to not need to worry about how
Coconut cache comes with a number of built-on replacement policies that are applicable in various scenarios. The next sections will discuss each of the policies.

Note: If no cache replacement policy the cache will automatically choose a replacement policy (but not neccessesarily the optimal one) if needed.

Paging based replacement policies

A replacement policy based on paging is a policy where all elements have uniform sizes and cost to retrieve. That is a document with a size of 1 MB and one with a size of 10 MB is treated equally by the policy.

The best, offline cache replacement policy is Belady's MIN that replaces the page that is used farthest in the future[1]. Of course, in practice, we are only interested in online cache replacement policies that do not demand any prior knowledge of the workload.

Variable cost/size replacement policies.

Consider a small application that consists of 10 documents that the users access randomly. 9 of the documents needs 1 mb to be stored and the last document needs 5

Special Policies

There is a number

• Opt/Belady min Policy
• Threshold Policy
• Filter Policy : Wraps an existing replacement policy but rejects elements that does not parse a specified filter. Can be used for selecting entries that should not be cached.

Out-Of-The-Box supported replacement policies

The following is a list of the various replacement policies that are currently available with the default distribution.

Another concept that might be used by
Spatial locality
The concept that likelihood of referencing a resource is higher if a resource near it was just referenced. For example, if the user accesses a web page. The likehood of him opening a the next page he opens has an outgoing link from the page is higher then....