CNS Core: Small: Caching with Delayed Hits

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Caches are responsible for storing data close to where computer systems access them in order to make things faster. For example, when a user accesses a website, the web browser first checks the cache to see if the webpage files are already there; if not, the cache goes to the website servers, which takes longer. Unfortunately, caches are small and don’t have room to store everything. In order to make systems faster, this project’s goal is to decide what to store in the cache while accounting for "delayed hits", which occur when multiple requests happen for the same data back-to-back. This project will explore the impact of delayed hits on cache performance. Delayed hits occur when a request "misses" in the cache, and a second request occurs for the same object before the first request has returned from the backing store. The second hit does not have equal latency to a true "hit" nor a true "miss". Because caches assume that requests result in either a hit or a miss, caches do not achieve the best possible latency. This project will explore new caching algorithms to achieve better latency by taking delayed hits into account. The technical impact of this project will be to improve latencies for a broad range of computer systems that rely on caches, from key-value stores in data centers to web caches. Systems with very long latencies will benefit the most, leading to the hypothesis that one will see strong benefits for web caches in Internet-underserved regions which may be hundreds of miles from their nearest data center. This project will also impact education and broaden participation in computing by including undergraduate researchers in the research process. All simulators, scripts, and analysis resulting from this work will be uploaded to public repositories (http://www.github.com/cmu-snap) where they may be accessed by the public indefinitely. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.