reiserfs 是由 namesys 公司的 Hans Reiser 设计并开发的一种通用日志文件系统，它是第一个进入 Linux 标准内核日志文件系统。从诞生之日起，reiserfs 就由于其诸多非常有吸引力的特性而受到很多用户的青睐，迅速成为 Slackware 等发行版的默认文件系统。它也一度也是 SUSE Linux Enterprise 发行版上的默认文件系统，直到 2006 年 10 月 12 日 Novell 公司决定将默认文件系统转换到 ext3 为止。尽管其主要设计人员 Hans Reiser 由于涉嫌杀害妻子遭到指控而入狱，从而导致他不得不试图出售 namesys 公司来支付庞大的诉讼费用，但是 reiserfs 已经受到广大社区开发人员和用户的极大关注，有很多志愿者已经投入到新的 reiserfs 4 的开发工作中来。本文中的介绍都是基于最新的稳定版本 3.6 版本的，所引用的代码都基于 2.6.23 版本的内核。

reiserfs 最初的设计目标是为了改进 ext2 文件系统的性能，提高文件系统的利用率，并增强对包含大量文件的目录的处理能力（ext2/ext3 文件系统中一个目录下可以包含的子目录最多只能有 31998 个）。传统的 ext2 和 ufs 文件系统都采用了将文件数据和文件元数据分离开保存的形式，将元数据保存到索引节点中，将文件数据保存到单独的磁盘块中，并通过索引节点中的 i_block 数组利用直接索引和间接索引的形式在磁盘上定位文件数据。这种设计非常适合存储较大的文件（比如20KB以上），但是对于具有大量小文件的系统来说就存在一些问题。首先在于文件系统的利用率，由于 ext2 会将文件数据以数据块为单位（默认为 4KB）进行存储，因此对于存储只有几十个字节的文件来说，会造成空间的极大浪费。另外由于在读取文件时需要分别读取文件元数据和文件数据，加上多读取数据块的开销，ext2 文件系统在处理大量小文件时，性能会比较差。为了获取最好的性能和最大程度地利用磁盘空间，很多用户会在文件系统之上采用数据库之类的解决方案来存储这些小文件，因此会导致上层应用程序的接口极不统一。

为了解决上面提到的问题，reiserfs 为每个文件系统采用一棵经过专门优化的 B+ 树来组织所有的文件数据，并实现了很多新特性，例如元数据日志。为了提高文件系统的利用率，reiserfs 中采用了所谓的尾部封装（tail packing）设计，可以充分利用已分配磁盘块中的剩余空间来存储小文件。实际上，reiserfs 文件系统中存储的文件会比 ext2/ext3 大 5% - 6% 以上。下面让我们来探索一下 reiserfs 文件系统中数据在磁盘上究竟是如何存储的。

磁盘布局

与 ext2/ext3 类似，reiserfs 文件系统在创建时，也会将磁盘空间划分成固定大小的数据块。数据块从 0 开始编号，最多可以有 232 个数据块。因此如果采用默认的 4KB 大小的数据块，单个 reiserfs 文件系统的上限是 16TB。reiserfs 分区的前 64KB 保留给引导扇区、磁盘标签等使用。超级块（super block）从 64KB 开始，会占用一个数据块；之后是一个数据块位图，用来标识对应的数据块是否处于空闲状态。如果一个数据块位图可以标识 n 个数据块，那么 reiserfs 分区中的第 n 个数据块也都是这样一个数据块，用来标识此后（包括自己）n 的数据块的状态。reiserfs 文件系统的磁盘结构如图 1 所示。

与 ext2/ext3 类似，reiserfs 文件系统的一些关键信息也保存超级块中。reiserfs 的超级块使用一个 reiserfs_super_block 结构来表示，其定义如清单1 所示：

该结构定义中还包含了其他结构的定义，例如 journal_params，这是有关日志的一个结构，并非本文关注的重点，读者可以自行参考内核源代码中的 include/linux/ reiserfs_fs.h 文件。

实际上，超级块并不需要一个完整的数据块来存储，这个数据块中剩余的空间用来解决文件对象 id 的重用问题，详细内容请参看本系列文章下一部分的介绍。

B+ 树

与 ext2/ext3 的超级块比较一下会发现，reiserfs 的超级块中并没有索引节点表的信息，这是由于 reiserfs 并没有使用索引节点表，而是采用了 B+ 树来组织数据（在 reiserfs 的文档中也称为是 S+ 树）。图 2 中给出了一棵典型的 2 阶 B+ 树，其深度为 4。

图 2. 2 阶 B+ 树

