Chapter 6. Eviction Policies
Prev |  | Next

## Chapter 6. Eviction Policies

Eviction policies specify the behavior of a node residing inside the cache, e.g., life time and maximum numbers allowed. Memory constraints on servers mean caches cannot grow indefinitely, so policies need to be in place to restrict the size of the cache in memory.

## 6.1. Eviction Policy Plugin

The design of the JBoss Cache eviction policy framework is based on the loosely coupled observable pattern (albeit still synchronous) where the eviction region manager will register a `TreeCacheListener` to handle cache events and relay them back to the eviction policies. Whenever a cached node is added, removed, evicted, or visited, the eviction registered `TreeCacheListener` will maintain state statistics and information will be relayed to each individual Eviction Region. Each Region can define a different `EvictionPolicy` implementation that will know how to correlate cache add, remove, and visit events back to a defined eviction behavior. It's the policy provider's responsibility to decide when to call back the cache "evict" operation.

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 `TreeCacheListener` aggregated adds, removes and visits (gets) 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: org.jboss.cache.eviction.EvictionPolicy, org.jboss.cache.eviction.EvictionAlgorithm, org.jboss.cache.eviction.EvictionQueue and org.jboss.cache.eviction.EvictionConfiguration. When compounded together, each of these interface implementations define all the underlying mechanics necessary for a complete eviction policy implementation.

Figure 6.1. TreeCache eviction UML Diagram

    public interface EvictionPolicy
    {
       /**
        * Evict a node form the underlying cache.
        *
        * @param fqn DataNode corresponds to this fqn.
        * @throws Exception
        */
       void evict(Fqn fqn) throws Exception;

       /**
        * Return children names as Objects
        *
        * @param fqn
        * @return Child names under given fqn
        */
       Set getChildrenNames(Fqn fqn);

       /**
        * Is this a leaf node?
        *
        * @param fqn
        * @return true/false if leaf node.
        */
       boolean hasChild(Fqn fqn);

       Object getCacheData(Fqn fqn, Object key);

       /**
        * Method called to configure this implementation.
        */
       void configure(TreeCache cache);

       /**
        * Get the associated EvictionAlgorithm used by the EvictionPolicy.
        * <p/>
        * This relationship should be 1-1.
        *
        * @return An EvictionAlgorithm implementation.
        */
       EvictionAlgorithm getEvictionAlgorithm();

       /**
        * The EvictionConfiguration implementation class used by this EvictionPolicy.
        *
        * @return EvictionConfiguration implementation class.
        */
       Class getEvictionConfigurationClass();

    }

    public interface EvictionAlgorithm
    {
       /**
        * Entry point for evictin algorithm. This is an api called by the EvictionTimerTask
        * to process the node events in waiting and actual pruning, if necessary.
        *
        * @param region Region that this algorithm will operate on.
        */
       void process(Region region) throws EvictionException;

       /**
        * Reset the whole eviction queue. Queue may needs to be reset due to corrupted state, for example.
        *
        * @param region Region that this algorithm will operate on.
        */
       void resetEvictionQueue(Region region);

       /**
        * Get the EvictionQueue implementation used by this algorithm.
        *
        * @return the EvictionQueue implementation.
        */
       EvictionQueue getEvictionQueue();

    }

    public interface EvictionQueue
    {
       /**
        * Get the first entry in the queue.
        * <p/>
        * If there are no entries in queue, this method will return null.
        * <p/>
        * The first node returned is expected to be the first node to evict.
        *
        * @return first NodeEntry in queue.
        */
       public NodeEntry getFirstNodeEntry();

       /**
        * Retrieve a node entry by Fqn.
        * <p/>
        * This will return null if the entry is not found.
        *
        * @param fqn Fqn of the node entry to retrieve.
        * @return Node Entry object associated with given Fqn param.
        */
       public NodeEntry getNodeEntry(Fqn fqn);

       public NodeEntry getNodeEntry(String fqn);

       /**
        * Check if queue contains the given NodeEntry.
        *
        * @param entry NodeEntry to check for existence in queue.
        * @return true/false if NodeEntry exists in queue.
        */
       public boolean containsNodeEntry(NodeEntry entry);

       /**
        * Remove a NodeEntry from queue.
        * <p/>
        * If the NodeEntry does not exist in the queue, this method will return normally.
        *
        * @param entry The NodeEntry to remove from queue.
        */
       public void removeNodeEntry(NodeEntry entry);

       /**
        * Add a NodeEntry to the queue.
        *
        * @param entry The NodeEntry to add to queue.
        */
       public void addNodeEntry(NodeEntry entry);

       /**
        * Get the size of the queue.
        *
        * @return The number of items in the queue.
        */
       public int size();

       /**
        * Clear the queue.
        */
       public void clear();

    }

    public interface EvictionConfiguration
    {
       public static final int WAKEUP_DEFAULT = 5;

       public static final String ATTR = "attribute";
       public static final String NAME = "name";

       public static final String REGION = "region";
       public static final String WAKEUP_INTERVAL_SECONDS = "wakeUpIntervalSeconds";
       public static final String MAX_NODES = "maxNodes";
       public static final String TIME_TO_IDLE_SECONDS = "timeToIdleSeconds";
       public static final String TIME_TO_LIVE_SECONDS = "timeToLiveSeconds";
       public static final String MAX_AGE_SECONDS = "maxAgeSeconds";
       public static final String MIN_NODES = "minNodes";
       public static final String REGION_POLICY_CLASS = "policyClass";

       /**
        * Parse the XML configuration for the given specific eviction region.
        * <p/>
        * The element parameter should contain the entire region block. An example
        * of an entire Element of the region would be:
        * <p/>
        * <region name="abc">
        * <attribute name="maxNodes">10</attribute>
        * </region>
        *
        * @param element DOM element for the region. <region name="abc"></region>
        * @throws ConfigureException
        */
       public void parseXMLConfig(Element element) throws ConfigureException;
    }

