org.gridgain.grid.cache.eviction.lirs
Class GridCacheLirsEvictionPolicy<K,V>

java.lang.Object
  org.gridgain.grid.cache.eviction.lirs.GridCacheLirsEvictionPolicy<K,V>

All Implemented Interfaces:

GridCacheEvictionPolicy<K,V>, GridCacheLirsEvictionPolicyMBean

public class GridCacheLirsEvictionPolicy<K,V>
extends Object
implements GridCacheEvictionPolicy<K,V>, GridCacheLirsEvictionPolicyMBean

Very efficient implementation of LIRS cache eviction policy which often provides better hit ratio than the LRU eviction policy. It in particular offers much better performance for access patterns with weak locality, such as regular access over more entries than the cache size. Instead of standard LRU eviction based on access order, LIRS maintains a main LRU stack, called LIRS Stack, as primary Low Inter-reference Recency stack, and a secondary queue, called HIRS Queue) for High Inter-Reference recency entries.

Note that this implementation is extremely efficient as it is essentially lock-contention-free and does not create any additional table-like data structures. For more information see Low Inter-Reference Recency Set (LIRS) algorithm by Sone Jiang and Xiaodong Zhang.

Wiki & Forum:

Wiki
Forum

Field Summary

static float

DFLT_QUEUE_SIZE_RATIO Default ratio of HIRS (High Inter-reference Recency Set).

Constructor Summary

GridCacheLirsEvictionPolicy()
Constructs LIRS eviction policy with all defaults.

GridCacheLirsEvictionPolicy(int max)
Constructs LIRS eviction policy with maximum size.

GridCacheLirsEvictionPolicy(int max, boolean allowEmptyEntries)
Constructs LIRS eviction policy with maximum size and specified allow empty entries flag.

GridCacheLirsEvictionPolicy(int max, float queueRatio)
Constructs LIRS eviction policy with maximum size and secondary queue ratio to compute size of secondary queue.

GridCacheLirsEvictionPolicy(int max, float queueRatio, boolean allowEmptyEntries)
Constructs LIRS eviction policy with maximum size and secondary queue ratio to compute size of secondary queue.

Method Summary

int	getCurrentQueueSize() Gets current HIRS queue size.
int	getCurrentStackSize() Gets current main stack size.
int	getMaxQueueSize() Gets maximum allowed size of HIRS queue before entries will start getting evicted.
int	getMaxSize() Gets maximum allowed cache size.
int	getMaxStackSize() Gets maximum allowed size of main stack This value is computed based on GridCacheLirsEvictionPolicyMBean.getQueueSizeRatio() value.
String	getMetaAttributeName() Gets name of metadata attribute used to store eviction policy data.
double	getQueueSizeRatio() Gets ratio for HIRS queue size relative to main stack size.
boolean	isAllowEmptyEntries() Gets flag indicating whether empty entries (entries with null values) are allowed.
void	onEntryAccessed(boolean rmv, GridCacheEntry<K,V> entry) Callback for whenever entry is accessed.
Collection<GridCacheEntry<K,V>>	queue() Gets read-only view on secondary HIR queue to hold High Inter-reference Recency entries.
void	setAllowEmptyEntries(boolean allowEmptyEntries) Sets flag that allows empty entries (entries with null values) to be stored in cache.
void	setMaxSize(int max) Sets maximum allowed size of cached entries.
void	setQueueSizeRatio(double queueRatio) Sets ratio of HIRS queue size compared to main stack size.
Collection<GridCacheEntry<K,V>>	stack() Gets read-only view on main internal stack for LIRS implementation.
String	toFullString() Gets string representation of all queue and stack contents.
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

DFLT_QUEUE_SIZE_RATIO

public static final float DFLT_QUEUE_SIZE_RATIO

Default ratio of HIRS (High Inter-reference Recency Set). Default value is 0.02, which means that HIRS set size is 2% of LIRS set size.

See Also:

Constant Field Values

Constructor Detail

GridCacheLirsEvictionPolicy

public GridCacheLirsEvictionPolicy()

Constructs LIRS eviction policy with all defaults.

GridCacheLirsEvictionPolicy

public GridCacheLirsEvictionPolicy(int max)

Constructs LIRS eviction policy with maximum size.

Parameters:

max - Maximum allowed size of entries in cache.

GridCacheLirsEvictionPolicy

public GridCacheLirsEvictionPolicy(int max,
                                   boolean allowEmptyEntries)

Constructs LIRS eviction policy with maximum size and specified allow empty entries flag.

Parameters:

max - Maximum allowed size of entries in cache.

allowEmptyEntries - If false, empty entries will be evicted immediately.

GridCacheLirsEvictionPolicy

public GridCacheLirsEvictionPolicy(int max,
                                   float queueRatio)

Constructs LIRS eviction policy with maximum size and secondary queue ratio to compute size of secondary queue.

Parameters:

