在今日的儲存系統中，檔案(file)的存取，即檔案系統(file system)是最常見的應用；而可靠度(reliability)於儲存系統中一向扮演著重要的角色。過去，人們使用了許多方法來提升儲存系統的可靠度，例如硬碟與光儲存媒體區塊上之檢查碼(checksum)，以及廣為人知的磁碟陣列系統(RAID)。雖然這些做法的確達成錯誤容忍的效果，成功地提升可靠度，但皆忽略其應用於檔案系統之事實，而未從檔案的角度來處理此一問題。其結果是，無論檔案的重要性與否，在同一系統下，皆受相同的處理(例如相同數量之複製備份)。不但欠缺彈性，且在無形中造成許多浪費。
針對這些問題，本論文提出一個新的架構。此架構將從檔案的角度來處理可靠度的問題。目的是使不同的檔案可以擁有不同的可靠度設定，以增加彈性、減少可能的浪費。為了達成此目的，我們將修改Linux作業系統之中的虛擬檔案系統(VFS)層，藉此定義檔案可靠度之相關操作，並提供底層檔案系統模組實作檔案可靠度相關功能所需之介面。
此外，我們亦提出一個修改過的Ext2檔案系統，作為基於新架構之檔案系統範例。該Ext2檔案系統將對不同的可靠度層級進行定義，並對歸屬於各層級之檔案施予不同之的保護措施，如：同位元檢查(parity)與不同編碼率之里德所羅門錯誤檢查碼(Reed-Solomon Error Correcting Code)，以達成上述彈性調整之目的。

This work presents a new scheme of reliability mechanism in storage systems. The new scheme defines reliability and protects data in the scope of file, which is very different from traditional strategies, which protect data in the scopes of storage block or the whole device. The scheme provides the possibility to store highly reliable files and normal ones under the same file system, increasing flexibilities but decreasing costs of storage systems. To implement this scheme, Linux virtual file system (VFS) layer has been modified to perform reliability related operations during I/O calling paths and provide new interfaces for file systems to define their own reliability methods. A modified Ext2 file system with different levels of reliability has also been built as an example design of the new scheme. Depending on reliability levels, files in the example design are protected by parity check and Reed-Solomon Code of different code rates, which incur different overheads.

Abstract i
Contents iv
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Background and Related Works 4
2.1 Brief Introduction to Linux Virtual File System (VFS) . . . . . . . . . . . . 4
2.2 File System Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 File-wise Reliability Scheme 9
3.1 The Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 User Space vs. Kernel Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Implementation Details of File-wise Reliability . . . . . . . . . . . . . . . . . 13
3.3.1 Recording and Conguration of Reliability Levels . . . . . . . . . . . 13
3.3.2 Fault-tolerance of File Contents . . . . . . . . . . . . . . . . . . . . . 14
3.4 Example: Modied Ext2 File System . . . . . . . . . . . . . . . . . . . . . . 18
3.4.1 Design of Fault-Tolerance . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4.2 Mapping between VFS layer and the File System Driver . . . . . . . 24
4 Evaluations 27
4.1 Experiment Environment and Methodology . . . . . . . . . . . . . . . . . . . 27
4.2 Modied VFS Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.1 Kernel Image Sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2.2 The Read and Write Performances . . . . . . . . . . . . . . . . . . . 29
4.3 Modied Ext2 File System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.3.1 Performance of Setting Reliability Levels . . . . . . . . . . . . . . . . 29
4.3.2 Performance of Reliable Read Operation (Functionext2 checkpage()) . 32
4.3.3 Performance of Transparent Recovery (Function ext2 recoverpage()) . 33
4.3.4 Setting Reliability Levels on Real System Directories . . . . . . . . . 34
5 Conclusion and Future Work 36
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Bibliography 40

