why use Window MRU position firstly?

[StephenRi]

I am reading the w-tinylfu algorithm implement of caffeine. I wonder why candidate = accessOrderWindowDeque.peekLast instead of peekFirst when cadidates == 0 in the evictFromMain method?
I don't understand why use MRU position instead of LRU position firstly.

void evictFromMain(int candidates) {
    while(weightedSize() > maximum()) {
        if (candidates == 0) {
            candidate = accessOrderWindowDeque().peekLast();    // why peekLast?
        }
    }
}

[ben-manes]

This occurs for weighted caches when a large entry causes many evictions. I don’t recall if this is intentional or accidentally flipped. You can look at the commit for an explanation and suggest changes if you think that there is a mistake.

464bc19

[ben-manes]

I ran a few weighted traces on the two versions to check for regressions.

Tencent Photo trace (50M - 50B)

This ranges from a 6% - 28% hit rate and is negatively impacted by up to 0.3%.

IBM Object Store (50M - 50B)

This ranges from a 40% - 95% hit rate and is negatively impacted by up to 2%.

MSR Cambridge - Project (50M - 500B)

This ranges from a 8% - 35% hit rate and is positively impacted by up to 4%.

Discussion

My experience is that anything within 5% is noise due to workloads differing so widely which makes it hard to draw a conclusion what is better or worse. Unfortunately, we don't have a enough weighted traces to draw a deeper analysis except that the changes appear to be within a tolerance and don't show a harmful regression. A more substantial algorithmic improvement that could improve the hit rates will come if we implement the optimizations in this paper.

I think the improved clarity and the lack of a substantial difference to the hit rate makes the suggested changes worthwhile.

[chiragpujara]

Just ran into this issue during testing. Newly added entries are getting evicted in favor existing entries even though they both have same weight. IS there a timeframe when this fix will be available/released?

[ben-manes]

Can you try using the SNAPSHOT build in your test to see if it resolves your problem?

[chiragpujara]

I just tried 3.1.2-SNAPSHOT. IT has different problem or fails on different use-case. If most recent entry has highest weight than it still removes most recent entry.

[ben-manes]

The cache is not LRU. It will sample the workload and reconfigure itself over time. If you can provide an access trace we can run it through the simulator to see the overall hit rate, which is what we are trying to optimize for. In many workloads the most recent is a one-hit wonder (aka cache pollution) so we favor keeping older, more frequently used entries.