We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 32 Issue 2
March  2017
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Xiao-Dong Meng, Chen-Tao Wu, Min-Yi Guo, Jie Li, Xiao-Yao Liang, Bin Yao, Long Zheng. A Hint Frequency Based Approach to Enhancing the I/O Performance of Multilevel Cache Storage Systems[J]. Journal of Computer Science and Technology, 2017, 32(2): 312-328. DOI: 10.1007/s11390-017-1724-0
Citation: Xiao-Dong Meng, Chen-Tao Wu, Min-Yi Guo, Jie Li, Xiao-Yao Liang, Bin Yao, Long Zheng. A Hint Frequency Based Approach to Enhancing the I/O Performance of Multilevel Cache Storage Systems[J]. Journal of Computer Science and Technology, 2017, 32(2): 312-328. DOI: 10.1007/s11390-017-1724-0
shu

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

  • Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Funds: 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.
More Information
  • Author Bio:

    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.

  • Corresponding author:

    Chen-Tao Wu E-mail: wuct@cs.sjtu.edu.cn

  • Received Date: April 04, 2016
  • Revised Date: December 28, 2016
  • Published Date: March 04, 2017
    Abstract
  • 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.
    • FullText(HTML)
    • References (53)
  • [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.
    • Relative Articles

  • Related Articles

    [1]Yuan Li, Jie Dai, Xiao-Lin Fan, Yu-Hai Zhao, Guo-Ren Wang. I/O Efficient Early Bursting Cohesive Subgraph Discovery in Massive Temporal Networks[J]. Journal of Computer Science and Technology, 2022, 37(6): 1337-1355. DOI: 10.1007/s11390-022-2367-3
    [2]Suren Byna, M. Scot Breitenfeld, Bin Dong, Quincey Koziol, Elena Pourmal, Dana Robinson, Jerome Soumagne, Houjun Tang, Venkatram Vishwanath, Richard Warren. ExaHDF5: Delivering Efficient Parallel I/O on Exascale Computing Systems[J]. Journal of Computer Science and Technology, 2020, 35(1): 145-160. DOI: 10.1007/s11390-020-9822-9
    [3]Anthony Kougkas, Hariharan Devarajan, Xian-He Sun. I/O Acceleration via Multi-Tiered Data Buffering and Prefetching[J]. Journal of Computer Science and Technology, 2020, 35(1): 92-120. DOI: 10.1007/s11390-020-9781-1
    [4]Qi Chen, Kang Chen, Zuo-Ning Chen, Wei Xue, Xu Ji, Bin Yang. Lessons Learned from Optimizing the Sunway Storage System for Higher Application I/O Performance[J]. Journal of Computer Science and Technology, 2020, 35(1): 47-60. DOI: 10.1007/s11390-020-9798-5
    [5]Kai Lu, Peng-Fei Wang, Gen Li, Xu Zhou. Untrusted Hardware Causes Double-fetch Problems in the I/O Memory[J]. Journal of Computer Science and Technology, 2018, 33(3): 587-602. DOI: 10.1007/s11390-018-1842-3
    [6]Dongchul Park, Weiping He, David H. C. Du. Hot Data Identification with Multiple Bloom Filters: Block-Level Decision vs I/O Request-Level Decision[J]. Journal of Computer Science and Technology, 2018, 33(1): 79-97. DOI: 10.1007/s11390-018-1809-4
    [7]Yuhun Jun, Jaemin Lee, Euiseong Seo. Evaluation of Remote-I/O Support for a DSM-Based Computation Offloading Scheme[J]. Journal of Computer Science and Technology, 2017, 32(5): 957-973. DOI: 10.1007/s11390-017-1775-2
    [8]Fang Lv, Hui-Min Cui, Lei Wang, Lei Liu, Cheng-Gang Wu, Xiao-Bing Feng, Pen-Chung Yew. Dynamic I/O-Aware Scheduling for Batch-Mode Applications on Chip Multiprocessor Systems of Cluster Platforms[J]. Journal of Computer Science and Technology, 2014, 29(1): 21-37. DOI: 10.1007/s11390-013-1409-2
    [9]Dan Feng, Hong Jiang, Yi-Feng Zhu. I/O Performance of an RAID-10 Style Parallel File System[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [10]SUN Ninghui. Reference Implementation of Scalable I/O Low-Level API on Intel Paragon[J]. Journal of Computer Science and Technology, 1999, 14(3): 206-223.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (25) PDF downloads (1018) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return