IBM WebSphere Extended Deployment (XD)TM
Release 6.0

com.ibm.websphere.objectgrid.plugins.builtins
LFUEvictor

java.lang.Object
  |
  +--com.ibm.websphere.objectgrid.plugins.builtins.LFUEvictor
All Implemented Interfaces
Evictor, RollbackEvictor, Runnable


This class manages a BackingMap using a simple Least Frequently Used (LFU) algorithm. It attempts to keep the BackingMap at less than a certain number of entries based on a usage count of each entry. This class uses an array of BinaryHeap objects for keeping the a LFUComparator object created for a CacheEntry. The LFUComparator object has the LFU count and key for the CacheEntry. The idea is to spread CacheEntry across multiple BinaryHeap objects so that there are fewer CacheEntry objects that collide on a synchronization point since they all do not use the same BinaryHeap.

An evictor thread is spawned during initialization that wakes up periodically and processes the array of BinaryHeap objects to determine if any CacheEntry needs to be evicted. The idea of using BinaryHeap is to obtain an ordering by LFU value so that it is not necessary to enumerate over every CacheEntry to determine if it needs to be evicted. Since BinaryHeap is a partial ordering, the cost to do the ordering is cheaper than creating a totally ordered list and/or sorting the list. But it also means the LFU algorithm is not 100% accurate, but it is close enough to be useful and avoids the cost of being 100% accurate by keep a totally ordered list.


Field Summary
public  longDEFAULT_SLEEP_TIME
           Default sleep time for evictor thread if the #setSleepTime(int) method is not called.
public  intDEFAULT_NUMBER_OF_HEAPS
           Default number of binary heaps to create if the #setNumberOfHeaps(int) method is not called.

Constructor Summary
LFUEvictor()
           Construct a LFUEvictor object with default values for the maximum size per heap, the number of heaps, and sleep time between sweeps of the heaps by evictor thread.


Method Summary
public  intgetMaxSize()
           Get maximum size of each binary heap.
public  voiddestroy()
           Destroy the evictor.
public  voidinitialize(com.ibm.websphere.objectgrid.BackingMap, com.ibm.websphere.objectgrid.plugins.EvictionEventCallback)
          
public  voidapply(com.ibm.websphere.objectgrid.plugins.LogSequence)
          
public  voidrollingBack(com.ibm.websphere.objectgrid.plugins.LogSequence)
          
public  intgetNumberOfHeaps()
           Get number of binary heaps being used.
public  voidsetNumberOfHeaps(int)
           Used to override the default number of binary heaps created by the initialize method for keeping the time to live data needed by the evictor thread.
public  intgetSleepTime()
           Get sleep time being used in seconds.
public  voidsetSleepTime(int)
           Used to override the default sleep time of evictor thread in seconds. .
public  voidsetMaxSize(int)
           Used to override the default maximum size for each heap used to keep LFU data.
public  voidrun()
           This method is implemented to periodically wake up and then evict entries.

Inherited Methods

Methods inherited from java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFAULT_SLEEP_TIME

public 
  static DEFAULT_SLEEP_TIME
Default sleep time for evictor thread if the #setSleepTime(int) method is not called.

DEFAULT_NUMBER_OF_HEAPS

public 
  static DEFAULT_NUMBER_OF_HEAPS
Default number of binary heaps to create if the #setNumberOfHeaps(int) method is not called.

Constructor Detail

LFUEvictor

public LFUEvictor( )
Construct a LFUEvictor object with default values for the maximum size per heap, the number of heaps, and sleep time between sweeps of the heaps by evictor thread. The default values can be overridden by use of the #setMaxSize(int), #setNumberOfHeaps(int), and #setSleepTime(int) methods. If setMaxSize is never called, the size of BackingMap is unlimited.


Method Detail

getMaxSize

public int getMaxSize()
Get maximum size of each binary heap.


Returns:
     same value that was passed to the #setMaxSize(int) method. If the set method is never called, then the default value is returned.


destroy

public void destroy()
Destroy the evictor.
See Also:
    destroy()


initialize

public void initialize(BackingMap map,EvictionEventCallback callback)

See Also:
    initialize(com.ibm.websphere.objectgrid.BackingMap, com.ibm.websphere.objectgrid.plugins.EvictionEventCallback)
Parameters:


apply

public void apply(LogSequence sequence)

See Also:
    apply(com.ibm.websphere.objectgrid.plugins.LogSequence)
Parameters:


rollingBack

public void rollingBack(LogSequence sequence)
Parameters:


getNumberOfHeaps

public int getNumberOfHeaps()
Get number of binary heaps being used.


Returns:
     same value that was passed to the #setNumberOfHeaps(int) method. If the set method is never called, then the default value used is returned.


setNumberOfHeaps

public void setNumberOfHeaps(int numberOfHeaps)
Used to override the default number of binary heaps created by the initialize method for keeping the time to live data needed by the evictor thread. This method must be called prior to the #initialize(BackingMap, EvictionEventCallback) method to avoid IllegalStateException being thrown. If this method is not called, then the constant #DEFAULT_NUMBER_OF_HEAPS is used as the number of heaps.
Parameters:
    numberOfHeaps - is the number of BinaryHeap instances used to hold evictor TTL data. The value must be greater than or equal to 1 and a prime number is recommended for best performance.


Throws:
    java.lang.IllegalArgumentExceptionjava.lang.IllegalStateException


getSleepTime

public int getSleepTime()
Get sleep time being used in seconds.


Returns:
     same value that is passed to #setSleepTime(int) or default value if set method was never called.


setSleepTime

public void setSleepTime(int seconds)
Used to override the default sleep time of evictor thread in seconds. Must be called prior to the #initialize(BackingMap, EvictionEventCallback) method to avoid IllegalStateException being thrown. If this method is not called, then the constant #DEFAULT_SLEEP_TIME is used as the sleep time.
Parameters:
    seconds - is the number of seconds evictor thread sleeps in between each sweep of the BinaryHeap data being kept for TTL data.


Throws:
    java.lang.IllegalArgumentExceptionjava.lang.IllegalStateException


setMaxSize

public void setMaxSize(int maxSize)
Used to override the default maximum size for each heap used to keep LFU data. The evictor thread will attempt to keep each heap to be no larger than the maximum size. Must be called prior to the #initialize(BackingMap, EvictionEventCallback) method to avoid IllegalStateException being thrown.
Parameters:
    maxSize - is the maximum size per heap. Any value <= 0 indicates to allow heap to be of unlimited size. In which case, no LFU data is kept.


Throws:
    java.lang.IllegalStateException


run

public void run()
This method is implemented to periodically wake up and then evict entries.
See Also:
    run()


IBM WebSphere Extended Deployment (XD)TM
Release 6.0