日志结构文件系统研究综述.doc

《日志结构文件系统研究综述.doc》由会员分享，可在线阅读，更多相关《日志结构文件系统研究综述.doc（3页珍藏版）》请在三一办公上搜索。

1、日志结构文件系统研究综述贺勤 广州网易互动娱乐有限公司，广东 广州510665摘要：因为传统文件系统存在磁盘I/O效率低、崩溃恢复速度慢等缺点，以及硬件的不平衡发展，使日志结构文件系统（LFS）应运而生。本文综述了LFS的数据结构和磁盘布局，及空闲空间管理、读写机制、段清洁机制与策略等。分析了快速崩溃恢复、高的磁盘带宽利用率等优点，并 介绍了在事务与版本语义、工程负荷中的应用和算法等方面的研究进展。关键词：日志结构文件系统；日志结构文件系统的结构；空闲空间管理；段清洁；崩溃恢复中图分类号：TP39 文献标识码：A 文章编号：1003-9767(2009)07-0128-03Overviews

2、on Log-structured File Systems ResearchHE Qin Guangzhou NetEase Interactive Entertainment Limited，Guangzhou Guangdong 510665Abstract: Log-structured file system (LFS) emerged as requires of the lopsided developments of hardware and the shortcomings of traditional file systemssuch as bad performance

3、of disk I/O and slow crash recovery. LFS data structure, disk layout, free space management, access mechanism and segment cleaning mechanism were summarized. Virtues of LFS such as faster recovery time and higher utilization of disk bandwidth were analyzed and the advancements of researches on LFS s

4、uch as transaction and versioning semantics, LFS for tertiary storage devices and embedded memory devices, engineering LFS, self-tuning LFS were introduced in this paper.Key words: log-structured file system; LFS structure; free space management; segment cleaning; crash recovery引言处理器、磁盘和主存的技术会显著地影响文

5、件系统的设计。由机械运动决定的磁盘访问时间至今仍无重大提高。当前，磁盘I/O性能 相对太差是提高文件系统效率和性能的瓶颈1。传统文件系统设计时，主要考虑效率和性能。但企业用户更看重 数据的可靠存储和可靠访问，要求文件系统具有可恢复性。如何针对 普遍的小文件的工作负荷设计出可恢复的文件系统，是一个很现实的 课题。能。采用日志也自然而然地加快了崩溃后的恢复速度，不必像传统文件系统那样，在崩溃后必须扫描整个磁盘来恢复一致性；LFS只需要 检查日志的最近部分。2. 日志结构文件系统的结构日志文件系统的日志仅仅是临时存储，永久数据则是存储在磁盘上的随机访问存储结构中。相反，LFS逻辑上把整个磁盘看作一个

6、大 的日志，把数据永久存储在日志中1。2.1 日志结构文件系统的数据结构 LFS在磁盘上的主要数据结构及其作用和位置见表12。检查点区域是磁盘上的一个固定位置，用来定位索引结点图所在的磁盘块， 并确定日志中的最后一个检查点。用索引结点图来维护每个索引结点 的当前位置，其活动部分缓存在主存中，因而在查找时几乎不需要访 问磁盘。表1 LFS在磁盘上的主要数据结构1. 基于日志技术的文件系统为了推广在强调数据完整性和可恢复性的企业级服务器中的应用，借鉴如Oracle等大型数据库，文件系统引入了日志。文件系统引 入日志的设计思想是跟踪文件系统元数据的变化，在把元数据写入日 志后，才把实际数据写到磁盘上

7、，这使文件系统可以用事务处理的方 式提交或撤消其变化。1.1 日志文件系统日志文件系统6（journal file system）采用独立的日志文件跟踪 文件系统的变化，用来改善磁盘写性能和加快崩溃后的恢复速度。目 前商业化应用的日志文件系统有IBM的JFS；为Linux开发的EXT3；为 Windows NT开发的NTFS7等。因为设计相对较简单，日志文件系统 已成为面向高端企业级用户的主流文件系统。1.2 日志结构文件系统 Ousterhout于1988年提出了日志结构文件系统（log-structuredfile system，简称LFS）的设想1，Rosenblum设计并实现了Spri