Note that:

- The EvictionConfiguration class 'parseXMLConfig(Element)' method expects only the DOM element pertaining to the region the policy is being configured for.

- The EvictionConfiguration implementation should maintain getter and setter methods for configured properties pertaining to the policy used on a given cache region. (e.g. for LRUConfiguration there is a int getMaxNodes() and a setMaxNodes(int))

Alternatively, the implementation of a new eviction policy provider can be further 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

    public abstract class BaseEvictionPolicy implements EvictionPolicy
    {
       protected static final Fqn ROOT = new Fqn("/");

       protected TreeCache cache_;

       public BaseEvictionPolicy()
       {
       }

       /** EvictionPolicy interface implementation */

       /**
        * Evict the node under given Fqn from cache.
        *
        * @param fqn The fqn of a node in cache.
        * @throws Exception
        */
       public void evict(Fqn fqn) throws Exception
       {
          cache_.evict(fqn);
       }

       /**
        * Return a set of child names under a given Fqn.
        *
        * @param fqn Get child names for given Fqn in cache.
        * @return Set of children name as Objects
        */
       public Set getChildrenNames(Fqn fqn)
       {
          try
          {
             return cache_.getChildrenNames(fqn);
          }
          catch (CacheException e)
          {
             e.printStackTrace();
          }
          return null;
       }

       public boolean hasChild(Fqn fqn)
       {
          return cache_.hasChild(fqn);
       }

       public Object getCacheData(Fqn fqn, Object key)
       {
          try
          {
             return cache_.get(fqn, key);
          }
          catch (CacheException e)
          {
             e.printStackTrace();
          }
          return null;
       }

       public void configure(TreeCache cache)
       {
          this.cache_ = cache;
       }

    }

    public abstract class BaseEvictionAlgorithm implements EvictionAlgorithm
    {
       private static final Log log = LogFactory.getLog(BaseEvictionAlgorithm.class);

       protected Region region;
       protected BoundedBuffer recycleQueue;
       protected EvictionQueue evictionQueue;

       /**
        * This method will create an EvictionQueue implementation and prepare it for use.
        *
        * @param region Region to setup an eviction queue for.
        * @return The created EvictionQueue to be used as the eviction queue for this algorithm.
        * @throws EvictionException
        * @see EvictionQueue
        */
       protected abstract EvictionQueue setupEvictionQueue(Region region) throws EvictionException;

       /**
        * This method will check whether the given node should be evicted or not.
        *
        * @param ne NodeEntry to test eviction for.
        * @return True if the given node should be evicted. False if the given node should not be evicted.
        */
       protected abstract boolean shouldEvictNode(NodeEntry ne);

       protected BaseEvictionAlgorithm()
       {
          recycleQueue = new BoundedBuffer();
       }

       protected void initialize(Region region) throws EvictionException
       {
          this.region = region;
          evictionQueue = setupEvictionQueue(region);
       }

       /**
        * Process the given region.
        * <p/>
        * Eviction Processing encompasses the following:
        * <p/>
        * - Add/Remove/Visit Nodes
        * - Prune according to Eviction Algorithm
        * - Empty/Retry the recycle queue of previously evicted but locked (during actual cache eviction) nodes.
        *
        * @param region Cache region to process for eviction.
        * @throws EvictionException
        */
       public void process(Region region) throws EvictionException
       {
          if (this.region == null)
          {
             this.initialize(region);
          }

          this.processQueues(region);
          this.emptyRecycleQueue();
          this.prune();
       }

       public void resetEvictionQueue(Region region)
       {
       }

       /**
        * Get the underlying EvictionQueue implementation.
        *
        * @return the EvictionQueue used by this algorithm
        * @see EvictionQueue
        */
       public EvictionQueue getEvictionQueue()
       {
          return this.evictionQueue;
       }

       /**
        * Event processing for Evict/Add/Visiting of nodes.
        * <p/>
        * - On AddEvents a new element is added into the eviction queue
        * - On RemoveEvents, the removed element is removed from the eviction queue.
        * - On VisitEvents, the visited node has its eviction statistics updated (idleTime, numberOfNodeVisists, etc..)
        *
        * @param region Cache region to process for eviction.
        * @throws EvictionException
        */
       protected void processQueues(Region region) throws EvictionException
       {
          EvictedEventNode node;
          int count = 0;
          while ((node = region.takeLastEventNode()) != null)
          {
             int eventType = node.getEvent();
             Fqn fqn = node.getFqn();

             count++;
             switch (eventType)
             {
                case EvictedEventNode.ADD_EVENT:
                   this.processAddedNodes(fqn);
                   break;
                case EvictedEventNode.REMOVE_EVENT:
                   this.processRemovedNodes(fqn);
                   break;
                case EvictedEventNode.VISIT_EVENT:
                   this.processVisitedNodes(fqn);
                   break;
                default:
                   throw new RuntimeException("Illegal Eviction Event type " + eventType);
             }
          }

          if (log.isTraceEnabled())
          {
             log.trace("processed " + count + " node events");
          }

       }

       protected void evict(NodeEntry ne)
       {
    //      NodeEntry ne = evictionQueue.getNodeEntry(fqn);
          if (ne != null)
          {
             evictionQueue.removeNodeEntry(ne);
             if (!this.evictCacheNode(ne.getFqn()))
             {
                try
                {
                   recycleQueue.put(ne);
                }
                catch (InterruptedException e)
                {
                   e.printStackTrace();
                }
             }
          }
       }

       /**
        * Evict a node from cache.
        *
        * @param fqn node corresponds to this fqn
        * @return True if successful
        */
       protected boolean evictCacheNode(Fqn fqn)
       {
          if (log.isTraceEnabled())
          {
             log.trace("Attempting to evict cache node with fqn of " + fqn);
          }
          EvictionPolicy policy = region.getEvictionPolicy();
          // Do an eviction of this node

          try
          {
             policy.evict(fqn);
          }
          catch (Exception e)
          {
             if (e instanceof TimeoutException)
             {
                log.warn("eviction of " + fqn + " timed out. Will retry later.");
                return false;
             }
             e.printStackTrace();
             return false;
          }

          if (log.isTraceEnabled())
          {
             log.trace("Eviction of cache node with fqn of " + fqn + " successful");
          }

          return true;
       }

       /**
        * Process an Added cache node.
        *
        * @param fqn FQN of the added node.
        * @throws EvictionException
        */
       protected void processAddedNodes(Fqn fqn) throws EvictionException
       {
          if (log.isTraceEnabled())
          {
             log.trace("Adding node " + fqn + " to eviction queue");
          }

          long stamp = System.currentTimeMillis();
          NodeEntry ne = new NodeEntry(fqn);
          ne.setModifiedTimeStamp(stamp);
          ne.setNumberOfNodeVisits(1);
          // add it to the node map and eviction queue
          if (evictionQueue.containsNodeEntry(ne))
          {
             if (log.isTraceEnabled())
             {
                log.trace("Queue already contains " + ne.getFqn() + " processing it as visited");
             }
             this.processVisitedNodes(ne.getFqn());
             return;
          }

          evictionQueue.addNodeEntry(ne);

          if (log.isTraceEnabled())
          {
             log.trace(ne.getFqn() + " added successfully to eviction queue");
          }
       }

       /**
        * Remove a node from cache.
        * <p/>
        * This method will remove the node from the eviction queue as well as
        * evict the node from cache.
        * <p/>
        * If a node cannot be removed from cache, this method will remove it from the eviction queue
        * and place the element into the recycleQueue. Each node in the recycle queue will get retried until
        * proper cache eviction has taken place.
        * <p/>
        * Because EvictionQueues are collections, when iterating them from an iterator, use iterator.remove()
        * to avoid ConcurrentModificationExceptions. Use the boolean parameter to indicate the calling context.
        *
        * @param fqn FQN of the removed node
        * @throws EvictionException
        */
       protected void processRemovedNodes(Fqn fqn) throws EvictionException
       {
          if (log.isTraceEnabled())
          {
             log.trace("Removing node " + fqn + " from eviction queue and attempting eviction");
          }

          NodeEntry ne = evictionQueue.getNodeEntry(fqn);
          if (ne != null)
          {
             evictionQueue.removeNodeEntry(ne);
          }

          if (log.isTraceEnabled())
          {
             log.trace(fqn + " removed from eviction queue");
          }
       }

       /**
        * Visit a node in cache.
        * <p/>
        * This method will update the numVisits and modifiedTimestamp properties of the Node.
        * These properties are used as statistics to determine eviction (LRU, LFU, MRU, etc..)
        * <p/>
        * *Note* that this method updates Node Entries by reference and does not put them back
        * into the queue. For some sorted collections, a remove, and a re-add is required to
        * maintain the sorted order of the elements.
        *
        * @param fqn FQN of the visited node.
        * @throws EvictionException
        */
       protected void processVisitedNodes(Fqn fqn) throws EvictionException
       {
          NodeEntry ne = evictionQueue.getNodeEntry(fqn);
          if (ne == null)
          {
             this.processAddedNodes(fqn);
             return;
          }
          // note this method will visit and modify the node statistics by reference!
          // if a collection is only guaranteed sort order by adding to the collection,
          // this implementation will not guarantee sort order.
          ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
          ne.setModifiedTimeStamp(System.currentTimeMillis());
       }

       /**
        * Empty the Recycle Queue.
        * <p/>
        * This method will go through the recycle queue and retry to evict the nodes from cache.
        *
        * @throws EvictionException
        */
       protected void emptyRecycleQueue() throws EvictionException
       {
          while (true)
          {
             Fqn fqn;

             try
             {
                fqn = (Fqn) recycleQueue.poll(0);
             }
             catch (InterruptedException e)
             {
                e.printStackTrace();
                break;
             }

             if (fqn == null)
             {
                if (log.isTraceEnabled())
                {
                   log.trace("Recycle queue is empty");
                }
                break;
             }

             if (log.isTraceEnabled())
             {
                log.trace("emptying recycle bin. Evict node " + fqn);
             }

             // Still doesn't work
             if (!evictCacheNode(fqn))
             {
                try
                {
                   recycleQueue.put(fqn);
                }
                catch (InterruptedException e)
                {
                   e.printStackTrace();
                }
                break;
             }
          }
       }

       protected void prune() throws EvictionException
       {
          NodeEntry entry;
          while ((entry = evictionQueue.getFirstNodeEntry()) != null)
          {
             if (this.shouldEvictNode(entry))
             {
                this.evict(entry);
             }
             else
             {
                break;
             }
          }
       }

    }

