Multi-Tenant In-Memory Key-Value Cache Partitioning Using Efficient Random Sampling-Based LRU Model
Multi-Tenant In-Memory Key-Value Cache Partitioning Using Efficient Random Sampling-Based LRU Model
复制标题
DOI：
10.1109/tcc.2023.3300889
复制
发表时间：
2023-10
影响因子：
6.5
通讯作者：
Yuchen Wang;Junyao Yang;Zhenlin Wang
中科院分区：
文献类型：
--
作者：
Yuchen Wang;Junyao Yang;Zhenlin Wang
在web应用程序、基于磁盘的存储和分布式系统中，内存中的键值缓存被广泛用作性能关键层。最近最少使用（Least Recently Used， LRU）替换策略已经成为这些系统中事实上的标准，因为它很好地利用了工作负载局部性。然而，由于维护对象优先级的严格数据结构以及对象顺序更新的锁，LRU实现的成本可能很高。Redis作为最有效和最普遍的商业系统之一，采用了一种近似的LRU策略，从一个小的，随机抽样的项目集中选择最近最少使用的项目来驱逐。这种基于随机抽样的策略是轻量级的，并且显示了它的灵活性。我们观察到，在不同的采样规模$K$K下，精确LRU和基于随机抽样的LRU之间可能存在显著的缺失率差距。因此，现有的LRU缺失比曲线（MRC）构建技术无法在不损失精度的情况下直接应用。在本文中，我们引入了一种新的概率堆栈算法KRR来精确地建模基于随机抽样的lru，并将其扩展到处理键值缓存中的固定和可变对象。我们提出了一种有效的堆栈更新算法，该算法显著降低了KRR的预期运行时间。为了提高内存中使用随机抽样替换的多租户键值缓存的性能，我们提出了kRedis，这是一种参考的位置和延迟感知内存分区方案。kRedis指导租户之间的内存分配，并动态自定义$K$K，以便更好地利用每个租户的局部性。对不同工作负载的评估结果表明，我们的模型为固定和可变对象大小的工作负载生成了准确的脱靶率曲线，并实现了实用的、低开销的在线MRC预测。配备KRR，与Redis相比，kRedis提供了高达50.2%的平均访问延迟减少，以及高达262.8%的吞吐量提高。此外，与pRedis （Redis中最先进的内存分配设计）相比，kRedis在平均访问延迟和吞吐量方面分别提高了24.8%和61.8%。
In-memory key-value caches are widely used as a performance-critical layer in web applications, disk-based storage, and distributed systems. The Least Recently Used (LRU) replacement policy has become the de facto standard in those systems since it exploits workload locality well. However, the LRU implementation can be costly due to the rigid data structure in maintaining object priority, as well as the locks for object order updating. Redis as one of the most effective and prevalent deployed commercial systems adopts an approximated LRU policy, where the least recently used item from a small, randomly sampled set of items is chosen to evict. This random sampling-based policy is lightweight and shows its flexibility. We observe that there can exist a significant miss ratio gap between exact LRU and random sampling-based LRU under different sampling size $K$Ks. Therefore existing LRU miss ratio curve (MRC) construction techniques cannot be directly applied without loss of accuracy. In this article, we introduce a new probabilistic stack algorithm named KRR to accurately model random sampling based-LRU, and extend it to handle both fixed and variable objects in key-value caches. We present an efficient stack update algorithm that reduces the expected running time of KRR significantly. To improve the performance of the in-memory multi-tenant key-value cache that utilizes random sampling-based replacement, we propose kRedis, a reference locality- and latency-aware memory partitioning scheme. kRedis guides the memory allocation among the tenants and dynamically customizes $K$K to better exploit the locality of each individual tenant. Evaluation results over diverse workloads show that our model generates accurate miss ratio curves for both fixed and variable object size workloads, and enables practical, low-overhead online MRC prediction. Equipped with KRR, kRedis delivers up to a 50.2% average access latency reduction, and up to a 262.8% throughput improvement compared to Redis. Furthermore, by comparing with pRedis, a state-of-the-art design of memory allocation in Redis, kRedis shows up to 24.8% and 61.8% improvements in average access latency and throughput, respectively.