8、te- LFS2,3。LFS是基于以下设想：增大主存容量，把一系列文件系统 更改信息缓存于主存中，并在一次寻道操作中把所有更新信息连续地 写入磁盘。这就把传统文件系统的大量小的同步随机写转换为了大的 异步连续写；从而既有效满足读文件的请求，又显著改善磁盘写性超级块, 检查点区域, 索引结点图, 索引结点,间接块, 段摘要, 段使用表, 目录更改日志, 在磁盘上的一个固定位置, 在日志中.数据结构作用位置Superblock有静态的配置信息，如段编号和段大小FixedCheckpoint region定位inode map和segment usage table磁盘块，确定最后一个检查点Fixe

9、dInode map定位inode在日志中的位置，有最后访问时间和版本号LogInode定位文件块，含有文件属性LogIndirect block定位大文件的磁盘块LogSegment summary确定段的内容（文件号和每个磁盘块的偏移 量），下一个段的编号LogSegment usage table计算段中活数据的大小，保存段内最后一次写数 据的时间LogDirectory change log记录目录操作，以维护inode中引用计数的一致性Log(1)图1 LFS的磁盘布局图2 LFS的日志结构LFS采用写成本（write cost）来比较清洁策略。写成本定义包括所有清洁费用在内，每写入

10、一个字节新数据时使磁盘忙碌的均时间。LFS选择效益成本比最高的段进行清洁。段的利用率设2.3 日志结构LFS的一个重要问题是如何定位和读文件。LFS的日志使用顺 序的、只增的数据结构，文件的描述仍采用传统的索引组织方式。 LFS在日志中加入索引结点，索引结点使LFS能够以随机访问方式从 日志中找回文件的相关信息（参见图2）。LFS中查找一个索引结点 的步骤是：在位于磁盘上固定区域的检查点中，找到最近的索引结 点图；由索引结点图找到索引结点的最近版本；由索引结点就可以 找到相应的文件块。（0u1），效益由获得的空闲空间量（1-u）和最年轻磁盘块的龄（age）之积构成。清洁成本是1+u（1是读入段

11、的成本，u是回活数据的成本）。成本效益（cost and benefit）算法如下2：LFS基于成本效益算法挑选出一些只残留有很少活数据的段在清理时隔离并区别对待冷热数据。当把活磁盘块回写到空闲时，LFS把活磁盘块按其年龄排序。4. 日志结构文件系统的优点4.1 快速崩溃恢复13为了满足商业用户的需求，文件系统需具有可恢复性。LF用检查点和回滚技术来快速恢复一致性。LFS创建一个检查点分阶段：首先把所有更改信息写入日志，然后写一个检查点区域到3.日志结构文件系统采用的主要机制与策略3.1 空闲空间管理为了有空闲空间写入新的数据，LFS采用串连（threading）和复 制两种方式（不是用位示图

12、或者空闲链表）来管理空闲空间2,3。 串连方式把活数据（live data，即仍在使用的数据）保留在原处， 把空闲区域串连起来。其缺点是将产生很多碎片，不利于连续大量 写，而且不利于进一步提高LFS的性能。对只有部分活数据的段， 复制方式复制并紧凑活数据，然后回写到日志头部的空闲空间中， 以产生大的空闲区域。其缺点是复制的成本，尤其是长期存活的文 件可能反复复制。3.2 读写机制 LFS一旦找到文件的索引结点，读文件的磁盘I/O次数和传统文件系统中一样，所以读性能不会变差。因为文件块是连续分配，这 为读文件提供了好处。传统文件系统是对读进行优化，而LFS是对写进行优化。LFS 写日志机制如下：

