Eviction policies control JBoss Cache's memory management by managing how many nodes are allowed to be stored in memory and their life spans. Memory constraints on servers mean cache cannot grow indefinitely, so policies need to be in place to restrict the size of the cache. Eviction policies are most often used alongside cache loaders .
The basic eviction policy configuration element looks like:
... <attribute name="EvictionConfig"> <config> <attribute name="wakeUpIntervalSeconds">3</attribute> <!-- This defaults to 200000 if not specified --> <attribute name="eventQueueSize">100000</attribute> <!-- Name of the DEFAULT eviction policy class. --> <attribute name="policyClass">org.jboss.cache.eviction.LRUPolicy</attribute> <!-- Cache wide default --> <region name="/_default_"> <attribute name="maxNodes">100</attribute> </region> <!-- override policy used for this region --> <region name="/org/jboss/data" policyClass="org.jboss.cache.eviction.MRUPolicy"> <attribute name="maxNodes">250</attribute> </region> <!-- We expect a lot of events for this region, so override the default event queue size --> <region name="/org/jboss/test/data" eventQueueSize="500000"> <attribute name="maxNodes">60000</attribute> </region> </config> </attribute> ...
The concept of regions and the Region class were visited earlier when talking about marshalling. Regions also have another use, in that they are used to define the eviction policy used within the region. In addition to using a region-specific configuration, you can also configure a default, cache-wide eviction policy for nodes that do not fall into predefined regions or if you do not wish to define specific regions. It is important to note that when defining regions using the configuration XML file, all elements of the Fqn that defines the region are java.lang.String objects.
Looking at the eviction configuration snippet above, we see that a default region, _default_ , holds attributes which apply to nodes that do not fall into any of the other regions defined.
For each region, you can define parameters which affect how the policy which applies to the region chooses to evict nodes. In the example above, the LRUPolicy allows a maxNodes parameter which defines how many nodes can exist in the region before it chooses to start evicting nodes. See the javadocs for each policy for a list of allowed parameters.
It's possible to define regions that overlap. In other words, one region can be defined for /a/b/c , and another defined for /a/b/c/d (which is just the d subtree of the /a/b/c sub-tree). The algorithm, in order to handle scenarios like this consistently, will always choose the first region it encounters. In this way, if the algorithm needed to decide how to handle /a/b/c/d/e , it would start from there and work its way up the tree until it hits the first defined region - in this case /a/b/c/d .
Configuring eviction using the Configuration object entails the use of the org.jboss.cache.config.EvictionConfig bean, which is passed into Configuration.setEvictionConfig() . See the chapter on Configuration for more on building a Configuration programatically.
The use of simple POJO beans to represent all elements in a cache's configuration also makes it fairly easy to programatically add eviction regions after the cache is started . For example, assume we had an existing cache configured via XML with the EvictionConfig element shown above. Now at runtime we wished to add a new eviction region named "/org/jboss/fifo", using LRUPolicy but a different number of maxNodes :
Fqn fqn = Fqn.fromString("/org/jboss/fifo"); // Create a configuration for an LRUPolicy LRUConfiguration lruc = new LRUConfiguration(); lruc.setMaxNodes(10000); // Create the region and set the config Region region = cache.getRegion(fqn, true); region.setEvictionPolicy(lruc);
org.jboss.cache.eviction.LRUPolicy controls both the node lifetime and age. This policy guarantees a constant order ( O (1) ) for adds, removals and lookups (visits). It has the following configuration parameters:
org.jboss.cache.eviction.FIFOPolicy controls the eviction in a proper first in first out order. This policy guarantees a constant order ( O (1) ) for adds, removals and lookups (visits). It has the following configuration parameters:
org.jboss.cache.eviction.MRUPolicy controls the eviction in based on most recently used algorithm. The most recently used nodes will be the first to evict with this policy. This policy guarantees a constant order ( O (1) ) for adds, removals and lookups (visits). It has the following configuration parameters:
org.jboss.cache.eviction.LFUPolicy controls the eviction in based on least frequently used algorithm. The least frequently used nodes will be the first to evict with this policy. Node usage starts at 1 when a node is first added. Each time it is visted, the node usage counter increments by 1. This number is used to determine which nodes are least frequently used. LFU is also a sorted eviction algorithm. The underlying EvictionQueue implementation and algorithm is sorted in ascending order of the node visits counter. This class guarantees a constant order ( O (1) ) for adds, removal and searches. However, when any number of nodes are added/visited to the queue for a given processing pass, a single quasilinear ( O (n * log n) ) operation is used to resort the queue in proper LFU order. Similarly if any nodes are removed or evicted, a single linear ( O (n) ) pruning operation is necessary to clean up the EvictionQueue. LFU has the following configuration parameters:
org.jboss.cache.eviction.ExpirationPolicy is a policy that evicts nodes based on an absolute expiration time. The expiration time is indicated using the org.jboss.cache.Node.put() method, using a String key expiration and the absolute time as a java.lang.Long object, with a value indicated as milliseconds past midnight January 1st, 1970 UTC (the same relative time as provided by java.lang.System.currentTimeMillis() ).
This policy guarantees a constant order ( O (1) ) for adds and removals. Internally, a sorted set (TreeSet) containing the expiration time and Fqn of the nodes is stored, which essentially functions as a heap.
This policy has the following configuration parameters:
The following listing shows how the expiration date is indicated and how the policy is applied:
Cache cache = DefaultCacheFactory.createCache(); Fqn fqn1 = Fqn.fromString("/node/1"); Long future = new Long(System.currentTimeMillis() + 2000); // sets the expiry time for a node cache.getRoot().addChild(fqn1).put(ExpirationConfiguration.EXPIRATION_KEY, future); assertTrue(cache.getRoot().hasChild(fqn1)); Thread.sleep(5000); // after 5 seconds, expiration completes assertFalse(cache.getRoot().hasChild(fqn1));
Note that the expiration time of nodes is only checked when the region manager wakes up every wakeUpIntervalSeconds , so eviction may happen a few seconds later than indicated.
org.jboss.cache.eviction.ElementSizePolicy controls the eviction in based on the number of key/value pairs in the node. Nodes The most recently used nodes will be the first to evict with this policy. It has the following configuration parameters:
The design of the JBoss Cache eviction policy framework is based on an EvictionInterceptor to handle cache events and relay them back to the eviction policies. During the cache start up, an EvictionInterceptor will be added to the cache interceptor stack if the eviction policy is specified. Then whenever a node is added, removed, evicted, or visited, the EvictionInterceptor will maintain state statistics and information will be relayed to each individual eviction region.
There is a single eviction thread (timer) that will run at a configured interval. This thread will make calls into each of the policy providers and inform it of any aggregated adds, removes and visits (gets) events to the cache during the configured interval. The eviction thread is responsible for kicking off the eviction policy processing (a single pass) for each configured eviction cache region.
In order to implement an eviction policy, the following interfaces must be implemented:
When compounded together, each of these interface implementations define all the underlying mechanics necessary for a complete eviction policy implementation.
Note that:
The EvictionPolicyConfig implementation should maintain getter and setter methods for whatever configuration properties the policy supports (e.g. for LRUConfiguration among others there is a int getMaxNodes() and a setMaxNodes(int) ). When the "EvictionConfig" section of an XML configuration is parsed, these properties will be set by reflection.
Alternatively, the implementation of a new eviction policy provider can be simplified by extending BaseEvictionPolicy and BaseEvictionAlgorithm . Or for properly sorted EvictionAlgorithms (sorted in eviction order - see LFUAlgorithm ) extending BaseSortedEvictionAlgorithm and implementing SortedEvictionQueue takes care of most of the common functionality available in a set of eviction policy provider classes
Note that:
The BaseEvictionAlgorithm class maintains a processing structure. It will process the ADD, REMOVE, and VISIT events queued by the region first. It also maintains an collection of items that were not properly evicted during the last go around because of held locks. That list is pruned. Finally, the EvictionQueue itself is pruned for entries that should be evicted based upon the configured eviction rules for the region.
The BaseSortedEvictionAlgorithm class will maintain a boolean through the algorithm processing that will determine if any new nodes were added or visited. This allows the Algorithm to determine whether to resort the eviction queue items (in first to evict order) or to skip the potentially expensive sorting if there have been no changes to the cache in this region.
The SortedEvictionQueue interface defines the contract used by the BaseSortedEvictionAlgorithm abstract class that is used to resort the underlying queue. Again, the queue sorting should be sorted in first to evict order. The first entry in the list should evict before the last entry in the queue. The last entry in the queue should be the last entry that will require eviction.