›› 2017, Vol. 32 ›› Issue (2): 312-328.doi: 10.1007/s11390-017-1724-0

Special Issue: Computer Architecture and Systems

• Computer Architecture and Systems • Previous Articles     Next Articles

A Hint Frequency Based Approach to Enhancing the I/O Performance of Multilevel Cache Storage Systems

Xiao-Dong Meng, Member, CCF, Chen-Tao Wu*, Member, CCF, IEEE, Min-Yi Guo, Senior Member, IEEE, Jie Li, Senior Member, ACM, IEEE, Xiao-Yao Liang, Bin Yao, Long Zheng   

  1. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
  • Received:2016-04-05 Revised:2016-12-29 Online:2017-03-05 Published:2017-03-05
  • Contact: Chen-Tao Wu E-mail:wuct@cs.sjtu.edu.cn
  • About author:Xiao-Dong Meng is a Ph.D. student of computer science in Shanghai Jiao Tong University. He received his Bachelor's degree in electronic information science and technology from Wuhan University in 2007, and Master's degree in information technology from Monash University, Melbourne, in 2010. His main interest is in parallel and distributed computing, social graph processing, and storage systems.
  • Supported by:

    This work was supported by the National Basic Research 973 Program of China under Grant No. 2015CB352403, the National High Technology Research and Development 863 Program of China under Grant No. 2015AA015302, the National Natural Science Foundation of China under Grant Nos. 61332001, 61303012, 61572323 and 61628208, the Scientific Research Foundation for the Returned Overseas Chinese Scholars, and the CCF-Tencent Open Fund.

With the enormous and increasing user demand, I/O performance is one of the primary considerations to build a data center. Several new technologies in data centers, such as tiered storage, prompt the widespread usage of multilevel cache techniques. In these storage systems, the upper level storage typically serves as a cache for the lower level, which forms a distributed multilevel cache system. However, although many excellent multilevel cache algorithms have been proposed to improve the I/O performance, they still have potential to be enhanced by investigating the history information of hints. To address this challenge, in this paper, we propose a novel hint frequency based approach (HFA), to improve the overall multilevel cache performance of storage systems. The main idea of HFA is using hint frequencies (the total number of demotions/promotions by employing demote/promote hints) to efficiently explore the valuable history information of data blocks among multiple levels. HFA can be applied with several popular multilevel cache algorithms, such as Demote, Promote and Hint-K. Simulation results show that, compared with original multilevel cache algorithms such as Demote, Promote and Hint-K, HFA can improve the I/O performance by up to 20% under different I/O workloads.

[1] Zhao Q, Liew S C, Zhang S, Yu Y. Distance-based location management utilizing initial position for mobile communication networks. IEEE Transactions on Mobile Computing, 2016, 15(1):107-120.

[2] Yang R,Wang Z. Cross-oriented choquet integrals and their applications on data classification. Journal of Intelligent & Fuzzy System, 2015, 28(1):205-216.

[3] Zhu Z, Zhang Y, Ji Z, He S, Yang X. High-throughput DNA sequence data compression. Briefings in Bioinformatics, 2015, 16(1):1-15.

[4] Wang T, Liu D, Wang Y, Shao Z. Towards write-activityaware page table management for non-volatile main memories. ACM Transactions on Embedded Computing Systems, 2015, 14(2):34:1-34:23.

[5] Liu J K, Au M H, Susilo W, Liang K, Lu R, Srinivasan B. Secure sharing and searching for real-time video data in mobile cloud. IEEE Network, 2015, 29(2):46-50.

[6] Li J, Liu C, Liu B, Mao R, Wang Y, Chen S, Wang Q et al. Diversity-aware retrieval of medical records. Computers in Industry, 2015, 69:81-91.

[7] Huang X, Cheng H, Li R H, Qin L, Yu J X. Top-K structural diversity search in large networks. The VLDB Journal, 2015, 24(3):319-343.

[8] Chen R, Qin Z, Wang Y, Liu D, Shao Z, Guan Y. Ondemand block-level address mapping in large-scale NAND flash storage systems. IEEE Transactions on Computers, 2015, 64(6):1729-1741.

[9] Hao Y, Xu J, Bai J, Han Y. Image decomposition combining a total variational filter and a Tikhonov quadratic filter. Multidimensional Systems and Signal Processing, 2015, 26(3):739-751.

