作者 ｜ Aneesh Kumar K.V、Mingming Cao、Jose R Santos、Andreas Dilger
翻译 ｜ 焱融技术团队
在上一篇《深入浅出 Ext4 块和 Inode 分配器的优化（上）》中，我们简单地回顾了 Ext3 块分配器的原理和当前的限制，以及介绍了 Ext4 多块分配器和它是如何解决 Ext3 文件系统面对的限制。本文，我们将继续讨论关于 Ext4 和 Inode 分配器的相关内容。先从 Ext4 多块分配器的性能和优势开始，逐步介绍 Ext3 Inode 分配策略、Inode 分配对整体文件系统性能的影响、改变块组的概念如何使性能提升等内容。
Ext4 多块分配器的性能优势在哪里？
与小文件相关的多块分配器性能优势如图七所示，块更接近了，因为它们是在相同的本地（局部）组预分配空间被满足的。
与大文件相关的多块分配器的性能优势如图八所示，块更接近了，因为它们是在特定于 Inode 的预分配空间中被满足的。
图七：多块分配器的小文件性能
图八：多块分配器的大文件性能
下方表一显示了使用 data=orderedmount 选项比较 Ext4 和 Ext3 分配器的compilebench[5] 数量。Compilebench 尝试模拟一些在创建、编译、Patching、Stating 和读取内核树时常见的磁盘 IO 老化文件系统的场景，间接测量文件系统在磁盘填满和目录老化时，维护目录局部性的能力。
表一：Ext4 和 Ext3 分配器的 Compilebench 数量
分配器演化史
Ext4 中的 mballoc 分配器其实是 Alex Tomas（Zhuravlev）写的第三代分配器引擎。该分配器的前两个版本主要集中在大块分配（一次 1MB），而第三代致力于改进小文件分配。
即使在低速率 I/O 下，Ext3 使用的单块分配也不一定是块间分配的好决策。Linux VFS 层将提交给内核的任何大的 I/O 分割成页面大小的块，并强制文件系统分配单个块，而不提供关于该文件上其他未完成的 I/O 的任何信息。第一次分配的块通常是块组中的第一个空闲块，并且不会努力去寻找适合写入文件的数据量的空闲块范围。这会导致出现糟糕的分配决策，比如选择的空闲块范围对于单个 write() 调用来说不够大。
在非常高的 I/O 速率（超过 1GB/s）下，单块分配引擎也会成为 CPU 瓶颈，因为每个块分配都会遍历文件系统分配器，扫描空闲块并锁定，以更新数据结构。使用 mballoc，一项测试表明，通过降低每个分配块的 CPU 成本，可以在同一系统上从 800 MB/s 提高到 1500 MB/s。
mballoc 的成功关键是，基于尽可能多的文件数据块，作出智能分配判断的能力，这就需要为正常 I/O 开发延迟分配。当 mballoc 对文件的大小，以及要分配多少数据块有很好的了解时，就可以作出良好的决策。
第一个版本的 mballoc 只使用了伙伴分配器来分配连续的块，并将分配与空闲 extent 的开头对齐。虽然避免了多次分配的寻道和聚合，带来了一定程度上的性能提升，但当 I/O 在 RAID 磁盘和条带范围边界上正确对齐时，它在具有较低开销的 RAID 设备面前，并不是最优的选择。
第二个版本的 mballoc 改进了伙伴分配器以将大量分配与 RAID 设备边界对齐。这很容易直接从 RAID 几何结构的伙伴位图中完成，该几何结构在每个条带中使用数据磁盘的二次方数字，只需在 RAID 边界大小停止搜索伙伴位图中的空闲位即可。
避免 RAID 系统的“读取-修改-写入”周期，可以使性能提高一倍以上，故而也避免了昂贵的同步读取。在具有与条带边界对齐的读取缓存的 RAID 设备中，执行未对齐读取，将使从磁盘读取的数据量加倍并填充两个缓存行。
Ext4 超级块在 mke2fs 时间段内或使用 tune2fs 存储 RAIDgeometry 的字段时，mke2fs 为了自动填充这些字段，很可能在 mkfstime 为 XFS 完成的复杂 RAID 几何探测也将被采用。
在测试当前第三版 mballoc 的过程中，研究了小文件 I/O 的性能，发现只有在分配给不同文件的块之间没有寻道时，才能显著提高总体性能。因此，组分配机制用于将小分配打包在一起，它们中间没有任何空闲空间。过去，每个文件的末尾总是保留或留下空间，“以防万一”有更多的块要分配。对于小文件，会强制在每次读取或写入后进行查找。使用延迟分配，小文件的大小在分配时是已知的，不再需要每个文件之后的间隙。
当前的 mballoc 分配器可以将分配对齐到非二次方对齐的 RAID 几何结构，尽管它的开销稍微昂贵一些。
在优化定位器方面，仍有许多工作要做。尤其是，mballoc 保留了 Ext2/3 块分配器的“扫描组以获得良好分配”行为。像XFS一样，实现一个更优化的内存中的 free-extent 搜索，会进一步降低搜索空闲区的成本。
此外，初始化伙伴位图也有一些成本。在挂载时执行此操作，就像第一版本的 mballoc 所做的那样，对于非常大的文件系统会带来不可接受的挂载延迟。在首次访问时，执行此操作会增加延迟并损害文件系统首次使用的性能。在挂载时，启动一个线程来扫描组并异步执行伙伴初始化，将有助于避免这两个问题。
延迟分配概述和实现原理
因为 Ext4 会使用 extent 映射来有效地表示大文件，所以可以很自然地一起处理多个块分配，而不是像 Ext3 那样每次只分配一个块。因为 buffer I/O 的块分配请求在 write_begin 时间内一次通过 VFS 层传递，所以底层 Ext3 文件系统无法预见并合并未来的请求。因此，延迟分配被多次提出，以支持缓冲 buffer I/O 的多个块分配。
简而言之，延迟分配从 write() 操作时的块分配推迟到了刷新页的时间。这个方法有很多好处：它增加了将许多块分配请求组合成一个请求的可能性，减少了碎片并节省了 CPU 周期。同时，避免了对短期文件进行不必要的块分配。
通常，使用延迟分配，VFS 不会在 write_begin() 中分配磁盘块，而是进行普通块查找。对于那些未映射的 buffer-heads，它会计算需要保留的块数（包括数据块和元数据块），Ext4 块和 Inode 分配器的改进保留了它们，以确保文件系统中有足够的空闲块来满足写请求。上述操作完成后，buffer-head 会被标记为延迟分配（BH_DELAY），此时没有进行块分配。稍后，当页面通过 writepage() 或 writepages() 刷新到磁盘时，这些函数将遍历指定 Inode 中的所有脏页，聚集逻辑上连续的脏页，并尝试为所有标记为 BH_DELAY 的缓冲区头执行集群块分配，然后将页面提交给 bio 层。块分配完成后，未使用的保留块返回文件系统。
目前延迟分配的实现，大多在 VFS 层完成，希望 Ext2 和 Ext3 等多个文件系统能够受益于该特性。Ext4 为延迟分配模式添加了新的地址空间操作，为延迟分配提供了 write_begin()、write_end() 和writepage() 的回调函数，并具有更新的块的分配、保留、查找功能。当前的 Ext4 延迟分配仅支持 data=writeback 日志模式。将来，计划添加对 data=ordered 模式的延迟支持。
细说 FLEX_BG 和 Inode 分配器
旧 Inode 分配器
Ext2/3 文件系统中的 Inode 分配器使用块组作为媒介，来确定新 inode 在存储介质上的位置。Ext2/3/4 文件系统被分成多个小块组，块组大小由单个位图可以处理的块数量决定。在 4 KB 块文件系统中，单个块位图可以处理 32768 个块，每个块组总共 128 MB。这意味着对于每 128 MB，就有元数据块（block/Inode 位图和 Inode table block）中断连续块，该连续块本可用于分配数据。
Orlov 目录 Inode 分配器 [6] 试图通过减少在空闲块计数较低的块组中，分配一个 inode 的机会来最大化获得大块分配的机会。Orlov 分配器还试图维护相关数据（即同一目录中的文件）的局部性。Orlov 分配器通过查看空闲块、空闲索引节点和块组中的目录数量比例，来找到目录索引节点的最佳位置。非目录的 Inode 分配由第二个分配器处理，该分配器从父目录所在的块组开始空闲 Inode 搜索，并尝试将具有相同父 Inode 的 Inode 放置在同一块组中。虽然考虑到 Ext2/3/4 的块组设计，这种方法非常好，但它确实有一些限制：
- 1 TB 的文件系统大约有 8192 个块组，在大量使用的文件系统上搜索这么多块组，开销可能会变得很高。
- Orlov 可以将目录 Inode 放置在物理上远离其父目录的随机位置。
- Orlov 计算寻找单个 128 MB 块组的计算成本很高。
- 考虑到硬盘寻道时间在未来几年不会有太大的改善，同时容量和接口吞吐量会大幅度提升，Orlov 分配器在改善数据局部性方面几乎没有做任何动作。
当然，真正的问题不在于 Orlov 本身，而是块组大小对其施加的限制。解决此限制的一种解决方案是，实现多块位图。缺点是，在搜索空闲块以替换坏块时，处理其中一个位图或 Inode 表中的坏块之类的事情会变得非常复杂。一个更简单的解决方案是，摆脱元数据需要位于文件系统块组中的概念。
FLEX_BG
简单地说，新的 FLEX_BG 消除了特定块组的位图和 Inode 表必须位于该块组的块范围内的限制。我们可以消除这个限制，主要是因为 e2fsprogs 是一个通过 fsck 查找错误的强大工具。虽然激活 FLEX_BG 功能标志本身不会改变 Ext4 的任何行为，但该功能确实允许 mke2fs 用以前不可能的方式分配位图和 Inode 表。通过将位图和 Inode 表紧密地分配在一起，可以构建一个大型虚拟块组，从而绕过常规块组的一些大小限制。
通过移动元数据块，新的 extent 特性受益于新的元数据分配，否则会阻止存储介质上连续空闲块的可用性。通过将这些块移动到一个大型虚拟块组的开头，可以提高分配更大 extent 的可能性。此外，将多个块组的元数据连续存储在磁盘上，可以避免寻找元数据密集型工作负载，包括 e2fsck。
FLEX_BG Inode 分配器
既然我们现在可以拥有一个更大的块集合，可以称之为块组，那么让内容利用这种能力显然是下一步。由于 Orlov 目录 Inode 分配器的一些设计决策取决于传统块组的大小限制，所以新的 inode 分配器需要采用不同的技术，以便更好地利用磁盘元数据分配。新的 Inode 分配器与旧分配器的一些不同之处是：
- 分配器总是在尝试分配另一个组之前，尝试将虚拟块组填充到某个空闲块比率。这样做是为了通过尽可能避免寻道来改善磁盘上的数据局部性。
- 对目录的处理方式与常规 Inode 的处理相同。考虑到这些虚拟块组现在可以处理价值数 GB 的空闲块，跨块组扩展目录不仅不能提供相同的优势，而且实际上可能会因为允许对相对少量的数据进行更大的搜索而损害性能。
- 分配器可以向后搜索合适的块组。如果当前组没有足够的空闲块，它可以会先尝试前一个组，以防空间被释放。
- 分配器为组中的文件追加保留空间。如果使用了一个组中的所有块，那么将块追加到该组中的一个 Inode，可能意味着分配发生在存储介质内的较大偏移处，从而增加了寻道时间。除非最后一个组已超过其保留比例，否则这个块预留不会被使用。
虚拟组的大小始终是异常块组大小的二次方倍数，并在 mke2fs 时间指定。大小存储在超级块中，用来控制如何构建内存中空闲的 Inode 和块结构，算法使用这些块结构来确定虚拟块组的利用率。因为我们只在找到合适的虚拟组时，才查看 Ext4 块组描述符，所以在大端序机器上，该算法比传统的 Orlov 分配器需要更少的端序转换。
与旧的分配器相比，这种新的 Inode 分配器的一个重点是，维护数据和元数据的局部性，以减少寻道时间。另一个非常重要的部分是，减少分配开销。通过不同的方式处理目录 Inode，我们从旧分配器中消除了很多复杂性，而更少数量的虚拟块组使搜索足够的块组更容易。
既然一组 Inode 表被视为单个大型 Inode 表，那么新的分配器还受益于 Ext4 中的另一个新特性。未初始化的块组在 Inode 表没有被使用时，将其标记为未初始化，因此在 fsck 时跳过读取这些 Inode 表，从而显著提高了 fsck 的速度。因为分配器仅在同一虚拟组上的前一个表已满时，才使用 Inode 表，所以初始化的 Inode 表更少，从而需要加载的 Inode 表更少， fsck 时间也更短。
性能结果展示
我们使用 FFSB[4] 基准测试和一个配置文件，该配置文件执行小文件读取、写入、创建、追加和删除操作，这有助于模拟元数据繁重的工作负载。使用光纤通道磁盘阵列作为存储介质进行 FFSB 测试，具有1 GB 快速写入缓存。该基准测试是在一个包含 64 个打包组的 FLEX_BG 虚拟块组中运行的，并将其与安装有 bot mballoc 和 delalloc 的常规 Ext4 文件系统进行比较。请注意，64 个压缩组合并不是每个硬件配置的最佳数量，但这个数字为可用硬件上的工作负载提供了非常好的总体性能。需要进一步研究，以确定适合特定硬件配置或工作负载的合适大小。
表二：FFSB 小元数据光纤通道（1 个线程）- 具有 64 个块组的 FLEX_BG
在表二中，单线程结果显示每秒操作吞吐量总体提高了 10%。在表三中，16 个线程结果显示，比常规 Ext4 分配更好地提高了 18%。结果还表明，与正常分配相比，使用 FLEX_BG 分组时，从 1 到 16 个线程的可伸缩性提高了 5.6%。
表三：FFSB 元数据（16 个线程）FLEX_BG 有 64 个块组
为了查看新分配器对更复杂的目录布局的整体效果，我们使用了 Compilebench[5]，它会生成指定数量的 Linux 内核树状目录，其中的文件代表实际内核树中的文件大小。在表四中，我们看到使用分组和新的 Inode 分配器时，基准测试的总体结果更好。一个例外是“读取树”和“读取编译树”，它们显示的结果稍慢，这说明元数据分配和 Inode 分配器还有一定的改进空间。
表四：包含 64 个块组的 flex_BG
展望未来
Ext4 中元数据分组的概念仍然处于起步阶段，还有很大的改进空间。我们希望通过查看元数据的布局来提高 Ext4 文件系统的性能。因为 FLEX_BG 特性的定义消除了元数据放置的限制，这允许虚拟组的实现是流畅的，而不会牺牲向后兼容性。
其他值得探索的优化是，将元数据放置在虚拟组的中心，而不是开始寻找最坏的情况。因为当前的实现只集中于 Inode 来操作块分配器，所以未来的实现可以更进一步，使各种块分配器具有 FLEX_BG 分组感知能力。由于组的大小取决于与磁盘本身相关的内容，所以让 mke2fs 可以更智能地根据媒介大小、媒介类型和 RAID 配置自动设置虚拟组大小，这将有助于用户部署该特性。
消除文件系统大小限制的短期修复正在进行中。当前代码会在内存数据结构中存储了所有空闲块和构建虚拟块组的 Inode 总和。这意味着，如果数据结构超过页面大小，分配将失败，在这种情况下，我们将在非常大的文件系统上恢复到旧的分配器。虽然这是一种性能特性，但将所有这些信息存储在内存中，对于非常大的文件系统来说，可能有些过分。在 LRU 模式之上构建它可以消除这个限制并节省内核内存。
✦ 总结 ✦
从 Ext3 文件系统衍生出 Ext4 文件系统的主要动机是，打破相对较小的文件系统大小限制。这满足了大文件、大 I/O 和大量文件的需求。为了将 Ext4 文件系统维护为桌面上的通用文件系统，确保 Ext4 文件系统在小文件上表现更好也很重要。
我们已经讨论了与 Ext4 文件系统中的块分配和 Inode 分配有关的工作，以及如何满足使 Ext4 成为桌面和服务器的高性能通用文件系统这两种相互冲突的要求。预分配、延迟分配、组预分配和多个块分配的组合极大地减少了 Ext3 文件系统中出现的大文件分配时，出现的碎片问题和小文件的局部性差问题。通过与 FLEX_BG 紧密地分配位图和 Inode 表，可以构建一个大型虚拟块组，从而增加了分配大块扩展的可能性，并允许 Ext4 文件系统更好地处理元数据密集型工作负载。未来的工作，包括对 ordered 模式日志和在线碎片整理的延迟分配的支持，将有助于未来减少文件碎片问题。
,
