Practical File System Design

起源

主要是BeOS移植到了其他处理器上，并且随着曝光增多，各种问题凸显出来，到了不得不改的地步。因此设计新的FS，但需要保留原来FS（Old Be File System， OFS）的主要特性，同时增加一些时髦的特性（如：日志）64位支持，多线程，由于一些限制（人少时间短），BFS也就只能做到这样了

总的来说，开发新FS的动机主要是解决OFS的问题，并添加一些功能，OFS的功能是和BeOS紧密结合的（后面会提到），因此不是切换成其他先进的FS那么简单

什么是文件系统

文件系统作为用户和存储设备的中间层，提供数据在存储设备上存储组织和存取的接口，方便用户使用，通常文件系统会提供一些抽象，如：文件、目录，而这些抽象又可以有很多不同的实现，比如文件，它的结构可以分为元数据和数据，而数据又可以按照block来管理，也可以按照extent来管理，比如目录，它的数据可以是按照列表来存储，也可以使用B+树来存储

文件系统通常提供接口包括：挂载、取消挂载、创建文件/目录、打开文件/目录，读写文件，遍历目录、删除文件/目录，以及重命名等。除此之外，文件系统还可能提供扩展功能：软连接、硬连接、文件内存映射、属性、ACL等

需要注意的是，实现文件系统并没有“正确”的方法，取决于要解决的问题和限制，因此并不是所有特性都是必须的，比如对于分布式文件系统来说，元数据甚至可以和数据分开存储，目录和文件分开存储

BFS的结构

BFS支持配置不同的块大小，如1024、2048、4096、8192，至于为什么没有512是因为某些数据结构的大小就超过512字节，因此不好管理，索性就不支持了

在BFS中管理硬盘空间使用的是BitMap而不是XFS那样使用B+树，原因是实现简单（并且投入有限），但和XFS一样，使用Allocation Group来将硬盘空间划分为固定大小的块，但AG是逻辑上的结构，并没有具体的数据结构表示，这么做的好处是：关联的数据可以尽量安排在一起（例如，目录和inode都放在一个AG中），有更好的局部性，更有可能或者顺序IO，当然，如果空间非常碎片化了，那么就办法了

并且在BFS中， 每8个AG会用来存放目录和inode数据，例如: 1～8 是目录和inode, 9～15是文件数据，16～23又是目录和inode

在BFS中使用block_run来定位硬盘块，其中32位为AG号，16为AG中的起始块号，16为块的个数，这样BFS所能管理的硬盘大小就可以很容易的计算出来，假设块大小是1024，那么能管理的空间大小就是：2^32 * 2^16 * 2^10 = 2^58

在BFS中文件的数据仍然使用直接块+间接块来表示

在BFS中，使用B+树来实现目录，值得一提的是，使用B+树来实现目录在BFS中只是顺带的行为，因为BFS中的属性需要B+树来索引，因此用来实现目录不过是复用代码而已，下面就是创建和初始化B+树的代码，其中fTransaction仅用来确保只有一个写事务在执行

status_t InodeAllocator::CreateTree()
{
	Volume *volume = fTransaction->GetVolume();

	// force S_STR_INDEX to be set, if no type is set
	if ((fInode->Mode() & S_INDEX_TYPES) == 0)
		fInode->Node().mode |= HOST_ENDIAN_TO_BFS_INT32(S_STR_INDEX);

	BPlusTree *tree = new (std::nothrow) BPlusTree(*fTransaction, fInode);
	if (tree == NULL)
		return B_ERROR;

	status_t status = tree->InitCheck();
	if (status != B_OK) {
		delete tree;
		return status;
	}

	fInode->fTree = tree;

	if (fInode->IsRegularNode()) {
		if (tree->Insert(*fTransaction, ".", fInode->ID()) < B_OK || tree->Insert(*fTransaction, "..", volume->ToVnode(fInode->Parent())) < B_OK)
			return B_ERROR;
	}
	return B_OK;
}

