BoundedConcurrentHashMap/Eviction Logic on GETs
shane_dev Jun 8, 2011 11:24 PMI've been looking at the eviction implementation in the BoundedConcurrentHashMap, and there are a few things that are disconcerting to me.
Capacity = 1000
Load Factory = .75
Max Batch Size = 64 (Static - It will almost always be the smaller value.)
BoundedConcurrentHashMap.put
if segment count + 1 > table length,
--> LRU.execute
move accessQueue entries to lruQueue
--> LRU.isOverflow
return true if lruQueue.size > 750 (1000 * .75)
if true, remove the entry from lruQueue and segment
clear accessQueue
The eviction strategy with respect to PUT commands seems to make sense. If we reach capacity, we evict entries until we get back to Capacity * Load Factor.
What I'm not so sure about is why eviction is executed from GET commands.
BoundedConcurrentHashMap.get
--> LRU.onEntryHit
add it to accessQueue
return true if accessQueue.size >= 48 (64 * .75)
if true,
--> BoundedConcurrentHashMap.attemptEviction
--> LRU.thresholdExpired (I know this is only if a lock has not yet been acquired.)
return true if accessQueue.size >= 64
if lock acquired
--> LRU.execute()
move accessQueue entries to lruQueue
--> LRU.isOverflow
return true if lruQueue.size > 750 (1000 * .75)
if true, remove the entry from lruQueue and segment
clear accessQueue
First, what is the purpose of calling LRU.thresholdExpired? All calls to attemptEviction go through onEntryHit and it already checks using Max Batch Size * Load Factor. It seems the logic at this point is all about onbtaining the lock and I don't see why we're checking the threshold (Max Batch Size) should play a role in obtaining the lock.
Second, why is eviction even initiated by a GET command? I don't mean the call to onEntryHit, but the call to attemptEviction.
Third, why should it happen every 48 GETs? It seems like we'll be in a constant state of eviction (once we reach Capacity * Load Factor + 1) assuming that we are doing at least 1 PUT per every 48 GETs.
Finally, I've looked at the code for the EvictionManagerImpl and the documentation, but to me it looks like it schedules expiration. It does not appear to actually perform eviction. Is this interpretation correct?
EvictionManagerImpl.processEviction -> DefaultDataContainer.purgeExpired
It might be that I'm not interpreting the code correctly so please feel free to correct me .