20 ms·

Linux Kernel: The multi-generational LRU

170 points by signa11 6y ago

_pmf_ 6y ago
Hasn't cache handling in the kernel long reached the timing complexity of a garbage collector, mooting some points about system programming and GC?
- viraptor 6y ago
  As you said, "cache handling" possibly did. That's one of few well defined areas where you're handling GC by definition of the task. System programming is about a lot more than that.
truth_seeker 6y ago
This is encouraging. >> On Chrome OS, our real-world benchmark that browses popular websites in multiple tabs demonstrates 51% less CPU usage from kswapd and 52% (full) less PSI on v5.11 In addition, direct reclaim latency is reduced by 22% at 99th percentile and the number of refaults is reduced 7%. These metrics are important to phones and laptops as they are correlated to user experience. >> Use cases 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 Borg, a similar approach enables us to identify jobs that underutilize their memory and downsize them considerably without compromising any of our service level indicators. 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.
qiqitori 6y ago
> Consider, for example, an application that is reading sequentially through a file. Each page of the file will be put into the page cache as it is read, but the application will never need it again; in this case, recent access is not a sign that the page will be used again soon. Going off on a tangent here, but I've always felt there should be an easy way to read through files without causing the kernel to cache them into memory. When I grep through the odd multi-GB file I sometimes/often don't want that to be cached. Looking through the flags for open(2) I see O_DIRECT. Wonder if it'd make sense to expose that as an option in grep, or if there's a handy library somebody made that I could preload to anything to get that effect.
- londons_explore 6y ago
  I'd like to see the kernel figure this out automatically. If the last 100,000 files opened by grep were never accessed again, is it a good bet to cache the 100,001'st? I think the solution is not to come up with clever heuristics, but to use a tiny neural net which predicts "how many hours till this page is accessed again?". Train the net using a tiny sample of reads and writes. Obviously the net needs to be really tiny to run on every single page read, but I believe even say a network with 50 weights would outperform today's heuristics.
  - signa11 6y ago
    please...submit patches if you can, with benchmarks as well, so that the idea can perhaps be evaluated empirically ?
  - magicalhippo 6y ago
    In a previous comment[1] I mentioned finding a paper that made a neural net cache predictor with seemingly great success. A key thing however was that their actual predictor was a simpler model, SVM, designed using insight discovered from the behavior of the neural network one. In particular the source address was a strong indicator for the model. [1]: https://news.ycombinator.com/item?id=26455515 https://news.ycombinator.com/item?id=26455515
    - d33 6y ago
      My first intuitive thought is "gosh, please, don't". It sounds like a crazy idea to integrate a neural net to everything - it might work in the 99.999% cases, but when something like this fails, good luck debugging it, re-training the network and then verifying if your improvement helped on a tight schedule. And it's also a dangerous architectural paradigm - will we end up with syscalls deciding which side effects happen deciding on whether the neural network things the file is going to be useful in the future? I don't argument for excess simplicity, but if you can't explain (critical) behavior of your code without referring to a big matrix of NN weights, it's probably a bad idea.
gbrown_ 6y ago
Previous discussion https://news.ycombinator.com/item?id=26671848 https://news.ycombinator.com/item?id=26671848
k_bx 6y ago
What I would love to see is an expiration mechanism for files, e.g. you create a file that will get cleaned up in an hour. Would simplify my life on multiple occasions.
- pferde 6y ago
  You can with systemd (*cue boos from the audience*), although it involves a bit of additional configuration - what files to clean up, and set up a timer. See e.g. https://www.putorius.net/systemd-tmpfiles.html#user-specific-examples https://www.putorius.net/systemd-tmpfiles.html#user-specific... (no affiliation with the site, it was just the first one I found that describes the works).
  - k_bx 6y ago
    Wow, thank you! I didn't know it not only exists but is provided by systemd. I'm already using systemd to deploy my services, so this sounds like a perfect fit!
