4 ms·

Window-TinyLFU seems cool. Here's a blog post going through it at a level I mostly understand: https://9vx.org/post/on-window-tinylfu/ https://9vx.org/post/on-

by twic 6y ago

Window-TinyLFU seems cool. Here's a blog post going through it at a level I mostly understand: https://9vx.org/post/on-window-tinylfu/ https://9vx.org/post/on-window-tinylfu/ The core trick is to use some kind of Bloom-filter-style structure to keep approximate counts of accesses. Caffeine uses a count-min sketch, but you could also use a counting Bloom filter, and these are really just two members of a family of very similar things. The counts are occasionally halved, so they are really a sort of decaying average, allowing for changes in access pattern over time. There's a minor trick of using a simple Bloom filter (the post says "single-bit minimum-increment counting Bloom filter", but that is just a Bloom filter, isn't it?) as a 'doorkeeper', so you don't bother tracking frequency for objects until they are accessed for a second time. This helps if you have a long tail of objects which are only accessed once, because it means the main frequency counter can focus on a small subset of objects, and so be more accurate. The actual cache is split into two parts. New objects are added to the first part, which is managed by simple LRU. When objects are evicted from the LRU queue, their access frequency is examined, and if it is high enough, the object is added to the second part. The use of frequency like this is called a cache admission policy. There are a lot of details I don't understand. Mostly to do with how a cache admission policy is used in a two-part cache, rather than anything to do with Window-TinyLFU. How is the second part of the cache managed? LRU? Or do you evict the object with the lowest frequency? What is the frequency threshold for adding something to the second part? Are objects added to the first part if they have only just been added to the doorkeeper? Or only if they were already known to the doorkeeper? Does the doorkeeper also get reset occasionally? What are the relative sizes of the first and second parts? Do they change? Is an object ever added directly to the second part? You might have an object with high historical frequency, but which has been evicted because it wasn't used recently. I couldn't find a good general overview of cache admission policies.

donavanm 6y ago
There's some really good explanation (and implementation) in the Caffeine library[1]. Ben Manes worked with Gil Einziger on the implementation and actually contributed to an updated version of the TinyLFU paper, IIRC. Gil has a ton of very relevant work[2][3] around cache admission, control, and information density. Unfortunately cache admission is an understudied and woefully unimplemented area of CS & computer engineering as far as I can tell. There's some decent work around hardware layer problems, cache line insertion/eviction/etc, but not much in general purpose software caching. Gils research was definitely the most relevant and relatable when I was involved in this area a few years back. [1] https://github.com/ben-manes/caffeine/wiki/Efficiency#window-tinylfu https://github.com/ben-manes/caffeine/wiki/Efficiency#window... [2] https://scholar.google.com/citations?user=kWivlnsAAAAJ&hl=en https://scholar.google.com/citations?user=kWivlnsAAAAJ&hl=en [3] https://github.com/gilga1983 https://github.com/gilga1983
jandrewrogers 6y ago
Understanding that caching is a universal sequence prediction problem explains a lot, where efficiency maps to the abstract "compressibility" of the access sequence from the cache's perspective. Optimal sequence prediction is intractable, so any practical cache optimizes for good performance predicting some sequences to the exclusion of others. An understudied approach to cache efficiency is to dynamically shape the sequence of accesses the cache sees to better match the set of sequences it is designed to predict. This means putting some code/logic in front of the cache to make the sequences more cache friendly, either by filtering out "noise" accesses that are likely to pollute the sequence prediction model or re-ordering accesses, when permissible, to look like a sequence the cache is better at predicting. The objective is that the added overhead of cache admission is offset by improved efficiency of cache eviction by making the sequences more predictable. Both types of cache admission policies -- noise filtering and sequence reshaping -- are commonly used in database engines in extremely limited ways. An example of the former are so-called "cold scan" optimizations. An example of the latter are so-called "synchronized scan" optimizations, which have minimal benefit in many architectures. Cache admission is an open-ended algorithm problem with complex tradeoffs. Sequence reshaping is particularly interesting, and almost completely unstudied, because in theory it allows you to exceed the efficiency of Bélády's optimal algorithm since one of the limiting assumptions of that theorem are not always true in real systems. It is not trivial to design systems that can employ these kinds of optimizations broadly in a way that provides a net benefit. Of course, in real systems, cache efficiency is about more than cache hit rate. Both cache admission and cache eviction also need to be CPU efficient, and most academic algorithms are not. Even though cache access/management is in the hot path, you want it to be invisible in the profiler.
- donavanm 6y ago
  Check out some of the papers from Coho Data and alums. When I was looking circa 2014-16 they had some really interesting takes on tracking access (inter reference gap) across huge object populations. They were positioning it towards tiered storage migrations but it seemed generally applicable to admission control & eviction beyond normal working sets.
NovaX 6y ago
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

by twic 6y ago

donavanm 6y ago

There's some really good explanation (and implementation) in the Caffeine library[1]. Ben Manes worked with Gil Einziger on the implementation and actually contributed to an updated version of the TinyLFU paper, IIRC. Gil has a ton of very relevant work[2][3] around cache admission, control, and information density. Unfortunately cache admission is an understudied and woefully unimplemented area of CS & computer engineering as far as I can tell. There's some decent work around hardware layer problems, cache line insertion/eviction/etc, but not much in general purpose software caching. Gils research was definitely the most relevant and relatable when I was involved in this area a few years back. [1] https://github.com/ben-manes/caffeine/wiki/Efficiency#window-tinylfu https://github.com/ben-manes/caffeine/wiki/Efficiency#window... [2] https://scholar.google.com/citations?user=kWivlnsAAAAJ&hl=en https://scholar.google.com/citations?user=kWivlnsAAAAJ&hl=en [3] https://github.com/gilga1983 https://github.com/gilga1983

jandrewrogers 6y ago

Understanding that caching is a universal sequence prediction problem explains a lot, where efficiency maps to the abstract "compressibility" of the access sequence from the cache's perspective. Optimal sequence prediction is intractable, so any practical cache optimizes for good performance predicting some sequences to the exclusion of others. An understudied approach to cache efficiency is to dynamically shape the sequence of accesses the cache sees to better match the set of sequences it is designed to predict. This means putting some code/logic in front of the cache to make the sequences more cache friendly, either by filtering out "noise" accesses that are likely to pollute the sequence prediction model or re-ordering accesses, when permissible, to look like a sequence the cache is better at predicting. The objective is that the added overhead of cache admission is offset by improved efficiency of cache eviction by making the sequences more predictable. Both types of cache admission policies -- noise filtering and sequence reshaping -- are commonly used in database engines in extremely limited ways. An example of the former are so-called "cold scan" optimizations. An example of the latter are so-called "synchronized scan" optimizations, which have minimal benefit in many architectures. Cache admission is an open-ended algorithm problem with complex tradeoffs. Sequence reshaping is particularly interesting, and almost completely unstudied, because in theory it allows you to exceed the efficiency of Bélády's optimal algorithm since one of the limiting assumptions of that theorem are not always true in real systems. It is not trivial to design systems that can employ these kinds of optimizations broadly in a way that provides a net benefit. Of course, in real systems, cache efficiency is about more than cache hit rate. Both cache admission and cache eviction also need to be CPU efficient, and most academic algorithms are not. Even though cache access/management is in the hot path, you want it to be invisible in the profiler.

donavanm 6y ago
Check out some of the papers from Coho Data and alums. When I was looking circa 2014-16 they had some really interesting takes on tracking access (inter reference gap) across huge object populations. They were positioning it towards tiered storage migrations but it seemed generally applicable to admission control & eviction beyond normal working sets.

NovaX 6y ago

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