跳到主要內容

臺灣博碩士論文加值系統

(44.211.26.178) 您好!臺灣時間:2024/06/16 00:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳嘉佑
研究生(外文):Chia-Yu Chen
論文名稱:應用於混合式儲存裝置之資料預取方法
論文名稱(外文):An Adaptive Prefetching Scheme for HybridStorage Systems
指導教授:張軒彬張軒彬引用關係
口試委員:張大緯曾秀松徐玉青
口試日期:2014-07-30
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學與工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:中文
論文頁數:59
相關次數:
  • 被引用被引用:0
  • 點閱點閱:151
  • 評分評分:
  • 下載下載:6
  • 收藏至我的研究室書目清單書目收藏:0
傳統硬碟容量大價格低,但是存取效能差,而 NAND Flash 固態硬碟存取效能佳,卻價格昂貴,基於上述因素考量,有了混合式儲存裝置的架構出現,擷取兩種儲存裝置的優勢,將價格便宜且儲存容量大的傳統硬碟當作主要的儲存裝置,另外將價格昂貴但是存取效能較佳的固態硬碟來當作傳統硬碟的快取,來提升整體的 I/O 效能。
此外,傳統上為了提昇硬碟的 I/O 效能, Linux 核心會判斷資料的存取模式是否為循序性,如果是,則啟動資料預取機制以提升效能。然而 Linux 的資料預取機制是針對傳統硬碟所設計的。在混合式硬碟的架構下,資料可能來自於不同屬性與特色的硬碟。因此,我們提出一個應用於混合式儲存裝置的資料預取方法 CLAP(Cross-Layer Adaptive Prefetching),CLAP 會分析存取的循序度與預取的資料是源自哪一顆硬碟,根據循序度和該硬碟的特性,來決定需要預讀多少資料,並且加入 process Interleaving 的處理機制,提升系統的整體效能。
我們已實作於 CLAP 於 Linux 核心,從實驗結果可以發現,CLAP 的效能較原始的 Flashcache 與 Linux Readahead 有明顯的改善,減少執行的時間,提高 I/O Throughput。


Traditional hard disk has larger capacity and lower price than NAND Flash-based SSD (Solid-State Drive), but the access performance is much poorer than SSD. Consequently, the hybrid storage architecture that integrates both the hard disk and SSDs is proposed to take advantage of these two types of devices. The traditional hard disk is still used as the main storage to reduce the cost while a small amount of SSD is exploited as the hard disk cache to boost the I/O performance.
Besides, Linux proposes a data pre-fetching scheme,called “Linux Readahead” to boost the sequential read performance in traditional hard disks. Linux readahead
would detect the data access pattern and if sequential, it will pre-fetch data to amortize the expensive disk mechanical operations. Unfortunately, Linux readahead is proposed for traditional mechanical disks and cannot be efficiently applied in hybrid storage architectures, since the SSDs own different characteristics compared with hard disks. To address this issue, we proposed CLAP (Cross-Layer Adaptive Prefetching)data prefetching scheme for hybrid storage architectures. First, unlike the Linux readahead that is implemented in the file systems, CLAP is implemented in the data caching layer and thus can distinguish the types of disks where the requested data
comes from. Then, according to the device’s characteristics and the data sequentiality, CLAP computes appropriate prefetch size. Besides, CLAP proposes a per-file and per-application data prefetching scheme to overcome the problem of process interleaving.
We have implemented in CLAP scheme on Ubuntu 12.04. From the experimental results, the performance of CLAP is better than Linux Readahead, in both of response time and throughput.


第一章 緒論................................................................................................... 1
1.1 簡介................................................................................................... 1
1.2 研究動機 ........................................................................................... 2
1.3 研究貢獻 ........................................................................................... 3
1.4 論文架構 ........................................................................................... 4
第二章 背景知識與相關研究 ......................................................................... 5
2.1 Linux I/O 分層架構........................................................................... 5
2.1.1 The bio structure ..................................................................... 6
2.2 Device-Mapper Kernel Architecture .................................................. 7
2.3 Flashcache........................................................................................ 10
2.3.1 Caching Modes ...................................................................... 11
2.3.2 Set associative hash ................................................................ 11
2.3.3 Device Mapper Layer ............................................................ 12
2.3.4 Metadata and Metadata Overhead ........................................ 13
2.3.5 Replacement Policy................................................................ 13
2.3.6 Read Request Handler ........................................................... 13
2.3.7 Dirty block ............................................................................. 13
2.3.8 Non-cacheable........................................................................ 14
2.4 Prefetching in Linux........................................................................ 15
2.4.1 呼叫時機 call convention ...................................................... 17
2.4.2 Readahead Overall Flow........................................................ 17
2.4.3 Readahead Thrashing ............................................................ 19
第三章 系統設計與實作 .............................................................................. 21
3.1 系統架構 ............................................................................................ 21
3.2 系統設計與流程 ................................................................................. 23
3.2.1 Interception 模組 ................................................................... 23
3.2.2 Request Mgr 模組 .................................................................. 24
3.2.3 Prefetching Handler 模組 ................................................... 26
3.3 系統實作 ............................................................................................ 30
3.3.1 資料結構 .................................................................................. 30
3.3.2 Interception 模組 ................................................................... 33
3.3.3 Request Mgr 模組 .................................................................. 35
3.3.4 Prefetching Handler 模組 ...................................................... 37
3.4 整體運作流程..................................................................................... 38
第四章 實驗結果與討論 .............................................................................. 40
4.1 環境設定 ......................................................................................... 40
4.2 實驗結果 ......................................................................................... 43
4.2.1 Grep 測試結果 ....................................................................... 43
4.2.2 Diff 測試結果 ......................................................................... 45
4.2.3 Postmark 測試結果................................................................ 46
4.2.4 Interleaved 測試結果 ............................................................. 49
4.2.5 Prefetch Size 的變化 .............................................................. 51
第五章 結論及未來工作 .............................................................................. 55
5.1 結論.................................................................................................... 55
5.2 未來工作 ............................................................................................ 55
參考文獻 ................................................................................................... 57