Note that:

- The BaseEvictionAlgorithm class maintains a processing structure. It will process the ADD, REMOVE, and VISIT events queued by the Region (events are originated from the EvictionTreeCacheListener) 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.

       public abstract class BaseSortedEvictionAlgorithm extends BaseEvictionAlgorithm implements EvictionAlgorithm
       {
          private static final Log log = LogFactory.getLog(BaseSortedEvictionAlgorithm.class);

          public void process(Region region) throws EvictionException
          {
             super.process(region);
          }

          protected void processQueues(Region region) throws EvictionException
          {
             boolean evictionNodesModified = false;

             EvictedEventNode node;
             int count = 0;
             while ((node = region.takeLastEventNode()) != null)
             {
                int eventType = node.getEvent();
                Fqn fqn = node.getFqn();

                count++;
                switch (eventType)
                {
                   case EvictedEventNode.ADD_EVENT:
                      this.processAddedNodes(fqn);
                      evictionNodesModified = true;
                      break;
                   case EvictedEventNode.REMOVE_EVENT:
                      this.processRemovedNodes(fqn);
                      break;
                   case EvictedEventNode.VISIT_EVENT:
                      this.processVisitedNodes(fqn);
                      evictionNodesModified = true;
                      break;
                   default:
                      throw new RuntimeException("Illegal Eviction Event type " + eventType);
                }
             }

             if (log.isTraceEnabled())
             {
                log.trace("Eviction nodes visited or added requires resort of queue " + evictionNodesModified);
             }

             this.resortEvictionQueue(evictionNodesModified);

             if (log.isTraceEnabled())
             {
                log.trace("processed " + count + " node events");
             }

          }

          /**
           * This method is called to resort the queue after add or visit events have occurred.
           * <p/>
           * If the parameter is true, the queue needs to be resorted. If it is false, the queue does not
           * need resorting.
           *
           * @param evictionQueueModified True if the queue was added to or visisted during event processing.
           */
          protected void resortEvictionQueue(boolean evictionQueueModified)
          {
             long begin = System.currentTimeMillis();
             ((SortedEvictionQueue) evictionQueue).resortEvictionQueue();
             long end = System.currentTimeMillis();

             if (log.isTraceEnabled())
             {
                long diff = end - begin;
                log.trace("Took " + diff + "ms to sort queue with " + getEvictionQueue().size() + " elements");
             }
          }

       }