- loa_in_ 6y ago
  That isn't something kernel should concern itself with. It also can be accomplished by three line python script and one line of crontab
  - k_bx 6y ago
    To me, this is the same concern that tmpfile api is providing. Either remove the temp file/dir api or extend it with useful stuff.
    - loa_in_ 6y ago
      tmpfile isn't guaranteed by Linux kernel. It's POSIX and POSIX is userspace layer with elements of it (like IPC and IO) implemented in kernel for efficiency resons.
jonstewart 6y ago
The description of the current system as being composed of two LRU queues sound a lot like the 2Queues cache replacement algorithm. However, I was under the impression that Linux used CLOCK-Pro?
- NovaX 6y ago
  They decided against it, I believe because ClockPro was too complicated (but maybe NIH?). Instead they devised their own algorithm, DClock, borrowing ideas but is also different [1]. They use an ad hoc sizing rule (50%-99%) [2] which can dramatically impact its performance, neither extreme being universally better. When reimplementing their algorithm for analysis, the hit rates skewed towards being okay but not great [3]. You can compare ClockPro [4] and DClock [5] in the simulator. [1] https://github.com/torvalds/linux/blob/ac3a0c8472969a03c0496ae774b3a29eb26c8d5a/mm/workingset.c https://github.com/torvalds/linux/blob/ac3a0c8472969a03c0496... [2] https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42c992cabfd380e0338f2/mm/vmscan.c#L2176-L2204 https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42... [3] https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZeFn9i_iV0TPE8je4ADwlMNM8/edit#gid=1925412315 https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZe... [4] https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/irr/ClockProPolicy.java https://github.com/ben-manes/caffeine/blob/master/simulator/... [5] https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/irr/DClockPolicy.java https://github.com/ben-manes/caffeine/blob/master/simulator/...
yakubin 6y ago
It sounds a bit like a generational garbage collector.
yrral 6y ago
Facebook also talked about something similar back in 2014 for caching of people's photos. https://engineering.fb.com/2014/02/27/web/an-analysis-of-facebook-photo-caching-2/ https://engineering.fb.com/2014/02/27/web/an-analysis-of-fac... http://www.cs.cornell.edu/~qhuang/papers/sosp_fbanalysis.pdf http://www.cs.cornell.edu/~qhuang/papers/sosp_fbanalysis.pdf > Quadruply-segmented LRU. Four queues are maintained at levels 0 to 3. On a cache miss, the item is inserted at the head of queue 0. On a cache hit, the item is moved to the head of the next higher queue (items in queue 3 move to the head of queue 3). Each queue is allocated 1/4 of the total cache size and items are evicted from the tail of a queue to the head of the next lower queue to maintain the size invariants. Items evicted from queue 0 are evicted from the cache.
quelsolaar 6y ago
A FIFO cache of this kind can be very bad in some situations. Imagine if you have a cache of 8 entries and the application reads 9 entries in a loop from beginning to end over and over. In this case the FIFO cache algorithm will always eject the next entry just before its needed. Ejecting even a random entry is much better. Its an incredibly difficult problem to try to figure out what to keep in cache, so I find that the first thing one should allow is for the user to give hints. It would be great if there was a way for applications to designate some memory allocations as "hot" or "cold" to indicate the usage pattern, or indicate that its reading something linearly, or that its about to need something.
- NovaX 6y ago
  That assumes the developer can provide correct hints, which unfortunately is rarely true. In my experience it is better to invest in an algorithm that can detect these patterns, learn from the workload, and optimize accordingly. Modern cache policies are robustly near optimal, but developers don't bother to implement them.
- matheusmoreira 6y ago
  This is the point of the madvise system call. https://www.man7.org/linux/man-pages/man2/madvise.2.html https://www.man7.org/linux/man-pages/man2/madvise.2.html > MADV_RANDOM > MADV_SEQUENTIAL > MADV_WILLNEED > MADV_DONTNEED > MADV_COLD > MADV_PAGEOUT > MADV_DONTDUMP > MADV_WIPEONFORK
  - quelsolaar 6y ago
    Thanks!
- dr_zoidberg 6y ago
  But this algorithm isn't a FIFO: it's a multi-generational LRU cache. That means, LRU+some extra details (evry well explained in the post) to make it perform even better. There are some metrics in the post, and some in the comments here too.

