CAMP: A Cost Adaptive Multi-Queue Eviction Policy for Key-Value Stores
Shahram Ghandeharizadeh, Sandy Irani, Jenny Lam, Jason Yap · 2024
Read CAMP: A Cost Adaptive Multi-Queue Eviction Policy for Key-Value Stores by Shahram Ghandeharizadeh, Sandy Irani, Jenny Lam, Jason Yap (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01246.txt.
Description
Abstract Cost Adaptive Multi-queue eviction Policy (CAMP) is an algorithm for a general purpose key-value store (KVS) that manages key-value pairs computed by applications with different access patterns, key-value sizes, and varying costs for each key-value pair. CAMP is an approximation of the Greedy Dual Size (GDS) algorithm that can be implemented as efficiently as LRU.
Catalog record
| CREATOR | Shahram Ghandeharizadeh, Sandy Irani, Jenny Lam, Jason Yap |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01246
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
CAMP: A Cost Adaptive Multi-Queue Eviction Policy for Key-Value Stores Thanks: Sandy Irani and Jenny Lam are with the University of California, Irvine. Their research is supported in part by the NSF grant CCF-0916181. Shahram Ghandeharizadeh and Jason Yap are with the University of Southern California. Shahram Ghandeharizadeh, Sandy Irani, Jenny Lam, Jason Yap Abstract Cost Adaptive Multi-queue eviction Policy (CAMP) is an algorithm for a general purpose key-value store (KVS) that manages key-value pairs computed by applications with different access patterns, key-value sizes, and varying costs for each key-value pair. CAMP is an approximation of the Greedy Dual Size (GDS) algorithm that can be implemented as efficiently as LRU. In particular, CAMP’s eviction policies are as effective as those of GDS but require only a small fraction of the updates to an internal data structure in order to make those decisions. Similar to an implementation of LRU using queues, it adapts to changing workload patterns based on the history of requests for different key-value pairs. It is superior to LRU because it considers both the size and cost of key-value pairs to maximize the utility of the available memory across competing applications. We compare CAMP with both LRU and an alternative that requires human intervention to partition memory into pools and assign grouping of key-value pairs to different pools. The results demonstrate CAMP is as fast as LRU while outperforming both LRU and the pooled alternative. We also present results from an implementation of CAMP using Twitter’s version of memcached. A shorter version of CAMP appeared in the Proceedings of the ACM/IFIP/USENIX Middleware Conference, Bordeaux, France, December 2014. See https://github.com/scdblab/CAMP for an implementation. 1 Introduction Applications with a high read-to-write ratio augment their persistent infrastructure with an in-memory key-value store (KVS) to enhance performance. An example is memcached in use by popular Internet destinations such as Facebook, Twitter, and Wikipedia. Using a general purpose caching layer requires workloads to share infrastructure despite different access patterns, key-value sizes, and time required to compute a key-value pair [ 21 ] . An algorithm that considers only one factor may cause different application workloads to impact one another negatively, decreasing the overall effectiveness of the caching layer. As an example, consider two different applications of a social networking site: one shows the profile of members while a second determines the displayed advertisements. There may exist millions of key-value pairs corresponding to different member profiles, each computed using a simple database look-up that executed in a few milliseconds. The second application may consist of thousands of key-value pairs computed using a machine-learning algorithm that processed Terabytes of data and required hours of execution. This processing time is one definition of the cost of a key-value pair. With a limited memory size and a high frequency of access for member profile key-value pairs, a simple algorithm that manages memory using recency of references (LRU) may evict most of the key-value pairs of the second application, increasing the incurred cost. In general, reducing the incurred cost translates into a faster system that processes a larger number of requests per unit of time and may provide a better quality of service. The latter is due to availability of data ( e.g. , cache hit for a key-value computed using the machine learning algorithm) that enables the application to provide a user with more relevant content than content selected randomly. A possible approach is for a human expert to partition the available memory into disjoint pools with each pool managed using LRU. Next, the expert groups key-value pairs with similar costs together and assigns each group to a different pool [ 18 ] . With our example, the expert would construct two pools. One for the key-value pairs corresponding to members profiles and a second corresponding to advertisements. The primary limitation 1 1 1 Partitioning is known to reduce the utilization of resources by resulting in formation of hot spots and bottlenecks. One may address this limitation by over-provisioning resources. of this approach is that it requires a human familiar with the different classes of applications to identify the pools, construct grouping of key-value pairs, and assign each group to a pool. Over time, the service provider may either introduce a new application or discontinue an existing one. This means the human expert must again become involved to identify the pool for the key-value pairs of the new application and possibly rebalance memory across the pools once an application is discontinued. This paper introduces a novel caching method called Cost Adaptive Multi-queue eviction Policy (CAMP), that manages the available memory without partitioning it. CAMP is an approximation of the Greedy Dual Size (GDS) algorithm [ 4 ] that processes cache hits and misses more efficiently using queues. Hence, it is significantly faster than GDS and as fast as LRU. It is novel and different from LRU in that it constructs multiple LRU queues dynamically based on the size and cost of key-value pairs. The number of constructed LRU queues depends on the distribution of costs and sizes of the key-value pairs. CAMP manages these LRU queues without partitioning memory. Thus, there is no need for human involvement to construct groups of key-value pairs, dictate assignment of groups to the pools, or configure and adjust the memory pool characteristics. CAMP is robust enough to prevent an aged expensive key-value pair from occupying memory indefinitely. Such a key-value pair is evicted by CAMP as competing applications issue more requests. CAMP is parameterized by a variable that controls its precision. At the highest precision, CAMP’s eviction decisions are essentially equivalent to those made by GDS. Our empirical results show that CAMP does not suffer any degradation in the quality of its eviction decisions at lower precisions. Moreover, it is able to make those decisions much more efficiently than GDS. GDS requires an internal priority queue to determine a key-value pair to evict from the cache. The time to maintain its data structures consistent in a thread-safe manner is expensive because it requires synchronization primitives [ 12 ] with multiple threads performing caching decisions. Moreover, CAMP performs a significantly fewer updates of its internal data structures than GDS, reducing the number of times it executes the thread-safe software dramatically. The rest of this paper is organized as follows. Section 2 starts with a description of GDS to motivate CAMP and details its design decisions. Section 3 presents a simulation study of CAMP and compares it with LRU and the pooled approach that partitions resources, demonstrating its superiority. Section 4 describes an implementation of CAMP using a variant of Twemcache and compares this implementation with the original that uses LRU. Obtained results demonstrate that CAMP is as fast as LRU and provides superior performance as it considers, in addition to recency of requests, the size and the cost of the key-value pairs. Section 5 describes related work. Section 6 provides brief words of conclusions and future research directions. 2 CAMP The algorithm Greedy Dual Size (GDS) was developed in the context of replacement policies for web proxy caches. It captures many of the benefits of LRU and considers the fact that data objects on the web have varying sizes and incur varying