13、（1）把脏磁盘块和脏索引结点收集在一起，直至 达到一个完整段的尺寸，比如62kB1MB。（2）一次写完每个日志 段，即最多寻道一次。LFS把同一时间写的数据写在一起，是时间 局部性1；而FFS在写之前重组数据，把同一文件的磁盘块写在一盘上固定位置。LFS恢复时可以抛弃检查点后的所有数据，但为恢复尽可能多的数据，LFS利用在段末端段摘要磁盘块中的信息采用回滚技术来恢复最后一个检查点后的操作。4.2 高的磁盘I/O带宽利用率LFS把文件磁盘块和其索引结点块靠近，以减少寻道时间。磁盘分成固定大小的段，总是从头至尾连续写一个段。段的容量是选得足够大（比如1MB），使得读写一个段的传输时间远大于道时间。

14、这样对段操作时就几乎能利用整个磁盘带宽。大批创建除小文件时，LFS能够利用65%75%的磁盘带宽写新数据，其余宽用于清洁。而FFS仅能利用5%10%的带宽写新数据，其余带宽于寻道时间和潜伏时间2,3。5. 日志结构文件系统的发展5.1 事务与版本LFS用日志技术来储存文件，在文件系统中加入事务机制是然的扩展9。LFS只添加、没有改写的策略，使旧版本的文件仍留在磁盘上，稍做努力就能实现版本和历史存档语义1,9。5.2 工程应用方面的发展8,10Sprite-LFS存在占用内存空间大，需要大量空闲磁盘空间才有效写入新数据，崩溃恢复时不检查目录结构的一致性，只使用一个清洁工进程和一种清洁策略等局限性

15、，使其不适用于工程负荷。 为了能应用于工程负荷，Seltzer等在Sprite-LFS基础上实现了BSD- LFS，其主要改进如下：（1）改变段的磁盘布局，把段摘要块从段 的尾部移到段的头部，并从前向后构建段，这样就能简单地确定下 一个段摘要块的位置。（2）取消目录更改日志。（3）把段清洁工 由Sprite-LFS的内核态进程改为用户态进程。在一个文件系统中，可 以并行存在多个清洁工进程，每个进程采用不同的清洁策略。（4） 在崩溃恢复时，首先迅速从最后一个检查点回滚；然后采用类似 FFS的崩溃恢复策略，执行完整的一致性检查，以恢复丢失的或者 损坏的数据。5.3 算法方面的发展为了提高Sprit

16、e-LFS在只有少量空闲时间进行段清洁时的性能， Matthews等采用了自适应算法11。采取三条措施来提高LFS的写性 能：根据工作负荷和磁盘特性选择相匹配的段大小；根据磁盘利用 率的变化修改清洁策略；利用高速缓存的数据降低清洁成本。为了 提高读性能，重新动态组织数据，以匹配读模式。在事务处理负荷下，如采用大容量的段，清洁工的开销将使性 能损失35%40%9。Blackwell等采用简单的启发式清洁算法12， 清洁工进程仅作为后台活动，就可以很好地解决此问题。5.4 其他方面的发展 既然清洁工已经读入将回收的段，也能把这些段回写到备份设备，这使LFS成为在线备份的合适替代方案9。Christ

17、ian等在EXT2和块设备之间加入一日志层，实现了 LinLogFS文件系统13。以解决EXT2文件系统的两个问题：崩溃恢 复速度慢，有时还要求人工干预；当文件系统可写时，没有办法做 到一致性备份。为了提高嵌入式系统的效率，瑞典的Axis Communications于1999年开发了基于LFS的JFFS（journaling flash file system）14， 以为无盘的嵌入设备提供崩溃/断电安全的文件系统。JFFS在垃圾 收集时，对块进行了不必要的多余擦除；不支持压缩和硬链接。在2001年，Red Hat公司开发了JFFS215，以解决JFFS存在的问题。 国内也对LFS进行了有益

