Raven: belady-guided, predictive (deep) learning for in-memory and content caching
Raven: belady-guided, predictive (deep) learning for in-memory and content caching
复制标题
DOI：
10.1145/3555050.3569134
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Xinyue Hu;Eman Ramadan;Wei Ye;Feng Tian;Zhi-Li Zhang
中科院分区：
文献类型：
--
作者：
Xinyue Hu;Eman Ramadan;Wei Ye;Feng Tian;Zhi-Li Zhang
缓存算法的性能不仅决定了用户的经验质量，而且还会影响云服务提供商的运营和资本支出。当今的生产系统依靠启发式方法，例如LRU（最近使用的最少使用）及其变体，它们适合某些类型的工作负载，并且无法有效地应对各种和时变的工作量特征。尽管已经提出了基于学习的缓存算法来应对这些挑战，但它们仍然对工作量特征施加了假设，并且常常遭受较差的可推广性。在本文中，我们提出了Raven，这是一种基于一般学习的缓存框架，它利用离线最佳Belady算法的见解来进行内存和内容缓存。 Raven通过采用基于混合物密度网络（MDN）的通用分布估计来了解对象的下一要求到达时间的分布，而无需任何先前的假设。它利用估计的分布来计算比缓存中任何其他对象最远的对象的概率，并驱逐具有最大概率的对象的概率，如果适用，则由对象的大小调节。乌鸦（概率地）通过明确考虑对象到达过程的随机，时间变化和非平稳性的明确说明来近似Belady。生产工作量的评估结果表明，与现有的最佳缓存算法相比，Raven将物体的命中率和字节命中率提高了7.3％和7.1％，将平均访问延迟降低高达17.9％，而对原始服务器的流量最高为18.8％。
Performance of caching algorithms not only determines the quality of experience for users, but also affects the operating and capital expenditures for cloud service providers. Today's production systems rely on heuristics such as LRU (least recently used) and its variants, which work well for certain types of workloads, and cannot effectively cope with diverse and time-varying workload characteristics. While learning-based caching algorithms have been proposed to deal with these challenges, they still impose assumptions about workload characteristics and often suffer poor generalizability. In this paper, we propose Raven, a general learning-based caching framework that leverages the insights from the offline optimal Belady algorithm for both in-memory and content caching. Raven learns the distributions of objects' next-request arrival times without any prior assumptions by employing Mixture Density Network (MDN)-based universal distribution estimation. It utilizes the estimated distributions to compute the probability of an object that arrives farthest than any other objects in the cache and evicts the one with the largest such probability, regulated by the sizes of objects if appropriate. Raven (probabilistically) approximates Belady by explicitly accounting for the stochastic, time-varying, and non-stationary nature of object arrival processes. Evaluation results on production workloads demonstrate that, compared with the best existing caching algorithms, Raven improves the object hit ratio and byte hit ratio by up to 7.3% and 7.1%, respectively, reduces the average access latency by up to 17.9% and the traffic to the origin servers by up to 18.8%.