MemSC: A Scan-Resistant and Compact Cache Replacement Framework for Memory-Based Key-Value Cache Systems

详细信息    查看全文

• 作者：Mei Li ; Hong-Jun Zhang ; Yan-Jun Wu ; Chen Zhao
• 关键词：key ; value cache system ; cache replacement ; scan resistance ; space efficiency
• 刊名：Journal of Computer Science and Technology
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：32
• 期：1
• 页码：55-67
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Computer Science, general; Software Engineering; Theory of Computation; Data Structures, Cryptology and Information Theory; Artificial Intelligence (incl. Robotics); Information Systems Applications (
• 出版者：Springer US
• ISSN：1860-4749
• 卷排序：32

文摘

Memory-based key-value cache systems, such as Memcached and Redis, have become indispensable components of data center infrastructures and have been used to cache performance-critical data to avoid expensive back-end database accesses. As the memory is usually not large enough to hold all the items, cache replacement must be performed to evict some cached items to make room for the newly coming items when there is no free space. Many real-world workloads target small items and have frequent bursts of scans (a scan is a sequence of one-time access requests). The commonly used LRU policy does not work well under such workloads since LRU needs a large amount of metadata and tends to discard hot items with scans. Small decreases in hit ratio can result in large end-to-end losses in these systems. This paper presents MemSC, which is a scan-resistant and compact cache replacement framework for Memcached. MemSC assigns a multi-granularity reference flag for each item, which requires only a few bits (two bits are enough for general use) per item to support scan-resistant cache replacement policies. To evaluate MemSC, we implement three representative cache replacement policies (MemSC-HM, MemSC-LH, and MemSC-LF) on MemSC and test them using various workloads. The experimental results show that MemSC outperforms prior techniques. Compared with the optimized LRU policy in Memcached, MemSC-LH reduces the cache miss ratio and the memory usage of the resulting system by up to 23% and 14% respectively.