Abstract

Caches are at the heart of latency-sensitive systems. In this talk, we will focus on a growing challenge for the design of latency-minimizing caching called ‘delayed hits’. Delayed hits occur at high throughput, when multiple requests to the same object queue up before an outstanding cache miss for that object is resolved. This phenomenon increases latencies beyond the predictions of traditional caching models and simulators, and subverts expectations of existing caching algorithms; in fact, caching algorithms are designed as if delayed hits simply didn’t exist. We show that traditional caching strategies – even so-called ‘optimal’ algorithms – can fail to minimize latency in the presence of delayed hits. We present a new, latency-optimal offline caching algorithm called BELATEDLY , which computes up to 45% lower latencies compared to the traditional, hit-rate optimal Belady’s algorithm. Using BELATEDLY as our guide, we show that incorporating an object’s ‘Aggregate Delay’ into online caching heuristics can improve latencies for practical caching systems by up to 40%. We implement a prototype, Minimum-AggregateDelay (MAD), in the context of a CDN caching node. Using a CDN production trace and backends deployed in different geographic locations, we show that MAD can reduce average caching latencies in CDNs today by 12-18% depending on the backend RTTs.

Bio: Nirav is a third-year Ph.D. student in the Computer Science Department (CSD) at Carnegie Mellon University (CMU), where he is advised by Prof. Justine Sherry. Nirav’s research interests lie at the intersection of networking and performance modeling, and he’s part of the Systems, Networking, and Performance (SNAP) Lab at CMU . Prior to starting graduate school, Nirav completed his B.A.Sc in Computer Engineering at the University of Toronto, Canada, in 2018.