最后是，属性（Attribute），这是BFS的特点，也是和BeOS配合的关键，属性简单来说就是键值对（但允许重复的键），在BeOS中可以和邮件应用结合，用来存放发件人和收件人信息，已经和GUI结构存放图标等信息，并且可以被索引，这样的好处是可以对文件和目录分类以便快速查找（用户程序也能实现相同的功能），由文件系统直接支持的好处是“为所有程序提供一个通用的数据库支持，不用每个程序都搞自己的一套”

BFS 中的分配策略

分配策略需要更加硬盘的特性和数据特点进行调整，对硬盘来说应该减少随机IO，对数据来说，同类数据最好放在一起

文件预分配

对于文件写数据，BFS会采用预分配的策略，每次分配固定64K大小的空间，这么做的原因是：

1. 大部分文件都小于64K，一次预分配64K可以保证文件的数据是连续存放的
   
2. 对于超过64K大小的文件，64K的连续写差不多能达到硬盘的最大带宽
   
3. BFS是日志式的，如果预分配的块太小，由于写都需要开启事务，那么写日志会成为瓶颈
   

这个预分配是为了解决这个问题

The allocation policy for writing data to a file faces many conflicting goals. Small files should not waste disk space, and packing many of them together helps avoid fragmentation. Large files should be contiguous and avoid large skips in the block addresses that make up the file. These goals often conflict, and in general it is not possible to know how much data will eventually be written to a file

预分配也有缺点：文件的大小并不是刚好是64K的，因此文件系统适时地需要回收没有使用的空间，对于普通文件，BFS会在文件关闭后执行回收

当然，对于碎片化严重的硬盘来说，预分配通常会带来性能上的问题（最差的情况是程序不得不遍历整个磁盘来寻找连续的空间），这时，需要改变寻找空闲空间的策略：直接使用能找到的任何可用的块。（那么何时确定需要改变策略呢？文档中描述的是：如果寻找连续空间失败了太多次，就应该切换策略，可以看看具体实现）

除了文件，目录也可以使用预分配，不过目录大小的增长要慢得多，并且目录不需要打开就可以创建文件，因此目录预分配多余块的回收放在目录inode刷盘时进行（个人认为目录预分配多数情况实在没必要，可能在涉及到大量小文件操作时有点用，比如编译）

日志

为什么需要日志

对于硬盘来说，只有对单个块的操作能保证是原子的，不可分割的，在文件系统中，很多操作需要涉及到不止一个硬盘块，因此在出现故障时（系统崩溃、突然掉电等）可能出现文件系统的结构不完整，造成数据丢失或破坏，这时通过扫描整个文件系统有可能找回丢失的数据，但这样做并不能100%成功，并且相当耗时

当然，日志也不是万能的，对于磁盘本身的故障（坏块，位反转），日志无济于事，这时如何处理依赖于上层软件

使用日志，可以保证上述对硬盘的操作要么成功要么失败，并且在故障时，缩短恢复的时间

如何工作

基本思想是在整个事务过程中，所有被修改的结构锁定，直到事务完成，然后再解锁。事务完成的标志是，所有的操作都刷到了硬盘上该到的位置。当然，事务需要先写到日志中(Write Ahead Log)避免部分更新。

当系统崩溃恢复时，日志处理代码需要重放日志来将文件系统恢复到一致的状态，如果在重放过程中崩溃了，也不会有影响，下次重放重头开始即可。对于已经恢复的日志，需要标记为完成。

日志类型

1. undo日志 （old-value/new-value）
   要修改的值改前的值和改后的值都记录下来，好处是修改可以丢弃，而坏处是，需要多写数据，另外，在实现上要记录修改前的状态可能并不容易
2. redo日志 （new-value-only）
   即只记录新的修改，好处是，只写一份数据，实现也简单，而坏处是没法回退（即丢弃修改）

对于文件系统来说，选择redo日志是合理的，一方面性能会更好，另一方面对用户来说可以减少心智负担（不需要用户处理回退）

日志包含什么

在BFS中，日志仅包含文件系统被修改的元数据，不包括文件数据，原因是，日志区域是固定大小的环形缓冲，而文件数据可能超过这个缓冲的大小

