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

java.lang.Object
  com.ibm.websphere.objectgrid.plugins.builtins.LFUEvictor

All Implemented Interfaces:

Evictor, RollbackEvictor, Runnable

public final class LFUEvictor
extends Object
implements 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 binary heap objects for keeping a EvictorData object created for a CacheEntry. The EvictorData object has the LFU count and key for the CacheEntry. The idea is to spread cache entries across multiple binary heap objects so that there are fewer CacheEntry objects that collide on a synchronization point since they all do not use the same binary heap object.

An evictor thread is spawned during initialization that wakes up periodically and processes the array of binary heap objects to determine if any CacheEntry needs to be evicted. The idea of using a binary heap object 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 binary heap 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.

Since:

WAS XD 6.0, XC10

See Also:

Evictor

Field Summary

static int	DEFAULT_NUMBER_OF_HEAPS Default number of binary heaps to create if the setNumberOfHeaps(int) method is not called.
static long	DEFAULT_SLEEP_TIME Default sleep time for evictor thread if the setSleepTime(int) method is not called.

Constructor Summary

LFUEvictor()
Creates 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 the evictor thread.

Method Summary

void	activate() This method is called to activate the Evictor.
void	apply(LogSequence sequence) Called after a transaction has committed to allow the evictor to track object usage in the BackingMap.
void	deactivate() This method is called to deactivate the Evictor.
void	destroy() Called when the BackingMap associated with this evictor is destroyed.
int	getMaxSize() Gets the maximum size of each binary heap.
int	getNumberOfHeaps() Gets number of binary heaps being used.
int	getSleepTime() Gets the sleep time being used in seconds.
void	initialize(BackingMap map, EvictionEventCallback callback) Called by a BackingMap instance during the evictor initialization time.
void	rollingBack(LogSequence sequence) Called after a transaction rollback to allow an evictor to track object usage in a backing map even when rollback occurs instead of commit.
void	run() Periodically wakes up and evicts entries.
void	setMaxSize(int maxSize) Sets the maximum size of each binary heap.
void	setNumberOfHeaps(int numberOfHeaps) Sets the number of binary heaps to use.
void	setSleepTime(int seconds) Sets the sleep time to use in seconds.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFAULT_SLEEP_TIME

public static final long DEFAULT_SLEEP_TIME

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

See Also:

setSleepTime(int), Constant Field Values

DEFAULT_NUMBER_OF_HEAPS

public static final int DEFAULT_NUMBER_OF_HEAPS

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

See Also:

setNumberOfHeaps(int), Constant Field Values

Constructor Detail

LFUEvictor

public LFUEvictor()

Creates 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 the evictor thread.

The default values can be overridden by use of the setMaxSize(int), setNumberOfHeaps(int), and setSleepTime(int) methods. If the setMaxSize method is never called, the size of the map is unlimited.

See Also:

DEFAULT_NUMBER_OF_HEAPS, DEFAULT_SLEEP_TIME, setMaxSize(int), setNumberOfHeaps(int), setSleepTime(int)

Method Detail

getMaxSize

public int getMaxSize()

Gets the maximum size of each binary heap.

Returns:

the same value that was passed to the setMaxSize(int) method or the default value of zero if the setMaxSize method is never called

See Also:

setMaxSize(int)

destroy

public void destroy()

Description copied from interface: Evictor

Called when the BackingMap associated with this evictor is destroyed.

This method is the opposite of the initialize method. When it is called, the Evictor can free up any resources it uses.

Specified by:

destroy in interface Evictor

See Also:

Evictor.destroy()

initialize

public void initialize(BackingMap map,
                       EvictionEventCallback callback)

Description copied from interface: Evictor

Called by a BackingMap instance during the evictor initialization time.

The BackingMap calls this method so the Evictor instance can have references to the BackingMap and EvictionEventCallback instances. The evictor can signal events to have specific entries evicted using the EvictionEventCallback.

Specified by:

initialize in interface Evictor

Parameters:

map - the BackingMap instance

callback - the EvictionEventCallback instance

See Also:

Evictor.initialize(BackingMap, EvictionEventCallback)

apply

public void apply(LogSequence sequence)

Description copied from interface: Evictor

Called after a transaction has committed to allow the evictor to track object usage in the BackingMap.

This method also reports any entries that have been successfully evicted. Note, this method is not called for transactions that are rolled back. If there is a need to track object usage for rolled back transactions, the evictor must implement the RollbackEvictor interface as well.

