caffeine

I also ran an exhaustive analysis and had similar conclusion. I found that TinyLFU (mentioned in the article) matches or beats LIRS in database and search workloads. It is also much simpler to implement and is more memory efficient. https://github.com/ben-manes/caffeine/wiki/Efficiency The W-TinyLFU variant better handles recency by using an admission window so that new entries are not immediately discard. This resolves antirez's concern and improves performance in sparse burst workloads. In a way its similar to the HIR/LIR regions (window/main) using TinyLFU as a frequency filter. Happy to work with you, antirez, and others to simulate more policies and add trace files.

This is sometimes referred to as the "admission policy" of a cache and can have a large effect at increasing the hit ratio. Most policies try to minimize the impact of low frequency items. For example SLRU uses a small probation space that promotes to a protected region if re-accessed. This allows quickly discarding low frequent items. ARC uses an adaptive version of this idea. LIRS uses a very small region (HIR) that promotes to a large region (LIR) based in the inter-reference period. This allows it to discard many new arrivals by using a large number of ghosts to retain usage history. TinyLFU is a probabilistic LFU filter that decides whether to admit by comparing the frequency of the arrival to the victim. This is often near optimal, but can suffer due to sparse bursts causing consecutive misses. An admission window (W-TinyLFU) resolv

TinyLFU+FIFO is in the simulator (https://github.com/ben-manes/caffeine/wiki/Simulator). However, you'd probably also want the window cache to correct the deficiency outlined in the updated paper (http://arxiv.org/pdf/1512.00727.pdf). A FIFO version with that isn't in the simulator, but would be easy to add. mutli1 trace - W-TinyLFU: 55.6% - TinyLFU+Random: 53.8% - TinyLFU+FIFO: 48.6% - TinyLFU+LRU: 54.8% - FIFO: 41.0% - LRU: 46.7% FIFO's poor choice of a victim has a big impact, so it doesn't seem promising. A random policy looks like an attractive fit, though.

I believe the term youre looking for is "cache admission policy." This is an adjunct to cache eviction, both are needed for success. I'm very curious what a highly efficient insertion policy and trivial "eviction" policy (FIFO) would look like in practice. Cache insertion research is generally focused on use cases like small associative hardware caches. There's very little applicable public research for larger software caching systems, that Ive found. Probably the best would be Gil Einziger. He appears to have found it as an application of his work on extremely space/time efficient counting of sets, http://www.graduate.technion.ac.il/Theses/Abstracts.asp?Id=2... and http://www.cs.technion.ac.il/~gilga/. Of notable mention is TinyLFU http://www.cs.technion.ac.il/~gilga/TinyLFU_PDP2014.pdf. Gil submitted it to Caffeine (Java caching library