Bug 66524 - resource cache eviction is MRU not LRU
Summary: resource cache eviction is MRU not LRU
Status: RESOLVED FIXED
Alias: None
Product: Tomcat 9
Classification: Unclassified
Component: Catalina (show other bugs)
Version: 9.0.73
Hardware: PC Mac OS X 10.1
: P2 normal (vote)
Target Milestone: -----
Assignee: Tomcat Developers Mailing List
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2023-03-10 16:54 UTC by Steven Kearns
Modified: 2023-03-14 21:31 UTC (History)
0 users



Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Steven Kearns 2023-03-10 16:54:34 UTC
Cache.java evicts items using "MRU except we wont evict items last accessed
within 5s".

The comments indicate that LRU was intended.

The fix is simple, just remove the ".reverse()" from this line.

https://github.com/apache/tomcat/blob/main/java/org/apache/catalina/webresources/Cache.java#L211
Comment 1 Christopher Schultz 2023-03-11 17:18:04 UTC
Why reverse the reverse? What is being compared here? What do you think ought to be compared?
Comment 2 Steven Kearns 2023-03-11 21:38:12 UTC
The field CachedResource.nextCheck is what is being sorted, it is also a proxy for lastUsedTime.

since items will be evicted in iteration order, then sorting by "reverse nextCheck" makes the iteration order by descending nextCheck, or decreasing lastUsedTime, which means most recent to least recent.  That is MRU, not LRU.

Of course most resource caches should be LRU, not MRU, because an item is more likely to be accessed again if it has been accessed recently.  The hit ratio of the cache will be much improved when it iterates in the correct order.
Comment 3 Christopher Schultz 2023-03-13 18:23:28 UTC
(In reply to Steven Kearns from comment #2)
> The field CachedResource.nextCheck is what is being sorted, it is also a
> proxy for lastUsedTime.

Yup. I got the reversal reversed in my head when reading it as well.

We want to expire the lowest value for "nextCheck" because it is the same as the one with the oldest "lastCheck", and therefore the least-recently-used.

I agree with your analysis. I'd like a "second" from another committer before moving forward with the change.
Comment 4 Mark Thomas 2023-03-13 19:18:19 UTC
+1
Comment 5 Christopher Schultz 2023-03-14 21:31:43 UTC
Fixed in 85ba2ecd56e49e4e1d08a31ca86438010166821f (main) and 4823dc6f5095854c7236760cd859a44bdf4fd909 (8.5.x branch).

Will be in:
- 11.0.x for 11.0.0-M5 onwards
- 10.1.x for 10.1.8 onwards
-  9.0.x for  9.0.74 onwards
-  8.5.x for  8.5.88 onwards