计算机科学 ›› 2017, Vol. 44 ›› Issue (6): 23-30.doi: 10.11896/j.issn.1002-137X.2017.06.004

• 2016 年全国信息存储技术学术年会 • 上一篇    下一篇

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

刘燕,朱春节,王芳   

  1. 华中科技大学武汉光电国家实验室 武汉430074,华中科技大学武汉光电国家实验室 武汉430074,华中科技大学武汉光电国家实验室 武汉430074
  • 出版日期:2018-11-13 发布日期:2018-11-13

Analysis and Optimization of DiskSeen Prefetching Algorithm

LIU Yan, ZHU Chun-jie and WANG Fang   

  • Online:2018-11-13 Published:2018-11-13

摘要: 计算机存储层次结构是一种典型的金字塔形结构,以平衡计算机对存储系统的两方面需求,即高速处理数据和大的存储容量。然而随着信息技术的飞速发展,计算机处理器和磁盘之间的速度鸿沟持续扩大,因而磁盘访问便成为一个 影响 计算机系统性能的瓶颈问题。近几十年来,如何减小磁盘访问延迟对整个计算机系统性能的影响,一直是存储领域的热点研究问题。预取技术,通过提前预测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

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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .