A Study of Linux File System Evolution

OO~ posted @ 2013年10月24日 16:47 in 存储编码 , 1990 阅读

  这篇文章是今年由 Lanyue 等人发表的,文章深入研究了 Linux 文件系统代码的 evolution,就像将一个摄像机的镜头拉远,给我们呈现了文件系统 evolution 的全景图,有人说看了这篇文章没啥感觉,但是对于我这样的豆芽菜来说,还是蛮有收获的,所以在这里做了整理。

  在开始之前,简要说明一下文件系统发展的目的:关键字 moving target、by different teams with different goals, new features、fix bugs、improve performance and reliability .etc。如果我们将镜头距离拉近,会看到,在设计一个文件系统时会有很多因素被考虑,physical journaling, logical journaling, checksumming, copy-on-write, harsh tables, indirect blocks, extent maps, data structures, asynchronous thread pools, caching, pre-allocation, stable and so on,我们在专业学习的时候都是把这些分开来一门一门的学习,但是真正综合考虑分析,我觉得我没有这个概念和模型。

  文章的动机主要是考虑到本地文件系统发展的很快,要全部深入理解各个版本的基础代码往往是很费力的,或许这些个版本是有一些共性的,例如各个版本 bug 的类型是否一样,其特征化实现主要表现哪些方面等等问题。这样一来,如果我们把握了文件系统在 evolution 过程中所持有的共性以及创新,那么着对于文件系统的设计者、系统语言的设计者以及 bug 检测工具的设计者都是有很大意义的。

  而文章选取 linux FS 作为研究对象主要原因有两点,一是 linux FS 的每个版本代码都是开源的,二是每个版本基本都有比较详细的分析文档。所以本文分析了这 8 年来 linux FS evolution 的 5079 个版本,其中主要涉及 Ext3, Ext4, xFS, Btrfs, ReiserFS 和 JFS(考虑到这些版本呈现了不同的特点)。

  具体的研究方法是将 5079 个 FS 的版本按照其各自的特征归类,然后分析各个版本对应这些类的共有特征和区别。

  上表是对 FS 分类的类型,有 5 类,通过分析,主要结论有:

1.大约 50% 的版本是代码维护和文档工作。

2.很多 bug 不仅仅在不成熟的 FS 中出现,而且在稳定版本中也普遍出现了,bug 类型和数量不会随着版本的更新而有所减少。

3.文件系统一般都有相同的逻辑组成部分,如 inode 等等。

4.具体到 Bug 类型的分析中,语义 bug 如磁盘状态、逻辑分析等是主要的 bug,超过了 50%;同步 bug 是第二多的,约占 20%,大大用户状态下软件同步的 bug;接着是 Memory bug 和 error code bug;对应的 bug 都会使 FS 崩溃或出现故障,文中具体给出了各个 bug 出现的可能原因以及引发的后果,需要特别说明的是在 FS 中,大约三分之一的 bug 是由于 failure path 引起的。

5.在 performance 版本中,主要提高这 6 个方面的效率:Synchronization(25%), Access optimization,schedule,scalability,locality and other。各个具体涉及的技术文中有说明,最后的结论是大部分文件系统版本所使用的技术都是 fairly standard。

6.在reliability版本中,主要是5个方面的改进:robust,corruption,error,annotation,debug(各种方法中对应的详细策略文中有简要说明)。大部分文件系统都有相似的 Breakdown patterns,但是根据每个版本所达到的目的不同,其在提高 reliability 时,选择策略时也会有不同的侧重。

7.文章主要使用 PatchDB 工具进行分析,主要结果如下面表格中所示。图中给出了各版本的共同点(或者改进点),其结论和上述的部分结论是一一对应的,这里不多赘述。

8.根据本文分析,虽然语义错误有难检测性的特点,但是语义错误都对应会出现不同的 bug,或 FS 会出现不同的错误,所以可以在进行语义错误工具设计时考虑检测不同的 bug 来推断语义错误。

9.虽然每个 FS 的版本初看似乎很不相同,但是如果深入下去,每个 FS 的版本基本都是近似的。

  本文主要的局限是只针对 linux 文件分析,非 linux 文件的一些特征可能无法表现;对于其他版本的 linux 没有作考虑;且对于 bug 的类型,文中只讨论了被 reported 的 bug。其他相关研究工作有 operating-system bugs, user-level bugs, file-system bugs等。

  综合来说,文章的贡献还是蛮大的,特别是对 FS 的设计者,bug 检测工具的设计者等有比较大的意义,“These results are brilliant in a new generation of more robust, reliable and performant file system”。另外,作者通过系列分析,还提供了一个 FS 版本的数据库供将来进一步的学习和研究:

http://research.cs.wisc.edu/wind/Traces/fs-patch/


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter