[infinispan-dev] Eviction in Infinispan

[Manik Surtani]

FYI, I have detailed how this will look, etc on this wiki page:

	http://www.jboss.org/community/docs/DOC-13449


On 23 Mar 2009, at 20:18, Manik Surtani wrote:

> 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
>
>
>
>
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev

--
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/20090324/bb2cf8d8/attachment-0001.html