一棵 B+ 树有唯一一个根节点，其位置保存在超级块的 root_block 字段中。包含子树的节点都是中间节点（internal node），不包含子树的节点称为叶子节点（leaf node）。按照是否包含 B+ 树本身需要的信息，节点又可以分为两类，一类节点包含 B+ 树所需要的信息（例如指向数据块位置的指针，同时也包括文件数据），称为格式化节点（formatted node）；另外一类只包含文件数据，而不包含格式化信息，称为未格式化节点（unformatted node 或 unfleaf）。因此，所有的中间节点都必须是格式化节点。一个格式化的叶子节点中可以包含多个条目（item，也称为项），所谓条目是一个数据容器，其内容可以保存到一个数据块中，也就是说，一个条目只能隶属于一个数据块，它是节点管理空间的基本单位。

为了方便理解起见，我们可以认为对于 B+ 树来说，一共包含 3 类节点：中间节点（其中保存了对叶子节点的索引信息）、叶子节点（包含一个或多个条目项）和数据节点（仅仅用来存放文件数据）。

熟悉数据结构的读者都会清楚，B+ 树是一棵平衡树，从根节点到达每个叶子节点的深度都是相同的。与 B- 树相比，B+ 树的好处是可以将数据全部保存到叶子节点中，而中间节点中并不存放真正的数据，仅仅用作对叶子节点的索引。为了方便起见，树的深度从叶子节点开始计算，叶子节点的深度为 1，之上的中间节点逐层加 1。在 B+ 树中查找匹配项首先要对关键字进行比较并沿对应指针进行遍历，直至搜索到叶子节点为止；而叶子节点也是按照关键字从小到大的顺序进行排列的。也正是由于这种结构，使得 B+ 树非常适合用来存储文件系统结构。

关键字

reiferfs 中采用的关键字包含 4 个部分，形式如下：

