HackerPapers

arXiv:1512.00727cs.OS

TinyLFU: A Highly Efficient Cache Admission Policy

Gil Einziger, Roy Friedman, Ben Manes

Abstract

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.

arXiv comments
A much earlier and shorter version of this work appeared in the Euromicro PDP 2014 conference
Journal reference
DOI
Subjects
cs.OSOperating Systems

On Hacker News

Linked by 4 identifiable commenters in 5 comments across 5 threads, from Jan 2016 to Aug 2021. Found in 2 HN submissions from May 2018 to Oct 2022. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. Bloom Filters: More than a space-efficient hashmap 1 comment

    • 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…

      thomasmgView on HNParent context

  2. Constant Time LFU 1 comment

    • 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.

      T0pH4tView on HNParent context

  3. The Bloom Clock 1 comment

    • 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…

      karlmcguireView on HNParent context

  4. Ask HN: Cache Hit Ratio 1 comment

    • 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…

      NovaXView on HNParent context

  5. Apache Traffic Server 1 comment

    • 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…

      NovaXView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.