This method is called after a transaction has completed. Consequently, all transaction locks that were acquired by the completed transaction are no longer held. Potentially, multiple threads could call this method concurrently and each thread would be completing its own transaction. Since transaction locks are already released by the completed transaction, this method must provide its own synchronization to ensure it is thread safe. For an Evictor in an ObjectMap that is configured to use OutputFormat.RAW for the keys or values, the keys and values objects in the LogSequence will be SerializedKey or SerializedValue objects respectively. If required, you can use the SerializedEntry.getObject() method to retrieve (possibly inflating the serialized object) the original key or value object. To override the map's output format configuration, use the PluginOutputFormat annotation in the implementation class.

Specified by:

apply in interface Evictor

Parameters:

sequence - the LogSequence of changes committed to the map

See Also:

Evictor.apply(LogSequence)

rollingBack

public void rollingBack(LogSequence sequence)

Description copied from interface: RollbackEvictor

Called after a transaction rollback to allow an evictor to track object usage in a backing map even when rollback occurs instead of commit. Since the transaction is rolling back, the Evictor must be aware that it cannot depend on the LogElement type to infer the existence or non-existence of a map entry. See Evictor.apply(LogSequence) for other considerations when implementing this method. Many of the considerations with the Evictor.apply method also apply to this method.

Specified by:

rollingBack in interface RollbackEvictor

Parameters:

sequence - LogSequence of changes to the map

See Also:

RollbackEvictor.rollingBack(LogSequence)

getNumberOfHeaps

public int getNumberOfHeaps()

Gets number of binary heaps being used.

Returns:

the same value that was passed to the setNumberOfHeaps(int) method or the default value of DEFAULT_NUMBER_OF_HEAPS if the setNumberOfHeaps method is never called

See Also:

DEFAULT_NUMBER_OF_HEAPS, setNumberOfHeaps(int)

setNumberOfHeaps

public void setNumberOfHeaps(int numberOfHeaps)

Sets the number of binary heaps to use.

This method is used to override the default number of binary heaps created by the initialize method for keeping the usage count data needed by the evictor thread. This method must be called prior to the initialize method to avoid an IllegalStateException being thrown. If this method is not called,the DEFAULT_NUMBER_OF_HEAPS constant is used as the number of heaps.

Parameters:

numberOfHeaps - is the number of BinaryHeap instances used to hold entry usage count data. The value must be greater than or equal to 1 and a prime number is recommended for best performance.

Throws:

IllegalArgumentException - if numberOfHeaps < 1

IllegalStateException - if called after the initialize method.

See Also:

DEFAULT_NUMBER_OF_HEAPS, initialize(BackingMap, EvictionEventCallback)

getSleepTime

public int getSleepTime()

Gets the sleep time being used in seconds.

Returns:

the same value that was passed to the setSleepTime(int) method or the default value of DEFAULT_SLEEP_TIME if the setSleepTime method is never called

See Also:

setSleepTime(int)

setSleepTime

public void setSleepTime(int seconds)

Sets the sleep time to use in seconds.

This method is used to override the default sleep time of the evictor thread in seconds. This method must be called prior to the initialize method to avoid an IllegalStateException being thrown. If this method is not called, the DEFAULT_SLEEP_TIME constant is used as the sleep time.

Parameters:

seconds - is the number of seconds the evictor thread sleeps in between each sweep of the binary heap data being kept for entry usage count data.

Throws:

IllegalArgumentException - if seconds < 1

IllegalStateException - if called after the initialize method.

See Also:

DEFAULT_SLEEP_TIME, initialize(BackingMap, EvictionEventCallback)

setMaxSize

public void setMaxSize(int maxSize)

Sets the maximum size of each binary heap.

This method is used to override the default maximum size for each heap used to keep entry usage count data. The evictor thread will attempt to keep each heap to be no larger than the maximum size. This method must be called prior to the initialize method to avoid an IllegalStateException being thrown.

Parameters:

maxSize - is the maximum size per heap. Any value <= 0 indicates to allow each heap to be of unlimited size. In which case, no entry usage count data is kept.

Throws:

IllegalStateException - if called after the initialize method.

See Also:

initialize(BackingMap, EvictionEventCallback)

run

public void run()

Periodically wakes up and evicts entries.

Specified by:

run in interface Runnable

See Also:

Runnable.run()

activate

public void activate()

Description copied from interface: Evictor

This method is called to activate the Evictor. Until this method is called, the Evictor must not use the EvictionEventCallback interface to evict any map entries. If it does use the EvictionEventcallback interface to evict map entries prior to activate being called, an IllegalStateException is thrown.

Specified by:

activate in interface Evictor

See Also:

Evictor.activate()

deactivate

public void deactivate()

Description copied from interface: Evictor

This method is called to deactivate the Evictor. Once this method is called, the Evictor must quit using the EvictionEventCallback interface to evict any map entries. If it does use the EvictionEventcallback interface after this method is called, an IllegalStateException is thrown.

Specified by:

deactivate in interface Evictor

See Also:

Evictor.deactivate()