[1] D. A. Patterson, G. Gibson, and R. H. Katz, "A case for redundant arrays of inexpensive
disks (RAID)," in SIGMOD '88: Proceedings of the 1988 ACM SIGMOD international
conference on Management of data. New York, NY, USA: ACM, 1988, pp. 109-116.
[2] E. Pinheiro, W.-D. Weber, and L. A. Barroso, "Failure trends in a large disk drive
population," in FAST '07: Proceedings of the 5th USENIX conference on File and
Storage Technologies. Berkeley, CA, USA: USENIX Association, 2007, pp. 2-2.
[3] E. Zadok and J. Nieh, "FiST: a language for stackable le systems," in ATEC '00: Proceedings of the annual conference on USENIX Annual Technical Conference. Berkeley,
CA, USA: USENIX Association, 2000, pp. 5-5.
[4] J. S. Heidemann and G. J. Popek, "File-system development with stackable layers,"
ACM Trans. Comput. Syst., vol. 12, no. 1, pp. 58{89, 1994.
[5] N. Joukov, A. M. Krishnakumar, C. Patti, A. Rai, S. Satnur, A. Traeger, and E. Zadok,
\RAIF: Redundant Array of Independent Filesystems," in MSST '07: Proceedings of the 24th IEEE Conference on Mass Storage Systems and Technologies. Washington,
DC, USA: IEEE Computer Society, 2007, pp. 199-214.
[6] H. S. Gunawi, V. Prabhakaran, S. Krishnan, A. C. Arpaci Dusseau, and R. H. Arpaci
Dusseau, \Improving le system reliability with I/O shepherding," in SOSP '07: Pro-
ceedings of twenty-rst ACM SIGOPS symposium on Operating systems principles. New
York, NY, USA: ACM, 2007, pp. 293-306.
[7] M. D. Flouris and A. Bilas, "Violin: A Framework for Extensible Block-Level Storage,"
in MSST '05: Proceedings of the 22nd IEEE / 13th NASA Goddard Conference on Mass
Storage Systems and Technologies. Washington, DC, USA: IEEE Computer Society,
2005, pp. 128-142.
[8] J. Guerra, L. Useche, M. Bhadkamkar, R. Koller, and R. Rangaswami, \The case for
active block layer extensions," SIGOPS Oper. Syst. Rev., vol. 42, no. 6, pp. 3-9, 2008.
[9] R. Rivest, \The MD5 Message Digest Algorithm, Request for Comments (RFC)1321,"
1992.
[10] P. Pavan, R. Bez, P. Olivo, and E. Zanoni, \Flash memory cells-an overview," Proceed-
ings of the IEEE, vol. 85, no. 8, pp. 1248 {1271, Aug. 1997.
[11] S. Aritome, R. Shirota, G. Hemink, T. Endoh, and F. Masuoka, \Reliability issues of flash memory cells," Proceedings of the IEEE, vol. 81, no. 5, pp. 776 {788, May 1993.
[12] C. Dunn, C. Kaya, T. Lewis, T. Strauss, J. Schreck, P. He
ey, M. Middendorf, and
T. San, \Flash EPROM disturb mechanisms," in Reliability Physics Symposium, 1994.
32nd Annual Proceedings., IEEE International, 11-14 1994, pp. 299 -308.
[13] N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Davis, M. Manasse, and R. Panigrahy,
\Design tradeos for SSD performance," in ATC'08: USENIX 2008 Annual Technical
Conference on Annual Technical Conference. Berkeley, CA, USA: USENIX Association,
2008, pp. 57-70.
[14] Thomas Gleixner, \Reed-Solomon Library Programming Interface," 2004. [Online].
Available: http://www.kernel.org/doc/htmldocs/librs.html
[15] Lisa Hellerstein, Garth A. Gibson, Richard M. Karp, Randy H. Katz, and David A. Patterson,
\Coding Techniques for Handling Failures in Large Disk Arrays," Algorithmica,
Tech. Rep., 1988.
[16] S. B. Wicker, Reed-Solomon Codes and Their Applications. Piscataway, NJ, USA:
IEEE Press, 1994.