? 一种用于内存键值缓存系统的紧凑型抗扫描缓存替换框架
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | Help
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2017, Vol. 32 Issue (1) :55-67    DOI: 10.1007/s11390-017-1705-3
Computer Architecture and Systems << Previous Articles | Next Articles >>
一种用于内存键值缓存系统的紧凑型抗扫描缓存替换框架
Mei Li1,2(李梅), Hong-Jun Zhang1,2(张鸿骏), Yan-Jun Wu1,3(武延军), Senior Member, CCF, Member, ACM, and Chen Zhao1,3(赵琛), Senior Member, CCF
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
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 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

摘要
参考文献
相关文章
Download: [PDF 500KB]  
摘要 为了提高数据访问速度和减轻数据库负载,内存键值缓存系统已广泛应用于数据中心,例如Memcached和Redis。由于缓存通常不足以容纳所有数据,内存键值缓存系统需要将部分数据踢出缓存以存储新数据。一些研究表明真实工作负载通常以小数据请求为主,且常会出现一些仅访问一次的数据序列(称为扫描)。常用的LRU策略需要大量元数据,且不具备扛扫描性,因此LRU不能很好地适应这类工作负载。本文提出了一种用于Memcached的紧凑型抗扫描缓存替换框架MemSC。MemSC利用多粒度标识位来标识替换优先级,并利用一种紧凑型数据结构存储标识位,通过动态调整标识位即可支持具备抗扫描性的缓存替换策略。本文实现了三个具有代表性的缓存替换策略(MemSC_HM,MemSC_LH以及MemSC_LF),并利用多种工作负载进行了测试。实验结果表明,与现有技术相比,MemSC能够降低缓存未命中率23%和节省缓存空间14%。
关键词键值缓存系统   缓存替换   扛扫描性   空间利用率     
Abstract: 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.
Keywordskey-value cache system   cache replacement   scan resistance   space efficiency     
Received 2016-08-09;
本文基金:

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

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.
引用本文:   
Mei Li, Hong-Jun Zhang, Yan-Jun Wu, Chen Zhao.一种用于内存键值缓存系统的紧凑型抗扫描缓存替换框架[J]  Journal of Computer Science and Technology , 2017,V32(1): 55-67
Mei Li, Hong-Jun Zhang, Yan-Jun Wu, Chen Zhao.MemSC: A Scan-Resistant and Compact Cache Replacement Framework for Memory-Based Key-Value Cache Systems[J]  Journal of Computer Science and Technology, 2017,V32(1): 55-67
链接本文:  
http://jcst.ict.ac.cn:8080/jcst/CN/10.1007/s11390-017-1705-3
Copyright 2010 by Journal of Computer Science and Technology