TinyLFU caching policy

[ben-manes]

Congrats on the paper. If possible, I would enjoy reading it (ben.manes @ gmail).

I spent a lot of time evaluating eviction policies, and settled on TinyLFU with some minor improvements. While ARC is better than LRU and other classic policies, it does not retain its history robustly enough. LIRS is often overlooked because of its complexity and poorly described algorithm, but it is a very solid performer. TinyLFU matches or exceeds LIRS in many workloads, but is dramatically simpler and more efficient.

LIRS, ARC, and other modern policies rely on ghost entries in LRU lists. TinyLFU instead stores the history in a compact sketch to estimate the frequency. This is used as an admission filter to reject unpopular candidates entries, which would otherwise pollute the cache. By comparing the likelihood of reuse of the candidate and the eviction policy's victim, the cache can achieve good hit hit rates in a very cheap and straightforward manner.

I have a Java simulator that you could crib from. I'd like to learn more about your work since there is always an new angle of attack to further improve performance.

https://github.com/ben-manes/caffeine
(See links to paper and HighScability article for details).

Cheers,
Ben