Efficient Data Access Management over Flash-Memory Storage Systems

快閃記憶體已經成為嵌入式儲存系統一個相當好的選擇，基於它特別的硬體特性，既有的儲存系統設計並不能直接應用在快閃記憶體上，所以這幾年來，如何在快閃記憶體儲存系統上提供有效率的資料存取方法已經變成一個很重要的研究方向。 本論文首先探討小範圍修改對於快閃記憶體儲存系統的效能影響，由於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.Contents 1 Introduction 1 1.1 Introduction 1 1.2 Thesis Organization 3 2 Related Work 4 2.1 Flash-Memory Characteristics 4 2.2 Flash-Memory Managements 5 2.3 Previous Work 6 3 An Efficient B-Tree Layer Implementation for Flash-Memory Storage Systems 7 3.1 Motivation 7 3.2 The Design and Implementation of BFTL 9 3.2.1 Overview 9 3.2.2 The Physical Representation of a B-Tree Node: The Index Units 11 3.2.3 The Commit Policy 12 3.2.4 The Node Translation Table 13 3.3 System Analysis 15 3.4 Performance Evaluation 17 3.4.1 Experiment Setup and Performance Metrics 18 3.4.2 Performance of B-Tree Index Structures Creation 18 3.4.3 Performance of B-Tree Index Structures Maintenance 21 3.4.4 Performance of B-Tree Index Structures Search 22 3.4.5 The Size of the Reservation Buffer and the Energy Consumption Issues 23 3.4.6 Performance for Different Bounds 24 3.4.7 Performance for Different Fanouts 25 3.5 Summary 26 4 Efficient Initialization and Crash Recovery for Log-based File Systems over Flash Memory 27 4.1 Motivation 27 4.2 A Log-based Method for Flash-Memory File Systems 28 4.2.1 Overview 28 4.2.2 The Log-Record Manager 30 4.2.3 The Logger 33 4.2.4 Efficient Crash Recovery 36 4.3 Performance Evaluation 39 4.3.1 Experimental Setup and Performance Metrics 39 4.3.2 Different Append Ratios 40 4.3.3 Different Bu®er Sizes 41 4.3.4 Crash Recovery 41 4.4 Summary 42 5 A Space-Efficient Caching Mechanism for Flash-Memory Address Translation 43 5.1 Motivation 43 5.2 A Space-Efficient Caching Mechanism 46 5.2.1 Overview 46 5.2.2 Data Structures: Translation Node / Translation Unit 47 5.2.3 Manipulations of Translation Node / Translation Unit 48 5.2.4 A Replacement Strategy 51 5.3 Performance Evaluation 54 5.3.1 Experimental Setup and Performance Metrics 54 5.3.2 Performance Improvement and Overhead 55 5.4 Summary 58 6 Conclusion 59 Bibliography 6