[Bug] Cold queue increases infinitely for some partitions and cache sizes

[rafal-mz]

For some specific capacity partitions and cache sizes cold qeuue becomes unbounded an increases infinitely.

It can be observed by test WhenKeysAreContinuouslyRequestedInTheOrderTheyAreAddedCountIsBounded with WarmFavourPartition with Warm ratio 0.6 and cache sizes 64, 128. Its for ConcurrentLru implementation.

The fix is not to allow to cycle back from cold queue to warm if warm is full.

[bitfaster]

Thanks for reporting this and giving a repro! I suspect your fix is correct and I made a mistake here when I changed to use Interlocked/Volatile.Read a while back. I had thought the test you mentioned would detect this, will take a look at that as well - probably the test doesn't run with both partition schemes.

[bitfaster]

I pushed a fix for this, but it's still not correct so I will rewrite the cycle logic. If we prevent cycling back to warm as you suggested, hit rate is reduced for some scenarios. The intent is that after some number of attempts, if we are over size the coldest item (last item in cold queue) is dropped to stay at capacity.

[bitfaster]

Now fixed to correctly remove the coldest item after 5 attempts, constraining size within capacity.