Linux中基于连续块的B+树文件系统的设计与实现-智能与分布计算实验室

Linux中基于连续块的B+树文件系统的设计与实现

姓名	聂岚
论文答辩日期	2002.05.10
论文提交日期	2004.08.18
论文级别	硕士
中文题名	Linux中基于连续块的B+树文件系统的设计与实现
英文题名	Design and Implimentation of File System Based on Extent and Orgnized by B+ Tree in Linux
导师1	卢正鼎
导师2
中文关键词	Linux;文件系统;连续块;inode节点;B+树
英文关键词	Linux;file system;extent;inode;B+ tree
中文文摘	作为一种很有发展前途的操作系统，Linux一出现就受到了企业服务器操作系统市场的青睐，它的安全性和稳定性使其在该领域一枝独秀，市场占有率一直保持强势增长。访问速度和I/O效率是衡量服务器性能的重要标准。作为目前Linux的主流文件系统，Ext2文件系统在处理大文件和巨型目录结构时有一定的局限性。究其原因，是由它的基本组织结构决定的,它是为中小型文件量身定做的，采用传统的线性表和多级指针索引静态地组织数据，灵活性和效率都不高，随着海量存储器，磁盘阵列的出现，Ext2文件系统的管理已经显得力不从心。为了从根本上改变这种现状，实现对文件的快速高效访问，加强对大型文件系统的支持和管理，从改变文件系统的基本布局结构入手，提出并实现了一种基于平衡块的B+树文件系统(EBFS),从三方面对文件系统的性能进行扩展：一方面，采用B+树来组织大文件数据，磁盘空闲块以及目录项。使用B+树索引结构，对于大型文件和目录对象而言，访问速度有了明显提高，时间复杂度从o(n)提升到o(log n)；而且B+树结构也扩充了文件系统的寻址空间，由原来的4GB增长到512万亿字节；第二方面，用连续块分配策略替代传统的块分配策略，减少了分配时的I/O次数，保证文件数据尽量连续存储，减少了外部碎片，提高了文件顺序访问的效率；第三方面，对于小型文件，直接将文件数据存放在inode节点的内嵌数据区，提高小文件I/O性能的同时减少了内部碎片。 EBFS文件系统已成功试用于我们同中国船舶重工集团公司709研究所合作开发的国防预研项目??分布式实时操作系统DR-Linux中，该系统已通过国家有关部门鉴定，具有良好的应用前景。
英文文摘	As a promising operation system, Linux was fully favored by the market of enterprise server operation system by its advantage in security and stability Linux is peerless, which made it much superior than other operation systems and its occupancy keeps increasing in the server market. Access speed and I/O efficiency are the important standards in judging the server’s performance. As the main file system of current Linux OS, Ext2 file system has some drawbacks in processing the big files and giant bibliographic structures. These problems are determined by Ext2’s internal structure. The Ext2 file system was designed for the middle or small files, it adopted traditional linear list and multilevel pointers index structure to organize data statically, so its flexibility and efficiency are not very ideal. With the appearance of the mass storage and disc array, the management ability of Ext2 file system is not equal to its ambition. In order to change these situations, implement the rapid access to files, strengthen the support and management for lage-scale file system, we bring forward and implement a file system based on extent and organized by B+ tree(EBFS), which can expand the functions of file system in three aspects: firstly, using B+ tree to organize the large file datum, free blocks and directory entries. By B+ tree indexing struture, the access speed of large files and directorys is raised obviously, the time complexity is improved from o (n ) to o(log n). In the meantime, the address ability is expanded from 4GB to 512 trillion. Secondly, the traditional block allocation policy is replaced by the extent allocation policy, which can reduce the I/O times in allocation, keep the file datum stored spatially,lessen the external fragmention and improve the efficiency of access.Thirdly,to small file, we can store the file datum directly in the inline data field of the inode ,which can improve the I/O performance of small file and lessen internal fragmention. EBFS shows great performance on its test run in DR-Linux system, a high-tech project developed by our research group and The State Exploration Research Institute of ship industy, the system has passed the authentication and has a nicer market foreground.