[Feature request] Expire after access LRU

[rasmuskl]

It would be great to be able to use "expire after access" in addition to the already implemented "expire after write" found in ConcurrentTlru.

My use case is resource optimization of unloading unused values, not cache duration which is what I have used the "expire after write" implementation for recently. If I use the "expire after write" implementation I end up running the same expensive loading code more often.

I could use the plain LRU but then I am always keeping close to capacity in memory which is results in high resource use.

Caffeine provides expireAfterAccess for the same scenarios: https://github.com/ben-manes/caffeine/wiki/Eviction#time-based

[bitfaster]

Thanks Rasmus, this is a great suggestion and something I plan to add - hopefully in the next 2 or 3 months.

The difference between plain LRU and "expire after access" is eager eviction - instead of waiting for the cache to be full, eagerly evict items that have not been accessed recently - makes sense, for you this can reduce memory consumption by eliminating stale items. Right now your best option is to tune the cache size so you get a good balance of maximizing cache hits without using too much memory.

Under the covers ConcurrentLru will only be able to evict items as they are cycled between the hot/warm/cold queues (since cache maintenance is amortized across cache misses, and only a handful of items are examined per miss - you can read about the algorithm here). So in practice, there may be little difference between LRU and LRU + expire after access due to the internal implementation - for example if the cache is large and the number of misses is low, it will take some time to fully cycle each queue and the stale items can linger in the cache. This is why I hadn't prioritized adding this policy.

I'm working to replicate Caffeine's LFU algorithm in ConcurrentLfu (thanks to Ben). I have started work on time-based expiry, but I don't have it production ready yet. Since ConcurrentLfu performs maintenance in the background after every read/write, it will result in faster acting eviction - so LFU may be the best fit for your scenario.

I plan to keep both algorithms, since ConcurrentLru is lighter weight and a little faster for simple scenarios dominated by repeated hot path cache hits, whereas ConcurrentLfu has slightly better hit rate and can be extended with richer policies.

[rasmuskl]

Thanks for the detailed response - that makes sense. I suspected as much thinking about the problem myself after reading the wiki on implementation details.

For what it is worth, as I am optimizing for resource utilization over time without wanting to tweak the LRU capacity up and down, my requirement on expire after access is not that items are removed exactly at that time. Rather, I want to just get rid of them over time as they are not used to save capacity. So even cycling some out on write based on an access expiry threshold instead of a write expiry threshold would be adequate for my problem.

I can understand why you want the more general solution though, since that is probably what people will expect from the name of the data structure and the policy.

I ended up doing a quick workaround using a ConcurrentLru holding key and item and a ConcurrentDictionary that stores key + last access time. Periodically I will iterate through the access time dictionary and purge any items over the access threshold. Note that my use case is low write frequency and high read frequency, but each item is pretty memory intensive to keep around. So this works for me for now at least until I can replace with a new shiny LRU from this project.

[bitfaster]

Expire after access is now available in v2.4.0.

[ben-manes]

neat! It looks like you piggy back on the queue cycling, which sounds like a good approach. I used a timing wheel which has a small memory penalty for a few design benefits, though perhaps it was mostly for the fun of writing that data structure.

[rasmuskl]

Beautiful. Thanks!