Caches for the Persistent Memory and Flash Era

For a very long time, practical scaling of every level in the computing hierarchy has required innovation and improvement in caches. This is as true for CPUs as it is for storage and networked, distributed systems. As such, research into cache efficiency and efficacy improvements has been highly motivated and continues with strong improvements to this day. However, there are certain areas in cache algorithms optimization that have only recently experienced breakthroughs.

In this tutorial, we will start by reviewing the history of the caching algorithm research and practice in industry. Of particular interest to us are multi-tier memory hierarchies that are getting more complex and deep due to hardware innovations. These hierarchies and the workloads they generate motivate revisiting multi-tier algorithms. We will then describe cache utility curves and review recent literature that has made them easier to compute. Using this tool, we will excavate around caching policies and their trade-offs in different contexts. We will also spend some time thinking about optimality for caches.