[10] You Z H, Yu J Z, Zhu L, Li S,Wen Z K. A MapReduce based parellel SVM for large-scale predicting protein-protein interactions. Neurocomputing, 2014, 145:37-43.

[11] Motghare M, Shrawankar U. RFS-UCM:A unified multilevel cache management policy. In Proc. the 9th IEEE Int. Conf. Intelligent Systems and Control, Jan. 2015.

[12] Wong T M, Wilkes J. My cache or yours? Making storage more exclusive. In Proc. USENIX Annual Technical Conference, June 2002, pp.161-175.

[13] Gill B S. On multi-level exclusive caching:Offline optimality and why promotions are better than demotions. In Proc. the 6th USENIX Conference on File and Storage Technologies, Feb. 2008, pp.48-65.

[14] Koltsidas I, Viglas S D. Designing a flash-aware two-level cache. In Proc. the 15th Int. Conf. Advances in Databases and Information Systems, Sept. 2011, pp.153-169.

[15] Zhou Y, Philbin J, Li K. The multi-queue replacement algorithm for second level buffer caches. In Proc. the USENIX Annual Technical Conference, June 2001, pp.91-104.

[16] Zhou Y, Chen Z, Li K. Second-level buffer cache management. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(6):505-519.

[17] Appuswamy R, van Moolenbroek D C, Tanenbaum A S. Cache, cache everywhere, flushing all hits down the sink:On exclusivity in multilevel, hybrid caches. In Proc. the 29th IEEE Symposium on Mass Storage Systems and Technologies, May 2013.

[18] Li X, Aboulnaga A, Salem K et al. Second-tier cache management using write hints. In Proc. the USENIX FAST, Dec. 2005.

[19] Liu X, Aboulnaga A, Salem K, Li X. CLIC:CLientinformed caching for storage servers. In Proc. the USENIX FAST, Feb. 2009, pp.297-310.

[20] Yadgar G, Factor M, Schuster A. Karma:Know-it-all replacement for a multilevel cache. In Proc. the USENIX FAST, Feb. 2007, pp.169-184.

[21] Yadgar G, Factor M, Li K, Schuster A. MC2:Multiple clients on a multilevel cache. In Proc. the 28th IEEE ICDCS, June 2008, pp.722-730.

[22] Wu C, He X, Cao Q, Xie C. Hint-k:An efficient multi-level cache using k-step hints. In Proc. the 39th IEEE ICPP, Sept. 2010, pp.624-633.

[23] Wu C, He X, Cao Q, Xie C et al. Hint-K:An effcient multilevel cache using K-step Hints. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3):653-662.

[24] Denning P J. The working set model for program behavior. Communications of the ACM, 1968, 11(5):323-333.

[25] Robinson J T, Devarakonda M V. Data cache management using frequency based replacement. ACM SIGMETRICS Performance Evaluation Review, 1990, 18(1):134-142.

[26] Johnson T, Shasha D. 2Q:A low overhead high performance buffer management replacement algoritm. In Proc. the 20th Int. Very Large Data Bases, Sept. 1994, pp.439-450.

[27] O'neil E J, O'neil P E, Weikum G. The LRU-K page replacement algorithm for database disk buffering. ACM SIGMOD Record, 1993, 22(2):297-306.

[28] O'neil E J, O'Neil P E, Weikum G. An optimality proof of the LRU-K page replacement algorithm. Journal of the ACM, 1999, 46(1):92-112.

[29] Kim J M, Choi J, Kim J et al. A low-overhead highperformance unified buffer management scheme that exploits sequential and looping references. In Proc. the 4th Symp. Operating System Design & Implementation, Oct. 2000.

[30] Lee D, Choi J, Kim J H et al. LRFU:A spectrum of policies that subsumes the least recently used and least frequently used policies. IEEE Trans. Computers, 2001, 50(12):1352-1361.

[31] Jiang S, Zhang X. LIRS:An efficient low inter-reference recency set replacement policy to improve buffer cache performance. ACM SIGMETRICS Performance Evaluation Review, 2002, 30(1):31-42.

[32] Megiddo N, Modha D S. ARC:A self-tuning, low overhead replacement cache. In Proc. the USENIX FAST, Mar.31-Apr.2, 2003, pp.115-130.

