作者 ｜ Aneesh Kumar K.V、Mingming Cao、Jose R Santos、Andreas Dilger
翻译 ｜ 焱融技术团队
当前，对于小文件和大文件来说，文件系统对块分配器的需求是冲突的。相对小的文件应该在磁盘上紧挨着，使磁盘磁道缓存最大化并且可以避免寻道。为了避免碎片，文件的增长需要预留空间。Ext4 新的多块和延迟分配器通过推迟分配到刷新时间，可以连续地打包小文件和在 RAID 设备对齐的边界上分配大文件并为增长保留空间，来尝试满足这些需求。在本文中，我们讨论了 Ext4 的新多块分配器，并将其与基于预留 (reservation) 的分配进行了比较。我们同样讨论了将元数据块紧密放在磁盘上的性能优势，从而减少元数据密集型工作负载的搜索量。
什么是 Ext4 文件系统？
Ext4 文件系统是大约在两年前从 Ext3 文件系统中分化出来的，为了解决 Ext3 文件系统的容量和可扩展性瓶颈。Ext3 文件系统的大小在 x86 架构上被限制为 16TB，作为 32 位块编号的结果。目前全世界的企业都已经达到了这个极限。同时，随着磁盘容量每年 100% 增长，以及对更大文件系统存储个人数字媒体的需求不断增加，桌面用户很快就会希望消除对 Ext3 文件系统的限制。因此，在 Ext4 文件系统中做的第一个更改是，将最大文件系统大小从 232 个块（16TB 和 4KB 块大小）提升到 248 个块。
Ext4 也使用了范围映射(extent mapping)来实现新文件，而不是 Ext2/3 中两次三次的间接映射。Extent 在许多现代文件系统中都用到了 BEST, S. JFS 概述(http://jfs.sourceforge.net/pr...)，众所周知，它是一种通过减少处理大文件所需的元数据的方式，有效表示大型连续文件的方法。其中，Extent 有效提升了顺序文件读写的性能，主要是因为 Extent 写入的描述连续块元数据量要少得多，从而减少了文件系统开销。随着元数据更新的减少，它还大大减少了截断文件的时间。Ext4 支持的 Extent 格式如图 1 和图 2 所示。Ext4 功能的完整描述可以在 2007 年渥太华 Linux 研讨会上讨论的“新 Ext4 文件系统：当前状态和未来计划”（ols2007v2-pages-21-34.pdf (http://kernel.org)）中找到。
大多数文件只需要很少的 Extents 来描述它们从逻辑到物理上的块映射，这可以容纳在 Inode 或单个 Extent 映射块中。不过，一些极端的场景，例如具有随机分配模式的稀疏文件，或非常严重的碎片文件系统，则不能使用 Extent 映射来高效地表示。在 Ext4 中，更重要的是拥有一个高级块分配器来减少文件碎片。一个设计良好的块分配器应将小文件彼此靠近打包以实现局部性，并将大文件连续放置在磁盘上以提高 I/O 性能。
图一：Ext4 extent，头和索引结构
图二：Ext4 extent 树布局
如上，Ext3 文件系统中的块分配器无法实现在相同目录下，实现减少小文件碎片，并且保持组局部性的限制工作。Ext3 分配器尝试尽最大努力分配多个块，但不会进行智能搜索，找到放置大文件的更好位置。同时，它也无法感知不同文件之间的关系，所以很可能将相关的小文件放置在很远的地方，导致在加载大量相关文件时，出现额外的搜索。另外，Ext4 块分配器尝试使用新的多块分配器来解决这两个问题，并仍然可以使用旧的块分配器，以及 -o mballoc 和 -o nomballoc 挂载选项来分别启用和禁用多块分配。当前，Ext4 文件系统的开发版本默认启用多块分配器。
虽然在块分配器上做了很多工作，但不要忘记，Inode 分配器决定了块从哪里开始分配。尽管这些年来磁盘盘片密度急剧增加，但旧的 Ext3 Inode 分配器几乎没有确保数据和元数据的局部性，以便利用该密度并避免大量寻道。目前，Ext4 已经开始探索压缩数据，以便于增加局部性并减少寻道的可能性，并且带来更好的性能体验。在 Ext4 块组中受限删除的部分，可能需要重新考虑如何放置元数据和如何分配 Inode，而这些方式在 Ext3 中是无法实现的。
Ext3 和 Ext4 的异同
什么是 Ext3 文件系统块分配器？
块分配是文件系统设计的核心。在文件系统中，块分配的目标是通过减少文件系统碎片和维持相关文件的局部性，以此减少磁盘寻道时间。另外，它还需要在大型文件系统和并行分配场景中，有较好的扩展性。
据了解，Ext3 文件系统为了方便扩展，被分为多个 128MB 的块组块(block group chunks)。每个块组维持一个单独的 block bitmap 来描述这个块组内部的数据块可用性。同时，这种方式可以并行完成不同块组上的分配。
当为文件分配一个块时，Ext3 文件系统块分配器总是从 Inode 结构存储所在的块组开始，以此来使元数据和数据块彼此靠近。当目标块组内没有空闲的可用块时，它将搜索所有块组的剩下部分来找到一个空闲块。Ext3 总是试图让同一目录下的文件彼此靠近，直到父块组被填满。
为了减少大文件碎片，Ext3 通过一个目标块来提示它应该从哪里分配下一个块。如果应用程序正在执行顺序 I/O，则目标是获取最后分配的块后面的块。当目标块不可用时，它会进一步搜索一个至少拥有 8 个块的空闲范围，并从那里开始分配。通过连续的方式，进行分配。
在多个文件并行分配块的场景中，Ext3 块分配器通过块保留 (block reservation) 的方式，来确保对特定文件的块的后续请求在与其他文件交错之前得到服务，以此满足后续请求的块保留，并使块分配器可以放置与附近文件对应的块。同时，每个文件都有一个保留窗口，以此来表示为该文件保留的磁盘块范围。
但是，由于每个文件的保留窗口是全部在内存中完成，所以每个块的分配都会首先检查文件自己的保留窗口，然后在位图上查找未保留的空闲块。因为每文件系统的红黑树都会用于维护所有保留窗口，所以在确保使用位图分配块时，我们不会将块分配到另一个文件的保留窗口之外。
Ext3 文件系统块分配器存在的问题
尽管块预留使得在 Ext3 中分配多个块有了可能性，但这是非常有限的，并且是基于尽力而为的 (based on best effort basis) ，导致 Ext3 仍使用位图来搜索保留的空闲块。由于分配器仅在保留窗口内搜索空闲块，所以整个文件系统中缺少空闲范围 (Extent) 信息，导致容易出现多块分配模式不佳的情况。
Ext3 块分配器的另一个缺陷是，它并不会区分大小文件的分配。大目录，像/etc，包含大量的小配置文件，这些文件都需要在启动时读取。如果文件放置在磁盘上相距很远的地方，那么启动过程会因为在底层设备上进行昂贵的寻道，导致出现延迟加载所有文件。 如果块分配器可以将这些相关的小文件放置得更近，那这将对读取性能有很大的好处。
我们通过两个测试用例来说明，Ext3 块分配器对小文件和大文件的性能特征。如图 3 和图 4 所示，在第一个测试中，我们使用一个线程来顺序地创建 20 个 12KB 的小文件；在第二个测试中，我们并行地创建了单个大文件和多个小文件。大文件是由单线程创建，而小文件由另一个线程并行创建。该图片上用 x 轴上的逻辑块号和 y 轴上的物理块号绘制。为了更好地说明局部性，绘制的物理块数是通过从实际分配的块数，减去第一个分配的块数来计算的。对于小文件，第四个逻辑块号是第二个文件的第一个逻辑块号，以便于更好地说明小文件在磁盘上的位置有多近。
图三：Ext3 对小文件的块分配器
图四：Ext3 对大文件的块分配器
由于 Ext3 仅使用目标块来确定新文件的放置位置，所以 Ext3 分配器有意将小文件分开，以避免在文件是大文件的情况下产生过多碎片。这主要是因为不知道这些小文件是由同一进程生成的，而本应该彼此靠近。正如我们在图三中看到的，尽管文件本身没有碎片，但是这些小文件的局部性仍然很差。
图四中，我们呈现了 Ext3 中大文件的碎片。因为 Ext3 不知道大文件和小文件是无关的，尽管块预留已经在一定程度上帮助减少了碎片，但仍旧会出现大文件和小文件争夺附近空闲空间的情况。想要解决这个问题，更好的解决方案是，在一开始就将大文件的分配与无关的分配保持距离，以避免交错碎片。
Ext4 文件系统多块分配器登场
Ext4 多块分配器的出现，主要是为了尝试解决上文讨论 Ext3 块分配器出现的限制——为大小文件提供更好的分配。解决这个限制的办法是，通过对来自不同分配的请求，使用不同策略的方式。其中，对相对小的分配请求，Ext4 可以让这些小文件彼此靠近，并尝试分配一个 Per-CPU 的局部组，局部组是被相同 CPU 的所有分配共享的；而大的分配请求首先会从每个文件的预分配中分配。与 Ext3 预留一样，Ext4 为每个文件维护一个内存中的预分配范围，并以此解决并发分配带来的碎片问题。
Ext4 多块分配器维护两个预分配空间，从中满足块的请求：一个 Per-Inode 的预分配空间；另一个 Per-CPU 的局部组预分配空间。其中，Per-Inode 预分配空间用于更大的请求。同时分配块的情况，则有助于确保更大的文件更少交错。而 Per-CPU 的局部组预分配空间则用于较小的文件分配，并有助于确保将小文件放在磁盘上更近的位置。
使用哪个预分配空间取决于，当前的文件大小和分配请求得出的总大小。分配器提供了一个可调的 /prof/fs/ext4//stream_req，默认为 16。如果总文件大小小于 s tream_req 个块，那么我们可以使用每个 CPU 局部组预分配空间。
当从 Inode 预分配空间中分配块时，我们可以通过随机写入的方式，减少碎片选择块。这是通过把逻辑块号存储设计为预分配空间的一部分，并使用该值来判断后续请求分配的物理块。
如果我们无法从预分配空间中分配块，那么我们将查看每个块组的伙伴缓存 (Buddy Cache)。伙伴缓存由多个空闲 Extent 映射和组位图构成。Extent 映射是在第一个分配时，通过扫描所有的空闲块形成的。
当扫描一个块组中的空闲块时，我们将预分配空间中的块视为已分配，而不将它们视为空闲块。以此确保从区段映射分配块时，我们不会从预分配空间分配块，否则会导致文件碎片。
通过扫描块组获得的空闲 Extent，映射如图五所示的格式存储，称为伙伴位图。同时，还呈现了块组位图和 Extent 图。此位图与磁盘上的块组位图的不同之处在于，它将预分配空间中的块已分配，然后空闲 Extent 信息和位图存储在内核 Inode 的页面缓存中，并使用组号进行索引。另外，包含空闲区段信息和位图的页面计算如图 6 所示。
图五：Ext4 伙伴缓存布局
图六：伙伴缓存 Inode 偏移映射
在从伙伴缓存分配块之前，我们将请求规范化，这有助于防止空闲 Extent 映射的严重碎片化。该映射以 2 的幂对空闲块进行分组。从伙伴缓存中分配的额外块，随后会被添加到预分配空间，以便从预分配空间提供后续块请求。在大文件的情况下，规范化遵循基于文件大小的启发式列表 (list of heuristics based on file size)；对于较小的文件，我们将块请求规范化为条带大小（如果在挂载时指定）或 s_mb_group_prealloc。s_mb_group_prealloc 默认为 512，可以通过 /proc/fs/ext4/<partition group_prealloc="" 进行配置。="" <="" div="">
在伙伴缓存中搜索块包括：
- 在 Extent 映射中搜索请求数量的块；
- 如果没找到，并且请求大小与条带大小相同，则在条带对齐的块中搜索空闲块。 搜索条带对齐的块可以在 RAID 配置下更好地分配；
- 如果未找到，在位图中搜索空闲块，并使用找到的最佳 extent。
每次搜索都会从找到目标块的块组开始，并非所有块组都用于伙伴缓存搜索。如果我们在 Extent 映射中查找块，我们只查看具有请求的块顺序块组。当搜索条带大小对齐的空闲块时，我们只查看具有条带大小的空闲块的块组。 当位图中搜索空闲块时，我们则会查看具有请求数量的空闲块的块组。
✦ 后记 ✦
本篇文章简单地回顾了 Ext3 块分配器的原理和当前的限制，以及介绍了 Ext4 多块分配器和它是如何解决 Ext3 文件系统面对的限制的。接下来，我们将继续给大家解读 Ext3 Inode 分配策略、Inode 分配对整体文件系统性能的影响、改变块组的概念如何使性能提升，以及新的 Inode 分配器在元数据分配中使用这个新概念来操纵磁盘上的块分配和数据局部性等内容，请大家持续关注。
