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