max - Maximum allowed size of entries in cache.

queueRatio - Ratio of HIRS queue size compared to maximum allowed size.

GridCacheLirsEvictionPolicy

public GridCacheLirsEvictionPolicy(int max,
                                   float queueRatio,
                                   boolean allowEmptyEntries)

Constructs LIRS eviction policy with maximum size and secondary queue ratio to compute size of secondary queue.

Parameters:

max - Maximum allowed size of entries in cache.

queueRatio - Ratio of HIRS queue size compared to maximum allowed size.

allowEmptyEntries - If false, empty entries will be evicted immediately.

Method Detail

getMaxSize

public int getMaxSize()

Gets maximum allowed cache size.

Specified by:

getMaxSize in interface GridCacheLirsEvictionPolicyMBean

Returns:

Maximum allowed cache size.

setMaxSize

public void setMaxSize(int max)

Sets maximum allowed size of cached entries.

Specified by:

setMaxSize in interface GridCacheLirsEvictionPolicyMBean

Parameters:

max - Maximum allowed size of cached entries.

isAllowEmptyEntries

public boolean isAllowEmptyEntries()

Gets flag indicating whether empty entries (entries with null values) are allowed.

Specified by:

isAllowEmptyEntries in interface GridCacheLirsEvictionPolicyMBean

Returns:

True if empty entries are allowed, false otherwise.

setAllowEmptyEntries

public void setAllowEmptyEntries(boolean allowEmptyEntries)

Sets flag that allows empty entries (entries with null values) to be stored in cache.

Specified by:

setAllowEmptyEntries in interface GridCacheLirsEvictionPolicyMBean

Parameters:

allowEmptyEntries - If false, empty entries will be evicted immediately.

getQueueSizeRatio

public double getQueueSizeRatio()

Gets ratio for HIRS queue size relative to main stack size.

Specified by:

getQueueSizeRatio in interface GridCacheLirsEvictionPolicyMBean

Returns:

Ratio for HIRS queue size relative to main stack size.

getMetaAttributeName

public String getMetaAttributeName()

Gets name of metadata attribute used to store eviction policy data.

Specified by:

getMetaAttributeName in interface GridCacheLirsEvictionPolicyMBean

Returns:

Name of metadata attribute used to store eviction policy data.

setQueueSizeRatio

public void setQueueSizeRatio(double queueRatio)

Sets ratio of HIRS queue size compared to main stack size. Generally HIRS size should be much smaller than main stack size. The default value is 0.02 defined by GridCacheLirsEvictionPolicy.DFLT_QUEUE_SIZE_RATIO constant.

Parameters:

queueRatio - Ratio of HIRS set size compared to main stack size.

getMaxQueueSize

public int getMaxQueueSize()

Gets maximum allowed size of HIRS queue before entries will start getting evicted. This value is computed based on GridCacheLirsEvictionPolicyMBean.getQueueSizeRatio() value.

Specified by:

getMaxQueueSize in interface GridCacheLirsEvictionPolicyMBean

Returns:

Maximum allowed size of HIRS queue before entries will start getting evicted.

getMaxStackSize

public int getMaxStackSize()

Gets maximum allowed size of main stack This value is computed based on GridCacheLirsEvictionPolicyMBean.getQueueSizeRatio() value.

Specified by:

getMaxStackSize in interface GridCacheLirsEvictionPolicyMBean

Returns:

Maximum allowed size of main stack.

getCurrentStackSize

public int getCurrentStackSize()

Description copied from interface: GridCacheLirsEvictionPolicyMBean

Gets current main stack size.

Specified by:

getCurrentStackSize in interface GridCacheLirsEvictionPolicyMBean

Returns:

Current main stack size.

getCurrentQueueSize

public int getCurrentQueueSize()

Description copied from interface: GridCacheLirsEvictionPolicyMBean

Gets current HIRS queue size.

Specified by:

getCurrentQueueSize in interface GridCacheLirsEvictionPolicyMBean

Returns:

Current HIRS set size.

stack

public Collection<GridCacheEntry<K,V>> stack()

Gets read-only view on main internal stack for LIRS implementation.

Returns:

Read-only view on Main internal stack for LIRS implementation.

queue

public Collection<GridCacheEntry<K,V>> queue()

Gets read-only view on secondary HIR queue to hold High Inter-reference Recency entries.

Returns:

Secondary read-only view on HIR queue.

onEntryAccessed

public void onEntryAccessed(boolean rmv,
                            GridCacheEntry<K,V> entry)

Callback for whenever entry is accessed.

Specified by:

onEntryAccessed in interface GridCacheEvictionPolicy<K,V>

Parameters:

rmv - True if entry has been removed, false otherwise.

entry - Accessed entry.

toFullString

public String toFullString()

Gets string representation of all queue and stack contents.

Returns:

String representation of all queue and stack contents.

toString

public String toString()

Overrides:

toString in class Object