4 ms·

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

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

by remram 3y ago

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