Note that:

- 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.

    public interface SortedEvictionQueue extends EvictionQueue
    {
       /**
        * Provide contract to resort a sorted queue.
        */
       public void resortEvictionQueue();
    }

Note that:

- 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.

## 6.2. TreeCache Eviction Policy Configuration

TreeCache 1.2.X allows a single eviction policy provider class to be configured for use by all regions. As of TreeCache 1.3.x each cache region can define its own eviction policy provider or it can use the eviction policy provider class defined at the cache level (1.2.x backwards compatibility)

Here is an example of a legacy 1.2.x EvictionPolicyConfig element to configure TreeCache for use with a single eviction policy provider

              <attribute name="EvictionPolicyClass">org.jboss.cache.eviction.LRUPolicy</attribute>
              <!-- Specific eviction policy configurations. This is LRU -->
              <attribute name="EvictionPolicyConfig">
                 <config>
                    <attribute name="wakeUpIntervalSeconds">5</attribute>
                    <!-- Cache wide default -->
                    <region name="/_default_">
                        <attribute name="maxNodes">5000</attribute>
                        <attribute name="timeToLiveSeconds">1000</attribute>
                    </region>
                    <region name="/org/jboss/data">
                        <attribute name="maxNodes">5000</attribute>
                        <attribute name="timeToLiveSeconds">1000</attribute>
                    </region>
                    <region name="/org/jboss/test/data">
                        <attribute name="maxNodes">5</attribute>
                        <attribute name="timeToLiveSeconds">4</attribute>
                    </region>
                    <region name="/test/">
                        <attribute name="maxNodes">10000</attribute>
                        <attribute name="timeToLiveSeconds">5</attribute>
                    </region>
                    <region name="/maxAgeTest/">
                       <attribute name="maxNodes">10000</attribute>
                       <attribute name="timeToLiveSeconds">8</attribute>
                       <attribute name="maxAgeSeconds">10</attribute>
                    </region>
                 </config>
              </attribute>