170 points by signa11 6y ago

Hasn't cache handling in the kernel long reached the timing complexity of a garbage collector, mooting some points about system programming and GC?

viraptor 6y ago
As you said, "cache handling" possibly did. That's one of few well defined areas where you're handling GC by definition of the task. System programming is about a lot more than that.

truth_seeker 6y ago

This is encouraging. >> On Chrome OS, our real-world benchmark that browses popular websites in multiple tabs demonstrates 51% less CPU usage from kswapd and 52% (full) less PSI on v5.11 In addition, direct reclaim latency is reduced by 22% at 99th percentile and the number of refaults is reduced 7%. These metrics are important to phones and laptops as they are correlated to user experience. >> Use cases 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 Borg, a similar approach enables us to identify jobs that underutilize their memory and downsize them considerably without compromising any of our service level indicators. 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.

qiqitori 6y ago

> Consider, for example, an application that is reading sequentially through a file. Each page of the file will be put into the page cache as it is read, but the application will never need it again; in this case, recent access is not a sign that the page will be used again soon. Going off on a tangent here, but I've always felt there should be an easy way to read through files without causing the kernel to cache them into memory. When I grep through the odd multi-GB file I sometimes/often don't want that to be cached. Looking through the flags for open(2) I see O_DIRECT. Wonder if it'd make sense to expose that as an option in grep, or if there's a handy library somebody made that I could preload to anything to get that effect.

londons_explore 6y ago
I'd like to see the kernel figure this out automatically. If the last 100,000 files opened by grep were never accessed again, is it a good bet to cache the 100,001'st? I think the solution is not to come up with clever heuristics, but to use a tiny neural net which predicts "how many hours till this page is accessed again?". Train the net using a tiny sample of reads and writes. Obviously the net needs to be really tiny to run on every single page read, but I believe even say a network with 50 weights would outperform today's heuristics.
- signa11 6y ago
  please...submit patches if you can, with benchmarks as well, so that the idea can perhaps be evaluated empirically ?
- magicalhippo 6y ago
  In a previous comment[1] I mentioned finding a paper that made a neural net cache predictor with seemingly great success. A key thing however was that their actual predictor was a simpler model, SVM, designed using insight discovered from the behavior of the neural network one. In particular the source address was a strong indicator for the model. [1]: https://news.ycombinator.com/item?id=26455515 https://news.ycombinator.com/item?id=26455515
  - d33 6y ago
    My first intuitive thought is "gosh, please, don't". It sounds like a crazy idea to integrate a neural net to everything - it might work in the 99.999% cases, but when something like this fails, good luck debugging it, re-training the network and then verifying if your improvement helped on a tight schedule. And it's also a dangerous architectural paradigm - will we end up with syscalls deciding which side effects happen deciding on whether the neural network things the file is going to be useful in the future? I don't argument for excess simplicity, but if you can't explain (critical) behavior of your code without referring to a big matrix of NN weights, it's probably a bad idea.

gbrown_ 6y ago

Previous discussion https://news.ycombinator.com/item?id=26671848 https://news.ycombinator.com/item?id=26671848

k_bx 6y ago

What I would love to see is an expiration mechanism for files, e.g. you create a file that will get cleaned up in an hour. Would simplify my life on multiple occasions.

pferde 6y ago
You can with systemd (*cue boos from the audience*), although it involves a bit of additional configuration - what files to clean up, and set up a timer. See e.g. https://www.putorius.net/systemd-tmpfiles.html#user-specific-examples https://www.putorius.net/systemd-tmpfiles.html#user-specific... (no affiliation with the site, it was just the first one I found that describes the works).
- k_bx 6y ago
  Wow, thank you! I didn't know it not only exists but is provided by systemd. I'm already using systemd to deploy my services, so this sounds like a perfect fit!
