JBoss.orgCommunity Documentation

Chapter 10. Eviction

10.1. Design
10.1.1. Collecting Statistics
10.1.2. Determining Which Nodes to Evict
10.1.3. How Nodes are Evicted
10.1.4. Eviction threads
10.2. Eviction Regions
10.2.1. Resident Nodes
10.3. Configuring Eviction
10.3.1. Basic Configuration
10.3.2. Programmatic Configuration
10.4. Shipped Eviction Policies
10.4.1. LRUAlgorithm - Least Recently Used
10.4.2. FIFOAlgorithm - First In, First Out
10.4.3. MRUAlgorithm - Most Recently Used
10.4.4. LFUAlgorithm - Least Frequently Used
10.4.5. ExpirationAlgorithm
10.4.6. ElementSizeAlgorithm - Eviction based on number of key/value pairs in a node

Eviction controls JBoss Cache's memory management by restricting how many nodes are allowed to be stored in memory, and for how long. Memory constraints on servers mean caches cannot grow indefinitely, so eviction needs to occur to prevent out of memory errors. Eviction is most often used alongside cache loaders.

Eviction in JBoss Cache is designed around four concepts:

In addition, Regions play a key role in eviction, as eviction is always configured on a per-region basis so that different subtrees in the cache can have different eviction characteristics.

The concept of regions and the Region class were visited earlier when talking about marshalling. Regions are also used to define the eviction behavior for nodes within that region. In addition to using a region-specific configuration, you can also configure default, cache-wide eviction behavior 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 String objects.

For each region, you can define eviction 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 node /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.

Nodes marked as resident (using Node.setResident() API) will be ignored by the eviction policies both when checking whether to trigger the eviction and when proceeding with the actual eviction of nodes. E.g. if a region is configured to have a maximum of 10 nodes, resident nodes won't be counted when deciding whether to evict nodes in that region. In addition, resident nodes will not be considered for eviction when the region's eviction threshold is reached.

In order to mark a node as resident the Node.setResident() API should be used. By default, the newly created nodes are not resident. The resident attribute of a node is neither replicated, persisted nor transaction-aware.

A sample use case for resident nodes would be ensuring "path" nodes don't add "noise" to an eviction policy. E.g.,:



...
   Map lotsOfData = generateData();
   cache.put("/a/b/c", lotsOfData);
   cache.getRoot().getChild("/a").setResident(true);
   cache.getRoot().getChild("/a/b").setResident(true);
...
               

In this example, the nodes /a and /a/b are paths which exist solely to support the existence of node /a/b/c and don't hold any data themselves. As such, they are good candidates for being marked as resident. This would lead to better memory management as no eviction events would be generated when accessing /a and/a/b.

N.B. when adding attributes to a resident node, e.g. cache.put("/a", "k", "v") in the above example, it would make sense to mark the nodes as non-resident again and let them be considered for eviction..

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 LRUAlgorithm but a different number of maxNodes:



   Fqn fqn = Fqn.fromString("/org/jboss/fifo");
   // Create a configuration for an LRUPolicy
   LRUAlgorithmConfig lruc = new LRUAlgorithmConfig();
   lruc.setMaxNodes(10000);
   // Create an eviction region config
   EvictionRegionConfig erc = new EvictionRegionConfig(fqn, lruc);
   // Create the region and set the config
   Region region = cache.getRegion(fqn, true);
   region.setEvictionRegionConfig(erc);
         
This section details the different algorithms shipped with JBoss Cache, and the various configuration parameters used for each algorithm.

org.jboss.cache.eviction.LFUAlgorithm 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 visited, 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.ExpirationAlgorithm 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.