4 ms·

Better analysis here than in the SIEVE paper, imho. Ultimately, the right eviction policy depends on the application behavior, and you'll only find the right a

Better analysis here than in the SIEVE paper, imho. Ultimately, the right eviction policy depends on the application behavior, and you'll only find the right answer through profiling against actual data from service logs... and the difference between miss rates isn't large so I really don't think it should even be the first thing that gets profiled.. use LRU or LFU (based on intuition about usage) and move on. But I do love to see newly proposed algorithms, more tools for the bag.

remram 3y ago
This is one thing you can probably easily test on historical data. In fact I wonder if there is an automated tool/framework that can consume some structured log of accessed keys to select and tune the optimal policy.
- kevindamm 3y ago
  Easy to measure, sure, but that's different than impact on performance. You're much more likely to get a bigger win from analyzing database schema, divide-and-conquering the workload, tuning the algorithms in the critical path, or even choosing _what_ gets cached. If tuning the cache eviction is the main thing it is probably because that's the only thing.
- danbruc 3y ago
  This should be doable. On each access append the key to a list of recent keys which would also not be terrible expensive if the keys are much smaller than the values. Ever so often you can then look through the list of recent keys and analyze the access patterns and maybe change the eviction algorithm. But I think this might also not be too helpful overall. I think in many cases there is an obvious choice depending on how and for what the cache is used. And then there are caches that have more unpredictable access patterns, a file system cache might be a good candidate, experiencing the access patterns of all the different applications. In that case there is probably no best choice as several applications with different access patterns concurrently hit the cache. Or if there is a best choice, it might change very quickly as different applications or components of applications execute. In such a scenario it seems more promising to me to try to categorize the access patterns on a per source basis and treating them accordingly instead of trying to find one best policy for all sources combined. On the other hand something like this might quickly become prohibitively expensive.
- NovaX 3y ago
  The problem with that approach is not only the time and effort to capture and analyze the trace, but that the workload changes over the application's lifetime. When the workload is expensive and important then cache analysis is worth doing, and there are cache simulators that are pretty easy to work with. For the general case the ideal is an eviction policy that adapts to fit the given workload. Unfortunately adaptivity is not a very well explored area so most policies have heuristic settings that default to work well in a target range of workloads, but this has to be tuned for others. In this and the author's other paper, S3-FIFO, their lower hit rates with TinyLFU turned out to be due to the implementation. When running it with Caffeine, a productionized version that adds hill climbing and jitter, it had equivalent hit rates [1]. That cache is pretty robust across a wide range of workloads, but also much more complicated to implement. I'd really like to see more research on adaptivity because I think all policies are converging on similar structures and goals, but self-tuning is still an error prone art. [1] https://github.com/Yiling-J/theine/issues/21#issuecomment-1880217400 https://github.com/Yiling-J/theine/issues/21#issuecomment-18...
TheCondor 3y ago
In college we included the optimal case in understanding caching. It’s a very worthwhile process. Sieve’s claim is simplicity and lower eviction latency. That should be measured against hits. A tiny fraction more hits will almost always erase the differences between various eviction algorithms. Depending on cache size and the size of what you’re caching, LRU can add a nontrivial amount of memory. It is promising to see more experimenting with these algorithms.
- titzer 3y ago
  I mostly agree with this, except for hardware (CPU) caches, hit latency is absolutely critical, and all logic must be implemented with circuits. On top of the latency requirement, organizing the data structures and handling coherency are really tough design problems.
contravariant 3y ago
If you don't want to think about it, use LRU. The optimal algorithm can at best be twice as good as LRU using half the memory. And yes that includes an algorithm that knows exactly which memory is going to be requested. If LRU is not enough you need to be clever or use more memory. Something like LFU has no such guarantees. Just read a big block of data 10 times and you can get close to 100% cache misses just by continuing to read random bits of data 10 times after each other. LRU would only have 10%, and I think that's optimal.
- jonstewart 3y ago
  Twice as good meaning that the cache miss rate is halved? A standard homework problem in a computer architecture class is to work through the math on how marginal improvements to cache rates can provide dramatic performance improvements, due to the disparity in times of providing data from cache and from the source. Small improvements to caching are a big deal. I hadn’t heard of SIEVE but I’ve had to work more with traditional block cache strategies, where scans are intermixed with random access. LIRS works pretty well.
  - marcosdumay 3y ago
    Oh, "cache" means a huge amount of functionality, on both hardware and software, with a huge amount of dissimilarity. People are talking like of the one cache thing they are thinking about is the end-all be-all instance of "cache" and nothing can differ. Even the article's author, that really should know better. Anyway, you seem to be talking about a basically free network (probably a bus), with huge throughput and relatively short latency. The article seems to be about a more limited network, with comparatively lower throughput and larger latency. The same algorithm won't work for both cases.