loa_in_ 6y ago
That isn't something kernel should concern itself with. It also can be accomplished by three line python script and one line of crontab
- k_bx 6y ago
  To me, this is the same concern that tmpfile api is providing. Either remove the temp file/dir api or extend it with useful stuff.
  - loa_in_ 6y ago
    tmpfile isn't guaranteed by Linux kernel. It's POSIX and POSIX is userspace layer with elements of it (like IPC and IO) implemented in kernel for efficiency resons.

jonstewart 6y ago

The description of the current system as being composed of two LRU queues sound a lot like the 2Queues cache replacement algorithm. However, I was under the impression that Linux used CLOCK-Pro?

NovaX 6y ago
They decided against it, I believe because ClockPro was too complicated (but maybe NIH?). Instead they devised their own algorithm, DClock, borrowing ideas but is also different [1]. They use an ad hoc sizing rule (50%-99%) [2] which can dramatically impact its performance, neither extreme being universally better. When reimplementing their algorithm for analysis, the hit rates skewed towards being okay but not great [3]. You can compare ClockPro [4] and DClock [5] in the simulator. [1] https://github.com/torvalds/linux/blob/ac3a0c8472969a03c0496ae774b3a29eb26c8d5a/mm/workingset.c https://github.com/torvalds/linux/blob/ac3a0c8472969a03c0496... [2] https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42c992cabfd380e0338f2/mm/vmscan.c#L2176-L2204 https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42... [3] https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZeFn9i_iV0TPE8je4ADwlMNM8/edit#gid=1925412315 https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZe... [4] https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/irr/ClockProPolicy.java https://github.com/ben-manes/caffeine/blob/master/simulator/... [5] https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/irr/DClockPolicy.java https://github.com/ben-manes/caffeine/blob/master/simulator/...

yakubin 6y ago

It sounds a bit like a generational garbage collector.

yrral 6y ago

Facebook also talked about something similar back in 2014 for caching of people's photos. https://engineering.fb.com/2014/02/27/web/an-analysis-of-facebook-photo-caching-2/ https://engineering.fb.com/2014/02/27/web/an-analysis-of-fac... http://www.cs.cornell.edu/~qhuang/papers/sosp_fbanalysis.pdf http://www.cs.cornell.edu/~qhuang/papers/sosp_fbanalysis.pdf > Quadruply-segmented LRU. Four queues are maintained at levels 0 to 3. On a cache miss, the item is inserted at the head of queue 0. On a cache hit, the item is moved to the head of the next higher queue (items in queue 3 move to the head of queue 3). Each queue is allocated 1/4 of the total cache size and items are evicted from the tail of a queue to the head of the next lower queue to maintain the size invariants. Items evicted from queue 0 are evicted from the cache.

quelsolaar 6y ago

A FIFO cache of this kind can be very bad in some situations. Imagine if you have a cache of 8 entries and the application reads 9 entries in a loop from beginning to end over and over. In this case the FIFO cache algorithm will always eject the next entry just before its needed. Ejecting even a random entry is much better. Its an incredibly difficult problem to try to figure out what to keep in cache, so I find that the first thing one should allow is for the user to give hints. It would be great if there was a way for applications to designate some memory allocations as "hot" or "cold" to indicate the usage pattern, or indicate that its reading something linearly, or that its about to need something.

NovaX 6y ago
That assumes the developer can provide correct hints, which unfortunately is rarely true. In my experience it is better to invest in an algorithm that can detect these patterns, learn from the workload, and optimize accordingly. Modern cache policies are robustly near optimal, but developers don't bother to implement them.
matheusmoreira 6y ago
This is the point of the madvise system call. https://www.man7.org/linux/man-pages/man2/madvise.2.html https://www.man7.org/linux/man-pages/man2/madvise.2.html > MADV_RANDOM > MADV_SEQUENTIAL > MADV_WILLNEED > MADV_DONTNEED > MADV_COLD > MADV_PAGEOUT > MADV_DONTDUMP > MADV_WIPEONFORK
- quelsolaar 6y ago
  Thanks!
dr_zoidberg 6y ago
But this algorithm isn't a FIFO: it's a multi-generational LRU cache. That means, LRU+some extra details (evry well explained in the post) to make it perform even better. There are some metrics in the post, and some in the comments here too.