This paper proposes to use a frequency based cache admission policy in order to boost the effectiveness of caches subject to skewed access distributions. Given a newly accessed item and an eviction candidate from the cache, our scheme decides, based on the recent access history, whether it is worth admitting the new item into the cache at the expense of the eviction candidate. Realizing this concept is enabled through a novel approximate LFU structure called TinyLFU, which maintains an approximate representation of the access frequency of a large sample of recently accessed items. TinyLFU is very compact and light-weight as it builds upon Bloom filter theory. We study the properties of TinyLFU through simulations of both synthetic workloads as well as multiple real traces from several sources. These simulations demonstrate the performance boost obtained by enhancing various replacement policies with the TinyLFU eviction policy. Also, a new combined replacement and eviction policy scheme nicknamed W-TinyLFU is presented. W-TinyLFU is demonstrated to obtain equal or better hit-ratios than other state of the art replacement policies on these traces. It is the only scheme to obtain such good results on all traces.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
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…
Read the full comment
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) resolves this problem, usually with a 1% window.
I have a simulator and traces that you could easily add onto to experiment. [1]
I recommend reading the TinyLFU paper as I think it is the best match to your ideas. [2]
[1] https://github.com/ben-manes/caffeine
[2] http://arxiv.org/pdf/1512.00727.pdf
If you need the ability to remove entries, then I would consider the counting Bloom filter (which is simpler, but needs more space), and the cuckoo filter. But you do need to be a bit careful as both can overflow if you are unlucky, or if you add too many entries. In which case you would have to re-build them. So better be prepared for this case, or prevent overflowing the filters by using a cascade of filters.
Some clever cache implementations internally use special kinds of Bloom filters, e.g. the Caffeine cache (Java) uses TinyLFU, which "builds upon Bloom filter theory" (from the abstract of the paper): https://github.com/ben-manes/caffeine and https://arxiv.org/pdf/1512.00727.pdf
Maybe also consider tinylfu (https://arxiv.org/abs/1512.00727). I've implemented the windowed version with segmented caches and it works really well. Though it is a much more complicated implementation.
Thanks for writing this.
I'd love to hear your input on a possible application for this. I'm not sure if you're aware, but Counting Bloom Filters are useful as space efficient counters in LFU cache admission/eviction [1].
I'm wondering if bloom clocks would be a good data structure for a space efficient LRU admission/eviction. Full LRU uses a linked list and sampled LRU just uses random sampling, but my intuition is that bloom clocks might perform similarly or better than sampled LRU...
The difficult part will be dealing with concurrency. I suppose it'd be easy to treat threads as "nodes", but not all languages have the luxury of thread-local storage (Go), so I'll cross that bridge when I get there.
Anyways, I'm going to test it out later - thought you might be interested in my thoughts on a possible use.
[1]: https://arxiv.org/abs/1512.00727
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.
Abstract If future net-zero emissions energy systems rely heavily on solar and wind resources, spatial and temporal mismatches between resource availability and electricity demand may challenge system reliability.