日志仅能保证文件系统的完整，并不保证文件系统是最新的状态。举例来说：如果一个文件打开并正在写入，这时系统崩溃了。那么在系统重启后，这个文件要么是空的，要么不存在。前者出现的原因是，修改已经记录到了日志，在重启后重放日志，创建了这个文件；后者出现的原因是，修改还没有记录到日志，日志不完整，被丢弃

那么有没有记录文件数据的实现呢？答案是有的，那就是 Log Structured File System (LFS， BSD 4.4)，在LFS中，整个硬盘被作为日志的区域，并且文件永远不会被删除，只是简单的覆盖，在LFS中空间的重用是通过覆盖那些已经废弃的事务实现的

日志的代价

最明显的缺点是，数据需要写两次，一次写日志，二次写到元数据。但从结果来看，并没有太大的影响，一是，日志的写是批量操作，并且是顺序的大块写，这有助于减少硬盘的寻址，二是，前面的写日志会导致buffer的排序，在写元数据时同样减少了寻址

其次，只有单日志才是最大的瓶颈，这会导致写日志操作被串行化，这里有两种优化方案 1. 使用多个日志文件 - 这样做还需要记录事务的时间戳，以便在多个日志间保证操作的顺序，同时还需要重新研究文件系统的锁机制来保证高效和正确 2. 事务固定大小，记录较多的事务可以分配多出的记录给后续的事务 - 这样可以根据日志区域的大小和事务的大小并行化写操作，但是同样会造成大量的顺序和加锁上的问题，具体可以参考XFS的实现（论文上没写，需要看代码）

BFS的实现

它的实现做了很多的假设，例如事务不会太大，日志区域不会用完等。日志用到的块在格式化时就初始换了，存放在superblock中，日志块当作环形缓冲使用，因此才有前面的假设

优化： 批量记录，比如在解压缩文件的过程中，会有大量的文件创建操作针对同一个目录，可以将这个操作缓存起来，一次性的做日志操作

后续需要分析代码（Haiku OS中有BFS的实现，Linux中只有只读部分）

下面的描述基于Haiku@ee658d503b

transaction 存什么

下面是创建inode(bfs_create)的大致流程

	Transaction transaction(volume, directory->BlockNumber());

	Inode *inode;
	bool created;
	status_t status = Inode::Create(transaction, directory, name, S_FILE | (mode & S_IUMSK), openMode, 0, &created, _vnodeID, &inode);

	// Disable the file cache, if requested?
	if (status == B_OK && (openMode & O_NOCACHE) != 0 && inode->FileCache() != NULL) {
		status = file_cache_disable(inode->FileCache());
	}

	entry_cache_add(volume->ID(), directory->ID(), name, *_vnodeID);

	if (status == B_OK)
		status = transaction.Done();

上面的代码会创建一个block用来存放bfs_inode，而这个block会存在volume中的block cache里面，在手动调用flush或者缓存超限时会复用write系统调用将bfs_inode整个block写到日志区

因此，transaction 记录的是修改的block，存放在缓存中，手动或自动写到日志区

上面代码中，会锁定整个日志结构直到Done调用

日志回放怎么做

在刷写数据到硬盘时需要将修改的block的编号和block的数据进行编码，由一个包含block_run数量和block_run内容的头block数据连续存储在日志区域，大致结构如下

journal format
+--------+-------+--------+-------+------+
| header | data  | header | data  | ...  |
+--------+-------+--------+-------+------+

header format
+-------+----------+-----------+-----------+------+
| count | max_runs | block_run | block_run | ...  |
+-------+----------+-----------+-----------+------+

在回放日志时只需要从日志的起始偏移处开始解析数据，写到这些块原本的位置即可

---

Remark

这里大致记录了书中的部分以及个人的看法，总的来说，在那个时代BFS是一个中规中矩的文件系统实现，它和BeOS结合紧密，而这也是它的局限。这本书中花了很大的篇幅讲它的attribute和index和cache，但这些东西和BeOS一起被抛弃了。虽然如此，这本书和它的名字一样，描述了文件系统基本实现的方方面面，以及各种 trade off，姑且可以作为一个指导使用

Reference

Practical File System Design