Caching with Delayed Hits
Caching with Delayed Hits
复制标题
DOI：
10.1145/3387514.3405883
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Nirav Atre;Justine Sherry;Weina Wang;Daniel S. Berger
中科院分区：
文献类型：
--
作者：
Nirav Atre;Justine Sherry;Weina Wang;Daniel S. Berger
缓存是延迟敏感系统的核心。在本文中，我们确定了延迟最小化缓存设计的一个日益增长的挑战，称为延迟命中。延迟命中发生在高吞吐量时，即在解决未完成的缓存缺失之前，对同一对象队列的多个请求出现。这种影响增加了延迟，超出了传统缓存模型和模拟的预测；事实上，缓存算法的设计就好像延迟命中根本不存在一样。我们表明，传统的缓存策略——即使是所谓的“最优”算法——在出现延迟点击的情况下，也无法最大限度地减少延迟。我们设计了一种新的延迟优化的离线缓存算法，称为延迟缓存，与传统的命中率最优的Belady算法相比，延迟降低了45%。使用迟来作为我们的指南，我们展示了将对象的“聚合延迟”合并到在线缓存启发式中可以将实际缓存系统的延迟提高多达40%。我们在CDN缓存节点中实现了一个原型，Minimum-AggregateDelay （mad）。使用CDN生产跟踪和部署在不同地理位置的后端，我们发现mad可以根据后端rtt减少12-18%的延迟。
Caches are at the heart of latency-sensitive systems. In this paper, we identify a growing challenge for the design of latency-minimizing caches called delayed hits. Delayed hits occur at high throughput, when multiple requests to the same object queue up before an outstanding cache miss is resolved. This effect increases latencies beyond the predictions of traditional caching models and simulations; 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 design a new, latency-optimal offline caching algorithm called belatedly which reduces average latencies by up to 45% 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), within a CDN caching node. Using a CDN production trace and backends deployed in different geographic locations, we show that mad can reduce latencies by 12-18% depending on the backend RTTs.