18、的研究16,17，中国科学院针对嵌入式存 储设备开发的JFFS文件系统已经成为红旗嵌入式存储方案的重要组 成部分16。参考文献：1 Ousterhout, J., Douglis, F.Beating the I/O Bottleneck: A Case forLog Structured File Systems. University of California, Berkeley, UCB/CSD88/467, 1988.2 Rosenblum, M.,Ousterhout, J.The Design and Implementation of a Log-Structured File

19、system.ACM Transactions on Computer Systems,1992,10:2652.3 Rosenblum M.The Design and Implementation of a Log- Structured Filesystem Ph.D. Thesis. University of California at Berkeley,1992.4 Marshall K. McKusick,William N. Joy,Samuel J.Leffler, et al.Afast file system for UNIXJ.Trans.Comp. Syst.,198

20、4,2:181197.5 Marshall Kirk McKusick,Willian N. Joy,Samuel J. Leffler, Robert S. Fabry.Fsck - The UNIX File System Check Program.Unix System Managers Manual - 4.3 BSD Virtual VAX-11 Version.USENIX, 1986,4.6 Ricardo Galli.Journal File Systems in Linux.Technical Report,2002. /body.phtml? nIdNoticia=115

21、4.7 David A.Solmon.Windows NT技术内幕M,第二版.清华大学出 版社/Microsoft Press,1999.8 Seltzer M., Bostic K., McK usick M., Staelin C.An implementation of a log-structured file system for UNIXC.In Proc. 1993Winter Techn. Conf., San Diego, CA, USA,1993:307326.9 Margo Ilene Seltzer.File System Performance and Transac

22、tionSupport Ph.D. Thesis.University of California at Berkeley,1992.10 Seltzer, M.,Bostic, K.,McKisick, M.,Staelin, C.The Design and Implementation of the 4.4BSD Log-structured File SystemC.Proceedings of the 1993 Winter Usenix, San Diego, CA,1993.11 Matthews, J., Roselli, D., Costello, A., et al.Imp

23、roving the Performance of Log-Structured File Systems with Adaptive MethodsC. Proc. of 16th ACM SOSP, Saint Malo, France,1997.12 Trevor Blackwell, Jeffrey Harris, Margo Seltzer. Heuristic cleaning algorithms in log-structured file systemsC. Annual USENIX Technical Conference, pages 277288. USENIX As

24、sociation, 1995.13 Czezatke C., Ertl M. LinLogFS - A Log-Structured FilesystemFor Linux. Usenix 2000 Freenix Track,2000:7788.14 Axis Communications. Journaling Flash File System. TechnicalReport, 2002. /software/jffs/.15 Woodhouse D.JFFS:The Journalling Flash File SystemC.LinuxSymposium 2001,Ottawa,

25、Canada,2001.16 郑良辰.日志文件系统在嵌入式存储设备上的设计和实现D.北京:中国科学院,2001.17 林晓东, 刘心松. 文件系统中日志技术的研究J. 计算机应 用,1998,18(1):2830.6. 总结与展望日志结构文件系统是一种很有特色的磁盘存储管理技术，除了良好的磁盘写性能和快速崩溃恢复外，其特性使其自然地就扩展出 事务与版本语义，并可以方便地应用于第三级存储设备（如磁带） 和嵌入式存储设备中。经过不同方面的改进，已出现了可以应用于 工程负荷的BSD-LFS和自适应LFS。目前对LFS的研究十分活跃，但仍主要集中于California大学 Berkeley分校。Harvard大学、惠普公司和中国科学院也进行了十分 有益的研究。尽管已经出现了很多基于LFS技术的文件系统，但仍 需要在以下方面进行研究： 研究更好的清洁策略，以减小段清洁工的大量开销。 优化研究段大小、批量写数据的大小及影响。