[33] Bansal S, Modha D S. CAR:Clock with adaptive replacement. In Proc. the USENIX FAST, Mar.31-Apr.2, 2004, pp.187-200.

[34] Gniady C, Butt A R, Hu Y C. Program-counter-based pattern classification in buffer caching. In Proc. OSDI, Dec. 2004, pp.395-408.

[35] Gill B S,Modha D S. SARC:Sequential prefetching in adaptive replacement cache. In Proc. the USENIX Annual Technical Conference, Apr. 2005, pp.293-308.

[36] Zhou F, von Behren J R, Brewer E A. AMP:Program context specific buffer caching. In Proc. the USENIX Annual Technical Conference, Apr. 2005, pp.371-374.

[37] Jiang S, Ding X, Chen F, Tan E, Zhang X. DULO:An effective buffer cache management scheme to exploit both temporal and spatial locality. In Proc. the 4th USENIX Conference on File and Storage Technologies, Dec. 2005.

[38] Jiang S, Chen F, Zhang X. CLOCK-Pro:An effective improvement of the CLOCK replacement. In Proc. the USENIX Annual Technical Conference, Apr. 2005, pp.323-336.

[39] Gill B S, Modha D S. WOW:Wise ordering for writes-Combining spatial and temporal locality in non-volatile caches. In Proc. the 4th USENIX Conference on File and Storage Technologies, Dec. 2005.

[40] Zhu Y, Jiang H. RACE:A robust adaptive caching strategy for buffer cache. IEEE Transactions on Computers, 2008, 57(1):25-40.

[41] Gill B S, Ko M, Debnath B et al. STOW:A spatially and temporally optimized write caching algorithm. In Proc. the USENIX Annual Technical Conference, June 2009.

[42] Bairavasundaram L N, Sivathanu M, Arpaci-Dusseau A C, Arpaci-Dusseau R H. X-ray:A non-invasive exclusive caching mechanism for raids. In Proc. Annual International Symposium Computer Architecture, June 2004, pp.176-187.

[43] Chen Z, Zhou Y, Li K. Eviction-based cache placement for storage caches. In Proc. the USENIX Annual Technical Conference, June 2003, pp.269-281.

[44] He X, Ou L, Kosa M J, Scott S L, Engelmann C. A unified multiple-level cache for high performance storage systems. International Journal of High Performance Computing and Networking, 2007, 5(1/2):97-109.

[45] Gill B S. Systems and methods for multi-level exclusive caching using hints. U.S. Patent US 7761664 B2, 2010.

[46] Wang Y, Meng X, Zhang L et al. Chint:An effective and reliable cache management for RDMA-accelerated key-value stores. In Proc. the ACM Symposium on Cloud Computing, Nov. 2014.

[47] Jiang S, Zhang X. ULC:A file block placement and replacement protocol to effectively exploit hierarchical locality in multi-level buffer caches. In Proc. the 24th Int. Conf. Distributed Computing Systems, Mar. 2004, pp.168-177.

[48] Yadgar G, Factor M, Li K et al. Management of multilevel, multiclient cache hierarchies with application hints. ACM Transactions on Computer Systems, 2011, 29(2):5.

[49] Al Assaf M M, Alghamdi M I, Jiang X, Zhang J, Qin X. A pipelining approach to informed prefetching in distributed multi-level storage systems. In Proc. the 11th IEEE Int. Symp. Network Computing and Applications, Aug. 2012, pp.87-95.

[50] Meng X, Zheng L, Li L et al. PAM:An efficient power-aware multi-level cache policy to reduce energy consumption of Software Defined Network. In Proc. the 1st IEEE Int. Industrial Networks and Intelligent Systems, Mar. 2015, pp.18-23.

[51] Benhase M T, Gupta L M. Caching data in a storage system having multiple caches including non-volatile storage cache in a sequential access storage device. U.S. Patent US 8806122 B2, 2014.

[52] González A, Aliagas C, Valero M. A data cache with multiple caching strategies tuned to different types of locality. In Proc. Int. Supercomputing 25th Anniversary, June 2014, pp.217-226.

[53] Zhang Y, Soundararajan G, Storer M W et al. Warming up storage-level caches with bonfire. In Proc. the 11th USENIX Conf. File and Storage Technologies, Feb. 2013, pp.59-72.
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] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

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