Here is an example of configuring a different eviction provider per region

          <attribute name="EvictionPolicyConfig">
             <config>
                <attribute name="wakeUpIntervalSeconds">5</attribute>
                <!-- Cache wide default -->
                <region name="/_default_" policyClass="org.jboss.cache.eviction.LRUPolicy">
                   <attribute name="maxNodes">5000</attribute>
                   <attribute name="timeToLiveSeconds">1000</attribute>
                </region>
                <region name="/org/jboss/data" policyClass="org.jboss.cache.eviction.LFUPolicy">
                   <attribute name="maxNodes">5000</attribute>
                   <attribute name="minNodes">1000</attribute>
                </region>
                <region name="/org/jboss/test/data" policyClass="org.jboss.cache.eviction.FIFOPolicy">
                   <attribute name="maxNodes">5</attribute>
                </region>
                <region name="/test/" policyClass="org.jboss.cache.eviction.MRUPolicy">
                   <attribute name="maxNodes">10000</attribute>
                </region>
                <region name="/maxAgeTest/" policyClass="org.jboss.cache.eviction.LRUPolicy">
                   <attribute name="maxNodes">10000</attribute>
                   <attribute name="timeToLiveSeconds">8</attribute>
                   <attribute name="maxAgeSeconds">10</attribute>
                </region>
             </config>
          </attribute>

