Multigenerational LRU: more performant, versatile, straightforward than Linux's
lore.kernel.org
lore.kernel.org
That implements a custom algorithm, Double Clock, which is inspired by LIRS. This patch touches related code, but not that file where the core algorithm is described. I tried to reimplement it in a simulator for analysis and found its hit rate varied significantly on workloads due to the percent given to LRU/LFU regions being based on machine's total memory capacity [2]. That caused it to do better in MRU/LFU workloads on high memory systems and better at LRU workloads on low-memory systems [3]. Talking to the author and there were other details not documented that might make those regions adaptive. In the end, I gave up trying to understand the page cache and if there was a benefit of switching to an alternative eviction policy. It is well written but very confusing code that seems scattered if not a kernel developer.
[1] https://github.com/torvalds/linux/blob/master/mm/workingset....
[2] https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42...
[3] https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZe...
You can compare the code of ARC [1], LIRS [2], and DClock [3] to see how similar they are.
ARC obtained a lot of awareness but the hit rate is not that great. It is modestly better than LRU, but very wasteful in metadata overhead. LIRS is much better, except it is complex and the paper is confusing so almost all implementations are broken. DClock seems okayish by borrowing LIRS' ideas, but I think it performs worse in most comparisons.
[1] https://github.com/ben-manes/caffeine/blob/master/simulator/...
[2] https://github.com/ben-manes/caffeine/blob/master/simulator/...
[3] https://github.com/ben-manes/caffeine/blob/master/simulator/...
I met Kirk McKusick (BSD fame) at Fast'20 where he expressed interest in that for ZFS. We tried introducing the idea to the contributors at FreeBSD, Delphix, and LLNL. There is frustration at ARC being memory hungry and the locking is expensive. Unfortunately while there is interest in replacing ARC, all of our contacts were too busy to explore that option.
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.
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... [2] https://scholar.google.com/citations?user=kWivlnsAAAAJ&hl=en [3] https://github.com/gilga1983
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.
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
[2] http://highscalability.com/blog/2016/1/25/design-of-a-modern...
[3] http://highscalability.com/blog/2019/2/25/design-of-a-modern...
[4] https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsU...
[5] https://people.cs.umass.edu/~ramesh/Site/HOME_files/CCRpaper...
[6] https://www.usenix.org/conference/nsdi17/technical-sessions/...
Profiling a warehouse-scale computer https://research.google/pubs/pub44271/
Google-Wide Profiling: A Continuous Profiling Infrastructure for Data Centers https://research.google/pubs/pub36575/
AutoFDO: Automatic Feedback-Directed Optimization for Warehouse-Scale Applications https://research.google/pubs/pub45290/
> Over the past decade of research and experimentation in memory overcommit, we observed a distinct trend across millions of servers and clients: the size of page cache has been decreasing because of the growing popularity of cloud storage. Nowadays anon pages account for more than 90% of our memory consumption and page cache contains mostly executable pages.
On Android, our most advanced simulation that generates memory pressure from realistic user behavior shows 18% fewer low-memory kills, which in turn reduces cold starts by 16%.
...
On Chrome OS, our field telemetry reports 96% fewer low-memory tab discards and 59% fewer OOM kills from fully-utilized devices and no UX regressions from underutilized devices.
Additionally, TFA has massive impressively statistics for client-side devices, as a cousin comment notes.
But I maintain it needs more independant testing, on good-old-not-cloud-server, especially databases (which are not client-side devices). It may very well be that it is positive for that workoad too. Or not. That is all I'm saying.
Don't a lot of databases bypass the page cache for their payload data anyhow?
The kernel page cache doesn't know better than databases themselves when it comes to what to cache. All high performance databases do this in user space, and they use AIO with direct IO or the latest io_uring to bypass the kernel page cache. Modern cloud (distributed) file systems do the same, including GFS: https://en.wikipedia.org/wiki/Google_File_System
And speaking of io_uring, check this out to see how much improvement when copying without going through page cache: https://wheybags.com/blog/wcp.html
However, there are plenty of databases that do not prioritize performance which could benefit, including most open source ones.
Memory that looks expensive because it has little effect on P50 (expensive to the device maker) is cheap to the end user who experiences a big change.
For some reason (maybe because I work with Android) I always thought that XNU is better at memory management (fewer low memory kills, better paging, etc.).
If this makes phones faster, I am all for it.
Apple is pretty good at this with ios.
This causes "janks" (slow UI rendering) and negatively impacts user experience."
[0] - https://learningsys.org/nips17/assets/slides/dean-nips17.pdf (pp 29, 50 etc)
But it did make me wonder, so I went searching and found this paper: "Applying Deep Learning to the Cache Replacement Problem"[1], which sounded quite interesting.
In the paper they train a LSTM network to predict if an item should be cached or not, but then analyze the resulting model and identify key features of its performance. From the paper:
We use these insights to design a new hand-crafted feature that represents a program’s control-flow history compactly and that can be used with a much simpler linear learning model known as a support vector machine (SVM). Our SVM is trained online in hardware, and it matches the LSTM’s offline accuracy with significantly less overhead; in fact, we show that with our hand-crafted feature, an online SVM is equivalent to a perceptron, which has been used in commercial branch predictors.
We use these insights to produce the Glider4 cache replacement policy, which uses an SVM-based predictor to outperform the best cache replacement policies from the 2nd Cache Replacement Championship. Glider significantly improves upon Hawkeye, the previous state-of-the-art and winner of the 2nd Cache Replacement Championship.
Training a neural network and then using it to restate the problem in more optimal way is an approach I haven't seen before (though I'm just a casual observer of the field), and which sounds very interesting.