论文标题
延迟命中的缓存的下限
Lower Bounds for Caching with Delayed Hits
论文作者
论文摘要
卡车是对潜伏期敏感计算机系统的基本组成部分。 [ASWB20]的最新工作启动了对延迟命中的研究：缓存和备用商店之间的延迟远大于新请求之间的时间大得多的缓存现象。我们为延迟命中缓存模型提供了两个结果。 （1）竞争比下限。我们证明，[ASWB20]中该算法的竞争比率至少是延迟命中的任何确定性在线算法的竞争比，至少是Omega（kz），其中k是k尺寸，z是延迟参数。 （2）延迟命中潜伏期的抗突出性。抗巨孔性是缓存延迟的自然理想属性：高速缓存而不是缓存失误应导致整体延迟较低。我们证明，延迟命中模型的延迟不是通过表现出一种情况而不是击中的场景，而不是错过的情况，从而导致整体延迟增加。我们还提出了延迟命中模型的修改，该模型使延迟抗肌发酮。
Caches are a fundamental component of latency-sensitive computer systems. Recent work of [ASWB20] has initiated the study of delayed hits: a phenomenon in caches that occurs when the latency between the cache and backing store is much larger than the time between new requests. We present two results for the delayed hits caching model. (1) Competitive ratio lower bound. We prove that the competitive ratio of the algorithm in [ASWB20], and more generally of any deterministic online algorithm for delayed hits, is at least Omega(kZ), where k is the cache size and Z is the delay parameter. (2) Antimonotonicity of the delayed hits latency. Antimonotonicity is a naturally desirable property of cache latency: having a cache hit instead of a cache miss should result in lower overall latency. We prove that the latency of the delayed hits model is not antimonotone by exhibiting a scenario where having a cache hit instead of a miss results in an increase in overall latency. We additionally present a modification of the delayed hits model that makes the latency antimonotone.
