中国科学技术大学学位论文原创性和授权使用声明.docVIP

中国科学技术大学硕士学位论文文件系统中元数据更新关键技术的研究作者姓名：韩春晓学科专业：计算机应用导师姓名：龚育昌 教授完成时间：2008-5-9Research of Key Techniques in File System Meta-data UpdateUniversity of Science and Technology of ChinaA dissertation for masters degreeAuthors Name：Han ChunxiaoSpeciality：Computer ApplicationSupervisor：Prof. Gong Yuchang Finished Time：May 9, 2008中国科学技术大学学位论文原创性和授权使用声明本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。本人授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密的学位论文在解密后也遵守此规定。作者签名：_年 月 日摘 要摘 要文件系统是存储系统的重要组成部分之一，随着用户对数据存储可靠性要求的不断提高，文件系统可靠性的研究也越来越受到重视。元数据更新是文件系统设计的核心问题之一。元数据更新机制决定了文件系统在崩溃的情况下能否恢复到一致的状态。现有的元数据更新技术主要有日志、日志结构化及软更新。这些元数据更新技术在提高文件系统可靠性的同时，也导致了文件系统I/O性能的损失。本文主要针对基于磁盘的日志文件系统和采用日志结构化设计的Flash文件系统，主要贡献是分析现有元数据更新机制中存在的I/O性能瓶颈并提出了改进方案，然后通过实验量化验证了分析的正确性和改进方案对I/O性能的提升，所做的主要工作包括：1， 以ext3为例详细介绍和分析了日志文件系统的设计和实现，针对ext3日志功能设计和实现中的不足，提出了相应的改进方案以消除性能瓶颈，并通过实验数据验证了分析的正确性和改进的有效性；2， 针对Flash文件系统中元数据更新引起的损耗均衡问题，以JFFS2 文件系统为例详细介绍和分析了日志结构化的设计思想及其在Flash文件系统中的应用，以UBIFS文件系统为例介绍和分析了损耗均衡算法的设计与实现；3， 通过实验数据验证了关于损耗均衡对系统I/O性能的影响的分析，提出了一种综合考虑Flash可用空间以及系统I/O负载的自适应损耗均衡算法，并通过实验数据验证了分析的正确性和算法改进的有效性。关键词: 文件系统 元数据更新 日志 Flash文件系统 损耗均衡VIIAbstractFile System is one of the most crucial components of Storage System. The reliability of File System becomes hot topic in recent years due to the growing demand of data integrity in Storage System. Meta-data Update is the key problem to ability of file system to quickly and reliably recover from corruption. Existing meta-data update mechanisms include journaling file system, log-structured file system and soft update. The defect of these techniques is that they greatly enhance file system reliability at the expense of I/O performance losses. Works done in this thesis mainly focus on disk-based journaling file system and log-structured Flash file system, the contributions of this thesis are that I/O bottlenecks in existing meta-data update mechanisms are analyzed, improvement schemes are proposed to fix these I/O bottlenecks. Work involved in this thesis includes:1, a typical journaling file system-ext3 is analyzed, and several improvement schemes are proposed to overcome the I/O bottlenecks in original design and implementation of ext3 journal mechanism. The correctness of analysis and effect of improvement schemes are confirmed by benchmark data; 2, Wear-leveling is a problem caused by meta-data update in Flash file system. The implementation of log-structured design in Flash File System is introduced and analyzed by using JFFS2 file system as an example. The design and implementation of wear-leveling mechanism is introduced and analyzed by using UBIFS as an example; 3, the impact of wear-leveling on system I/O performance is analyzed and confirmed by benchmark data, a new adaptive wear-leveling algorithm is proposed and its improvement over existing algorithm is confirmed by benchmark data.Keywords: File System Meta-data Update Journaling Flash File System Wear-leveling表格目录目 录摘 要IAbstractII第 1 章绪论11.1引言11.2文件系统与元数据更新21.2.1本地文件系统中的元数据更新21.2.2Flash文件系统中的元数据更新31.2.3分布式文件系统中的元数据更新31.3相关研究41.3.1快速文件系统41.3.2日志文件系统51.3.3日志结构化文件系统51.3.4软更新61.4论文组织与主要工作7第 2 章基于磁盘的日志文件系统中的元数据更新82.1日志文件系统82.1.1日志文件系统的基本设计思想82.1.2日志文件系统的实现82.2ext3日志文件系统的磁盘布局与元数据92.2.1磁盘布局92.2.2元数据102.3ext3文件系统的日志功能112.4日志块设备层132.4.1日志记录142.4.2原子操作描述符142.4.3事务152.5ext3现有日志功能的不足162.6本章小结17第 3 章对ext3日志文件系统的改进与实现183.1对ext3磁盘块分配算法的改进与实现183.1.1问题分析183.1.2改进方案与实现203.1.3实验与分析233.2对ext3日志提交周期的改进与实现243.2.1问题分析243.2.2改进方案与实现253.2.3实验与分析273.3对ext3日志模式的改进与实现293.3.1问题分析293.3.2日志大小与日志模式313.3.3改进方案与实现323.3.4实验与分析343.4对日志事务粒度的改进与实现363.4.1问题分析363.4.2改进方案与实现373.4.3实验与分析383.5本章小结39第 4 章Flash文件系统中的元数据更新404.1Flash文件系统404.1.1Flash存储介质的特性404.1.2Flash文件系统设计的难点414.1.3基于Flash转换层的Flash文件系统424.2日志结构化文件系统434.2.1日志结构化文件系统的设计思想434.2.2日志结构化文件系统的实现444.2.3日志结构化文件系统的优点和不足444.3日志结构化在Flash文件系统中的应用454.3.1日志结构化的Flash文件系统464.3.2损耗均衡与垃圾回收484.3.3数据属性对损耗均衡和垃圾回收的影响504.4本章小结51第 5 章对Flash文件系统损耗均衡算法的改进与实现525.1UBIFS文件系统中的损耗均衡算法525.1.1头部数据525.1.2损耗均衡单元对物理擦除块的组织525.1.3保护机制和灵活的触发条件535.1.4UBI中损耗均衡的实现535.2损耗均衡对系统I/O性能的影响545.2.1实验环境545.2.2实验结果与分析555.3自适应的损耗均衡算法565.3.1算法设计565.3.2算法实现575.3.3实验与分析615.4本章小结61第 6 章总结与展望626.1总结626.2进一步工作626.2.1日志结构化的元数据626.2.2固态硬盘与元数据更新63参考文献64附 录68在读期间发表的学术论文与取得的研究成果69致 谢70插图目录图 11过去25年内CPU，内存，网络和磁盘的带宽和延迟的提升1图 12计算任务中CPU时间与I/O时间所占比例的变化1图 13 Google文件系统的设计架构4图 21 ext3文件系统的磁盘布局9图 22 ext3文件系统的寻址机制10图 23 ext3文件系统的日志文件构成11图 24 journal日志模式下追加写入涉及的日志操作12图 31 ext3写入操作中引起的磁盘寻道18图 32 日志存放在分区头部19图 33 日志存放在分区中部19图 34 基于文件数据属性预测的磁盘块分配算法设计框架21图 35 磁盘块分配算法的改进对I/O性能的提升24图 36 自适应的日志写回周期机制26图 37 ordered日志模式下日志提交周期对性能的影响28图 38 journal日志模式下日志提交周期对性能的影响28图 39 writeback日志模式下日志提交周期对性能的影响29图 310 ext3三种日志模式的不同30图 311 不同日志模式下日志大小对I/O性能的影响31图 312 自适应的日志模式设计框架33图 313 postmark测试中三种日志模式的性能35图 314 随机写负载下三种日志模式的I/O性能35图 315 自适应日志模式算法对I/O性能的提升35图 316事务粒度对并行性的影响36图 317 不同日志模式下事务粒度对性能的影响38图 318 日志粒度改进对I/O性能的提升39图 41基于Flash转换层的Flash文件系统设计42图 42 Flash转换层中虚拟扇区到物理扇区的映射43图 43 Spirit-LFS和FFS元数据更新操作的不同44图 44 JFFS2文件系统中的元数据和数据存储设计47图 45 Flash容量对JFFS2文件系统加载时间的影响48图 46 JFFS2文件系统的损耗均衡测试50图 51 自适应的损耗均衡算法设计框架57图 52 自适应的损耗均衡算法的I/O性能61表格目录表 31 静态数据预测模型21表 32 静态数据属性预测算法22表 33 实验环境23表 34 自适应的日志提交周期算法26表 35 实验环境27表 36 自适应日志模式算法实现中的数据结构33表 37 自适应的日志模式算法34表 38 日志事务粒度改进涉及的数据结构37表 39 日志事务粒度改进算法37表 51 实验环境55表 52 测试结果55表 53 改进的垃圾回收算法58第 6 章 总结与展望第 1 章 绪论1.1 引言近年来，随着半导体技术的快速发展，计算系统中的CPU、内存等子系统的性能提升非常迅速，例如一块芯片上集成的晶体管数量每年以40%-55%的速度增长，DRAM的容量每年以40%的速度增加。作为存储系统的主要组成部分之一的磁盘的容量每年也以60%左右的速度增加，但磁盘的I/O带宽和寻道时间的提升却比较缓慢(图 11 (Hennessy，Patterson，2006)。技术发展的不平衡导致存储子系统与其他子系统的性能差距越来越大。由计算机系统的Amdahl定律可知，一个子系统的改进对整个系统的性能提升受限于子系统的执行时间占整个执行时间的比例。CPU和内存等子系统性能的快速提升和磁盘子系统性能相对缓慢的增长使得计算系统由80年代之前的计算密集变为现在的I/O密集(图 12 (Burns，2007)，I/O子系统成为现代计算系统的最大性能瓶颈。71图 11过去25年内CPU，内存，网络和磁盘的带宽和延迟的提升图 12计算任务中CPU时间与I/O时间所占比例的变化同时，随着信息量的爆炸性增长，用户对存储系统的需求也在不断提高。新的存储技术如Flash存储技术(Toshiba，2006)和固态硬盘(Texas Memory Systems，2006)等的出现也为存储系统的设计提出了新的挑战。学术界和工业界都致力于研究低成本，高性能和高可靠性的存储系统，存储系统的相关研究成为近年来计算系统领域的最大热点。现代存储系统的研究热点主要有分布式海量存储、高效缓存机制、故障检测与恢复、高性能文件系统及可靠文件系统等。1.2 文件系统与元数据更新文件系统是存储系统的核心组成部分，负责向上层应用提供一个统一的编程接口和实现数据在存储介质上的存储。文件系统使得上层应用只需使用标准的编程接口如read、write即可实现对文件数据的可靠存取，而无需关心数据在底层的物理存储设备上的存储实现。过去近40年的文件系统研究主要集中在提升文件系统的性能，包括优化文件的磁盘布局以充分利用磁盘带宽和减少磁盘寻道，通过提高缓存效率减少对磁盘的I/O操作等。但随着存储系统的复杂性越来越高和数据量的快速增加，存储系统出现故障的几率也随之增加。因此，用户对数据存储可靠性的需求也越来越迫切，用户期望在系统出现故障的情况下仍可以不受影响的进行数据存取或者至少可以从故障中快速恢复并确保不会丢失数据。近年来文件系统可靠性已经成为存储系统的研究热点之一，其中元数据更新是文件系统可靠性研究中的核心问题之一。下面从文件系统可靠性的几个主要研究方向分别介绍元数据更新，分别是本地文件系统、Flash文件系统和分布式文件系统。本论文的工作主要针对本地文件系统和Flash文件系统中的相关问题展开研究。 1.2.1 本地文件系统中的元数据更新本地文件系统为了有效的存储数据，需要使用控制数据来管理数据在存储介质上的存取。这些用于组织用户数据的控制数据被称为元数据(meta-data)，也被称为“关于数据的数据”。以ext2 (Card，Tso，Tweedie，1994)文件系统为例，文件系统中的inode、超级块、块组描述符、文件间接块、inode位图与磁盘块位图都属于元数据。文件的某些操作涉及对多个元数据的修改，而这些元数据一般是存储在磁盘的不同位置，底层的磁盘驱动无法保证涉及多个磁盘块的写操作的原子性。如果元数据更新的过程中软硬件故障导致操作被中断，文件系统可能会因此崩溃。例如，ext2文件系统的文件删除操作分为3步：(1)删除文件在父目录中对应的目录项；(2)删除文件的inode并回收；(3)删除文件对应的数据块中的数据，并回收数据块。如果不限制元数据更新的顺序，则由于缓存机制和I/O调度的影响可能会出现如下情况：磁盘上文件的inode已被回收且被另外一个文件使用，而磁盘上文件的目录项还未删除，如果在此时系统出现故障，文件系统恢复后本应被删除的文件的目录项指向已属于另外一个文件的inode，导致文件系统处于不一致状态。因此元数据更新设计必须保证文件系统可以从故障中恢复到一致的状态。1.2.2 Flash文件系统中的元数据更新近年来Flash闪存在消费类电子产品和嵌入式系统中得到越来越广泛的应用，基于Flash存储技术的固态硬盘逐渐取代传统硬盘。相比传统的磁盘，Flash存储技术具有低耗能、抗震荡等诸多优点，但Flash的物理特性决定了其存在编程/擦除寿命有限、动态出现坏块和位反转、擦除后才可更新数据等固有的不足。传统的磁盘文件系统在设计上主要为磁盘的存取特性优化，如优化文件的磁盘布局以减少读写过程中的磁盘寻道，这种优化设计在不存在寻道时间的Flash存储介质中的效果并不明显。另外，磁盘文件系统中将频繁更新的元数据固定存放的做法会严重影响Flash的损耗均衡(CORSAIR，2007)。Flash存储技术的特点决定了Flash文件系统一般采用不同于传统磁盘文件系统的设计，以克服Flash存储技术固有的不足和充分利用Flash存储技术的优点。现代的主流Flash文件系统设计主要有两种：一种是基于Flash转换层(Intel，1998)的设计，基本思想是通过Flash转换层将Flash模拟为标准的块设备，然后在虚拟的块设备上运行传统的磁盘文件系统，Flash转换层负责解决Flash的损耗均衡，坏块管理等功能，采用这种设计的主要是商业Flash文件系统，如M-System的TrueFFS (M-Systems，2002)。另一种设计方案是直接在Flash的驱动程序MTD (Memory Technology Devices，2008)之上设计文件系统，一般采用日志结构化的设计思想以实现损耗均衡和保证文件系统的可靠性，采用这种设计的主要是开源的Flash文件系统，如JFFS1/2 (Red Hat，2003)、UBIFS(UBIFS，2008)、YAFFS1/2 (YAFFS，2008)等。1.2.3 分布式文件系统中的元数据更新现代分布式文件系统如Google File System (Ghemawat，2003)，Hadoop Distributed File System (Hadoop，2003)通常由成千上万个采用IDE/SATA等廉价硬盘的存储节点通过高速网络连接组成。采用廉价硬盘可以大大降低成本，但单个硬盘出现故障的概率很高。为了保证数据的存取不受硬件故障的影响，GFS将一份数据多份冗余存储到不同的节点，一个节点的故障不会导致数据丢失。为了提高存储系统的性能，GFS采用元数据和数据独立分开存储的设计，如图 13所示。一个GFS集群中的GFS master负责处理客户端的请求，master负责维护文件系统的名字空间和目录树的逻辑视图，并提供文件名到文件数据所在数据节点(chunkserver)的存储位置的映射。GFS数据节点(chunkserver)建立在本地的Linux文件系统之上，以chunk(典型大小为64M)为单位负责提供数据存储，不需要关心chunk的数据属于什么文件。一个典型的读写过程如下：客户端向master发出读写请求，包括文件名和请求数据在文件内部的偏移，master根据存储的元数据查找名字空间获得文件数据在存储节点上的位置并将其封装为消息返回给客户端。为了减轻GFS master节点的负载并防止GFS master节点成为系统性能的瓶颈，GFS master节点并不参与实际数据的传输。客户端根据收到的消息向存储节点发出数据存取请求，存储节点最后完成实际的I/O操作。图 13 Google文件系统的设计架构GFS采用的是单主节点的设计，主节点中主要存储3种元数据：文件和chunk的名字空间，文件到chunk的映射关系，chunk的多个备份的存储位置。为了提高性能，所有的元数据被缓存在内存中。为了提高可靠性，对名字空间和映射关系元数据的修改以操作日志(operation log)的形式存储到主节点的本地磁盘上并多份备份到远程机器上。采用日志使得主节点的状态可以被简单高效可靠的更新，同时可以迅速从故障中恢复到一致性状态。chunk的多个备份的存储位置信息并不永久存储在主节点中，而是由主节点查询数据节点获得。1.3 相关研究本节主要介绍元数据更新相关的研究现状。1.3.1 快速文件系统BSD4.2中的快速文件系统(Joy，1984)的设计影响了几乎所有的现代Unix-like文件系统。FFS在最早的Unix文件系统上做了很多改进，除了通过优化文件的磁盘布局来提升性能和增加软链接等新功能之外，对文件系统的可靠性也有贡献。如将超级块多份拷贝存放在磁盘的不同位置，以及以同步的方式将元数据更新按照依赖关系决定的顺序写入磁盘，保证文件系统在出现故障的情况下仍能通过fsck工具恢复到一致的状态。这种方法可以保证文件系统可靠性，但同步的元数据更新方式严重影响了系统的性能。1.3.2 日志文件系统日志文件系统借鉴了数据库中具有原子性的事务概念(Gray，1993)，将文件操作作为事务来处理。日志文件系统的基本思想是将文件操作涉及的元数据更新首先提交到事务日志，然后再将元数据的更新写回磁盘，从而确保在出现故障的情况下文件操作只可能存在已提交到日志和未提交到日志两种情况。对未提交到日志的情况，则取消操作。对已提交到日志的情况，则根据日志中相应的事务记录将元数据的更新写入磁盘，完成操作，从而保证了操作的原子性。日志文件系统的优点是设计清晰，允许多种灵活的实现，易于在已有的文件系统上增加日志功能，因此现代文件系统如JFS (Best，2000) (Best，2004)，XFS (Sweeney，1996) (Mostek，2000)，ReiserFS (Reiser，2004)，NTFS (Russinovich，2005)，ext3 (Tso，2002) (Tweedie，1998) (Tweedie，2000)均为日志文件系统。日志文件系统的主要不足是日志的引入增大了I/O开销，另外文件系统从故障回复时依赖日志本身的可靠性。本论文的第二章将以ext3为例详细分析日志文件系统并针对其不足做相应改进。1.3.3 日志结构化文件系统日志结构化文件系统(Rosenblum，1991) (Seltzer，1993)设计思想基于日志文件系统，但日志结构化文件系统直接将日志记录作为文件系统存储数据的基本单位，每次写入操作将新的元数据和数据作为日志记录追加写入日志，整个磁盘被看作是一个循环使用的逻辑日志。对数据的更新操作采用异地更新(write out of place)，而不是传统文件系统中的就地更新(write in place)。磁盘上不仅存储文件的当前有效数据及元数据，还会存储文件的过期无效数据和元数据。类似日志文件系统，日志结构化文件系统可以根据日志记录从故障中恢复到一致的状态。日志结构化文件系统最早被提出是为了解决文件系统的写效率低下的问题。日志结构化的设计使得所有的写操作都被组织为日志记录追加到日志尾部，对应到磁盘的操作为顺序写入，从而大大减少了磁盘寻道，将磁盘带宽的利用率从传统Unix文件系统的5%-10%提高到了70%。但日志结构化的设计决定了文件系统必须通过额外的垃圾回收操作清理过期无效数据占用的磁盘空间，日志结构化文件系统在磁盘空间使用率较高时性能会快速下降。另一方面，基于传统Unix文件系统的性能优化研究如簇读写(McVoy，1991)使得日志结构化文件系统的性能优势不再明显，最终日志结构化文件系统未能在磁盘文件系统中得到推广，仅在4.4BSD (McKusick，1996)和NetBSD (NetBSD，2008) (Schroder，2002)等系统中得到实现。但日志结构化设计的固有优点使得其在Flash文件系统中得到了广泛应用。1.3.4 软更新软更新(Soft Update)技术(McKusick，1999) (McKusick，2002) (Ganger，1994)的设计出发点主要是针对日志文件系统的两个缺点：(1)日志文件系统依赖日志的正确性来恢复文件系统，如果日志本身出错，则很难恢复文件系统；(2)日志文件系统中的元数据需要两次写入操作，增加了I/O开销。软更新的主要思想是通过在内存中跟踪元数据更新的依赖关系来决定元数据写回的顺序，从而延迟写回操作。软更新确保写回磁盘的元数据可以保证文件系统的一致性，使得上层应用和磁盘得到的是同一个磁盘块的两份不同内容，上层应用程序得到的是最新的有效数据，而磁盘则保证每次写入的数据都是能够满足文件系统一致性的过期数据。软更新的实现主要基于以下3个原则：(1)从不指向一个未初始化的元数据，如一个inode在被目录项引用之前，必须被初始化；(2)必须在一个资源的引用全部消失的情况下使用这个资源，如inode对一个磁盘块的指针必须被清空后，这个磁盘块才可以被其他inode使用；(3)从不在指向资源的新指针未被设定之前清空指向资源的旧指针，如在重命名操作中，在新的目录项被成功写入磁盘之前，旧的目录项不会被清空。软更新技术的优点是避免了日志文件系统的两次元数据更新写回操作，同时不需要日志占用的磁盘空间。但其缺点是设计较为复杂，跟踪元数据更新的依赖关系导致实现比较困难，维护依赖关系需要消耗额外的内存，因此只在FreeBSD(FreeBSD，2008) (McKusick，2004)和OpenBSD(OpenBSD，2008)等系统中得到应用。相关研究(Seltzer，2000)详细分析并评测了软更新与日志技术，结论是软更新与日志在多数应用中性能相当。1.4 论文组织与主要工作本论文的内容组织如下：第一章绪论简要介绍了论文的研究背景和研究出发点，引出对研究问题的阐述，然后简要介绍了相关研究的现状。第二章首先介绍了日志文件系统的基本思想和实现的难点，然后以ext3日志文件系统为例详细介绍了日志文件系统的磁盘布局和元数据，在此基础上介绍和分析了ext3文件系统中日志功能的设计原理与具体实现，并指出了ext3现有的日志功能在设计和实现上的不足。第三章针对第二章中提出的ext3文件系统中日志功能在设计和实现上的每一个不足，详细分析了I/O性能瓶颈产生的原因，提出并实现了相应的改进方案以消除I/O性能瓶颈，并通过实验数据验证了分析的正确性和改进方案对I/O性能的提升。第四章首先介绍了Flash存储技术的特性以及其对Flash文件系统设计带来的挑战，在介绍和分析了基于Flash转换层的文件系统设计的优缺点后，详细介绍和分析了在现代Flash文件系统中得到广泛应用的日志结构化设计，并以JFFS2文件系统为例分析了日志结构化Flash文件系统的关键技术，包括数据存储设计、损耗均衡算法、垃圾回收算法，最后通过实验验证了对JFFS2的分析。第五章针对损耗均衡算法对系统I/O性能的影响，以UBIFS文件系统为例分析了其损耗均衡算法的设计与实现的特点及存在的不足，通过实验数据验证了对其的分析，在此基础上提出并实现了一个综合考虑系统可用空间、系统I/O负载和垃圾回收效率的损耗均衡算法，并通过实验数据验证了新算法的有效性。第六章总结了论文的主要工作，并提出进一步工作的初步设想。第 2 章 基于磁盘的日志文件系统中的元数据更新2.1 日志文件系统2.1.1 日志文件系统的基本设计思想日志文件系统借鉴了数据库系统中的事务概念。类似数据库中具有原子性的事务，日志文件系统将文件的操作看作一个事务，通过写前日志(write-ahead logging)来记录文件操作涉及的元数据修改。以ext3中的文件删除为例，首先创建一个事务，在将所有元数据更新提交到事务日志后，才将元数据更新写入到磁盘。当确认所有元数据的更新已经写入到磁盘后，日志中的事务记录可以被删除，这样就保证了文件操作的原子性。如果在元数据的修改已经提交到日志，但尚未完全写回磁盘的情况下系统出现故障，文件系统在恢复后可以根据日志中的记录redo或者undo，将文件系统恢复到一致的状态。值得注意的是，文件系统中的文件操作与传统的数据库系统中的事务操作有很大的不同，这些不同可以用来简化日志功能的设计。下面分析两者之间主要的区别：(1) 数据库系统需要提供事务的abort操作，即在事务尚未完成时，放弃事务并将事务引起的修改回滚到事务开始之前的状态。但在文件系统的日志设计中不需要事务的abort操作，因为在对文件系统做任何修改前已经确保修改可以被合法的完成。在尚未对文件系统做出任何修改时abort一个事务不会引起问题，因为可以通过提交一个不会引起文件系统数据修改的事务来达到同样的效果；(2) 文件系统中的事务的生命周期通常很短，这大大简化了事务之间的依赖关系。如果需要考虑生命周期很长的事务，则设计必须允许不存在依赖关系的事务以任意顺序提交，否则一个阻塞的事务会影响整个系统的运行。而如果所有事务的生命周期都很短，则设计完全可以按严格的顺序将事务提交到磁盘，而不会严重影响系统性能。2.1.2 日志文件系统的实现日志文件系统的设计允许多种灵活的实现(Vahalia，1996)，从而使得可以在可靠性，功能和性能间取得较好的权衡：(1)日志是否记录用户数据：日志只需要记录元数据的更新就可以将文件系统恢复到一致的状态，但用户数据可能会丢失。在日志中记录用户数据可以提高用户数据的可靠性，但会影响系统的性能；(2)redo日志和undo日志：redo日志只记录新数据，而undo日志还会记录旧数据。undo日志的功能更为强大，允许回滚操作，但设计更复杂，开销也更大；(3)日志的空间回收：一般系统分配给日志使用的空间有限，随着不停的向日志追加数据，日志的早期记录所属的事务已经完成，其占用的空间可以被回收；(4)组提交：为了提高系统的I/O性能，日志一般将多个事务合并成一个事务组写回磁盘，从而提高性能，但这同时降低了可靠性。2.2 ext3日志文件系统的磁盘布局与元数据ext3文件系统是在ext2文件系统基础上开发的，主要的区别在于ext3提供了日志功能。Ext3在通过日志提高文件系统可靠性的同时，最大程度上保持了与ext2的兼容性。在文件的磁盘布局(disk layout)和元数据存储设计上，ext3与ext2完全相同，下面分别介绍。2.2.1 磁盘布局图 21 ext3文件系统的磁盘布局如图 21 (Bovet，2005)所示，每个ext3分区的第一个磁盘块被保留用于作为ext3分区的启动扇区，分区的剩余空间被划分为块组(block groups)，每个块组内部的空间使用情况如下：块组头部的磁盘块用于集中存储文件系统的元数据，如文件系统超级块和块组描述符的备份，数据磁盘块位图和inode位图，inode表。其余的磁盘块用于存储文件数据。文件系统超级块和块组描述符在每一个块组内都存在备份，这样做的主要目的是为了提高文件系统的可靠性。正常情况下只有第0号块组的超级块和块组描述符会被使用，当e2fsck程序检查文件系统一致性时，会使用第0号块组的超级块和块组描述符，并将其复制到其他块组。如果第0号块组所在的磁盘块出现数据故障导致其中的超级块和块组描述符失效，e2fsck程序根据其他块组中的超级块和块组描述符备份将文件系统恢复到一致的状态。2.2.2 元数据ext3文件系统中有六种元数据：超级块，块组描述符，inode，文件的间接寻址块(indirect block)，数据磁盘块位图，inode位图。超级块存储文件系统的属性信息，如文件系统的大小，可用磁盘空间，块大小等。块组描述符存储块组的属性信息，如块组的容量，数据磁盘块位图和inode位图所在磁盘块号等。inode存储文件的属性信息，如文件大小，创建及修改时间，权限等。数据磁盘块位图和inode位图被用来记录磁盘块和inode表中的inode的使用情况，每个磁盘块或inode是否正被使用(存有有效数据)通过一个bit来标识。文件间接块则用于文件间接寻址。图 22 ext3文件系统的寻址机制ext3文件系统为了提供文件内的逻辑地址到磁盘逻辑块号(LBN，Logic Block Number)的映射，采用了直接寻址和间接寻址结合的方案，如图 22所示。Ext3文件系统通过每个文件的inode中的i_block数组存储文件逻辑地址空间到磁盘逻辑块号的映射关系。i_block数组的前12个元素采用直接寻址，即其中存储的磁盘逻辑块号指向的磁盘块存储的是文件的数据。数组第13个元素采用的是一级间接寻址，即数组元素指向的磁盘块存储的并不是文件的数据，而是磁盘逻辑块号，这些磁盘逻辑块号指向的磁盘块存储的才是文件数据。数组的第14个元素采用的二级间接寻址和第15个元素采用的三级间接寻址也类似。假定磁盘块大小为b字节，则小于12b字节的文件只需要直接寻址，而当文件大小超过12b时，则需要一级间接寻址，随着文件增大，可能需要二级或三级间接寻址。ext3的文件寻址设计方案的优点是提高了小文件的读写性能，同时兼顾大文件的性能。研究(Vogels，1999) (Agrawal，2007) (Bach，1986)表明文件系统中绝大多数文件是小文件，在ext3中这些文件只需要使用inode直接寻址，即首先读取inode中的i_block数组，然后根据数组元素找到对应的磁盘块读取实际的文件数据即可，整个操作只需要两次读操作，读取性能可以得到提升。对较大的文件，可能需要先要读取间接寻址块，然后根据间接寻址块的内容索引到文件数据所在的磁盘块后读取，对非常大的文件，整个读取过程可能涉及3，4次磁盘读取操作。当然在实际使用中，文件系统的inode缓存，目录项缓存和页缓存会大大减少磁盘读取操作。实际上现代的文件系统在大部分典型应用下由于页缓存等的影响，磁盘的I/O操作主要是写操作，读操作大部分由页缓存等缓存机制满足(Roselli，2000)。2.3 ext3文件系统的日志功能ext3文件系统的日志结构如图 23 (Prabhakaran，2005)所示：ext3文件系统默认在文件系统所在的磁盘上存储日志，日志存放位置为文件系统所在分区的头部，因此日志所占用的是分区初始的块组。日志所在的块组中除了inode位图和数据块位图以及inode等所有块组都有的元数据外，还有日志超级块来存储日志相关的信息，如日志的大小，日志的写回周期等。日志记录在日志中以日志描述块(Journal Descriptor Block)存储，标记事务完成的为日志提交块(Journal Commit Block)。图 23 ext3文件系统的日志文件构成ext3的日志功能的基本思想是将文件系统的操作分为两步。首先将被修改的数据所在的磁盘块组织为日志记录写入到日志中，然后文件系统可以选择合适的时机将数据写回文件系统。以journal日志模式下向文件追加1个磁盘块为例，文件操作的过程中涉及的日志操作如图 24(Frost，2007)所示，图中的箭头表示一个更新依赖于另一个更新。图 24 journal日志模式下追加写入涉及的日志操作(1) 操作需要新分配一个磁盘块，所以磁盘块位图所在的块需作为日志记录写入日志。操作修改了文件的属性，如大小，时间戳等，因此文件inode所在的磁盘块也需要作为日志记录写入日志。由于采用journal日志模式，追加写入的数据所在的新分配的磁盘块也需要作为日志记录写入日志；(2) 在(1)中的3条日志记录写入日志后，提交记录(commit record)被写入日志以标记写入的日志记录为有效记录，可以在文件系统恢复时用于分辨无效日志记录与有效日志记录；(3) 在提交记录被写入日志后，文件系统可以选择合适的时间将文件数据和文件inode及磁盘块位图写回磁盘，在日志文件系统中这一步骤被称为check pointing；(4) 在确认文件数据已经写回磁盘后，一个完成记录(complete record)被写入日志，以标记日志记录已经不再需要，其占用的空间可以被回收。从系统故障中恢复的时候，e2fsck程序(Henson，2006)可以分辨如下情况：(1) 系统故障发生在日志记录被提交到日志之前，即日志中不存在对应上层操作的日志记录或者日志记录不完整，在此情况下，e2fsck直接忽略日志记录；(2) 系统故障发生在日志记录被提交到日志之后，日志记录有效，e2fsck根据日志记录redo，将日志记录对应的文件更新写入文件系统。在(1)的情况下，上层操作被取消，但文件系统的一致性得到了保证。在(2)的情况下，e2fsck根据日志记录防止了系统出现故障时未完成的I/O对文件系统一致性的影响。从上面的介绍可以看出，ext3采用的是redo-only的日志。JFS，XFS等日志文件系统只在日志中存储元数据，并不存储文件数据。元数据的日志记录足以在系统故障后将文件系统恢复到一致的状态，但文件的数据由于未能存储到日志中，可靠性不能得到保证。ext3对此提供了更灵活的选择。在日志中记录文件操作涉及的元数据和文件数据可能会带来很大的开销从而影响系统性能，而只记录元数据又不能保证文件数据的可靠性，这对某些应用是不可接受的。ext3提供了3种日志模式供系统管理员根据需求在文件系统加载时灵活选择：(1)journal模式，日志会记录元数据和用户数据的更新，可靠性最高，性能最低；(2)ordered模式，日志只记录元数据的更新，但通过保证用户数据先于元数据写入磁盘，提供了较高的可靠性，ext3 默认采用ordered模式；(3)writeback模式，日志只记录元数据，同时不限制用户数据的写入顺序，可靠性最低，但性能最好。2.4 日志块设备层ext3文件系统为了更好的实现模块化的设计，将日志功能封装为日志块设备层(JBD，journal block device)，ext3通过调用日志块设备层提供的服务来完成事务相关的操作，其他的文件系统也可以使用日志块设备层来实现日志功能。ext3日志通常存储在文件系统根目录下，一般是一个文件名为.journal的隐藏文件。ext3文件系统通过调用日志块设备层提供的接口确保文件系统的操作在系统故障的情况下不会破坏磁盘数据结构。不过需要注意的是，一般情况下用于记录文件系统操作的日志块设备层跟文件系统本身共用一块磁盘，所以日志本身跟文件系统一样需要能从系统故障中恢复。ext3文件系统和日志块设备层间的交互主要基于三个基本单位：(1) 日志记录(log record)，用来描述文件系统中一个磁盘块的一次更新；(2) 原子操作描述符(atomic operation handle)，包括一个文件系统上层操作引起的所有日志记录，典型情况下，引起文件系统内容更新的一个系统调用对应一个原子操作描述符；(3) 事务(transaction)，包括多个原子描述操作符，这些原子操作符被e2fsck同时标记为有效。2.4.1 日志记录一条日志记录用来描述文件系统引起的底层操作。在某些日志文件系统中，日志记录只包括文件系统底层操作所修改的内容及内容在文件系统内的位置信息。但日志块设备层的日志记录由文件系统底层操作修改的内容所在的整个缓冲区(buffer)组成。这种设计有其优点和不足。对某些更新频繁但每次更新修改的内容都很少的操作，如位图元数据的更新，每次更新可能只涉及一个bit，但需要将整个位图都记录到日志中，而位图元数据的更新又非常频繁，因此会导致日志空间的浪费。主要优点是日志块设备层可以和磁盘缓存整合，日志记录在日志中以普通数据块或元数据块的方式存储，但每个日志记录都会被分配一个类型为journal_block_tag_t的标记，用来记录日志记录在文件系统内的逻辑磁盘块号和一些状态信息。当日志块设备层需要使用一个缓冲区的时候，一般是因为缓存区存储的是一条日志记录或者缓存区中的数据需要在其他元数据之前被写回磁盘(ordered日志模式)，内核会为缓冲区分配一个journal_head数据结构，用于控制缓冲区写回磁盘。2.4.2 原子操作描述符每个引起文件系统更新的系统调用一般会由多个修改磁盘数据结构的底层操作组成。以追加操作为例，假设ext3需要满足上层发出的向文件尾部追加一个磁盘块大小的数据的请求。文件系统必须找到文件的最后一个磁盘块，在文件系统中找到一个可用磁盘块，更新可用磁盘块所在的块组的数据磁盘块位