net.sf.ehcache.store
Class LfuMemoryStore

java.lang.Object
  net.sf.ehcache.store.MemoryStore
      net.sf.ehcache.store.LfuMemoryStore

All Implemented Interfaces:

Store

public class LfuMemoryStore
extends MemoryStore

Less Frequently Used (LFU) implementation of the memory store. Actually keeping track of the least used, then the second least and so on is very expensive, 3 or 4 orders of magnitude more expensive than the others policies. Costs are incurred on put, get and remove.

Instead this implementation does not quarantee that the element removed will actually be the least used. Rather, it lets you make statements about confidence intervals against the likelihood that an element is in some lowest percentile of the hit count distribution. Costs are only incurred on overflow when an element to be evicted must be selected.

For those with a statistical background the branch of stats which deals with this is hypothesis testing and the Student's T distribution. The higher your sample the greater confidence you can have in a hypothesis, in this case whether or not the "lowest" value lies in the bottom half or quarter of the distribution. Adding samples rapidly increases confidence but the return from extra sampling rapidly diminishes.

Cost is not affected much by sample size, indicating it is probably the iteration that is causing most of the time. If we had access to the array backing Map, all would work very fast.

A 99.99% confidence interval can be achieved that the "lowest" element is actually in the bottom quarter of the hit count distribution with a sample size of 30, which is the default.

Version:

$Id: LfuMemoryStore.java 537 2007-08-14 23:52:19Z gregluck $

Author:

Greg Luck

Field Summary

Fields inherited from class net.sf.ehcache.store.MemoryStore

cache, diskStore, map, status

Constructor Summary

protected

LfuMemoryStore(Ehcache cache, Store diskStore) Constructor for the LfuMemoryStore object.

Method Summary

void	doPut(Element elementJustAdded) Puts an element into the cache.
(package private) Element	findRelativelyUnused(Element elementJustAdded) Find a "relatively" unused element, but not the element just added.
(package private) LfuPolicy.Metadata[]	sampleElements(int size) Uses random numbers to sample the entire map.

Methods inherited from class net.sf.ehcache.store.MemoryStore

backedUp, clear, containsKey, create, dispose, evict, expireElements, flush, get, getBackingMap, getKeyArray, getQuiet, getSize, getSizeInBytes, getStatus, isFull, notifyExpiry, put, remove, removeAll, spoolAllToDisk, spoolToDisk

Methods inherited from class java.lang.Object

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

Constructor Detail

LfuMemoryStore

protected LfuMemoryStore(Ehcache cache,
                         Store diskStore)

Constructor for the LfuMemoryStore object.

Method Detail

doPut

public final void doPut(Element elementJustAdded)

Puts an element into the cache.

Overrides:

doPut in class MemoryStore

findRelativelyUnused

final Element findRelativelyUnused(Element elementJustAdded)

Find a "relatively" unused element, but not the element just added.

sampleElements

LfuPolicy.Metadata[] sampleElements(int size)

Uses random numbers to sample the entire map.

Returns:

an array of sampled elements