臺灣博碩士論文加值系統

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

本論文首先探討小範圍修改對於快閃記憶體儲存系統的效能影響，由於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 61

Bibliography
[1] R. Bez, E. Camerlenghi, A. Modelli, and A. Visconti, Introduction to Flash Mem-
ory," Proceedings of The IEEE, Vol. 91, No. 4, April 2003.
[2] D. Woodhouse, Red Hat, Inc. JFFS: The Journalling Flash File System".
[3] http://www.linux-mtd.infradead.org/tech/JFFS3design/
[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-
tion".
[7] Intel Corporation, Software Concerns of Implementing a Resident Flash Disk".
[8] Intel Corporation, FTL Logger Exchanging Data with FTL Systems".
[9] U.S. Pat. No. 5,404,485 FLASH FILE SYSTEM"
[10] U.S. Pat. No. 5,937,425 FLASH FILE SYSTEM OPTIMIZED FOR PAGE-MODE
FLASH TECHNOLOGIES"
[11] Compact Flash Association, CompactF lashTM 1.4 Speci‾cation," 1998.
[12] SSFDC Forum, "SmartMediaTM Speci‾cation", 1999.
[13] R. Bayer, and E. M. McCreight: Organization and Maintenance of Large Ordered
Indices," Acta Informatica, Vol. 1, 1972, pp. 173-189.
[14] D. Comer, The Ubiquitous B-Tree," ACM Computing Surveys, Vol. 11, No. 2,
1979, pp. 121-137.
[15] M. Rosenblum, and J. K. Ousterhout, The Design and Implementation of a Log-
Structured File System," ACM Transactions on Computer Systems, Vol 10, No. 1,
1992, pp. 26-52.
[16] T. W. Kuo, J. H. Wey, and K. Y. Lam, Real-Time Data Access Control on B-Tree
Index Structures," the IEEE 15th International Conference on Data Engineering
(ICDE 1999), Sydney, Australia, March 1999, pp. 458-467.
[17] M. Freeston, A General Solution of the n-dimensional B-Tree Problem," SIGMOD
Conference, San Jose, May 1995, pp. 80-91.
[18] H. Yokota, Y. Kanemasa, and J. Miyazaki: Fat-Btree: An Update-Conscious Par-
allel Directory Structure," the IEEE 15th International Conference on Data Engi-
neering (ICDE 1999), Sydney, Austrialia, March 1999, pp. 448-457.
[19] B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer: An Asymptotically
Optimal Multiversion B-Tree," VLDB Journal, Vol. 5, No. 4, 1996, pp. 264-275.
[20] Ramakrishnan and Gehrke, Database Management Systems," Published by
McGraw-Hill, 2003.
[21] A. Kawaguchi, S. Nishioka, and H. Motoda, A Flash-Memory Based File System,"
USENIX Technical Conference on Unix and Advanced Computing Systems, New
Orleans, LA, January 1995, pp. 155-164.
[22] H. J. Kim and S. G. Lee, A New Flash Memory Management for Flash Storage
System," Twenty-Third Annual International Computer Software and Applications
Conference, Phoenix, Arizona, October 1999, pp. 284-289.
[23] L. P. Chang, and T. W. Kuo, An Adaptive Striping Architecture for Flash Mem-
ory Storage Systems of Embedded Systems," The 8th IEEE Real-Time and Embed-
ded Technology and Applications Symposium (RTAS 2002), San Jose, California,
September 2002, pp. 187-196
[24] M. Wu, and W. Zwaenepoel, eNVy: A Non-Volatile, Main Memory Storage Sys-
tem," Proceedings of the 6th International Conference on Architectural Support for
Programming Languages and Operating Systems (ASPLOS 1994), October 1994,
pp. 86-97.
[25] L. P. Chang, T. W. Kuo, and S. W. Lo, Real-Time Garbage Collection for Flash-
Memory Storage Systems of Real-Time Embedded Systems," ACM Transactions on
Embedded Computing Systems, Volume 3 , Issue 4, 2004.
[26] C. H. Wu, T. W. Kuo, and C. L. Yang, 2004, Energy-E±cient Flash-Memory
Storage Systems with Interrupt-Emulation Mechanism," accepted and to appear
in the IEEE/ACM/IFIP International Conference on Hardware/Software Codesign
and System Synthesis, Stockholm, Sweden, September, 2004, pp. 134-139.
[27] K. S. Yim, J. Kim, and K. Koh, A Fast Start-Up Technique for Flash Memory
Based Computing Systems," To appear in Proceedings of the ACM Symposium on
Applied Computing (SAC''05), Santa Fe, USA, March 2005, pp. 843-849.
[28] J. Kim, J. M. Kim, S. H. Noh, S. L. Min, and Y. Cho, A Space-E±cient Flash
Translation Layer for Compact-Flash Systems," IEEE Transactions on Consumer
Electronics, Vol. 48, No. 2, MAY 2002.
[29] F. Douglis, R. Caceres, F. Kaashoek, K. Li, B. Marsh, and J. A. Tauber, Stor-
age Alternatives for Mobile Computers," in Proceedings of the 1st Symposium on
Operating Systems Design and Implementation (OSDI), Monterey, CA, November
1994, pp. 25-37.
[30] L. P. Chang, and T. W. Kuo, A Dynamic-Voltage-Adjustment Mechanism in Re-
ducing the Power Consumption of Flash Memory for Portable Devices," IEEE Con-
ference on Consumer Electronic (ICCE 2001), LA. USA, June 2001, pp. 218-219.
[31] C. Park, J. Kang, S. Y. Park, J. Kim, Energy-Aware Demand Paging on NAND
Flash-based Embedded Storages," ISLPED, Newport Beach, CA, USA, August
2004, pp. 338-343.
[32] C. Park, J. Seo, S. Bae, H. Kim, S. Kim, and B. Kim, A Low-cost Memory Ar-
chitecture with NAND XIP for Mobile Embedded Systems," Proceedings of the
1st IEEE/ACM/IFIP international conference on Hardware/software codesign and
system synthesis, October 2003, Newport Beach, CA, USA, pp. 138-143.
[33] M. L. Chiang, C. H. Lee, and R. C. Chang, Using Data Clustering to Improve
Cleaning Performance for Flash Memory," SoftwareXPractice and Experience, Vol-
ume 29 , Issue 3, March 1999, pp. 267-290.
[34] E. Levy and A. Silberschatz, Incremental Recovery in Main Memory Database
Systems," IEEE Transactions on Knowledge and Data Engineering, Vol. 4, No. 6,
1992, pp. 529-540.
[35] X. Li and M. H. Eich, Post-crash Log Processing for Fuzzy Checkpointing Main
Memory Databases." In Proc. 9th IEEE Int. Conf. on Data Engineering, Vienna,
Austria, April 1993, pp. 117V124.
[36] R. B. Hagmann, A Crash Recovery Scheme for a Memory-resident Database Sys-
tems." IEEE Transactions on Computer, Vol. 35, No. 9, 1986, pp. 839-843.
[37] K. Salem and H. Garcia-Molina, Checkpointing Memory-resident Databases." In
Proc. 5th IEEE Int. Conf. on Data Engineering, Los Angeles, CA, February 1989,
pp. 452-462.
[38] D. Lee and H. Cho, Checkpointing Schemes for Fast Restart in Main Memory
Database Systems." In 1997 IEEE Paci‾c Rim Conf. on Communications, Comput-
ers, and Signal Processing, Victory, BC, July 1997, pp. 663-668.
[39] T. W. Kuo, Y. H. Hou, and K. Y. Lam, The Impacts of Write Through Procedures
and Checkpointing on Real-Time Concurrency Control," Computer Journal (SCI),
Vol. 46, No. 2, 2003, pp. 174-192.
[40] Alan Jay Smith, Cache Memories," ACM Computing Surveys (CSUR), Vol. 14,
No. 3, September 1982, pp. 473-530.
[41] John L. Hennessy and David A. Patterson, Computer Architecture : A Quantita-
tive Approach," San Francisco, CA : Morgan Kaufmann Publishers.
[42] Abraham Silberschatz, and Peter B. Galvin, Operating System Concepts,"
Addison-Wesley Publishing Company.
[43] J. Bradley Chen, Anita Borg, and Norman P. Jouppi, A Simulation-Based Study of
TLB Performance," Proc. of the 19th annual international symposium on Computer
architecture, Queensland, Australia, May 1992, pp. 114-123.
[44] J. Choi, J. Lee, S. Jeong, S. Kim and C. Weems. A Low Power TLB Structure for
Embedded Systems." IEEE Computer Society Technical Committee on Computer
Architecture (TCCA), Vol. 1, Issue 1, Jan 2002, pp. 3.
[45] Samsung Electronics. NAND Flash-memory Datasheet and SmartMedia Data Book,
2002.
[46] Intel Corporation, Flash File System Selection Guide".
[47] http://www.samsung.com/Products/Semiconductor/Flash/index.htm
[48] M. R. Garey, and D. S. Johnson, Computers and Intractability", 1979.
[49] Vijay V. Vazirani, Approximation Algorithm," Springer publisher, 2001.