We consider Time-to-Live (TTL) caches that tag every object in cache with a specific (and possibly renewable) expiration time. State-of-the-art models for TTL caches assume zero object fetch delay, i.e., the time required to fetch a requested object that is not in cache from a different cache or the origin server. Particularly, in cache hierarchies, this delay has a significant impact on performance metrics such as the object hit probability. Recent work suggests that the impact of the object fetch delay on the cache performance will continue to increase due to the scaling mismatch between shrinking inter-request times (due to higher data center link rates) in contrast to processing and memory access times. In this paper, we analyze tree-based cache hierarchies with random object fetch delays and provide an exact analysis of the corresponding object hit probability. Our analysis allows understanding the impact of random delays and TTLs on cache metrics for a wide class of request stream models characterized through Markov arrival processes. This is expressed through a metric that we denote delay impairment of the hit probability. In addition, we analyze and extend state-of-the-art approximations of the hit probability to take the delay into account. We provide numerical and trace-based simulation-based evaluation results showing that larger TTLs do not efficiently compensate for the detrimental effect of object fetch delays. Our evaluations also show that unlike our exact model the state-of-the-art approximations do not capture the impact of the object fetch delay well especially for cache hierarchies. Surprisingly, we show that the impact of this delay on the hit probability is not monotonic but depends on the request stream properties, as well as, the TTL.
翻译:我们考虑的是将每个对象标记在缓存中的“时间到生命”缓存(TTL)缓存,这种缓存将标记每个对象在特定(而且可能可再生)到期时间的缓存中。TTL缓存的“状态”模型假定的是零天缓存延迟,即从不同的缓存或源服务器上获取一个请求的不是在缓存的物件所需的时间。特别是在缓存等级中,这种延迟对诸如目标撞击概率等性能衡量标准有重大影响。最近的工作表明,由于与处理和存储存存存存存存存存时间相比,请求时间不断减少(由于数据中心链接率提高)之间的不匹配,该天体将持续增加该天体对缓存性的影响。在本文件中,我们分析基于树枝的缓存等级等级和缓存缓存量对一个请求流模型的影响,通过一个测量标准来显示该天体的延迟概率,但并非由于数据中心的延迟。此外,我们分析并扩展了基于树本的缓存时间,因此显示我们准确的缓存结果。