net.sf.ehcache.store

Class LfuMemoryStore

public final 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 171 2006-08-12 22:39:48Z gregluck $

Author: Greg Luck

Constructor Summary
protected LfuMemoryStore(Ehcache cache, DiskStore diskStore)
Constructor for the LfuMemoryStore object.
Method Summary
voiddoPut(Element elementJustAdded)
Puts an element into the cache.
ElementfindRelativelyUnused(Element elementJustAdded)
Find a "relatively" unused element, but not the element just added.
Element[]sampleElements(int sampleSize)
Uses random numbers to sample the entire map.

Constructor Detail

LfuMemoryStore

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

Method Detail

doPut

public final void doPut(Element elementJustAdded)
Puts an element into the cache.

findRelativelyUnused

final Element findRelativelyUnused(Element elementJustAdded)
Find a "relatively" unused element, but not the element just added.

sampleElements

final Element[] sampleElements(int sampleSize)
Uses random numbers to sample the entire map.

Parameters: sampleSize how many samples to take

Returns: an array of sampled elements