未分类

A Study of Linux File System Evolution(笔记)

2018年11月24日 阅读(36)

原文:https://www.usenix.org/system/files/login/articles/03_lu_010-017_final.pdf

本文对Linux从2003(Linux2.6.0)到2011(linux2.6.39)的八年时间里,各个文件系统(XFS, ext4, Btrfs, ext3, ReiserFS, JFS)提交的总共5079个patch进行了整理分析,得出了一些有趣的观察和结论:

1.无论是成熟的还是年轻的文件系统,bugs是普遍存在的

2.在这些bug中,大部分是语义bug

3.随着时间的推进,bug的数目并没有减少,在整个文件系统的生命周期内基本保持一个常数

4.数据损坏和系统crash是这些bug造成的最常见后果

5.元数据管理模块具有非常高的bug密度

6.错误处理路径尤其容易出bug

7.相同的性能优化技术可以应用到多个文件系统,但是提高可靠性技术则不太具备通用性

每个patch中通常包含如下信息:类型(bug fix/性能改进/可靠性增强/新feature/代码维护和重构),大小(改动涉及的代码行数),bug所属的模块,bug的pattern(语义/并发/内存/Error Code),bug的影响(数据损坏/系统crash/unexpected error/死锁/系统hang/资源泄漏),发现途径。

patch类型分析

从patch类型上看,重构和维护的占的最多,bug fix第二大概占40%,性能和可靠性增强在不断发生,但比前两类要少很多,新feature占比比较少,但是修改的代码行通常要比其他类型patch多。具体如下:

bug pattern

可以进一步细分如下:

其中,语义方面的bug占了大多数,大多数这种类型的bug都需要文件系统的领域知识才能理解、检测、fix它们。并发bug在各个文件系统中大概平均占20%,除了ReiserFS只有不到3%的并发相关bug,主要是因为ReiserFS从2.6.33开始,它不再使用引入大量并发bug的BKL(Big Kernel Lock)。同时在所有文件系统中,都有相当数量的内存bug。Error Code相关的bug大概占了10%。具体参加上图1中的b。

bug的数目不会随着时间的演进而逐渐平息(即使是稳定的文件系统),而是处于起伏涨落中。同时语义、并发、内存、ErrorCode这些不同类型bug的比例随着时间在发生变化,但是不会收敛到某一个。

bug影响后果

一个patch可能涉及多种后果。其中数据损坏是这些bug产生的最主要后果(40%)。crash第二,大概20%,大部分crash都是由BUG()或者Assert()调用以及NULL指针解引用引起。unexpected error和死锁出现的也很频繁,大概10%。

bug在代码中的分布

文件系统的代码复杂度在不断上升。原始的FFS只有1200行代码,但是在现代系统中,ext4有2.9万行,Btrfs有4.7万行,XFS有6.4万行。

文件系统通常都具有类似的模块结构,比如inodes、superblocks、journals。为了进行比较,我们把文件系统划分为9个逻辑组件:data block allocation (balloc), directory management (dir), extent mapping (extent), file read and write operations (file), inode metadata (inode), transactional support (trans), superblock metadata (super), generic tree procedures (e.g., insert an entry) (tree) and other supporting components (other)。

我们发现,对于所有的文件系统来说,file、inode、super这三个组件具有最高的bug密度。file组件的bug密度高,要么是在fsync路径(ext3),要么是为了实现更高性能添加的custom file I/O routines(XFS/ext4/ReiserFS/JFS),尤其是对于XFS来说,为了可扩展它有一个custom buffer cache和I/O管理器。inode和superblock因为保存了文件和文件系统重要信息核心元数据结构,会被频繁访问和更新,这也就不奇怪为啥bug密度也很高(比如有时忘了更新inode里面的时间字段,或者是错误使用了superblock配置flag)。

第二,transactional部分的code通常占了很大的代码量,因此对于大多数文件系统来说,它们的bug也是与代码量成比例的。对于ext3来说,这个关系也成立,即使它使用了一个独立的journaling模块JBD;ext4的bug比例要相对轻些,因为从2.6.19开始它基于一个更稳定的JDB版本。总体来说,事务一直是个双刃剑,一方面它提高了crash时的数据一致性,但是由于它们巨大的代码量也带来了很多bug。

第三,与代码量相比,XFS/Btrfs/ReiserFS的bug比例令人吃惊地少。

bug在错误处理路径上的占比

很多bug都是发生在错误处理路径上。文件系统需要处理各种故障,包括资源分配、IO操作、静默数据错误、错误的系统状态。这个结果表明我们必须要格外关注文件系统中错误处理代码的质量。

性能优化

我们把性能优化相关的patch分成如下六类:

inefficient usage of synchronization methods (sync), smarter access strategies (access), I/O scheduling improvement (sched), scale on-disk and in-memory data structures (scale), data block allocation opti- mization (locality), and other performance techniques (other).

sync patch占了超过1/4。典型的解决方案有:消除不必要的锁、使用细粒度的锁机制、使用读写锁代替写锁。

access patch,使用更加智能的策略优化性能,包括caching和work avoidance。比如ext3为了避免IO,会把元数据stats cache到内存。在Btrfs中,在搜索空闲的blocks之前,先检查是否有足够的剩余空间,来避免不必要的工作。

sched patch,通过改进IO调度策略获取更好的性能。比如batching of writes, opportunistic readahead, and avoiding unnecessary synchrony in I/O。与sync和access相比,sched占据了类似比例。

Scale patches utilize scalable on-disk and in-memory data struc- tures, such as hash tables, trees, and per block-group struc- tures. XFS has a large number of scale patches, as scalability was always its priority.

 

You Might Also Like

No Comments

Leave a Reply