Computer Science ›› 2017, Vol. 44 ›› Issue (6): 23-30.doi: 10.11896/j.issn.1002-137X.2017.06.004

Previous Articles     Next Articles

Analysis and Optimization of DiskSeen Prefetching Algorithm

LIU Yan, ZHU Chun-jie and WANG Fang   

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

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   
No Suggested Reading articles found!