A new flexible multi-flow LRU cache management paradigm for minimizing misses
A new flexible multi-flow LRU cache management paradigm for minimizing misses
复制标题
一种新的灵活的多流 LRU 缓存管理范例，可最大限度地减少丢失
DOI：
10.1145/3309697.3331509
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Shroff, N.
中科院分区：
文献类型：
--
作者：
Quan, G;Tan, J;Eryilmaz, A;Shroff, N.
最近最少使用（LRU）缓存及其变体用于大型数据系统中，以便为各种应用程序提供高速数据访问。尽管如此，一个基本问题仍然悬而未决：为了最大限度地减少丢失概率，应该如何组织缓存空间来服务多个数据流？常用的策略可以分为两种设计：池化 LRU (PLRU) 缓存和分离 LRU (SLRU) 缓存。然而，这些设计都不能令人满意地解决这个问题。 PLRU 缓存易于实现且具有自适应性，但由于其可行的解决方案集有限，因此通常无法实现最佳甚至高效的性能。 SLRU 缓存可以静态配置，以实现固定工作负载的最佳性能，但在动态变化的环境和冷启动问题中可能会受到影响。为此，我们提出了一种新的基于插入的池化 LRU 范例，称为 I-PLRU，其中数据流可以插入池化缓存的不同位置。这种新设计可以实现静态SLRU的最佳性能，并通过资源共享保留PLRU的适应性。从理论上讲，我们描述了 I-PLRU 的渐近缺失概率，并证明，对于任何给定的 SLRU 设计，始终存在实现相同渐近缺失概率的 I-PLRU 配置，反之亦然。接下来我们设计一个策略来最小化错过概率。然而，在 I-PLRU 范式下，遗漏概率最小化问题被证明是非凸的。值得注意的是，我们利用 I-PLRU 和 SLRU 之间的等价映射来有效地找到最佳 I-PLRU 配置。我们证明 I-PLRU 优于 PLRU，并且对于固定工作负载实现了与最佳 SLRU 相同的丢失概率。从工程上讲，I-PLRU 的灵活性避免了内存空间的分离，支持动态和精细的配置，并缓解了冷启动问题，可能会产生比 SLRU 和 PLRU 更好的性能。
The Least Recently Used (LRU) caching and its variants are used in large-scale data systems in order to provide high-speed data access for a wide class of applications. Nonetheless, a fundamental question still remains open: in order to minimize miss probabilities, how should the cache space be organized to serve multiple data flows? Commonly used strategies can be categorized into two designs: pooled LRU (PLRU) caching and separated LRU (SLRU) caching. However, neither of these designs can satisfactorily solve this problem. PLRU caching is easy to implement and self-adaptive, but does not often achieve optimal or even efficient performance because its set of feasible solutions are limited. SLRU caching can be statically configured to achieve optimal performance for stationary workload, which nevertheless could suffer in a dynamically changing environment and from a cold-start problem. To this end, we propose a new insertion based pooled LRU paradigm, termed I-PLRU, where data flows can be inserted at different positions of a pooled cache. This new design can achieve the optimal performance of the static SLRU, and retains the adaptability of PLRU in virtue of resource sharing. Theoretically, we characterize the asymptotic miss probabilities of I-PLRU, and prove that, for any given SLRU design, there always exists an I-PLRU configuration that achieves the same asymptotic miss probability, and vice versa. We next design a policy to minimize the miss probabilities. However, the miss probability minimization problem turns out to be non-convex under the I-PLRU paradigm. Notably, we utilize an equivalence mapping between I-PLRU and SLRU to efficiently find the optimal I-PLRU configuration. We prove that I-PLRU outperforms PLRU and achieves the same miss probability as the optimal SLRU for stationary workload. Engineeringly, the flexibility of I-PLRU avoids separating the memory space, supports dynamic and refined configurations, and alleviates the cold-start problem, potentially yielding better performance than both SLRU and PLRU.