[infinispan-issues] [JBoss JIRA] Commented: (ISPN-1347) LIRS eviction not evicting correctly

[Vladimir Blagojevic (JIRA)]

    [ https://issues.jboss.org/browse/ISPN-1347?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12626373#comment-12626373 ] 

Vladimir Blagojevic commented on ISPN-1347:
-------------------------------------------

Jozef, thanks for the effort regarding this report. I have looked at the edg-functional-tests that you have written. LIRS and LRU work on a level of hash Segment and thus we can not expect 100% precision when it comes to BoundedConcurrentHashMap (BCHM) itself but rather a single Segment of a BCHM. LIRS and LRU eviction algorithms are also implementing amortization technique described in http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-09-1.pdf which might further dampen precision of small test sets. 

The LIRS test you have will most likely fail since it tried to assert 100% eviction precision of a BCHM on a set of a couple entries. I suggest you have a look at org.infinispan.stress.MapStressTest where we test overall precision of all eviction strategies. As expected LIRS is more precise than other strategies. 

Having said that I have reviewed thoroughly once again the main algorithm and I could not find problems you described. Yes, I found two minor LIRS problems. In method switchBottomostLIRtoHIRAndPrune when transitionLIRResidentToHIRResident is invoked on a LIR node currentLIRSize should be decremented. In handleHIRHit method when transitionToLIRResident is invoked on selected HashEntry currentLIRSize should be incremented.

Looking forward to your feedback!



> LIRS eviction not evicting correctly
> ------------------------------------
>
>                 Key: ISPN-1347
>                 URL: https://issues.jboss.org/browse/ISPN-1347
>             Project: Infinispan
>          Issue Type: Bug
>          Components: Eviction
>    Affects Versions: 5.0.0.FINAL
>            Reporter: Jozef Vilkolak
>            Assignee: Vladimir Blagojevic
>            Priority: Critical
>             Fix For: 5.1.0.ALPHA1, 5.1.0.FINAL
>
>
> It seems LIRS eviction at this moment only evicts the first entry in the HIR queue and nothing else. I have written a test based on [this presentation|https://docs.google.com/viewer?a=v&q=cache:jcEF5qSkCo4J:www.ece.eng.wayne.edu/~sjiang/Projects/LIRS/sig02.ppt+lirs+algorithm&hl=cs&gl=cz&pid=bl&srcid=ADGEESjKS6wTMJZZEGG8I6G7pOh-Va1lkLS4-JIFK-86NPAi-uKGOy2hHcQA3xoHmDcek6j7jd5pEUuj_iLwU_oUN6dlFqRH9CN2YkHD46hBzFJ2UbHBPECnelAvbWZ4soE1c-7xdu-g&sig=AHIEtbRMUTRpEWGssf3i4CMDJvnnpJEdFA] located in the eviction-strategy module of [edg-functional-tests|https://svn.devel.redhat.com/repos/jboss-qa/edg/edg-functional-tests/trunk/] that is at the moment failing. 
> Upon closer examination I have found a couple of things I think may be the cause:
> * in infinispan.util.concurrent.BoundedConcurrentHashMap
> ** in execute() of the LIRS eviction if you have more items in the accessQueue and while processing you choose an item to be evicted it is added to the evicted Set. But if it is still in the accessQueue(and the operation was put) it gets proccesed but in the end still ends up evicted because it was not removed from the evicted set.
> ** in onEntryMiss of the LIRS eviction the very first if shouldn't first increment currentLIRSize because otherwise LIRSize is never full and therefore the LIRS algorithm never truly happens because execute() is never called that's why it only evicts from the HIR queue. It also causes the cache to be able to hold only maxEntries-1 entries. Also if (queue.size() < hirSizeLimit) condition is true the item should also be added to the stack in order to track its recency. And lastly I don't think onEntryMiss should be evicting elements because that way we can't track their recency. They will get eventually evicted by pruning.
> ** the function onEntryRemove should not in my opinion remove entries from the stack because otherwise there is no way to track recency of HIR-nonresident blocks. They will eventually get removed from the stack by pruning. It also seems this function gets called when clearing the cache instead of clear.
> * in Segment class 
> ** the remove operation makes entries behave as if they were just added as is already documented there with a TODO
> ** the get operation calls onEntryHit which can cause problems if get is used while servicing a put operation because it gets called twice
> If some of these things were design choices let me know so I will modify the test.

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira