  We consider elastic resource provisioning in the cloud, focusing on in-memory
key-value stores used as caches. Our goal is to dynamically scale resources to
the traffic pattern minimizing the overall cost, which includes not only the
storage cost, but also the cost due to misses. In fact, a small variation on
the cache miss ratio may have a significant impact on user perceived
performance in modern web services, which in turn has an impact on the overall
revenues for the content provider that uses those services. We propose and
study a dynamic algorithm for TTL caches, which is able to obtain
close-to-minimal costs. Since high-throughput caches require low complexity
operations, we discuss a practical implementation of such a scheme requiring
constant overhead per request independently from the cache size. We evaluate
our solution with real-world traces collected from Akamai, and show that we are
able to obtain a 17% decrease in the overall cost compared to a baseline static
configuration.
