[infinispan-dev] Eviction in Infinispan

[Brian Stansberry]

Manik Surtani wrote:
> 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.

Did you mean "LFU somewhat useful"? If so, yeah, agreed.

>> 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?

Theoretically it's important for passivation, but in practice I find it 
makes more sense to let the web/sfsb container decide what gets 
passivated. So don't let AS passivation drive this.

For entity caching, supporting maxAge is very important as that allows 
guaranteed flushing of stale data from the cache; important in use cases 
where other systems may update the DB making the cache invalid, but the 
application is willing to accept that for a certain period.

Eviction based on time-since-last-access I think is more of a 
convenience. It helps shield users from needing to think about # of 
nodes; they can just reason "if this data hasn't been used in 5 minutes, 
I don't need it." A nice heuristic.

With the flat structure the problem of reasoning about number of nodes 
is a bit less, since structural nodes are gone.

My gut feeling on this is that eviction based on time-since-last-access 
is not strictly necessary but if you take it away you'll get lots of 
grumbling.

>> 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)

I think that is fine. Not a regression as I don't think JBC eviction has 
ever claimed to be super-accurate. It takes a snapshot based on events 
queued up to a particular point in time and then evicts; the underlying 
data could have changed in the meantime.

>>
>> Cheers
>> --
>> Manik Surtani
>> Lead, JBoss Cache
>> http://www.jbosscache.org
>> manik at jboss.org <mailto:manik at jboss.org>
>>
>>
>>
>>
>> _______________________________________________
>> infinispan-dev mailing list
>> infinispan-dev at lists.jboss.org <mailto: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 <mailto:manik at jboss.org>
> 
> 
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev


-- 
Brian Stansberry
Lead, AS Clustering
JBoss, a division of Red Hat
brian.stansberry at redhat.com