1 Reply Latest reply on Jan 24, 2005 1:17 PM by Ben Wang

    prune in LRUAlgorithm

    kkalmbach Newbie

      Question about the prune method in LRUAlgorithm. This is probably a small issue that will not actually affect anyone, but I'm looking for an opinion.

      I hope this explanation makes sense....

      Currently, the process method runs through the queue processing the gets/adds/deletes, then it runs through the items in the cache looking to see if it should evict them.

      There is a window of time (maybe large depending upon how many things are in the cache), that after the queue is drained and the first part of the cache is being pruned that a get comes in for something (at the end of the cache) that has been timed out (but not yet pruned) the get is successful (while the prune is still going on). The prune then gets to the end of the cache and evicts the newly gotten object (the newly gotten object placed a GET event in the queue, but the queue is not processed until the next time the eviction runs).

      The result of this is a get can be successful, but then immediately after, the get will fail. Since a get is supposed to reset the time, if a get is successful, it should not be removed until at least TimeToLive seconds after the last successful get.

      A couple of questions about this..
      1) If this really a problem, or is it just me? I think the saving grace of this is that the window is small unless the cache gets really big.
      2) Is there a simple fix for this? Can you drain the queue again during the prune method, before each eviction to make sure the object is still available for eviction?

      Because this is such a relatively small window of time, I can't make a reliable JUnit test (Unless I add a sleep the prune method to simulate a really large cache).


        • 1. Re: prune in LRUAlgorithm
          Ben Wang Master


          To re-phrase your question, yes, I think there is a use case when a GET is on-going and while evict is blocked. And when GET succeeds, evict will succeed as well in removing the same node. Next time GET will return a null.

          But keep in mind that with eviction policy, there is no quaranttee that a GET will always be successful anyway. You will always need to guard against null return value anyway. So I don't think this is a serious issue. What do you think?

          Finally, if CacheLoader is used, this is not an issue.