[infinispan-dev] Eviction in Infinispan

[Manik Surtani]

Hello all.

So as you know eviction changed pretty substantially from JBC3 but the  
overall design still remained the same.  I'm proposing a radical  
change to the design, which we briefly discussed in Neuchatel.

Here's a recap of what has changed already since JBC3:

1.  ExpirationAlgorithm and ElementSizeAlgorithm dropped,  
unnecessary.  Leaves us with {FIFO, LRU, MRU, LFU}
2.  Eviction queue design improved to O(1) for most operations on most  
algorithms, except LFU (O(log n))
3.  Expiration treated as a top-level construct where lifespans for  
entries can be provided on a per-entry basis
4.  Eviction watermarks are now exclusively size-based (numElements)  
and not time-based.
5.  MinTTL still supported.

Now here is how I want to change things further:

1.  Drop MRU and LFU.  I don't see MRU being useful except in very  
specific edge cases.  LRU somewhat useful but very expensive.
2.  Re-introduce a time-based watermark.  Brian, this is where your  
thoughts are most useful - how do you see this being used?  In  
passivation?
3.  Get rid of the eviction queues.  Unnecessary duplication of keys.   
The core datastructure can be refactoreed to provide an efficient,  
threadsafe lookup for entries, where entries are also ordered for  
eviction.
4.  To support 3. and make it as efficient as possible, eviction may  
only be an approximation.  (e.g., if items 1 - 10 are added in order,  
and 3 need to be removed based on FIFO, we may lose 7, 9 and 10  
instead of 8, 9 and 10.).  How much of a concern is this?  (typical  
tradeoff of accuracy vs efficiency)

Cheers
--
Manik Surtani
Lead, JBoss Cache
http://www.jbosscache.org
manik at jboss.org




-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/infinispan-dev/attachments/20090323/51541cea/attachment-0001.html