Lastly, an example of mixed mode. In this scenario the regions that have a specific policy defined will use that policy. Those that do not will default to the policy defined on the entire cache instance.

          <attribute name="EvictionPolicyClass">org.jboss.cache.eviction.LRUPolicy</attribute>
          <!-- Specific eviction policy configurations. This is LRU -->
          <attribute name="EvictionPolicyConfig">
             <config>
                <attribute name="wakeUpIntervalSeconds">5</attribute>
                <!-- Cache wide default -->
                <region name="/_default_">
                   <attribute name="maxNodes">5000</attribute>
                   <attribute name="timeToLiveSeconds">1000</attribute>
                </region>
                <region name="/org/jboss/data" policyClass="org.jboss.cache.eviction.FIFOPolicy">
                   <attribute name="maxNodes">5000</attribute>
                </region>
                <region name="/test/" policyClass="org.jboss.cache.eviction.MRUPolicy">
                   <attribute name="maxNodes">10000</attribute>
                </region>
                <region name="/maxAgeTest/">
                   <attribute name="maxNodes">10000</attribute>
                   <attribute name="timeToLiveSeconds">8</attribute>
                   <attribute name="maxAgeSeconds">10</attribute>
                </region>
             </config>
          </attribute>

TreeCache now allows reconfiguration of eviction policy providers programatically at runtime. An example of how to reconfigure at runtime and how to set an LRU region to have maxNodes to 12345 timeToLiveSeconds to 500 and maxAgeSeconds to 1000 programatically.

             // note this is just to show that a running TreeCache instance must be
             // retrieved somehow. How it is implemented is up to the implementor.
             TreeCache cache = getRunningTreeCacheInstance();

             org.jboss.cache.eviction.RegionManager regionManager = cache.getEvictionRegionManager();
             org.jboss.cache.eviction.Region region = regionManager.getRegion("/myRegionName");
             EvictionConfiguation config = region.getEvictionConfiguration();
             ((LRUConfiguration)config).setMaxNodes(12345);
             ((LRUConfiguration)config).setTimeToLiveSeconds(500);
             ((LRUConfiguration)config).setMaxAgeSeconds(1000);

## 6.3. TreeCache LRU eviction policy implementation

TreeCache has implemented a LRU eviction policy, `org.jboss.cache.eviction.LRUPolicy`, that controls both the node lifetime and age. This policy guarantees O(n) = 1 for adds, removals and lookups (visits). It has the following configuration parameters:

- `wakeUpIntervalSeconds`. This is the interval (in seconds) to process the node events and also to perform sweeping for the size limit and age-out nodes.

- `Region`. Region is a group of nodes that possess the same eviction policy, e.g., same expired time. In TreeCache, region is denoted by a fqn, e.g., `/company/personnel`, and it is recursive. In specifying the region, the order is important. For example, if `/org/jboss/test` is specified before `/org/jboss/test/data`, then any node under `/org/jboss/test/data` belongs to the first region rather than the second. Note also that whenever eviction policy is activated, there should always be a `/_default_` region which covers all the eviction policies not specified by the user. In addition, the region configuration is not programmable, i.e., all the policies have to be specified via XML configuration.

  - `maxNodes`. This is the maximum number of nodes allowed in this region. 0 denotes no limit.

  - `timeToLiveSeconds`. Time to idle (in seconds) before the node is swept away. 0 denotes no limit.

  - `maxAgeSeconds`. Time an object should exist in TreeCache (in seconds) regardless of idle time before the node is swept away. 0 denotes no limit.