这 4 个部分分别表示父目录的 id、本对象的 id、本对象在整个对象（文件）中的偏移量以及类型。关键字的比较就是按照这 4 个部分逐一进行的。读者可能会好奇为什么不简单地采用对象 id 作为关键字。实际上，这种设计是有很多考虑的，采用 directory-id作为关键字的一部分，可以将相同目录中的文件和子目录组织在一起，加快对目录项的存取。offset 的出现是为了支持大文件，一个间接条目（后文中会介绍）最多能指向 (数据块大小-48）/4 个数据块来存放文件数据，在默认的 4KB 数据块中最大只能支持 4048KB 的文件。因此使用 offset 就可以表明该对象在文件中所处的偏移量。type 可以用来区分对象的类型。目目前reiserfs 支持四种类型，TYPE_STAT_DATA、TYPE_INDIRECT 1、TYPE_DIRECT 2、 TYPE_DIRENTRY，解释见后文的条目头部分。

在 3.5 之前的版本中，这 4 部分都是 32 位的整数，这样造成的问题是最大只能支持大约 232=4GB 的文件。从 3.6 版本开始，设计人员将 offset 扩充至 60 位，将 type 压缩至 4 位。这样理论上能够支持的最大文件就达到了 260 字节，但是由于其他一些限制，reiserfs 中可以支持的文件上限是 8TB。正是由于这个原因，reiserfs 中有两个版本的关键字，相关定义如清单 2 所示。

清单2. reiserfs 中与关键字有关的定义

尽管结构定义中并没有显式地声明 offset 和 type 分别是 60 位和 4 位长，但是从几个相关函数中可以清楚地看到这一点。

数据块头

在图 2 中我们曾经介绍过，b+ 树中的节点可以分为格式化节点和未格式化节点两种。未格式化节点中保存的全部是文件数据，而格式化节点中包含了 b+ 树本身需要的一些信息。为了与未格式化节点区分开来，每个格式化节点所占用的数据块最开头都使用一个数据块头来表示。数据块头大小为 24 个字节，定义如清单 3 所示。

清单3. block_head 结构定义

block_head 结构中的 blk_level 表示该节点在 B+ 树中的层次，对于叶子节点来说，该值为 1；blk_nr_item 表示这个数据块中条目的个数；blk_free_space 表示这个数据块中的空闲磁盘空间。

格式化节点可以分为中间节点和叶子节点两类，它们所采用的存储结构是不同的。

中间节点

中间节点由数据块头、关键字和指针数组构成。中间节点中的关键字和指针数组都是按照从小到大的顺序依次存放的，它们在磁盘上的布局如图 3 所示。

图 3. 中间节点的布局

每个关键字就是一个 16 字节的 reiserfs_key 结构，而指针则是一个 disk_child 结构，其大小为 8 个字节，定义如清单 4 所示。

清单4. disk_child 结构定义

其中 dc_block_number 字段是所指向子节点所在的数据块块号，dc_size 表示这个数据块中已用空间的大小。对于一共有 n 个关键字的中间节点来说，第 i 个关键字位于 24+i*16 字节处，对应的指针位于 24+16*n+8*i 字节处。

需要注意的是，对于中间节点来说，数据块头的 blk_nr_item 字段表示的是关键字的个数，而指针数总是比关键字个数多 1，这是由 B+ 树的结构所决定的，小于 Key 0 的关键字可以在 Pointer 0 指针指向的数据块（下一层中间节点或叶子节点）中找到，而介于 Key 0 和 Key 1 之间的关键字则保存在 Pointer 1 指向的数据块中，依此类推。大于Key n的关键字可以在Pointer n+1中找到。

叶子节点

格式化叶子节点的结构比中间节点的结构稍微复杂一点。为了能够在一个格式化叶子节点中保存多个条目，reiserfs 采用了如图 4 所示的布局结构。

图 4. 格式化叶子节点的布局

从图中可以看出，每个格式化叶子节点都以一个数据块头开始，然后是从两端向中间伸展的条目头和条目数据的数组，空闲空间保留在中间，这种设计是为了扩充方便。

所谓条目（item，或称为项）就是可以存储在单个节点中的一个数据容器，我们可以认为条目是由条目头和条目数据体组成的。

清单5. item_head 结构定义

从 item_head 结构定义中可以看出，关键字已经包含在其中了。ih_item_len 和 ih_item_location 分别表示对应条目的数据体的长度和在本块中的偏移量。请注意该结构的第 17、18 个字节是一个联合结构，对于不同类型的条目来说，该值的意义不同：对于 stat 数据条目（TYPE_STAT_DATA）或直接数据条目（TYPE_DIRECT），该值为 15；对于间接数据条目（TYPE_INDIRECT），该值表示最后一个未格式化数据块中的空闲空间；对于目录条目（TYPE_DIRENTRY），该值表示目录条目中目录项的个数。

目前 reiserfs 支持的条目类型有 4 种，它们是依靠关键字中的 type 字段来区分的；而在旧版本的关键字中，则是通过 uniqueness 字段来标识条目类型的，其定义如清单 6 所示。

清单6. reiserfs 支持的条目类型

下面让我们逐一来了解一下各种条目的存储结构。

STAT 条目

stat 数据（TYPE_STAT_DATA）非常类似于 ext2 中的索引节点，其中保存了诸如文件权限、MAC（modified、accessed、changed）时间信息等数据。在3.6 版本的 reiserfs 中，stat 数据使用一个stat_data 结构表示，该结构大小为 44 字节，其定义如清单 7 所示：

清单7. stat_data 结构定义

stat_data 条目使用的关键字中，offset 和 type 的值总是 0，这样就能确保 stat 数据是相同对象（object-id）中的第一个条目，从而能够加快访问速度。

与 ext2 的 ext2_indoe 结构对比一下就会发现，stat_data 中既没有记录数据块位置的地方，也没有记录删除时间，而这正是我们在 ext2/ext3 中恢复删除文件的基础，因此可以猜测得到，在reiserfs 文件系统中要想恢复已经删除的文件，难度会变得更大。

目录条目

目录条目中记录了目录项信息。目录条目由目录头和目录项数据（即文件或子目录名）组成。如果一个目录中包含的目录项太多，可以扩充到多个目录条目中存储。为了方便管理某个目录中子目录或文件的增减，目录条目也采用了与条目头类似的设计：从两端向中间扩充，其布局结构如图 5 所示。

图 5. 目录条目存储结构

目录头是一个 reiserfs_de_head 结构，大小为 16 字节，其定义如清单 8 所示。

清单8. reiserfs_de_head 结构定义

reiserfs_de_head 结构中包含了 deh_dir_id 和 deh_objectid fields 这两个字段，它们就是其父目录关键字中对应的两个字段。deh_offset 的 7 到 30 位是文件名的 hash 值，0 到 6 位用来解决 hash 冲突的问题（reiserfs 中可以使用 3 种 hash 函数：tea、rupasov 和 r5，默认为 r5）。文件名的位置保存在 deh_location 字段中，而 deh_state 的第 2 位表示该目录条目是否是可见的（该位为 1 则表示该目录条目是可见的，为 0 表示不可见）。文件名是一个字符串，以空字符结束，按照 8 字节对齐。

直接条目与间接条目

在 reiserfs 中，文件数据可以通过两种方式进行存取：直接条目（direct item）和间接条目（indirect item）。对于小文件来说，文件数据本身和 stat 数据可以一起存储到叶子节点中，这种条目就称为直接条目。直接条目就采用图 4 所示的存储结构，不过每个条目数据体就是文件数据本身。对于大文件来说，单个叶子节点无法存储下所有数据，因此会将部分数据存储到未格式化数据块中，并通过间接条目中存储的指针来访问这些数据块。未格式化数据块都是整块使用的，最后一个未格式化数据块中可能会遗留一部分剩余空间，大小是由对应条目头的 ih_free_space_reserved 字段指定的。图 6 给出了间接条目的存储结构。

图 6. 间接条目存储结构

对于缺省的 4096 字节的数据块来说，一个间接条目所能存储的数据最大可达 4048 KB（4096*(4096-48)/4 字节），更大的文件需要使用多个间接条目进行存储，它们之间的顺序是通过关键字中的 offset 进行标识的。

另外，文件末尾不足一个数据块的部分也可以像小文件一样存储到直接条目中，这种技术就称为尾部封装（tail packing）。在这种情况下，存储一个文件至少需要使用一个间接条目和一个直接条目。

实例分析

下面让我们来看一个实际的例子，以便了解 reiserfs 中的实际情况是什么样子。首先让我们来创建一个 reiserfs 文件系统，这需要在系统中安装 reiserfs-utils 包，其中包含的内容如清单 9 所示。

清单9. reiserfs-utils 包中包含的文件

mkreiserfs 命令用来创建 reiserfs 文件系统，debugreiserfs 用来查看 reiserfs 文件系统的详细信息，如清单 10 所示。

清单10. 创建 reiserfs 文件系统

从输出结果中可以看出，这是大约是一个 4GB 的分区，总共划分成 977952 个 4096B 大小的数据块；而超级块是第 16 个数据块（从 0 开始计算）。格式化过程中占用了其中的 8241 个数据块，其中从第 18 个数据块开始的 8193 个数据块用于日志（第 8210 数据块供日志头使用）。这个 B+ 树的根节点保存在该分区的第 8211 个数据块中。另外，数据块位图总共占用了 30 个数据块，-m 参数给出了这些数据块位图所占用的数据块的具体位置，这与前文中的介绍是完全吻合的。

我们真正关心的是存储实际数据的部分，从中可以了解在 reiserfs 中是如何对文件进行访问的。下面让我们来看一个实际文件系统的例子。

清单11. 分析 8211 数据块的内容

block.8211.hex 文件中就是根节点中的实际数据，图 7 给出了一个更为清晰的分析结果。

图 7. 新文件系统根节点的数据分析

从图 7 中可以清楚地看出，这是一个格式化叶子节点（深度为 1），其中包含 4 个条目：两个是 STAT 条目，另外两个是目录条目。实际上，它们分别是当前目录和其父目录。继续分析就会发现，当前目录中只包含两个目录项：当前目录及其父目录，因此这是一个空目录。

小结

总体来说，reiserfs 所采用的设计很多都是专门针对如何充分提高空间利用率和改进小文件的访问速度。与 ext2/ext3 不同，reiserfs 并不以固定大小的块为单位给文件分配存储空间。相反，它会恰好分配文件大小的磁盘空间。另外，reiserfs 还包括了围绕文件末尾而专门设计的尾部封装方案，将文件名和文件数据（或部分数据）共同保存在 B+ 树的叶子节点中，而不会像 ext2 那样将数据单独保存在一个磁盘上的数据块中，然后使用一个指针指向这个数据块的位置。

这种设计会带来两个优点。首先，它可以极大地改进小文件的性能。由于文件数据和 stat_data（对应于 ext2 中的 inode）信息都是紧邻保存的，只需要一次磁盘 I/O 就可以将这些数据全部读出。其次，可以有效提高对磁盘空间的利用率。统计表明，reiserfs 采用这种设计之后，可以比相应的 ext2 文件系统多存储超过 6% 的数据。

不过，尾部封装的设计可能会对性能稍有影响，因为它每次文件发生修改时，都需要重新对尾部数据进行封装。由于这个原因，reiserfs 的尾部封装特性被设计为可以关闭的，这样就为管理员在性能和存储效率之间可以提供一个选择。对于性能非常关键的应用程序来说，管理员可以使用 notail 选项禁用这个特性，从而牺牲一部分磁盘空间来获得更好的性能。

与 ext2/ext3 相比，在处理小于 4KB 的文件时，reiserfs 的速度通常会快 10 到 15 倍。这对于新闻组、HTTP 缓存、邮件发送系统以及其他一些小文件性能非常重要的应用程序来说是非常有益的。