5 ms·

ARC shares the concept of non-resident (ghost) entries with LIRS, but uses that to dynamically adjust the SLRU partition (an LRU where probation entries are pro

by NovaX 6y ago

ARC shares the concept of non-resident (ghost) entries with LIRS, but uses that to dynamically adjust the SLRU partition (an LRU where probation entries are promoted to a protected region on a second hit). LIRS has fixed partitions and uses a larger history (~3x) to track the "inter-reference recency". This is a much more complex algorithm, but offers a higher hit rate and is more scan resistant. Linux's DClock calculates the "refault distance" which is their similar concept. 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/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/adaptive/ArcPolicy.java https://github.com/ben-manes/caffeine/blob/master/simulator/... [2] https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/irr/LirsPolicy.java https://github.com/ben-manes/caffeine/blob/master/simulator/... [3] 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/...

XorNot 6y ago
I wonder if ZFS on Linux could be adapted to use this instead of the custom ARC implementation it brings along?
- NovaX 6y ago
  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 all workload patterns we have tried. This is what I proposed to the Linux folks when analyzing DClock. 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. [1] https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency
  - 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

by NovaX 6y ago

XorNot 6y ago

I wonder if ZFS on Linux could be adapted to use this instead of the custom ARC implementation it brings along?

NovaX 6y ago
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 all workload patterns we have tried. This is what I proposed to the Linux folks when analyzing DClock. 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. [1] https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency
- 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