Please see the above section for an example.

## 6.4. TreeCache FIFO eviction policy implementation

TreeCache has implemented a FIFO eviction policy, `org.jboss.cache.eviction.FIFOPolicy`, that will control the eviction in a proper first in first out order. This policy guarantees O(n) = 1 for adds, removals and lookups (visits). It has the following configuration parameters:

- `wakeUpIntervalSeconds`. This is the interval (in seconds) to process the node events and also to perform sweeping for the size limit and age-out nodes.

- `Region`. Region is a group of nodes that possess the same eviction policy, e.g., same expired time. In TreeCache, region is denoted by a fqn, e.g., `/company/personnel`, and it is recursive. In specifying the region, the order is important. For example, if `/org/jboss/test` is specified before `/org/jboss/test/data`, then any node under `/org/jboss/test/data` belongs to the first region rather than the second. Note also that whenever eviction policy is activated, there should always be a `/_default_` region which covers all the eviction policies not specified by the user. In addition, the region configuration is not programmable, i.e., all the policies have to be specified via XML configuration.

  - `maxNodes`. This is the maximum number of nodes allowed in this region. Any integer less than or equal to 0 will throw an exception when the policy provider is being configured for use.

Please read the above section for an example.

## 6.5. TreeCache MRU eviction policy implementation

TreeCache has implemented a MRU eviction policy, `org.jboss.cache.eviction.MRUPolicy`, that will control 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 O(n) = 1 for adds, removals and lookups (visits). It has the following configuration parameters:

- `wakeUpIntervalSeconds`. This is the interval (in seconds) to process the node events and also to perform sweeping for the size limit and age-out nodes.

- `Region`. Region is a group of nodes that possess the same eviction policy, e.g., same expired time. In TreeCache, region is denoted by a fqn, e.g., `/company/personnel`, and it is recursive. In specifying the region, the order is important. For example, if `/org/jboss/test` is specified before `/org/jboss/test/data`, then any node under `/org/jboss/test/data` belongs to the first region rather than the second. Note also that whenever eviction policy is activated, there should always be a `/_default_` region which covers all the eviction policies not specified by the user. In addition, the region configuration is not programmable, i.e., all the policies have to be specified via XML configuration.

  - `maxNodes`. This is the maximum number of nodes allowed in this region. Any integer less than or equal to 0 will throw an exception when the policy provider is being configured for use.

Please read the above section for an example.

## 6.6. TreeCache LFU eviction policy implementation

TreeCache has implemented a LFU eviction policy, `org.jboss.cache.eviction.LFUPolicy`, that will control 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 O(n) = 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 O(n) = n*log(n) operation is used to resort the queue in proper LFU order. Similarly if any nodes are removed or evicted, a single O(n) = n pruning operation is necessary to clean up the EvictionQueue. LFU has the following configuration parameters:

- `wakeUpIntervalSeconds`. This is the interval (in seconds) to process the node events and also to perform sweeping for the size limit and age-out nodes.

- `Region`. Region is a group of nodes that possess the same eviction policy, e.g., same expired time. In TreeCache, region is denoted by a fqn, e.g., `/company/personnel`, and it is recursive. In specifying the region, the order is important. For example, if `/org/jboss/test` is specified before `/org/jboss/test/data`, then any node under `/org/jboss/test/data` belongs to the first region rather than the second. Note also that whenever eviction policy is activated, there should always be a `/_default_` region which covers all the eviction policies not specified by the user. In addition, the region configuration is not programmable, i.e., all the policies have to be specified via XML configuration.

  - `maxNodes`. This is the maximum number of nodes allowed in this region. A value of 0 for maxNodes means that there is no upper bound for the configured cache region.

  - `minNodes`. This is the minimum number of nodes allowed in this region. This value determines what the eviction queue should prune down to per pass. e.g. If minNodes is 10 and the cache grows to 100 nodes, the cache is pruned down to the 10 most frequently used nodes when the eviction timer makes a pass through the eviction algorithm.

Please read the above section for an example.

Prev | Up | Next
Chapter 5. Transactions and Concurrency | Home | Chapter 7. Cache Loaders