DiskSeen预取算法的分析及优化研究

doi:10.11896/j.issn.1002-137X.2017.06.004

摘要/Abstract

摘要： 计算机存储层次结构是一种典型的金字塔形结构,以平衡计算机对存储系统的两方面需求,即高速处理数据和大的存储容量。然而随着信息技术的飞速发展,计算机处理器和磁盘之间的速度鸿沟持续扩大,因而磁盘访问便成为一个影响计算机系统性能的瓶颈问题。近几十年来,如何减小磁盘访问延迟对整个计算机系统性能的影响,一直是存储领域的热点研究问题。预取技术,通过提前预测I/O请求并将数据读入缓存中,以对上层应用程序隐藏I/O延迟,是缓解这一瓶颈问题的重要技术手段。DiskSeen是一种块级预取算法,通过分析磁盘块的位置和访问时间的联系来提高磁盘访问的顺序性和总体的预取性能。针对DiskSeen算法,文中主要做了以下几方面工作:首先,分析DiskSeen算法的不足之处,据此提出动态控制预取粒度和二次匹配激活历史预取方法,以优化效率；然后,实现了DiskSeen算法及改进后的算法；最后,在模拟仿真实验环境下对算法进行了性能对比测试。实验结果显示,DiskSeen算法能够明显提高缓存命中率并减少平均响应时间,而优化后的DiskSeen算法则可以进一步提升上述两方面的系统性能。

关键词: 存储系统,预取,I/O延迟,DiskSeen,优化

Abstract: To balance the demand for high-speed process and large storage capacity,computer storage hierarchy is a typi-cal pyramid-shaped structure.However,as the information technology develops rapidly,the speed gap between computerprocessor and disk has been widened,which makes the disk access become the bottleneck of the computer system.In recent decades,how to reduce the impact of I/O delay has been a hot issue in storage fields.Prefetching,namely predicting I/O requests in advance and reading the data into cache to hide I/O delay behind application,is a vital technique to alleviate the bottleneck.DiskSeen is a block-level prefetch policy.It can improve the sequential access of disk and prefetching performance by analyzing the relationships between the blocks’ locations and access times.Based on DiskSeen,the following work was done in this paper.First,based on the drawbacks of DiskSeen,we proposed dynamic control for prefetch size and active history-aware prefetch in second match to optimize the efficiency.Secondly,we realized DiskSeen algorithm and the optimization of it.Lastly,we conducted comparison test in a simulation environment.The results show that DiskSeen can effectively increase hit ratio and reduce average response time.Furthermore,our optimization can further improve system performance on above two aspects.

Key words: Storage system,Prefetching,I/O delay,DiskSeen,Optimization

刘燕,朱春节,王芳. DiskSeen预取算法的分析及优化研究[J]. 计算机科学, 2017, 44(6): 23-30. https://doi.org/10.11896/j.issn.1002-137X.2017.06.004

LIU Yan, ZHU Chun-jie and WANG Fang. Analysis and Optimization of DiskSeen Prefetching Algorithm[J]. Computer Science, 2017, 44(6): 23-30. https://doi.org/10.11896/j.issn.1002-137X.2017.06.004

参考文献

[1] GILL B S,MODHA D S.SARC:Sequential Prefetching in Adaptive Replacement Cache[C]∥Proc.of USENIX 2005 An-nual Technical Conference.Boston,MA,USA:2005:293-308.
[2] WU F G,XI H S,XU C F.File prefetching algorithm for concurrent streams[J].Journal of Software,2010,1(8):1820-1833.(in Chinese) 吴峰光,奚宏生,徐陈锋.一种支持并发访问流的文件预取算法[J].软件学报,20101,1(8):1820-1833.
[3] GILL B S,BATHEN L A D.AMP:Adaptive Multi-stream Prefetching in a Shared Cache[C]∥Proceedings of the Fifth USENIX Symposium on File and Storage Technologies (FAST’07).San Jose,CA,2007:185-198.
[4] PATTERSON R H,GIBSON G A,SATYANARAYANAN M.A Status Report on Research in Transparent Informed Prefet-ching[J].ACM Operating Systems Review,1993,27(2):21-34.
[5] TRAN,NANCY,REED D A.Automatic ARIMA time series modeling for adaptive I/O prefetching[J].IEEE Transactions on Parallel and Distributed Systems,2004,15(4):362-377.
[6] BYAN,SURENDRA,et al.Parallel I/O prefetching using MPI file caching and I/O signatures[C]∥Proceedings of the 2008 ACM/IEEE Conference on Supercomputing.Austin,TX:IEEE Press,2008.
[7] GU P,ZHU Y,JIANG H,et al.Nexus a novel weighted-graph-based prefetching algorithm for metadata servers in petabyte-scale storage systems[C]∥Proc.Sixth IEEE Int’l Symp(CCGRID’06).Singapore.2006:409-416.
[8] JIANG S,ZHANG X.STEP:Sequentiality and Thrashing Detection Based Prefetching to Improve Performance of Networked Storage Servers[C]∥Proc.of ICDCS’07.Toronto,2007.
[9] CHEN Y,LI F,DU B,et al.A Quantitative Analysis on Semantic Relations of Data Blocks in Storage Systems[J].Journal of Circuits,Systems and Computers,2015,4(8):1550118.
[10] LI Z,CHEN Z,SRINIVASAN S M,et al.C-Miner:Miningblock correlations in storage systems[C]∥Proc.of FAST’04.Berkeley,CA,USA,2004.
[11] DING X,JIANG S,CHEN F,et al.DiskSeen:Exploiting Disk Layout and Access History to Enhance I/O Prefetch[C]∥USENIX Annual Technical Conference.2007:261-274.
[12] SCHLOSSER S W,SCHINDLER J,PAPADOMANOLAKIS S,et al.On Multidimensional Data and Modern Disks[C]∥Proceedings of the 4th USENIX Conference on File and Storage Technology (FAST’05).Berkeley,CA,USA,2005.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed