快閃記憶體儲存系統之有效率資料存取管理

Efficient Data Access Management over Flash-Memory Storage Systems

吳晉賢(Chin-Hsien Wu)

指導教授 ： 郭大維

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2006年)

https://doi.org/10.6342/NTU.2006.00134

摘要

快閃記憶體已經成為嵌入式儲存系統一個相當好的選擇，基於它特別的硬體特性，既有的儲存系統設計並不能直接應用在快閃記憶體上，所以這幾年來，如何在快閃記憶體儲存系統上提供有效率的資料存取方法已經變成一個很重要的研究方向。

本論文首先探討小範圍修改對於快閃記憶體儲存系統的效能影響，由於B-Tree是相當普遍的資料結構，我們首先選擇其為主要探討的對象，我們提出了一個方法可以有效率處理因B-Tree所產生的小範圍修改跟寫入的效能降低問題，一系列的實驗結果也顯示出我們方法的效率。論文第二個部分係針對快閃記憶體管理上一個很重要的可靠性問題，我們提出一個以紀錄為基礎(log-based)的方法用來加速檔案系統初始化以及系統錯誤恢復，我們以一個著名的快閃記憶體檔案系統(YAFFS)作為我們工作評估的的系統平台。論文第三個部分探討快閃記憶體上的效率問題，我們提出一個以搜尋樹為基礎的快取機制，用來加速目前設計上的位址轉換效率，一個低時間複雜度的置換策略也被提出來監控目前經常被存取的邏輯區塊位址。在對於快閃記憶體轉換層 (例如NFTL)實驗上，這個快取機制跟置換策略確實有效率地降低許多的位址轉換時間。

關鍵字

快閃記憶體 ； 儲存系統 ； 檔案系統 ； 嵌入式系統

並列摘要

Flash memory has become an excellent alternative for the storage-system designs of embedded systems and consumer electronics. Due to its very distinct characteristics, many designs for existing storage systems could not be directly applied to flash-memory storage systems. How to provide efficient data access management over flash-memory storage systems has become important research topics in recent years.

This work first starts with the study of small-write problems over flash-memory storage systems. B-Tree index structures are targeted because they are extremely popular in the organization of data. In this work, we propose a very different approach which can efficiently handle fine grained updates/modifications caused by B-Tree index access over flash memory. The results were evaluated by a series of experiments to demonstrate the effectiveness of the proposed approach. The second part of the thesis aims at one very essential issue in flash-memory management, i.e., the reliability problem. A log-based methodology is proposed for the acceleration of mounting and crash recovery for flash-memory file systems. A system prototype based on a well-known flash-memory file system YAFFS was implemented with performance evaluation. The third part of the thesis is on the performance issue, that is another critical issue beside reliability. We propose a search tree-like caching mechanism to improve the performance of existing designs for efficient address translation. A replacement strategy with a low time complexity is presented to monitor the access status of recently used LBA's. The proposed caching mechanism and replacement strategy are shown being highly effective in the reducing of the address translation time over popular translation layer designs, such as NFTL, where realistic workloads are adopted for experiments.

並列關鍵字

Flash Memory ； Storage Systems ； File Systems ； Embedded Systems

參考文獻

[4] Intel Corporation, LFS File Manager Software: LFM".

[5] Aleph One Company, Yet Another Flash Filing System".

[6] Intel Corporation, Understanding the Flash Translation Layer(FTL) Speci‾ca-

[13] R. Bayer, and E. M. McCreight: Organization and Maintenance of Large Ordered

[14] D. Comer, The Ubiquitous B-Tree," ACM Computing Surveys, Vol. 11, No. 2,