Fresh Caching for Dynamic Content
Fresh Caching for Dynamic Content
复制标题
DOI：
10.1109/infocom42981.2021.9488731
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
B. Abolhassani;John Tadrous;A. Eryilmaz;E. Yeh
中科院分区：
文献类型：
--
作者：
B. Abolhassani;John Tadrous;A. Eryilmaz;E. Yeh
我们引入了一个框架和可证明有效的方案，用于在（前端）本地内容缓存中进行“新鲜”缓存，这些内容在（后端）数据库中进行“动态”更新。我们首先为此设置制定硬缓存约束问题，由于缓存有限，该问题很快就会变得棘手。为了绕过这一挑战，我们首先提出了一种灵活的基于时间的驱逐模型，以导出平均系统成本函数，该函数除了定期缓存未命中成本之外，还可以衡量由于老化内容服务而导致的系统成本。接下来，我们解决缓存不受约束的情况，这揭示了内容的刷新动态和流行度如何影响最佳缓存。然后，我们将我们的方法扩展到软缓存约束版本，在该版本中我们可以保证缓存使用以任意高的概率受到限制。相应的解决方案揭示了一个有趣的见解：“是否在本地缓存中缓存某个项目？”主要取决于其受欢迎程度，而“在驱逐之前缓存的项目应在缓存中保留多长时间？”主要取决于其刷新率。此外，我们研究了成本与缓存节省的权衡，并证明随着数据库大小的增长，可以获得大量的缓存收益，同时渐进地实现最低成本。
We introduce a framework and provably-efficient schemes for ‘fresh’ caching at the (front-end) local cache of content that is subject to ‘dynamic’ updates at the (back-end) database. We start by formulating the hard-cache-constrained problem for this setting, which quickly becomes intractable due to the limited cache. To bypass this challenge, we first propose a flexible time-based-eviction model to derive the average system cost function that measures the system’s cost due to the service of aging content in addition to the regular cache miss cost. Next, we solve the cache-unconstrained case, which reveals how the refresh dynamics and popularity of content affect the optimal caching. Then, we extend our approach to a soft-cache-constrained version, where we can guarantee that the cache use is limited with arbitrarily high probability. The corresponding solution reveals the interesting insight that ‘whether to cache an item or not in the local cache?’ depends primarily on its popularity level, whereas ‘how long the cached item should be held in the cache before eviction?’ depends primarily on its refresh rate. Moreover, we investigate the cost-cache saving tradeoffs and prove that substantial cache gains can be obtained while also asymptotically achieving the minimum cost as the database size grows.