Cache Modeling and Optimization Using Miniature Simulations [pdf]

https://www.usenix.org/system/files/conference/atc17/atc17-waldspurger.pdf

by erwan • 8 years ago

30 9 8 years ago

erwan2• 8 years ago

Sharing this paper because effective workload simulation is a necessary step toward the Holy Grail: workload aware and self-tuning caches. In plain english, that means a cache that can adjust its parameters so that it is most effective for a given workload. Ideally, you want all of that without human supervision or pre-trained models, and in its fully accomplished form the cache can provision resources if it is worth it. Note that effectiveness here is traditionally measured in terms of hit:miss ration but other metrics exist too.

That's part of the broader idea of "intelligent systems" pro-actively adjusting themselves (resources, internal structure, overall policies) to the workload they are fed in order to optimize performance or cost-effectiveness.

The most basic caches have static eviction policies (e.g LRU/LFU), there has been some work on adaptive eviction policies (e.g ARC), and more recently on a clever combination of adjusting eviction policies and admission policies (e.g TinyLFU). The overarching goal of this line of research is to figure out a "silver bullet" cache which perform optimally (or close-to) regardless of R/W distributions by scrambling between different policies wrt. admission and eviction.

JDWolf2• 8 years ago

Thank you for the post. This is an area I am currently exploring in regards to parallelization and have had a somewhat tough time finding papers on the topic.

erwan2• 8 years ago

My pleasure! Could you give a high-level description of what is the problem/angle you are approaching?

NovaX• 8 years ago

Along your line of thinking, we have a paper scheduled for Middleware (Dec. 2018) and it explores how to make W-TinyLFU adaptive. I can share this paper privately until the conference (ben.manes @ gmail). It shows how to use simple, low-overhead schemes to improve the policy across workloads that exhibit various recency/frequency biases.

yvdriess• 8 years ago

Are there not significant diminishing returns to such techniques? More sophisticated eviction strategies need to be proporially more effective to compensate for the increased overhead. Or do you see the simulations only as an offline tool for better researching caching strategies.

d--2• 8 years ago

It turns out that most caching algorithms we use in practice (CDNs, memcached, storage, etc.) are still pretty far from the optimal hit ratio/ miss ratio.

See, e.g., recent work that exposes that gap (I'm an author)

https://www.cs.cmu.edu/~dberger1/pdf/2018PracticalBound_SIGM...

https://github.com/dasebe/optimalwebcaching

gstaro• 8 years ago

Another pointer to a paper that seems related: https://www.usenix.org/conference/nsdi18/presentation/beckma...

This is a very hot topic recently. It seems to me that several communities (databases, CDNs, storage, CPU architecture, theory) do a lot of redundant work and don't communicate a lot with each other..

d--2• 8 years ago

Yes, that paper LHD (from a colleague of mine) does use online stochastic modeling of the workload to make better decisions. So this definitely fits the bill

Cache Modeling and Optimization Using Miniature Simulations [pdf]

Related Stories