4 ms·

I would recommend W-TinyLFU [1]. It offers higher hit rates, is adaptive, has lower metadata overhead, is O(1), and is the only policy that is robust against al

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