Advances in storage technology have introduced Non-Volatile Memory, NVM, as a new storage medium. NVM, along with DRAM and Disk present a system designer with a wide array of options in designing caching middleware. Moreover, design decisions to replicate a data item in more than one level of a caching memory hierarchy may enhance the overall system performance with a faster recovery time in the event of a memory failure. Given a fixed budget, the key configuration questions are: Which storage media should constitute the memory hierarchy? What is the storage capacity of each hierarchy? Should data be replicated or partitioned across the different levels of the hierarchy? We study a model of these cache configuration questions and present results from a simple algorithm to evaluate design tradeoffs in the context of a memory hierarchy for a Key-Value Store, e.g., memcached. The results show selective replication is appropriate with certain failure rates and workload characteristics. With a slim failure rate and frequent data updates, tiering of data across the different storage media that constitute the cache is superior to replication.

We introduce the subset assignment problem in which items of varying sizes are placed in a set of bins with limited capacity. Items can be replicated and placed in any subset of the bins. Each (item, subset) pair has an associated cost. Not assigning an item to any of the bins is not free in general and can potentially be the most expensive option. The goal is to minimize the total cost of assigning items to subsets without exceeding the bin capacities. The subset assignment problem models the problem of managing a cache composed of banks of memory with varying cost/performance specifications. The ability to replicate a data item in more than one memory bank can benefit the overall performance of the system with a faster recovery time in the event of a memory failure. For this setting, the number n of data objects (items) is very large and the number d of memory banks (bins) is a small constant (on the order of 3 or 4). Therefore, the goal is to determine an optimal assignment in time that minimizes dependence on n. The integral version of this problem is NP-hard since it is a generalization of the knapsack problem. We focus on an efficient solution to the LP relaxation as the number of fractionally assigned items will be at most d. If the data objects are small with respect to the size of the memory banks, the effect of excluding the fractionally assigned data items from the cache will be small. We give an algorithm that solves the LP relaxation and runs in time $$O(\left( {\begin{array}{c}3^d\\ d+1\end{array}}\right) {\text {poly}}(d) n \log (n) \log (nC) \log (Z))$$ , where Z is the maximum item size and C the maximum storage cost.

In the generalized caching problem, items can have varying costs and sizes. We consider a variant of this problem in which the cache management policy must not only specify which items to evict to make room for an incoming item (cache replacement), but must also specify a location in memory where each object can be placed contiguously (memory allocation). The problem is motivated by current implementations of key-value stores in large commercial databases with high read-to-write ratio such as those maintained by Facebook and Twitter. We propose a simple algorithm and show that if the algorithm is given some additional memory to account for fragmentation, it is competitive against an offline optimal algorithm that does not specify memory layout. (The optimal algorithm needs only to ensure that the sum of the sizes of the items in the cache does not exceed the total capacity of the cache). On the benchmark traces in the experiments presented here, our algorithm requires approximately 10–15– additional space to be k-competitive against the optimal offline algorithm. Through trace-driven simulations, we demonstrate that the caching performance of our algorithm for cache replacement with memory allocation is close to that of competitive strategies that are not required to manage memory layout within the cache.

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 in that its eviction policy is as effective as GDS. At the same time, its implementation is as efficient at LRU. 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.