›› 2017, Vol. 32 ›› Issue (1): 55-67.doi: 10.1007/s11390-017-1705-3

Special Issue: Computer Architecture and Systems

• Computer Architecture and Systems • Previous Articles     Next Articles

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

Mei Li1,2(李梅), Hong-Jun Zhang1,2(张鸿骏), Yan-Jun Wu1,3(武延军), Senior Member, CCF, Member, ACM, and Chen Zhao1,3(赵琛), Senior Member, CCF   

  1. 1 National Engineering Research Center of Fundamental Software, Institute of Software, Chinese Academy of Sciences Beijing 100190, China;
    2 University of Chinese Academy of Sciences, Beijing 100049, China;
    3 State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2016-08-09 Revised:2016-11-21 Online:2017-01-05 Published:2017-01-05
  • About author:Mei Li is a Ph.D. candidate in computer software and theory of Institute of Software, Chinese Academy of Sciences, Beijing. She received her B.S. degree in computer science and technology from Beijing University of Posts and Telecommunications, Beijing, in 2011. Her research interests include operating system and cloud computing.
  • Supported by:

    This work was supported by the Next Generation of Information Technology Strategic Research Program of Chinese Academy of Sciences under Grant No. XDA06010600.

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 scanresistant 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.

[1] Fitzpatrick B. Distributed caching with memcached. Linux Journal, 2004, 2014(124):5.

[2] Lim H, Han D, Andersen D G, Kaminsky M. MICA:A holistic approach to fast in-memory key-value storage. In Proc. the 11th USENIX Symposium on Networked Systems Design and Implementation, April 2014, pp.429-444.

[3] Li M, Zhao C, Wu Y, Xie P. DataOS:Principle, design and prototype implementation. SCIENTIA SINICA Informationis, 2015, 45(6):703-720.

[4] Atikoglu B, Xu Y, Frachtenberg E, Jiang S, Paleczny M. Workload analysis of a large-scale key-value store. In Proc. the 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, June 2012, pp.53-64.

[5] Nishtala R, Fugal H, Grimm S, Kwiatkowski M, Lee H, Li H C, McElroy R, Paleczny M, Peek D, Saab P, Stafford D, Tung T, Venkataramani V. Scaling memcache at Facebook. In Proc. the 10th USENIX Symp. Networked Systems Design and Implementation, April 2013, pp.385-398.

[6] Xu Y, Frachtenberg E, Jiang S, Paleczny M. Characterizing Facebook's Memcached workload. IEEE Internet Computing, 2014, 18(2):41-49.

[7] Cidon A, Eisenman A, Alizadeh M, Katti S. Cliffhanger:Scaling performance cliffs in web memory caches. In Proc. the 13th USENIX Symposium on Networked Systems Design and Implementation, March 2016, pp.379-392.

[8] Cidon A, Eisenman A, Alizadeh M, Katti S. Dynacache:Dynamic cloud caching. In Proc. the 7th USENIX Workshop on Hot Topics in Cloud Computing, July 2015.

[9] Fan B, Andersen D G, Kaminsky M. MemC3:Compact and concurrent memcache with dumber caching and smarter hashing. In Proc. the 10th USENIX Conference on Networked Systems Design and Implementation, April 2013, pp.371-384.

[10] Johnson T, Shasha D. 2Q:A low overhead high performance buffer management replacement algorithm. In Proc. the 20th International Conference on Very Large Data Bases, September 1994, pp.439-450.

[11] Cooper B F, Silberstein A, Tam E, Ramakrishnan R, Sears R. Benchmarking cloud serving systems with YCSB. In Proc. the 1st ACM Symposium on Cloud Computing, June 2010, pp.143-154.

[12] Li C, Cox A L. GD-Wheel:A cost-aware replacement policy for key-value stores. In Proc. the 10th European Conference on Computer Systems, April 2015, pp.5:1-5:15.

[13] Hu X, Wang X, Li Y, Zhou L, Luo Y, Ding C, Jiang S, Wang Z. LAMA:Optimized locality-aware memory allocation for key-value cache. In Proc. the USENIX Annual Technical Conference, July 2015, pp.57-69.

[14] Lee D, Choi J, Kim J H, Noh S H, Min S L, Cho Y, Kim C S. On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies. In Proc. the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, May 1999, pp.134-143.

[15] O'Neil E J, O'Neil P E, Weikum G. The LRU-K page replacement algorithm for database disk buffering. In Proc. the ACM SIGMOD International Conference on Management of Data, May 1993, pp.297-306.

[16] Megiddo N, Modha D S. ARC:A self-tuning, low overhead replacement cache. In Proc. the 2nd USENIX Conference on File and Storage Technologies, March 31-April 2, 2003, pp.115-130.

[17] Bansal S, Modha D S. CAR:Clock with adaptive replacement. In Proc. the 3rd USENIX Conference on File and Storage Technologies, March 31-April 2, 2004, pp.187-200.

[18] Subramanian R, Smaragdakis Y, Loh G H. Adaptive caches:Effective shaping of cache behavior to workloads. In Proc. the 39th Annual IEEE/ACM International Symposium on Microarchitecture, December 2006, pp.385-396.

[19] Corbato F J. A paging experiment with the multics system. In Honor of Philip M. Morse, 1969, pp.217-228. http://tocs.ulb.tu-darmstadt.de/197560164.pdf, Dec. 2016.

[20] Jaleel A, Theobald K B, Steely Jr S C, Emer J. High performance cache replacement using re-reference interval prediction (RRIP). In Proc. the 37th Annual International Symposium on Computer Architecture, June 2010, pp.60-71.

[21] Wu C J, Jaleel A, Hasenplaugh W, Martonosi M, Steely Jr S C, Emer J. SHiP:Signature-based hit predictor for high performance caching. In Proc. the 44th Annual IEEE/ACM International Symposium on Microarchitecture, December 2011, pp.430-441.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Gong Zhenhe;. On Conceptual Model Specification and Verification[J]. , 1987, 2(1): 35 -50 .
[8] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[9] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved