The minimum-increment approach for a frequency sketch is supposed to help improve the sketch's accuracy. Instead of incrementing all of the hashed counters (e.g

The minimum-increment approach for a frequency sketch is supposed to help improve the sketch's accuracy. Instead of incrementing all of the hashed counters (e.g. 4), it first reads to find the minimum, and then only increments those. When analyzing for the purposes of TinyLFU this wasn't beneficial because it only cares about heavy hitters to judge relative worth so hit rate was unchanged. The two halves can be any algorithm, but LRU and SLRU were chosen in Caffeine. SLRU uses a probation and protected region (20/80 split) so that on a subsequent hit, the item is moved into the protected region. This more aggressively removes an item that was not used, e.g. inaccurately promoted by TinyLFU due to hash collisions. It is a cheap way to get a good recency/frequency eviction ordering. The frequency threshold is a direct comparison of the two victims (admission window's and the main region's). If the candidate has a higher estimated frequency than the main's victim then it is admitted, otherwise it is discarded. The admission window accepts all new items and is placed in front of TinyLFU. TinyLFU implements the doorkeeper, popularity sketch, and reset interval. When reset, the doorkeeper is cleared and the counters are halved. The optimal admission/main sizes depends on the workload. A LRU-biased workload prefers a large admission window (e.g. blockchain mining), while an MRU/LFU-biased one prefers a smaller window (e.g. loop/scans). The policy is adaptive by using hill climbing to [1] walk the hit rate curve towards the best configuration. The design evolution is described in [2-4]. There is no fast track promotion to the main region. A popular item will end up being promoted. The SLRU ordering and reset interval will age it out if unused. The adaptive sizing will grow or shrink the frequency region based on how effective it is. Cache admission has not been well studied. While TinyLFU is an admission policy, W-TinyLFU turns it into a promotion strategy by always admitting into the window cache. Prior to TinyLFU, bloom filters were used by CDNs to avoid one-hit wonders from polluting the cache [5]. Afterwards, AdaptSize [6] used entry sizes instead of frequency as an admission criteria. RL-Cache [7] tries to defer to ML to sort it out from a dozen signals. There is a paper under review that optimizes W-TinyLFU for entry size aware eviction. [1] https://dl.acm.org/doi/10.1145/3274808.3274816 https://dl.acm.org/doi/10.1145/3274808.3274816 [2] http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html http://highscalability.com/blog/2016/1/25/design-of-a-modern... [3] http://highscalability.com/blog/2019/2/25/design-of-a-modern-cachepart-deux.html http://highscalability.com/blog/2019/2/25/design-of-a-modern... [4] https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsUUBQfAJ2c2NsFPNPr2qymIBs https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsU... [5] https://people.cs.umass.edu/~ramesh/Site/HOME_files/CCRpaper.pdf https://people.cs.umass.edu/~ramesh/Site/HOME_files/CCRpaper... [6] https://www.usenix.org/conference/nsdi17/technical-sessions/presentation/berger https://www.usenix.org/conference/nsdi17/technical-sessions/... [7] https://ieeexplore.ieee.org/document/9109339 https://ieeexplore.ieee.org/document/9109339