[1] N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Davis, M. Manasse and R.Panigrahy, "Design Tradeoffs for SSD Performance," in Proceedings of Annual Technical Conference, CA, USA, 2008.

[2] R. Appuswamy, D. C. v. Moolenbroek and A. S. Tanenbaum, "Integrating Flash-based SSDs into the Storage Stack," in Proceedings of Mass Storage Systems and Technologies Conference, Monterey, California, 2012.

[3] L. A. D. Bathen and B. S. Gill, "AMP: Adaptive Multi-stream Prefetching in a Shared Cache," in Proceedings of File and Storage Technologies Conference, San Jose,CA, 2007.

[4] D. P. Bovet and M. Cesati, Understanding the Linux Kernel, 3rd Edition, 3 ed., O''Reilly, 2005.

[5] M.Brain,"HowStuffWorks,"March2013.[Online].Available: http://computer.howstuffworks.com/hard-disk.htm.

[6] F. Chen, X. Ding and S. Jiang, "Exploiting Disk Layout and Block Access History for I/O Prefetch," in Proceedings of Advanced Operating Systems and Kernel Applications: Techniques and Technologies, IGI Global, 2009, pp. 201-216.

[7] S. Y. Liao, "A Data Caching Scheme for Hybrid Hard Drives," 2010.

[8] M. KerrisK, The Linux Programming Interface, 1 ed., No Starch Press, 2010.

[9] Y. Klonatos, T. Makatos, M. Marazakis, M. D. Flouris and A. Bilas, "Azor: Using Two-level Block Selection," in Proceedings of Networking, Architecture and Storage (NAS) Conference, Dalian, Liaoning, 2011.

[10] L. Lin, Y. Zhu, J. Yue, Z. Cai and B. Segee, "Hot Random Off-loading: A Hybrid Storage System With Dynamic Data Migration," in Proceedings of Modeling, Analysis&SimulationofComputerandTelecommunicationSystems (MASCOTS) Conference, Singapore, 2011.

[11] R. Love, Linux Kernel Development, 3 ed., Addison-Wesley Professional, 2010.

[12] J. M. Liu, "Design and Implementation of a Data Prefetching Scheme for Hybrid Storage," 2013.

[13] X. Shi and D. Feng , "ASEP: An Adaptive Sequential Prefetching Scheme for Second-level Storage System," Journal of Computers, pp. 1853-1864, August2012.

[14] A. J. Uppal, R. C. Chiang and H. H. Huang, "Flashy Prefetching for High-Performance Flash Drives," in Proceedings of Mass Storage Systems and Technologies Conference, Monterey, California, 2012.

[15] F. Wu, "Sequential File Prefetching in Linux," in Advanced Operating Systems and Kernel Applications: Techniques and Technologies, Y. Wiseman and S. Jiang,Eds., IGI Global, 2009, pp. 217-236.

[16] F. Wu, H. Xi and J. Li, "Linux readahead: less tricks for more," in Proceedings of the Linux Symposium, Ottawa, Ontario,Canada, 2007.

[17] Q. Zhu, . E. Gelenbe and Y. Qiao, "Adaptive prefetching algorithm in disk controllers," Performance Evaluation, pp. 382-395, May 2008.

[18] "Flashcache," [Online]. Available: https://github.com/facebook/flashcache/.

[19] "IBM DevelopeWorks cn," [Online]. Available: http://www.ibm.com/developerworks/cn/linux/l-devmapper/.

[20] "Postmark," [Online]. Available: http://postmarkapp.com/.

[21] "WikiPedia," [Online]. Available: http://zh.wikipedia.org/.

[22] A.Huang,"ADRIAN''SBLOG,"1932010.[Online].Available: http://adrianhuang.blogspot.tw/.

[23] S. Jiang, X. Ding, Y. Xu and K. Davis, "A Prefetching Scheme Exploiting both Data Layout and Access History on Disk," in ACM Transactions on Storage, August 2013.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top