- taneq 3y ago
  I tend to think similarly about most optimisation things. Sure, sometimes in niche cases (embedded, or sometimes gaming, are good examples) doubling performance takes it from a no-go to a go, so it's definitely worth knowing things like this. Usually though we're looking for more than 50% scalability, and if you're within 50% of max capacity you need to re-think things on a much higher level.

remram 3y ago

This is one thing you can probably easily test on historical data. In fact I wonder if there is an automated tool/framework that can consume some structured log of accessed keys to select and tune the optimal policy.

kevindamm 3y ago
Easy to measure, sure, but that's different than impact on performance. You're much more likely to get a bigger win from analyzing database schema, divide-and-conquering the workload, tuning the algorithms in the critical path, or even choosing _what_ gets cached. If tuning the cache eviction is the main thing it is probably because that's the only thing.
danbruc 3y ago
This should be doable. On each access append the key to a list of recent keys which would also not be terrible expensive if the keys are much smaller than the values. Ever so often you can then look through the list of recent keys and analyze the access patterns and maybe change the eviction algorithm. But I think this might also not be too helpful overall. I think in many cases there is an obvious choice depending on how and for what the cache is used. And then there are caches that have more unpredictable access patterns, a file system cache might be a good candidate, experiencing the access patterns of all the different applications. In that case there is probably no best choice as several applications with different access patterns concurrently hit the cache. Or if there is a best choice, it might change very quickly as different applications or components of applications execute. In such a scenario it seems more promising to me to try to categorize the access patterns on a per source basis and treating them accordingly instead of trying to find one best policy for all sources combined. On the other hand something like this might quickly become prohibitively expensive.
NovaX 3y ago
The problem with that approach is not only the time and effort to capture and analyze the trace, but that the workload changes over the application's lifetime. When the workload is expensive and important then cache analysis is worth doing, and there are cache simulators that are pretty easy to work with. For the general case the ideal is an eviction policy that adapts to fit the given workload. Unfortunately adaptivity is not a very well explored area so most policies have heuristic settings that default to work well in a target range of workloads, but this has to be tuned for others. In this and the author's other paper, S3-FIFO, their lower hit rates with TinyLFU turned out to be due to the implementation. When running it with Caffeine, a productionized version that adds hill climbing and jitter, it had equivalent hit rates [1]. That cache is pretty robust across a wide range of workloads, but also much more complicated to implement. I'd really like to see more research on adaptivity because I think all policies are converging on similar structures and goals, but self-tuning is still an error prone art. [1] https://github.com/Yiling-J/theine/issues/21#issuecomment-1880217400 https://github.com/Yiling-J/theine/issues/21#issuecomment-18...

TheCondor 3y ago

In college we included the optimal case in understanding caching. It’s a very worthwhile process. Sieve’s claim is simplicity and lower eviction latency. That should be measured against hits. A tiny fraction more hits will almost always erase the differences between various eviction algorithms. Depending on cache size and the size of what you’re caching, LRU can add a nontrivial amount of memory. It is promising to see more experimenting with these algorithms.

titzer 3y ago
I mostly agree with this, except for hardware (CPU) caches, hit latency is absolutely critical, and all logic must be implemented with circuits. On top of the latency requirement, organizing the data structures and handling coherency are really tough design problems.

contravariant 3y ago

If you don't want to think about it, use LRU. The optimal algorithm can at best be twice as good as LRU using half the memory. And yes that includes an algorithm that knows exactly which memory is going to be requested. If LRU is not enough you need to be clever or use more memory. Something like LFU has no such guarantees. Just read a big block of data 10 times and you can get close to 100% cache misses just by continuing to read random bits of data 10 times after each other. LRU would only have 10%, and I think that's optimal.

jonstewart 3y ago
Twice as good meaning that the cache miss rate is halved? A standard homework problem in a computer architecture class is to work through the math on how marginal improvements to cache rates can provide dramatic performance improvements, due to the disparity in times of providing data from cache and from the source. Small improvements to caching are a big deal. I hadn’t heard of SIEVE but I’ve had to work more with traditional block cache strategies, where scans are intermixed with random access. LIRS works pretty well.
- marcosdumay 3y ago
  Oh, "cache" means a huge amount of functionality, on both hardware and software, with a huge amount of dissimilarity. People are talking like of the one cache thing they are thinking about is the end-all be-all instance of "cache" and nothing can differ. Even the article's author, that really should know better. Anyway, you seem to be talking about a basically free network (probably a bus), with huge throughput and relatively short latency. The article seems to be about a more limited network, with comparatively lower throughput and larger latency. The same algorithm won't work for both cases.
taneq 3y ago
I tend to think similarly about most optimisation things. Sure, sometimes in niche cases (embedded, or sometimes gaming, are good examples) doubling performance takes it from a no-go to a go, so it's definitely worth knowing things like this. Usually though we're looking for more than 50% scalability, and if you're within 50% of max capacity you need to re-think things on a much higher level.