On Resource Pooling and Separation for LRU Caching
On Resource Pooling and Separation for LRU Caching
复制标题
DOI：
10.1145/3179408
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Jian Tan;Guocong Quan;Kaiyi Ji;N. Shroff
中科院分区：
文献类型：
--
作者：
Jian Tan;Guocong Quan;Kaiyi Ji;N. Shroff
使用最近最少使用（LRU）原则的缓存系统现在已经变得无处不在。这些系统的一个基本问题是该高速缓存空间是否应该被汇集在一起或被划分以服务多个数据项请求流，以便最小化未命中概率。在本文中，我们表明，这个问题没有直接的是或不是答案，这取决于关键因素的复杂组合，包括，例如，请求速率、跨不同请求流的重叠数据项、数据项流行度及其大小。为此，我们描述了多个数据项请求流的性能下的资源池和分离的LRU缓存时，该高速缓存的大小是大的。分析上，我们表明，它是渐近最优的联合服务多个流，如果他们的数据项的大小和流行度分布是相似的，他们的到达率没有显着差异; LRU缓存的自组织属性自动优化它们之间的资源分配渐近。否则，分离这些流可能会更好，例如，当数据大小变化很大时。我们还量化了临界点，超过这个临界点，当重叠的数据项超过一定的水平时，资源池比每个流的分离更好。从技术上讲，对于一类广泛的重尾分布，我们推导出在共享LRU缓存空间中具有不同数据项大小的多个请求流的渐近未命中概率。在一定的条件下，验证了特征时间近似的正确性.这些结果为提高缓存系统的性能提供了新的见解。
Caching systems using the Least Recently Used (LRU) principle have now become ubiquitous. A fundamental question for these systems is whether the cache space should be pooled together or divided to serve multiple flows of data item requests in order to minimize the miss probabilities. In this paper, we show that there is no straight yes or no answer to this question, depending on complex combinations of critical factors, including, e.g., request rates, overlapped data items across different request flows, data item popularities and their sizes. To this end, we characterize the performance of multiple flows of data item requests under resource pooling and separation for LRU caching when the cache size is large. Analytically, we show that it is asymptotically optimal to jointly serve multiple flows if their data item sizes and popularity distributions are similar and their arrival rates do not differ significantly; the self-organizing property of LRU caching automatically optimizes the resource allocation among them asymptotically. Otherwise, separating these flows could be better, e.g., when data sizes vary significantly. We also quantify critical points beyond which resource pooling is better than separation for each of the flows when the overlapped data items exceed certain levels. Technically, for a broad class of heavy-tailed distributions we derive the asymptotic miss probabilities of multiple flows of requests with varying data item sizes in a shared LRU cache space. It also validates the characteristic time approximation under certain conditions. These results provide new insights on improving the performance of caching systems.