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.