本文收录在 Proceedings of the 19th USENIX Conference on File and Storage Technologies 中。

2021 年 2 月 23 日至 25 日

978-1-939133-20-5 开放访问会议记录

第 19 届 USENIX 文件和存储技术会议由 USENIX 赞助。

pFSCK：加速现代存储的文件系统检查和修复

David Domingo 和 Sudarsun Kannan，罗格斯大学

https://www.usenix.org/conference/fast21/presentation/domingo

pFSCK：加速现代存储的文件系统检查和修复

大卫·多明戈，苏达森·坎南

罗格斯大学

抽象

我们提出并设计了 pFSCK ，这是一种并行文件系统检查和恢复 （C/R） 工具，旨在利用现代存储设备中的计算和存储并行性。pFSCK 可在 inode 和目录块的粒度上实现细粒度并行性，而不会影响 C/R 的正确性。pFSCK 首先采用数据并行性，在检查逻辑的每个阶段识别功能操作，然后隔离依赖操作和共享数据结构。但是，完全隔离共享结构是不可行的，需要序列化更新。为了减少序列化瓶颈，pFSCK 引入了流水线并行性，允许多个阶段的 C/R 并发运行，而不会影响正确性。此外，pFSCK 还提供每线程 I/O 缓存管理、跨 C/R 阶段的动态线程放置以及资源感知调度程序，以减少 C/R 对共享 CPU 和文件系统的其他应用程序的影响。对 pFSCK 的评估显示，它比 e2fsck（Ext 文件系统 C/R）高出 2.6 倍以上，比 XFS 的 C/R 高出 1.8 倍以上，后者提供了粗粒度的并行性。

介绍

与硬盘相比，SSD、NVMe 和字节可寻址 NVM 存储技术等现代超快存储设备提供更高的带宽功能和更低的延迟，从而为利用 CPU 并行性提供了更好的机会。虽然I/O访问性能有所提高，但存储硬件和软件错误仍在继续增长，再加上影响文件系统可靠性的更新和探索性高性能设计[10,12,18,21,27,46]。几十年来，文件系统检查和修复工具（以下简称C/R）通过识别和纠正文件系统的不一致，在提高软件存储的可靠性和系统的可用性方面发挥了关键作用[41]。

先前的大量工作表明，在数据中心发生系统崩溃或故障时，C/R 通常用作系统恢复的第一个补救解决方案。之前的工作 [21， 27] 以及与文件系统维护人员和组织 IT 团队的讨论表明，C/R 在各种场景中运行。这包括由于硬件或软件错误[11,21,27]，定期维护或强制安全升级[37]而导致的重新启动期间的问题。当 C/R 以脱机方式在磁盘分区上运行时，该分区的数据不可用。某些 C/R 支持在线检查，但至关重要的是它们不会干扰使用同一设备的其他应用程序。因此，提高 C/R 性能和灵活性对于系统可用性和减少对其他应用程序的性能影响至关重要。

文件系统 C/R 工具通过识别和修复文件系统元数据的结构不一致来工作。不一致可能出在 inode、数据和 inode 位图、链接或目录条目结构中。众所周知且广泛使用的工具，如 e2fsck（Ext4 的文件系统检查器）[2] 将 C/R 划分为多个阶段（通常称为传递），每个传递负责检查文件系统结构（例如，目录、文件、链接）。然而，众所周知，C/R的速度非常慢，随着文件和目录数量的增加，C/R时间呈线性增加[24,38–41]，有时持续数小时[37]甚至数周[11]。尽管现代闪存和 NVM 技术提供了更低的延迟和带宽，但当前的 C/R 工具无法利用此类硬件功能或多核 CPU 并行性。虽然现代 C/R 试图提高并行性，但它们采用粗粒度方法，例如跨逻辑卷或逻辑组并行化 C/R，这不足以在跨逻辑组数据不平衡的文件系统上加速 C/R [20， 24， 39， 42]。

为了克服这些限制，我们提出了 pFSCK，这是一种并行 C/R，它利用 CPU 并行性和现代存储的高带宽来加速离线和在线形式的文件系统 C/R，从而减少系统停机时间并提高数据（和系统）的可靠性和可用性 [10， 20， 21， 39]。虽然 pFSCK 借鉴了先前任务并行性研究 [35， 45] 的思想，但它必须解决特定于 C/R 的几个挑战，其中包括在不影响正确性的情况下提高复杂文件系统布局和共享文件系统结构（例如通用位图）的可伸缩性，适应各种文件系统配置，以及减少 C/R 对其他应用程序的影响。pFSCK 引入了细粒度并行性，即在 inode 和目录块的粒度上并行，从而比传统的 C/R 执行速度快得多。尽管数据并行性加快了检查速度，但每次传递中对全局数据结构（例如位图）的更新旨在与文件系统的布局（例如，Ext4 文件系统中的块位图）相匹配，并且必须同步以确保检查的正确性。因此，随着线程数的增加，同步和序列化的成本很快就会超过性能提升。因此，pFSCK 引入了流水线并行性，以将 C/R 与逻辑流（即跨多个传递）并行化。

在 pFSCK 中支持数据和管道并行性需要解决多个挑战。首先，必须对正确性进行某些一致性检查。例如，一个

USENIX协会

第 19 届 USENIX 文件和存储技术会议 113

目录检查阶段无法证明目录没有错误，直到其所有文件都通过 inode 检查阶段验证为一致。为了解决这些排序限制，我们从现代硬件处理器中汲取灵感，这些处理器支持无序执行，但有顺序指令提交。我们隔离全局数据结构并并行执行所有必要的操作，但仅在合并结果时验证正确性。其次，跨不同 C/R 传递对 CPU 线程进行静态分区是次优的，因为处理不同元数据（例如，文件、目录、链接）的时间差异很大（例如，检查目录可能比文件花费的时间长得多）。因此，我们提出了 pFSCK 调度器，这是一个动态线程调度器，它监视 pFSCK 不同传递的进度，并使用待处理的工作比率进行线程分配。

第三，当前 C/R 中的 I/O 缓存和预读机制等 I/O 优化不是为多线程并行而设计的，我们通过设计线程感知 I/O 缓存来解决这一问题，从而大大减少 I/O 等待时间。最后，为了在不影响共享 CPU 或访问由 C/R 检查的相同磁盘的其他共同运行应用程序的性能（在线检查）的情况下利用多核并行性，我们设计了一个资源感知型 pFSCK 调度程序，它通过监控系统的总 CPU 利用率来动态扩展跨通道的 C/R 线程。

pFSCK 的上述技术的组合大大减少了 C/R 运行时间。例如，在 1TB NVMe（和 2TB SSD）上使用 pFSCK 的数据并行性和流水线并行性，与广泛使用的 e2fsck 相比，文件和目录密集型磁盘配置的 C/R 运行时间分别减少了 2.6 倍和 1.6 倍，比 XFS C/R 工具减少了 1.8 倍。此外，pFSCK 的调度器将收益提高了 1.1 倍。在 pFSCK 和 RocksDB 之间共享 CPU 时，资源感知机制将 pFSCK 性能下降降至 1.07 倍，并将 RocksDB 的性能开销限制在 1.05 倍。在线 C/R 性能比 vanilla e2fsck 提高了 1.7 倍。最后，pFSCK 将 I/O 吞吐量提高了 2.7 倍，内存使用量比 e2fsck 提高了 1.3 倍（从 e2fsck 中的 2.7 GB 增加到 3.5 GB），以管理线程的任务结构。

背景和动机

我们首先简要介绍当前硬件趋势、C/R 工具的背景，然后讨论加速 C/R 的先前方法及其局限性。

硬件和软件趋势

与传统硬盘相比，SSD和NVMe等现代超快存储设备不仅提供高带宽（8-16 GB/s），而且存储访问延迟降低了两个数量级（<20 μ秒）[31,49]。另一方面，快速存储类内存（如英特尔的 DC 傲腾 [5] 和其他字节可寻址持久内存技术）正在随着访问延迟< 1 微秒而发展。近年来

一些新的文件系统已经发展到利用这些硬件优势。大量先前和正在进行的研究正在开发优化的文件系统，以支持快速存储硬件。这包括用于 SSD 的文件系统 [34]、NVM [44]、针对 NVM 优化传统 Ext4 和 XFS 文件系统的开源工作 [48]，以及其他研究工作 [30， 33， 50]。然而，减少这些文件系统的数据损坏和错误需要几年的生产使用[9,28]。虽然文件系统 C/R 工具将在这些文件系统中发挥至关重要的作用，但它们尚未得到优化，以提取硬件存储优势和多核并行性。

文件系统检查和修复

自文件系统诞生以来，一致性一直是一个问题。尽管已经开发了诸如日志、写入时复制、日志结构写入和软更新等存储机制来缓解潜在的文件系统不一致，但它们受到限制，因为它们无法修复过去因磁盘故障、位翻转、过热或相关崩溃等事件表现出的软件错误或损坏而产生的错误 [13 –15,29,51]。在这些情况行的 C/R 工具（如 e2fsck 和 xfs_repair [42]）用于检测和修复损坏和错误，方法是遍历文件系统的布局并检查 inode 一致性、目录一致性、文件和目录连接性、目录条目一致性以及 inode 和块的一致引用计数

C/R 用法。文件系统 C/R 的频率和生成的运行时在实际环境中有很大差异。虽然缺乏有据可查的 C/R 最佳实践，但我们与文件系统 C/R 维护者、基础设施团队和其他公开讨论的讨论表明，e2fsck 和 xfs_repair 等 C/R 工具对于当前大规模和个人计算系统中的数据可靠性仍然至关重要，因为它们通常在系统错误后运行 [7， 21、27、29]、硬件或内核升级，甚至在强制性安全更新之后。不频繁的 C/R 和存储维护可能会使系统停机时间增加到 3 小时 [37]，在极端情况下，PB 级文件系统会增加数周 [11]。

相关工作

众所周知，磁盘容量、整体文件系统大小和文件计数的增加使 C/R 运行时间更长，导致停机时间延长，并迫使开发人员和用户冒着数据丢失的风险减少 C/R 使用量 [1， 7， 8， 25， 36]。接下来，我们将讨论离线（未挂载的文件系统）和在线 C/R 的最新 C/R 优化及其局限性。广泛使用的开源工具，如 Ext4 文件系统的 e2fsck 跨多个磁盘 （e2fsck） 并行化 C/R，其中 XFS 文件系统的xfs_repair跨磁盘和卷逻辑组并行化 C/R。Ffsck [41] 和 Chunkfs [26] 等其他方法建议通过修改文件系统来加速 C/R 速度，以在逻辑组之间提供更好的平衡。例如，Chunkfs 通过将文件系统划分为更小的隔离组来利用磁盘带宽，这些组可以单独和并行修复。相比之下，Ffsck [41] 重新排列元数据块

第 19 届 USENIX 文件和存储技术会议

USENIX协会

以降低寻道成本并优化文件系统遍历。SQCK [19] 通过利用声明性查询进行跨文件系统结构的一致性检查来增强 C/R。虽然以前的方法已经推进了 C/R 创新，但它们存在一些弱点。首先，大多数先前的技术都无法利用多核并行性和高存储带宽。其次，先前的并行化工作大多是粗粒度的（ e2fsck、xfs_repair、Chunkfs）。例如，正如我们在第 6 节中所示，对于跨逻辑组并行的 XFS 文件系统，跨逻辑组的文件数量的不平衡以及目录元数据检查缺乏并行性会导致高开销。最后，SQCK 和 Ffsck 等技术需要对文件系统元数据进行侵入性更改、块放置或重新构建 C/R，从而阻碍了广泛采用。

在线 C/Rs。在过去的十年中，我们一直在积极推动开发在线 C/R 技术，以识别和修复错误，同时应用程序同时使用文件系统，以减少系统停机时间并允许主动识别潜在的有害损坏。专有的在线 C/R（如 WAFL 文件系统的 Iron [32]（一种基于 NetApp 的 WAFL 文件系统的 C/R 工具）通过应用不变量（例如在使用任何软件之前检查所有块，在任何数据或元数据块（inode 块）之前检查祖先块（目录））来执行增量实时 C/R。为了将 C/R 扩展到 PB，WAFL-Iron 希望客户能够提供块级校验和、RAID，最重要的是，良好的存储实践。或者，Recon 通过在运行时验证元数据的一致性来保护文件系统元数据免受错误操作的影响 [16]。这样做允许 Recon 在将元数据提交到磁盘之前检测元数据损坏，从而防止错误传播。Recon 不执行全局扫描，也无法识别或修复源自硬件故障的错误。C/R，如e2fsck，传统上是供离线使用的，它允许在文件系统仍在使用时，利用基于LVM的快照和扫描快照上的错误来进行部分在线检查[3]。但是，如果需要修复错误，则必须脱机使用 C/R。在本文中，我们还研究和评估了开源和广泛使用的在线 e2fsck 与利用存储和计算并行性的在线 pFSCK。

C/R 正确性。为了确保 C/R 本身的正确性和崩溃一致性，并在系统故障时更可靠地恢复，Rfsck-lib [17] 为 C/R 提供了强大的撤消日志记录。pFSCK 的细粒度并行目标与 Rfsck-lib 是正交的;但是，合并 Rfsck-lib 可以进一步提高 pFSCK 的可靠性。

动机与分析

为了加速 C/R，我们首先破译了广泛使用的 Ext4 文件系统的 e2fsck C/R 工具的性能瓶颈。我们首先提供 e2fsck 的概述，然后检查 e2fsck 的运行时针对不同的文件系统配置。为简洁起见，我们在第 6 节中研究xfs_repair。

（a） 文件计数

敏感度：随着文件总数的增加，e2fsck 的运行时

（b） 目录计数

敏感度：e2fsck 的运行时作为总目录计数

增加

图 1：具有不同文件或目录计数的 1TB 文件系统的 C/R 运行时

e2fsck概览

E2fsck 对 C/R 使用五个顺序传递：第一个传递（称为 Pass-1）检查 inode 元数据的一致性;Pass-2 检查目录一致性;Pass-3 检查目录连接;Pass-4 检查引用计数;最后，Pass-5 检查数据和元数据位图的一致性。

设置和运行时分析

为了分析和破译 C/R 运行时的成本，我们在具有不同配置的文件系统上运行 e2fsck。我们对运行频率为 2.30GHz 的 64 核双 Intel ® Xeon Gold 5218、64GB DDR 内存、1TB NVMe 和运行 Ubuntu 18.04.1 的 2TB Micron 5200 SATA SSD 进行了分析。我们使用 fs_mark 填充文件系统，这是一个开源的文件系统基准测试工具 [47]。我们主要关注没有损坏的文件系统，但在第 6 节中研究有损坏的图像。为了更深入地了解 e2fsck 如何随文件系统配置进行扩展，我们研究了 C/R 运行时对多个文件系统变量（如文件计数和目录计数）的敏感性。

文件密集型文件系统。首先，为了了解文件计数如何影响运行时，我们生成了多个文件密集型文件系统配置，文件与目录的比例为 95：1。Pass-1 负责检查 inode 结构的一致性，它主导着 e2fsck 运行时，其次是 Pass-2，它检查目录块的一致性。图 2 显示了 Pass-1 中的功能细分，该细分检查文件 inode 的一致性，并跟踪在下一阶段中遇到的要检查的目录块。我们注意到用于错误处理的函数 dcigettext（一个看似无害的）语言翻译器（错误地）用于每个 inode 检查，导致明显的 C/R 速度变慢。其他步骤（如检查 inode 引用的块的 check_blocks、从磁盘读取下一个 inode 块的 next_inode、更新全局位图以跟踪遇到的元数据的 mark_bitmap 以及存储 inode 引用的 icount 存储在运行时也会增加。尽管目录较少，但 Pass-2（目录检查）的运行时会增加，因为目录块的数量会

我们向 e2fsck 开发人员报告了此问题，并且修复程序已上游发布。

USENIX协会

第 19 届 USENIX 文件和存储技术会议 115

图 2：e2fsck Pass-1 时间细分。随着文件总数的增加，在 inode 检查阶段 （Pass-1） 中花费的时间。

存储目录条目增加。对于所有文件计数，在 Pass-1 和 Pass-2 中花费的时间占运行时的 95% 以上。最后，对于较小的目录计数，Pass-3 从根目录检查目录的连接性和可访问性，运行时间较低。在保持文件计数不变时增加文件大小不会显著增加 C/R 运行时（为简洁起见，未显示）。

目录密集型文件系统。在图 1b 中，我们以 1：1 的文件与目录比率破译了目录密集型文件系统配置的运行时。为了确保每个目录需要相同的工作量，我们在每个目录中创建一个文件。首先，获取、识别目录块并将其添加到全局块列表 （db_list） 的成本会增加 Pass-1 的成本以及引用计数。正如预期的那样，随着目录计数的增加，由于目录块数量的增加，Pass-2 的运行时间显着增加。此外，目录块存储校验和，并根据存储在目录块中的校验和重新计算和并验证校验和，以确保一致性。与文件密集型文件系统类似，对于所有目录计数，超过 90% 的运行时都花在 Pass-1 和 Pass-2 中。

计算时间和 I/O 利用率

为了了解计算瓶颈与 I/O 瓶颈，我们分析了 e2fsck 在计算时间上花费的时间与等待 I/O 完成所花费的时间。我们的分析表明，在像 NVMe 这样的现代存储设备中，文件密集型和目录密集型配置的 I/O 等待时间仅占总执行时间的 3% 和 20%。我们还注意到存储吞吐量利用率很差，在具有 2 GB/s 和 512 MB/s 顺序和随机读取带宽的 NVMe 设备上，存储吞吐量利用率仅为 270 MB/s。这清楚地表明，（1）计算是主要的瓶颈，因为它主导了整体执行时间，以及（2）像e2fsck这样的C/R无法从现代存储设备带宽中受益。

总结。总而言之，我们对广泛使用的 C/R 工具（如 e2fsck（以及后面的第 6 节xfs_repair）的分析表明，高运行时开销主要是由于单线程或缺乏细粒度并行性。C/R 运行时的线性复杂性不适合，因为磁盘容量和文件系统大小呈上升趋势，可能需要数小时甚至数天才能检查数据中心规模的文件系统。此外，在文件系统不一致期间进行 C/R 修复可能会进一步增加 C/R 运行时间。

pFSCK目标和见解

pFSCK 旨在通过利用细粒度的多核并行性和更高的磁盘带宽来解决当前文件系统 C/R 的局限性。我们首先讨论我们的目标和见解，然后是 pFSCK 的设计和实施。

目标

主要目标是使文件系统 C/R 更快。我们希望在不影响修复能力的情况下提高扫描文件系统元数据的速度，并识别不一致之处。在此追求中，pFSCK 努力实现以下目标：（1） 适应不同的文件系统配置，无论文件系统大小、利用率或配置如何，例如文件密集型或目录密集型文件系统，（2） 支持在线和离线表单的高效 C/R，最后，（3） 适应不同的系统资源利用率，以减少对任何并发运行的应用程序的性能影响。

设计见解

见解 1：通过多核和数据并行性最大限度地提高潜在带宽。为了克服当前在磁盘、卷或逻辑组级别采用串行或粗粒度并行化技术的 C/R 工具的瓶颈，pFSCK 引入了细粒度数据并行性。如第 3.2 节所示，由于 Pass-1 和 Pass-2 占文件密集型文件系统运行时间的 90% 以上，因此 pFSCK 将工作重点放在这两个传递上。我们的方法在同时执行 C/R 的单个传递中，将更精细的文件系统结构（如 inode、目录块和 dirent）划分为工作线程池。虽然看似简单，但实现数据并行性需要跨线程的数据结构隔离，以减少同步瓶颈。

见解 2：通过减少

传递间依赖关系。尽管数据并行性加速了 C/R，但每次传递（例如，目录检查）都必须等待前一次传递（例如，inode 检查）完成。具体来说，在 C/R 中，使用多个传递间全局数据结构来构建文件系统的一致视图并识别不一致（例如位图）。因此，必须序列化对共享全局结构的更新，从而增加与共享结构的争用，增加线程数并限制 CPU 可伸缩性。为了减少序列化开销，pFSCK设计了流水线并行性，打破了跨通道的刚性壁，允许同时执行多个通道。pFSCK 管理每通道线程池，使用分割和合并方法隔离通道间共享结构，将检查与 inode 的实际认证区分开来，并减少 I/O 等待时间。

洞察 3：通过动态线程调度适应文件系统配置。数据和流水线并行性都需要在不同的传递中分配线程。由于缺少有关元数据类型（文件、目录、链接）的信息，CPU 线程的静态或相等分区是次优的

第 19 届 USENIX 文件和存储技术会议

USENIX协会

并跨通道工作。简单的检查（例如有关文件数量与目录 inode 的信息）是不够的，因为目录处理既复杂又耗时（参见第 3 节）。为了克服上述挑战，我们设计了一个 C/R 线程调度器，它可以跨传递动态分配和迁移线程，以便在发现不同的文件系统对象时对其进行处理。

见解 4：通过资源利用意识减少系统影响。文件系统 C/R 可能会与其他共享 CPU 的应用程序一起运行，同时在单独的磁盘上执行检查。鉴于 pFSCK 的目标是利用可用的 CPU，它可能会影响其他共同运行的应用程序。同样，C/R 可以在其他应用程序也积极用于存储数据的磁盘上运行。为了减少对协同运行应用程序和 pFSCK 的整体系统影响，我们为 pFSCK 的调度程序配备了资源感知功能，以动态识别在任何单个时间点使用的内核数量，以最大程度地减少对其他协同运行应用程序和 pFSCK 性能的潜在影响。

设计与实施

我们讨论了 pFSCK 的数据并行性、流水线并行性、动态线程调度器和资源感知调度的设计和实现。我们的目标是扩展广泛使用的 e2fsck，而无需更改文件系统布局和重用功能，例如基于快照的在线 C/R。

数据并行性

pFSCK 的数据并行性旨在以并行化 C/R 的 inode 粒度在每次传递中跨工作线程划分工作。但是，pFSCK 必须确保高效的并行性，而不会影响文件系统的完整性或正确性，方法是将 C/R 传递和每线程上下文进行功能分离，从而隔离全局数据结构以降低同步成本。

细粒度的 Inode 级并行性。对于细粒度的

ode 并行性，pFSCK 使用超级块信息来标识文件系统中的 inode 总数，并在 C/R 工作线程之间平均分配 inode。为了降低工人管理成本，我们使用之前工作中的线程池框架在工人之间分配任务[31]。

功能并行性可减少同步开销。仅将 C/R 的 inode 划分为工作线程是不够的。为了从细粒度并行性中受益，在不影响正确性的情况下降低每个通道中工作线程之间的同步成本至关重要。

pFSCK 将每个 C/R 传递分解为四个主要功能步骤，这些步骤占工作的 95%，并减少了这些步骤之间的同步。这些步骤包括 （1） 文件系统元数据检查，（2） 全局文件系统元数据更新，（3） 记帐，最后 （4） 中间结果共享。元数据检查验证元数据结构（例如，inode 校验和和块引用）的完整性。接下来，全局文件系统元数据更新包括对文件系统级位图的更改，这些位图维护检查器的视图

结构角色 pFSCK 的访问

dir_info_list维护目录

交往/关系

拆分为每个

线程列表

db_list

维护目录块，供 Pass-2 检查

拆分为每个

线程列表和

合并

inode_used_bitmap 使用锁跟踪有效的 inode inode_dir_bitmap 跟踪使用锁的目录 inode inode_reg_bitmap 使用锁跟踪常规文件 inode block_found_bitmap 使用锁跟踪使用的数据块 icount 跟踪 inode 引用

计数

使用锁

表 1：全局结构、其角色和访问方法。

文件系统，以便检测不一致。例如，表 1 中所示的块位图被标记以跟踪已看到哪些块引用以检测多个 inode 声明相同块的重复块引用。第三，C/R 级记帐涉及更新跟踪统计信息（如文件类型）的计数器。最后，中间结果共享涉及创建数据结构和列表，这些结构和列表包含要由下一遍处理的信息。此类结构包括目录信息列表和目录阻止列表，这些列表存储目录信息及其块的位置，以便可以在目录传递中检查。

虽然文件系统元数据检查（步骤 1）和全局元数据更新步骤（步骤 2）之间的同步是必不可少的，但通过允许线程单独维护每个线程的统计信息并生成数据结构，可以避免前两个步骤和最后两个步骤、C/R 计数器/统计信息更新（步骤 3）中间结果共享（步骤 4）之间的同步。步骤 3 和 4 的结果可以在下次传递之前进行聚合，从而显著降低同步成本。

用于隔离的线程上下文。在当前的 C/R 中，例如

e2fsck（和 xfs_repair），我们发现在通道内部和通道之间大量使用全局数据结构。为了减少共享并增加并发性，我们引入了类似于操作系统线程上下文的每线程上下文。这些上下文存储允许线程并行运行的信息。首先，文件系统对象的每线程块缓存、缓冲区（堆分配）和迭代器允许并行文件系统遍历。其次，每线程中间数据结构和计数器用于并行收集高级文件系统状态。例如，每个 inode 传递 （Pass-1） 线程都有自己的db_list（目录阻止列表）和dir_info列表（目录信息列表），用于收集有关目录的信息，并将这些信息导出到目录传递 （Pass-2） 线程进行处理。最后，每个线程计数器用于并行跟踪文件类型统计信息。但是，我们观察到，由于跨通道频繁访问全局位图（几乎每个操作），pFSCK 被迫通过锁定使用同步。虽然将这些位图分解为每线程结构是可行的，但它需要对 e2fsck 框架进行重大更改。

表 1 显示了共享结构及其在 e2fsck 中的作用。

线程托管以改善局部性。增加 lo-

cality 并更好地利用处理器缓存状态，在每次传递中，pFSCK 都会尝试在同一传递中共定位线程，以

USENIX协会

第 19 届 USENIX 文件和存储技术会议 117

阳极通道

目录通行证

线程池

延迟检查

线程池

（ a ） 数据并行性

（ b ） 流水线并行性

（ c ） 同步

依靠

检查

文件块

目录块

目录阻止延迟认证

旁路工作队列

每通道线程池

图 3：pFSCK 中的并行度。（a） 每个通道内的螺纹

允许数据并行操作（数据并行性）。（b） 多个线程池允许 pFSCK 的每个传递同时运行（流水线并行性）。（c） 任何需要同步执行的从属检查在其自身的逻辑传递内延迟。

相同的内核和内存插槽，以避免在处理器缓存之间弹跳锁定变量和共享结构。为了启用线程共置，pFSCK 会维护每个线程使用的 CPU 编号和特定传递使用的内核列表。 pFSCK 首先尝试将线程放置到以前使用的内核（如果可用），如果不可用，则使用同一传递中使用的其他可用内核。

通过每线程预取器和缓存减少 I/O 等待时间。尽管当前的 C/R （如 e2fsck 缓存和预取文件系统块），但缓存和预取机制不灵活且缺乏线程感知。首先，e2fsck 使用一个小型的、静态的、完全关联的基于 LRU 的缓存（有 8 个块）并预取 inode 块。E2fsck 不会预取目录数据块，与 inode 块不同，目录数据块可能是不连续的。其次，由于线程以不同的偏移量访问块，因此在线程之间共享缓存会导致冲突的逐出，从而增加 I/O 开销。

为了克服这些限制，我们设计并实现了一个每线程的缓存机制，以避免跨线程错误地逐出缓存条目。为了避免目录块的非连续性问题，我们实现了自适应预取机制（类似于 Linux 文件系统预取）——如果由于缺乏顺序访问而未使用先前预取的目录块，则减少预取窗口。

管道并行性

虽然数据并行性实现了在传递中处理文件系统对象的并发性，但如果不对文件系统布局或 C/R 进行实质性更改，则完全隔离每传递共享数据结构和全局数据结构是不可行的。因此，数据并行性并不能从增加 CPU 计数中完全受益。正如我们的结果所显示的那样，由于同步开销的增加，在更高的内核数下，这些好处会大大降低性能。

为了减少同步时间并提高 CPU 效率，流水线并行性打破了必须按顺序执行 C/R 传递的限制。pFSCK 的流水线并行性允许后续的 C/R 传递 （Pass） 甚至在先前的传递 （Pass） 完成之前以流水线方式（即

甚至在 inode 检查阶段之前，目录检查阶段中的目录。

每通道线程池和工作队列。

首先，为了便于并发执行传递，我们使用每通道线程池。如图 3 所示，inode 和目录检查阶段维护一个单独的线程池和一个专用的工作队列，其中充满了需要检查的文件系统对象。随着每个工次的运行，生成的任何中间工时都会被放置在下一个工次的工作队列中。例如，inode 检查通道在遇到表示目录的 inode 时，会将其块排队到目录检查通道的工作队列，以启用并发 C/R。

并发认证延迟。

允许使用流水线并行性并行运行多个传递需要对逻辑检查的正确性进行重新排序。例如，使用 pFSCK 的流水线并行性，目录数据块可以通过目录检查通道 （Pass-2） 与 inode 检查通道 （Pass-1） 并行检查目录中的所有 inode（文件和子目录）进行检查。虽然这两个传递可以并行进行，但只有在 inode 检查传递验证其子目录和文件的一致性后，才能将目录标记为一致。通过 C/R 认证目录有两个主要约束：（1） 此目录的 dirents 引用的所有 inode 都有效，以及 （2） 此目录引用的父目录有效。

提供订货保证。为了解决订购保证的挑战，pFSCK将某些检查延迟到先前的管道传递完成。例如，管道中的 inode 检查阶段负责创建目录 C/R 阶段中使用的目录结构。目录传递检查子目录，并检查子目录的父目录（由双点 ..） 表示）是否映射回目录。但是，由于 inode 和目录检查阶段并行运行，因此在检查父目录时，不会检查子目录的所有 inode。为了处理上述方案，pFSCK 通过将需要验证的关系封装到添加到单独工作队列的任务结构中来延迟认证。然后，只有在检查完所有 inode 之后（例如，在 inode 检查过程完成之后），才会处理此任务队列，如图 3 所示。延迟认证在文件密集型配置中很少见，而在目录密集型配置中很常见。pFSCK 的延迟认证增加了 Pass-1 和 Pass-2 之间的并发性，从而提高了性能。

总而言之，将流水线与数据并行性相结合可以减少 I/O 等待时间，并提高 pFSCK 在不同文件系统配置中的性能，正如我们的结果在第 6 节中所示。

动态线程调度程序

C/R 运行时可能会因文件系统的配置而有很大差异。例如，在文件系统上执行 C/R 时，具有较大文件的较小比例可能会导致

第 19 届 USENIX 文件和存储技术会议

USENIX协会

与文件数量少但较大的文件系统相比，运行时间更长，因为需要检查的元数据更多。同样，inode 类型（文件、目录、链接）的异构性也会影响运行时，并且在 inode 检查阶段（Pass-1）中迭代 inode 之前，确切的配置仍然是未知的。此外，C/R 中的每个通道对共享结构的访问程度都不同。因此，在每个传递中静态分配线程可能是无效的。因此，为了适应文件系统配置，pFSCK 实现了一个 C/R 感知调度器，pFSCK-sched，通过扩展线程池来支持，以允许在传递之间迁移线程。此外，pFSCK-sched 还维护一个空闲线程池，以保存任何未计划为任何传递运行的线程。

工作线程的线程分配和迁移。

在 pFSCK 中，我们通过实现一个调度程序来跨每个传递动态分配线程，该调度器主动监视进度并跨传递迁移线程。调度程序会定期扫描每个刀路的工作队列，以确定流水线刀路的工作分配比率，并使用此比率在它们之间分配线程。

图 4 显示了前两次传递的 pFSCK-sched 示例。最初，所有 CPU 线程都分配给第一遍（inode 检查传递），因为 pFSCK 只知道文件系统超级块的 inode 总数，而不知道 inode 的类型。当 inode C/R 线程标识一组目录 inode 时，它会将目录 inode 及其对应的目录块放置到目录 C/R 传递的工作队列中。如果用于目录传递的线程池中不存在线程，则 inode 传递中的线程将迁移到目录传递。为了计算要重新分配的线程数，专用调度程序线程使用以下模型查找所有传递中要完成的总工作。

让 Wbe 需要完成的工作量。设 q 为传递 i 的工作队列的长度。假设工作队列中每个条目需要处理的离散元素的数量。让 wbe 一些权重，使传递 i 中每个元素要完成的工作规范化。设 C 为核心预算，t 为传递 i 分配的线程数。

t= C ·QNW·

如公式 （1） 所示，要完成的总工作是每个传递中未完成工作的总和，它是工作队列长度 （q）、每个队列条目中封装的对象数 （n） 和归一化权重 （w） 的乘积。如公式 （2） 所示，对于需要完成的总工作量，调度程序可以根据总核心预算 （C） 和为每个传递计算的相对工作量来确定分配给传递 （t） 的理想线程数。请注意，规范化权重对于考虑处理不同文件类型（目录与 inode）的时间差异至关重要。我们

阳极通道

目录通行证

阳极列表

线程池

线程池

（1） 示例工作队列

（2） 重新分发线程

空闲线程

（3） 如果有更多可用内核，则从空闲线程池中获取线程

调度程序线程

旁路工作队列

图 4：动态线程调度。专用调度程序

线程定期在所有传递中对工作队列进行采样，并根据未完成工作的比例重新分配线程。

对不同文件系统配置的分析（在第 3 节中讨论）表明，在 pFSCK（和 e2fsck）中，处理一个目录所花费的平均 CPU 周期比处理一个 inode 高 1.8 倍 - 2.3 倍，这主要是由于目录校验和计算。总的来说，我们发现对目录检查队列使用更高的权重是有益的。

系统资源感知计划

文件系统 C/R 可能会与使用相同或另一个文件系统（或磁盘）的其他应用程序共存甚至共享 CPU。为了利用并行性，pFSCK必须减少对其他应用程序的影响。为了实现这一目标，我们引入了 pFSCK-rsched，这是一个系统资源感知的 pFSCK 调度器。

高效的 CPU 共享

首先，我们讨论一种情况，即 C/R 与其他应用程序一起运行，但在单独的未挂载磁盘上执行 C/R。为了减少 C/R 开销对其他应用程序的影响，pFSCK-rsched 维护了一个调度程序线程。最初，pFSCK-rsched 工作线程的优先级SCHED_IDLE主要在任何空闲的 CPU 上调度进程 [6]。当调度程序定期运行时，pFSCK-rsched 首先确定 CPU 内核预算，通过确定整个系统中活动使用的 CPU 数量、可用空闲内核的数量以及 pFSCK-rsched 使用的内核数量，确定它可以在任何时间点使用的最大线程数。根据 pFSCK-rsched 使用的有效内核数量，如果 pFSCK-rsched 使用少于可用的空闲内核，则 pFSCK-rsched 会增加 pFSCK 的核心预算，如果 pFSCK 使用的内核多于空闲内核，则会缩小 pFSCK 的核心预算，从而减少与其他应用程序的争用。确定核心预算后，调度程序使用每通道工作队列确定各个通道的工作比率，并在每个通道之间重新分配理想数量的线程。将线程添加到传递时，将从空闲线程池中获取线程并将其分配给每通道线程池。如果由于核心预算减少而需要删除线程，则会向线程发出信号并重新分配给空闲线程池。在第 6 节中，我们讨论了 pFSCK-rsched 在与另一个应用程序 （RocksDB） 共同运行和共享 CPU 时的性能优势和影响。

USENIX协会

第 19 届 USENIX 文件和存储技术会议 119

5.4.2 高效的 CPU 和文件系统共享 鉴于支持在线 C/R 的重新关注点 [32]，像 e2fsck 这样的 C/R 工具，最初是用于离线使用的，可以在 Linux 的逻辑卷管理器 （LVM） 的帮助下在线使用。LVM 的快照功能通过采用写入时复制的方法来捕获文件系统状态，以保留已修改块的原始版本。[23]. 这使得 C/R 工具能够主动使用，扫描预先存在的错误，而无需关闭系统。

对于使用 LVM 的联机 C/R，首先初始化一个空的快照卷。如果其他应用程序修改了任何块，LVM 会先将原始块复制到快照，然后再更新原始卷上的块。当 C/R 读取发现已修改的块时，读取将重定向到保存原始块的快照。未修改块的读取将重定向到原始卷。虽然快照初始化成本低廉，但应用程序会产生同步数据复制和 I/O 重定向的额外开销，从而降低 C/R 的可用存储带宽。当文件系统块频繁修改其他应用程序时，尤其如此。

在 pFSCK 的情况下，即使应用程序共享相同的文件系统（和磁盘），细粒度并行性也会加速在线 C/R。此外，pFSCK 的资源感知通过减少 CPU（和 I/O 争用）来减少对共同运行应用程序的影响，从而使应用程序运行得更快。我们在§6中进一步讨论了pFSCK对在线C/R的好处。

验证正确性和优化

正确性。为了确保 C/R 的正确性，具有细粒度并行性的 pFSCK 采用了一系列步骤。首先，尽管检查是并行完成的，但除非管道中的先前传递完成，否则 inode 不会标记为完成（例如，只有在检查了所有子 inode（目录条目）后，目录 inode 才会标记为完成。其次，C/R 线程在检测到错误时同步。检测到不一致的线程会通知其他线程停止，并尝试修复错误（例如，不正确的 inode、多个 inode 声明的块）或不使用用户输入（例如，不一致的位图），然后恢复并行执行。虽然 C/R 等工具允许部分和全部检查以及检查点中间状态，但可以添加更强大的工具来提高 C/R 崩溃一致性 [17]。

优化。作为对 e2fsck 和 pFSCK 的额外优化，我们限制了 § 3.2 中讨论的语言本地化的开销，利用英特尔的硬件加速进行校验和计算，并改进了 cachereadahead 机制。我们在§6（在图中称为e2fsck-opt）中评估了这些优化的好处。

pFSCK 支持其他文件系统和 C/R 工具。

虽然 pFSCK 目前扩展了 e2fsck（在 Ext 文件系统上），但细粒度的 inode 级数据和管道并行性以及高效调度可以应用于其他 C/R 工具，例如 xfs_repair 和 fsck.f2fs，它们实现了多个传递

描述

e2fsck 原始 FSCK for EXT 文件系统 e2fsck-opt 优化 e2fsck xfs_repair XFS 文件系统检查器 pFSCK 建议的文件系统检查器

表 2：评估的 C/R 系统。

描述

数据参数

仅启用数据并行性

datapara+pipeline-split-equal

流水线 + 数据并行性，在各个通道之间平均分配线程

datapara+pipeline-split-optimal

与上述相同，但手动选择最佳线程分配

谢德

具有动态线程分配的管道 + 数据并行性

RSCHED公司

具有系统级资源感知的 Sched 配置

表 3：pFSCK 增量系统设计

检查文件、目录、链接等。我们将在未来的工作中探索设计一个通用的 C/R。

评估

我们评估pFSCK以回答以下问题：

pFSCK 的数据并行性是否通过增加 CPU 并行性来减少 C/R 运行时间？

pFSCK 的流水线并行性在实现 C/R 传递的并发执行方面有多有效？

pFSCK 的动态线程放置对不同文件系统配置的效果如何？

pFSCK 的资源感知调度程序能否有效地将对其他应用程序的性能影响降到最低？• pFSCK 在在线 C/R 中表现如何？

pFSCK 在文件系统错误时如何执行？

实验装置

我们使用的机器配备了 64 核双 Intel ® Xeon Gold 5218，运行频率为 2.30GHz、64GB DDR 内存、1TB NVMe 和运行 Ubuntu 2200 的 18.04.1TB Micron 5200 SATA SSD。我们在具有不同线程数的各种文件系统配置上运行 pFSCK。如表 2 所示，我们比较了 vanilla e2fsck、e2fsck-opt（优化的 e2fsck，减少了语言本地化开销和 Intel 硬件加速校验和）和 xfs_repair。表 3 显示了 pFSCK 的增量设计方法。文件系统配置。文件系统中的文件和目录数量可以是可变的，并且取决于应用程序，并且没有公开可用的数据。我们对 RocksDB（键值存储）、视频服务器、Web 服务器和邮件服务器（使用 filebench）等工作负载以及我们组织中的两个共享服务器的分析表明，文件计数占主导地位（99% 的文件对 1% 的目录）。为了了解 pFSCK 的设计对文件和目录密集型配置的影响，我们使用 1TB NVMe 和 840GB 文件系统，使用 5000 万个 inode，在 SATA SSD 上使用 2TB 文件系统，使用 1 亿个 inode。我们评估了 pFSCK 对文件密集型（99% 文件）、中等目录密集型（25% 文件）的影响

第 19 届 USENIX 文件和存储技术会议

USENIX协会

目录），以及极端目录密集型（50% 目录）配置。

数据并行性

为了理解 pFSCK 的细粒度 inode 级数据并行性的性能改进和影响，即在每个传递中跨线程划分 inode，但串行运行传递，我们评估了一个文件密集型配置（在图 5a 中）、一个目录密集型配置（在图 5b 中）和一个极端目录密集型配置（在图 5c 中）。x 轴显示了四种 C/R 方法：普通的 e2fsck、我们优化的 e2fsck （e2fsck-opt）、粗粒度并行xfs_repair，最后是我们提出的具有数据并行性的 pFSCK （pFSCK[datapara]）。对于 xfs_repair 和 pFSCK[datapara]，我们还将线程数从 2 个线程更改为 16 个线程。

文件密集型配置。首先，如图 5a 所示，我们优化的 e2fsck-opt 通过优化 CRC 机制和避免语言本地化开销，性能优于原版 e2fsck。接下来，xfs_repair粗粒度分配组的粒度中并行化 C/R，这是无效的。XFS 文件系统配置有 16 个分配组（默认情况下）。虽然 xfs_repair 并行检查分配组的健全性，但不会并行检查分配组中的目录元数据。具体来说，当文件较小时，xfs_repair无法并行检查目录条目和链接计数，从而大大增加了 C/R 时间。此外，不同分配组的 inode 计数会进一步影响性能（增加分配组不会提高性能）。在所有情况下，e2fsck 和 pFSCK 的表现都优于 xfs_repair。最后，pFSCK[datapara] 具有细粒度的 inode 级并行性，将第一遍（inode 检查）的运行时间缩短了 2.1 倍，将目录检查传递（Pass-2）的运行时间缩短了 1.8 倍，从而使 vanilla e2fsck 上的四个线程的整体 C/R 加速提高了 1.9 倍，比 e2fsck-opt 提高了 1.52 倍。除了四个线程之外，pFSCK 的数据并行性扩展还受到高序列化和锁争用的阻碍，以更新共享结构，例如已使用/可用块位图。

目录密集型配置。如图 5b 和 5c 所示，目录密集型文件系统的趋势类似。即使有 50% 的目录，pFSCK 的 Pass-1 和 Pass-2 运行时也分别减少了 1.8 倍和 1.3 倍。与 e2fsck、e2fsck-opt 和不并行目录元数据检查的 xfs_repair 相比，pFSCK 实现了 1.4 倍、1.24 倍和 1.8 倍的整体 C/R 加速。对于 25% 的目录密集型配置，增益是 e2fsck 的 2 倍。然而，全局结构的同步开销阻止了 pFSCK 的数据并行性扩展到 4 个核心以上。

管道并行性和调度。

接下来，我们评估了将数据和流水线并行性相结合的好处，以及图 6a 中文件密集型配置和图 6b 和 6c 中两个目录密集型配置的动态线程放置需求。使用流水线并行性，C/R 刀路并发运行

每个传递的线程都以生产者消费者的方式为下一个传递添加工作。x 轴显示用于 C/R 的螺纹数量的增加。我们比较了四种情况：（1） pFSCK[datapara]，它一次只使用运行一个通道的数据并行性;（2） pFSCK[pipeline-split-equal]，它为每个同时执行的通道静态划分相等数量的线程（例如，在 4 线程配置中，将两个线程分配给 inode 检查通道 （Pass-1），将两个线程分配给目录检查通道 （Pass-2）;（3） pFSCK[pipeline-split-optimal]，代表手动选择的最佳线程配置;（4）pFSCK-sched，它使用pFSCK的动态线程调度器，根据每次传递中完成的未完成工作量动态分配线程。单线程 e2fsck 和 e2fsck-opt 标记为基线。由于 e2fsck 和 pFSCK 在所有情况下都优于 xfs_repair，因此我们不会显示xfs_repair。

文件密集型配置。首先，与数据不同

仅并行方法，管道并行方法可在增加线程数时提高性能。接下来，流水线拆分相等方法在各个通道之间平均拆分线程。对于低线程数（2 个和 4 个线程），与数据并行方法相比，性能提升微乎其微。这是因为，对于文件密集型配置，大多数工作都是在 inode 检查阶段 （Pass-1） 中完成的，在各个阶段之间静态和相等地划分线程，未充分利用目录检查阶段中分配的线程。增加线程数（沿 x 轴）只能通过增加 inode 检查传递中的并行度来略微提高性能。相比之下，当使用 pFSCK 的 pipeline-split-optimal 采用手动选择的线程配置并将四分之三的线程分配给 inode 检查阶段时，与仅数据并行性相比，性能提高了 1.3 倍。跨传递的并发工作还降低了数据并行扩展到四个线程以上的同步成本。最后，pFSCK 的调度程序 （pFSCK sched） 通过根据每次传递中要完成的未完成工作的相对数量自动迁移线程，避免了为不同文件系统配置优化线程放置的繁琐手动过程。事实上，与流水线拆分优化相比，动态线程放置将性能提高了 1.1 倍，与 vanilla e2fsck 相比，整体速度提高了 2.6 倍。

目录密集型配置。与文件密集型配置不同，对于极端的目录密集型配置（50% 目录），inode 和目录检查传递都需要大量工作，因此需要频繁地跨传递进行协调。我们观察到，使用 pFSCK-sched 的自动线程放置可以控制跨传递的线程数，从而减少每个传递中的争用，而线程迁移有助于加速 inode 检查（Pass-1），而不会积累大量要检查的目录 inode（在 Pass-2 中）。pFSCK 采用 5.2.2 中讨论的目录（带有子目录的目录）的延迟认证，这限制了可伸缩性。

USENIX协会

第 19 届 USENIX 文件和存储技术会议 121

线程

（a） 文件密集型金融服务。

运行时间（秒）

线程

xfs_repair

pFSCK[数据参数]

EFSCK（英语：EFSCK）

efsck -opt

（b） 目录密集型 FS，目录占 25%。

运行时间（秒）

线程

（c） 目录占 50% 的目录密集型 FS。

图 5：数据并行性影响。这些配置总共使用了 5000 万个 inode。

运行时间（秒）

线程

（a） 文件密集型金融服务。

4 8 16

线程

pFSCK[数据参数]

pFSCK[流水线拆分相等]

pFSCK[流水线拆分优化] pFSCK-sched efsck efsck -opt

（b） 目录密集型 FS，目录占 25%。

运行时间（秒）

线程

（c） 目录占 50% 的目录密集型 FS。

图 6：流水线并行度和调度程序的比较

线程

pFSCK[数据参数]

pFSCK[流水线拆分相等]

pFSCK[流水线拆分优化] efsck efsck -opt

图 7：具有文件密集型 FS 的 2TB SSD 上的 C/R。

（a） 文件密集型金融服务

（b） 目录密集型金融服务

图 8：I/O 带宽

总体而言，对于 25% 和 50% 的目录密集型配置，性能比 e2fsck 提高了 2.7 倍和 1.6 倍。

低带宽 SSD。最后，为了了解在大型 2TB 配置下，基于 SATA 的较慢 SSD（顺序带宽为 350MB/s）的增益，图 7 显示了文件密集型配置下的 pFSCK 性能。尽管与 NVMe 相比，SSD 的带宽较低，但 pFSCK 的加速速度比普通 e2fsck 和 e2fsck-opt 高出 2.1 倍和 1.73 倍。总之，pFSCK 的流水线并行性减少了数据并行性的序列化瓶颈，动态线程放置减少了工作不平衡，从而显着提高了快速 NVMe 和 SSD 设备的性能。

（a） 文件密集型金融服务

（b） 目录密集型金融服务

图 9：内存使用情况。

存储吞吐量和内存使用情况

我们分析了 pFSCK 在文件密集型和极端目录密集型（50% 目录）配置下的有效存储带宽使用和内存容量增加。为简洁起见，我们比较了单线程 e2fsck、e2fsck opt 和多线程 pFSCK-sched。

存储吞吐量

图 8a 和图 8b 显示了文件密集型和目录密集型配置的存储带宽利用率（以 MB/s） 为单位。首先，我们优化的 e2fsck （e2fsck-opt） 降低了同步读取之间的开销，将带宽利用率提高了 e2fsck 的 1.3 倍。相比之下，与 e2fsck 相比，pFSCK 将 8 个和 16 个线程的文件密集型配置的 I/O 吞吐量分别提高了 1.9 倍和 2.7 倍。目录密集型文件系统的 I/O 吞吐量利用率提高了 1.7 倍，显示了 pFSCK 在有效利用可用磁盘带宽方面的优势。

I/O 带宽利用率的提高来自于 pFSCK 的线程、预取目录块的能力、更好的缓存和调度，后者可以根据待处理的工作跨传递动态迁移线程。对于图 8a 中的文件密集型配置，调度程序允许线程读取 Pass-1 中的 inode 块，并将额外的线程迁移到 Pass-2 以读取

第 19 届 USENIX 文件和存储技术会议

USENIX协会

并行，提高带宽利用率。在图 8b 中，大多数线程在目录检查通道 （Pass-2） 中运行时，I/O 带宽利用率更高。但是，由于对表 1 中列出的全局共享结构（例如 db_list）的序列化访问，I/O 带宽的增加并不能随着线程数的增加而转化为更高的性能。

内存使用情况

在图 9 中，我们比较了内存 （DRAM） 容量使用情况。首先，对于图 9a 中的文件密集型配置，所有方法的总内存利用率都低于 1GB。e2fsck 和 e2fsck-opt 显示相同的内存使用情况。关于 e2fsck 和 e2fsck-opt 内存利用率（也适用于 pFSCK），内存使用源于用于跟踪目录信息的数据结构，例如保存所有目录数据块列表的db_list、跟踪目录之间关系的dirinfo_list、跟踪所有目录 HTREE 块dx_dirinfo列表，以及用于验证目录中各 dirent 之间的一致性的字典结构。对于 pFSCK -sched，内存使用量名义上增加了 300MB （2.1x）。pFSCK 的内存增加主要是由于维护任务队列。除了 Pass-1 的 inode 检查任务外，线程还发现目录并为 Pass-2 线程创建目录块任务以进行处理。请注意，每个任务结构（在队列条目中）都表示要处理的块的固定大小范围。队列当前是动态分配的，不受限制，但可以限制以减少内存增加。还可以增加每个任务分配的块范围，以减少生成的任务数量。因此，增加线程数不会或略微增加内存使用量。

接下来，对于图 9b 中的目录密集型配置，e2fsck 和 e2fsck-opt 使用 2.6GB 内存。与文件密集型配置类似，内存消耗的主要来源是用于跟踪目录信息的数据结构。随着目录计数的极端增加，这些数据结构的内存消耗会显著增加。pFSCK 的内存使用率相当，仅使用 3.5GB，导致 1.3 倍增加。与文件密集型配置类似，内存使用量的增加是由于任务结构的生成并添加到任务队列中。随着目录计数的急剧增加，任务结构的内存开销也会增加。

通常，内存使用率是文件系统利用率/配置的函数，而不是线程计数的函数。我们认为，pFSCK在当今系统中的性能提升超过了当今具有大内存容量的系统中标称内存的增加。此外，我们相信可以通过 pFSCK 的代码优化来减少内存使用。

系统资源感知计划程序

文件系统 C/R 可以与其他应用程序同时运行，其中 C/R 和应用程序可以在共享相同 CPU 的同时在相同或单独的文件系统上运行。要了解 pFSCK 资源的有效性——

（a） 离线 C/R。

（b） 在线C/R。

图 10：资源感知 pFSCK 对离线和在线 C/R 的影响。

感知调度器 （pFSCK -rsched） 为了减少对其他应用程序的影响，我们选择了一种流行的多线程和持久化 I/O 密集型键值存储 RocksDB [4]，它被用作几个实际应用程序的后端 [22， 43]。我们在离线设置中评估 pFSCK -rsched，其中 C/R 是在独立于 RocksDB 正在使用的文件系统的文件系统上执行的，以及在线设置，其中在线（实时）C/R 在 RocksDB 同时更新的文件系统上执行。对于离线和在线设置，我们评估了以下情况的性能：（1） e2fsckno-cpu-sharing，其中 RocksDB 和原版 e2fsck 不共享 CPU 内核;（2） e2fsck-cpu-sharing，其中 CPU 在 RocksDB 和原版 e2fsck 之间共享;（3） pFSCK rsched-no-cpu-sharing，采用 pFSCK-rsched，不与 RocksDB 共享 CPU;最后，（4） pFSCK rsched-cpu-shalish，它使用 pFSCK -rsched 与 RocksDB 共享 CPU。我们运行 12 个线程的 RocksDB，并通过运行 12 个线程的 pFSCK -rsched 来促进 CPU 共享，并将所有线程的亲和力限制为 16 个核心，导致 8 个核心重叠。同样，对于 e2fsck，我们将所有线程的亲和力限制为 12 个内核，从而导致 1 个内核的重叠。由于空间限制，我们只显示检查文件密集型文件系统配置的结果。

具有 CPU 共享的离线 C/R。

图 10a 显示了对每个 C/R 和 RocksDB 使用单独文件系统的离线方法性能。x 轴显示了没有 CPU 共享和有 CPU 共享的 e2fsck 和 pFSCK -rsched 方法。在 y 轴中，结果归一化为在不共享 CPU 的情况下使用 RocksDB 运行的 e2fsck 的性能 （e2fsck-no-cpu-sharing）。

首先，在共享 CPU 时，与 e2fsck-no-cpu-share 相比，vanilla e2fsck 和 RocksDB 的运行时受到显着影响（显示为 e2fsckcpu-share），因为频繁的上下文切换会占用 RockDB 的有效 CPU 时间;与无共享方法相比，e2fsck 的性能下降了 1.2 倍，RocksDB 的性能下降了 1.5 倍。相比之下，使用 pFSCK 的资源感知调度器，pFSCK -rsched 和 RocksDB 之间的 CPU 共享 （pFSCK -rsched-cpu-sharing） 对 pFSCK 和 RocksDB 的影响最小。资源意识

USENIX协会

第 19 届 USENIX 文件和存储技术会议 123

10000

100000

运行时间（秒）

阻止损坏

e2fsck

e2fsck-opt

pFSCK-sched

312031043109

图 11：不同损坏计数的修复运行时。

该功能自适应地缩小了用于执行 C/R 的线程数量，减少了远离 RocksDB 的 CPU 上下文切换，并最大限度地减少了相关开销。尽管 pFSCK -rsched 和 RocksDB 在 16 个内核中有 8 个内核重叠，但 pFSCK -rsched 能够将线程缩减到大约 4-6 个线程，从而使 RocksDB 能够始终如一地利用总共 16 个内核中的 12 个。因此，与无 CPU 共享情况相比，pFSCK-rsched 和 RocksDB 的性能下降分别为 1.07 倍和 1.05 倍。

具有 CPU 共享的在线 C/R。

图 10b 显示了每个 C/R 和 RocksDB 共享 CPU 和文件系统时的结果。如前所述，在前面的 5.4.2 中，pFSCK 利用基于 LVM 的快照来捕获文件系统更改，并在快照所表示的文件系统的稳定版本上执行 C/R。与离线 C/R 评估类似，我们将结果归一化为在不共享 CPU 的情况下使用 RocksDB 运行的 e2fsck 的性能。

首先，当重叠 e2fsck 和 RocksDB 时，性能分别显著下降 1.4 倍和 1.6 倍。性能下降主要是由于 e2fsck 和 RocksDB 之间的 CPU 上下文频繁切换。但是，性能下降的这一主要来源增加了快照必须保持活动状态的时间，从而导致 LVM 快照开销导致性能进一步下降。其次，使用 pFSCK -rsched，与 RocksDB 共同运行 pFSCK -rsched 时性能下降最小。这是由于 pFSCK -rsched 的资源感知线程分配（类似于脱机设置），它通过扩展 pFSCK 使用的线程数来减轻性能影响和上下文切换开销。由于上下文切换对性能的影响已降至最低，因此快照必须处于活动状态的时间量将降至最低，从而缓解了由于 LVM 快照开销而导致的任何进一步性能下降。与基准（无 CPU 或文件系统共享）相比，pFSCK -rsched 和 RocksDB 的性能下降是 1.2 倍。虽然高于脱机方法，但其中大部分是由于磁盘共享和由此产生的 LVM 快照开销。

总结。pFSCK -rsched 的资源感知有效地适应了 C/R 的可用 CPU 内核（和线程）的数量，并最大限度地提高了它们的利用率，从而在离线和在线环境中获得了更好的性能。对共同运行应用程序的性能影响也降至最低。

有错误的性能

为了评估 pFSCK 在文件系统错误方面的性能，我们使用 e2fsprogs 的模糊测试工具 e2fuzz 来引入随机

阻止文件密集型配置的损坏。在图 11 中，我们在 x 轴中引入了多达 100K 的损坏，并比较了使用 8 个线程的 e2fsck、e2fsck-opt 和 pFSCK -sched。请注意，先前对真实世界系统的研究表明，损坏的规模可能只有几位或几字节，硬件和软件损坏可能会有很大差异，从静默位损坏到FTL元数据损坏以及剪切或不完整的写入[12,18,27]。

首先，即使有 100 次损坏，pFSCK -sched 的 C/R 速度也分别比 e2fsck 和 e2fsck-opt 快 2.7 倍和 1.6 倍。但是，对于 10K 损坏，pFSCK -sched 的性能与 e2fsck-opt 类似，并且与 e2fsck 相比，C/R 速度仅提高了 1.1 倍。pFSCK 的加速随着损坏数量的增加而降低，因为长时间和连续执行的错误修复操作开始主导包括 pFSCK 在内的所有 C/R 的整体运行时。此外，对于 pFSCK -sched，我们观察到，如果损坏计数大于 10K，同步开销开始进一步降低并行性的性能提升。为了缓解线程同步带来的收益递减，pFSCK 会跟踪遇到的错误数量，并在发现 10K 错误后恢复为串行检查。这允许 pFSCK 在更高的错误计数下执行与 e2fsck-opt 类似的性能，并且由于初始线程同步而仅经历轻微的性能下降。我们未来的工作将集中在探索并行修复的方法，以加速高度损坏的文件系统的 C/R。

结论和未来工作

为了加速文件系统检查和修复工具，我们提出了 pFSCK ，这是一种并行 C/R 工具，它利用 CPU 并行性和现代存储设备的高带宽来加速 C/R 时间，而不会影响正确性。pFSCK 通过将线程分配给 inode、块或目录，并使用每个传递中的数据并行性和多个传递中的管道并行性有效地执行 C/R，从而探索细粒度并行性。此外，pFSCK 支持高效的线程管理技术，以适应不同的文件系统配置，并最大限度地减少对其他应用程序的性能影响。因此，pFSCK 的增益比 e2fsck 高出 2.6 倍以上，比 xfs_repair 高出 1.8 倍，从而提供了粗粒度的并行性。鉴于 pFSCK 的局限性，未来的工作将探索加速硬盘的 pFSCK，同时减少由于随机访问而导致的代价高昂的寻道，通过更高效的数据结构和速率限制来减少内存开销，并最终加速对具有较高损坏计数的磁盘的修复。

确认

我们感谢匿名审稿人和迪恩·希尔德布兰德（我们的牧羊人）的深刻评论和反馈。我们感谢罗格斯大学系统实验室成员的宝贵意见。该材料部分由NSF资助CNS-1910593资助。我们还要感谢 Rutgers Panic Lab 在存储基础架构方面的帮助。

第 19 届 USENIX 文件和存储技术会议

USENIX协会

引用

[1] 磁盘检查时间过长。linuxquestions.org。https：

www.linuxquestions.org/questions/linux-hardware-18/ disk-check-takes-too-long-to-check-510584/。

[2] E2FSCK：用于 ext4 的 FSCK。https://linux.die.net/man/8/e2fsck。

[3] E2Scrub：Ext4 的在线 FSCK。 https://lwn.net/Articles/ 749106/。

[4] 脸书 RocksDB.http://rocksdb.org/。

[5] 英特尔-美光内存 3D XPoint.http://intel.ly/1eICR0a。

[6] Linux sched（） 手册页。http://man7.org/linux/man-pages/ man7/sched.7.html。

[7] StackExchange - ext4 fsck 的时间非常长。

https://unix.stackexchange.com/questions/78785/ 极长时间的 an-ext4-fsck，2013 年 3 月。

[8] 文件系统检查 （fsck） 运行速度很慢，而且运行时间很长。

https://access.redhat.com/solutions/2210281,2016 年 9 月。

[9] 阿布塔利布·阿加耶夫、塞奇·威尔、迈克尔·库奇尼克、马克·纳尔逊、格雷戈里·甘格和乔治·阿姆夫罗西亚迪斯。文件系统不适合作为分布式存储后端：ceph 10 年发展的经验教训。

第 27 届 ACM 操作系统原理研讨会论文集，第 353–369 页，2019 年。

[10] 拉姆纳坦·阿拉加潘、艾西瓦娅·加内桑、尤夫拉杰·帕特尔、塔努-

马来亚人 Sankaranarayana Pillai、Andrea C. Arpaci-Dusseau 和 Remzi H. Arpaci-Dusseau。相关的崩溃漏洞。在第 12 届 USENIX 操作系统设计与实现会议论文集，OSDI'16，第 151–167 页，美国加利福尼亚州伯克利，2016 年。USENIX协会。

[11] 威廉（比尔）E.奥尔科克。HPC 中心的并行文件系统：我们

年龄、经验和建议。https://www.nersc.gov/ assets/Uploads/W01-DataIntensiveComputingPanel.pdf。

[12] 拉克希米·拜拉瓦桑达拉姆、安德里亚·阿帕奇-杜索、雷姆齐 H.

Arpaci-Dusseau、Garth R. Goodson 和 Bianca Schroeder。对存储堆栈中的数据损坏的分析。ACM Trans. Storage，4（3），2008 年 11 月。

[13] 拉克希米·拜拉瓦桑达拉姆、安德里亚·阿帕奇-杜索、雷姆齐 H

Arpaci-Dusseau、Garth R Goodson 和 Bianca Schroeder。对存储堆栈中的数据损坏的分析。ACM 存储事务 （TOS）， 4（3）：8， 2008.

[14] 拉克希米·拜拉瓦桑达拉姆（Lakshmi N. Bairavasundaram），加思·古德森（Garth R. Goodson），尚卡尔·帕苏帕西（Shankar Pasupathy），

和吉里·辛德勒。磁盘驱动器中潜在扇区错误的分析。

2007 ACM SIGMETRICS 计算机系统测量和建模国际会议论文集 - SIGMETRICS 07， 2007.

[15] 维杰·奇丹巴拉姆（Vijay Chidambaram），塔努马拉扬·桑卡拉纳拉亚纳·皮莱（Thanumalayan Sankaranarayana Pillai），安德里亚·

Arpaci-Dusseau 和 Remzi H Arpaci-Dusseau。乐观的崩溃

sistency。在第二十四届 ACM 操作系统原理研讨会论文集，第 228–243 页。ACM，2013 年。

[16] 丹尼尔·弗莱尔、孙奎、拉哈特·马哈茂德、程廷豪、肖恩·本-

jamin、Ashvin Goel 和 Angela Demke Brown。侦察：验证文件

运行时的系统一致性。ACM 存储事务 （TOS），8（4）：1–29,2012 年。

[17] 关于拉梅什瓦尔·加特拉、穆罕默德·哈米德、迈郑、维亚切斯拉夫

杜贝科、亚当·曼萨纳雷斯、菲利普·布拉戈耶维奇、西里尔·居约特和罗伯特·马特埃斯库。迈向健壮的文件系统检查器。第 16 届 USENIX 文件和存储技术会议 （FAST 18），第 105-122 页，加利福尼亚州奥克兰，2018 年 2 月。USENIX协会。

[18] 约翰·戈尔岑。 静默数据损坏是真实存在的。

https://changelog.complete.org/archives/ 9769-silent-data-corruption-is-real/。

[19] 哈里亚迪·古纳维、阿布舍克·拉吉姆瓦勒、安德里亚·阿帕奇-杜索、

和 Remzi H Arpaci-Dusseau。Sqck：声明式文件系统检查器。

[20] Haryadi S. Gunawi、Abhishek Rajimwale、Andrea C. Arpaci-Dusseau 和 Remzi H. Arpaci-Dusseau。Sqck：声明式文件系统检查器。

第八届USENIX操作系统会议论文集

设计与实现，OSDI'08，第 131-146 页，美国加利福尼亚州伯克利，2008 年。USENIX协会。

[21] 哈里亚迪·古纳维、里扎·苏明托、罗素·西尔斯、凯西·戈利赫、

斯瓦米纳坦·桑达拉拉曼、林星、蒂姆·艾玛米、盛伟光、内马图拉·比多赫蒂、凯蒂·麦卡弗里、加里·格里德、帕克斯·菲尔兹、凯文·哈姆斯、罗伯特·罗斯、安德烈·雅各布森、罗伯特·里奇、柯克·韦伯、彼得·阿尔瓦罗、H. Birali Runesha、郝明哲和李怀成。 大规模故障慢：大型硬件性能故障的证据

生产系统。在第 16 届 USENIX 文件和存储会议上

技术 （FAST 18），第 1-14 页，加利福尼亚州奥克兰，2018 年。USENIX协会。

[22] 伊桑·汉密尔顿。 Rocksdb 正在吃

数据库

世界。

https://rockset.com/blog/ rocksdb-is-eating-the-database-world/。

[23] 迈克尔·哈森斯坦。逻辑卷管理器 （lvm）。白皮书

[24] Val Henson， Zach Brown， and Arjan van de Ven. 减少 ext2 文件系统的 fsck 时间.04 2019.

[25] 瓦尔·汉森、阿米特·古德、阿尔扬·范德文和扎克·布朗。块fs：

使用分而治之来提高文件系统的可靠性和修复能力。In Proceedings of the Second Conference on Hot Topics in System Dependability， HotDep'06， pages 7–7， Berkeley， CA， USA， 2006.

USENIX协会。

[26] 瓦尔·汉森、阿尔扬·范德文、阿米特·古德和扎克·布朗。Chunkfs：使用分而治之来提高文件系统的可靠性和修复能力。

在 HotDep，2006 年。

[27] 谢赫巴兹·贾弗、斯塔西斯·马内斯、安迪·黄和比安卡·施罗德。

评估固态硬盘上的文件系统可靠性。2019年 USENIX

年度技术会议 （USENIX ATC 19），第 783–798 页，华盛顿州伦顿，2019 年 7 月。USENIX协会。

[28] Shehbaz Jaffer、Stathis Maneas、Andy Hwang 和 Bianca Schroeder。

评估固态硬盘上的文件系统可靠性。2019 年 {USENIX} 年度技术会议 （{USENIX}{ATC} 19），第 783–798 页，2019 年。

[29] 谢赫巴兹·贾弗、斯塔西斯·马内斯、安迪·黄和比安卡·施罗德。

评估固态硬盘上的文件系统可靠性。2019年 USENIX

年度技术会议 （USENIX ATC 19），第 783–798 页，华盛顿州伦顿，2019 年 7 月。USENIX协会。

[30] Rohan Kadekodi、Se Kwon Lee、Sanidhya Kashyap、Taesoo Kim、

Aasheesh Kolli 和 Vijay Chidambaram。Splitfs：减少文件系统中的软件开销，以实现持久内存。在会议记录中

第 27 届 ACM 操作系统原理研讨会，第 494–508 页，2019 年。

[31] Sudersoon Kannan、Nitish Bhat、Ada Gavrovska、Andrea C. Arpasi-

杜梭和 Remzi H. Arpaci-Dusseau。使用 novelsm 重新设计非易失性存储器的 lsms。在 Haryadi S. Gunawi 和 Ben-

jamin Reed，编辑，2018 USENIX 年度技术会议，USENIX ATC 2018，美国马萨诸塞州波士顿，2018 年 7 月 11-13 日，第 993-1005 页。USENIX 协会，2018 年。

[32] 拉姆·凯萨万、哈伦德拉·库马尔和苏什鲁特·博米克。WAFL铁：

修复实时企业文件系统。在第 16 届 USENIX 会议上

文件和存储技术 （FAST 18），第 33–48 页，加利福尼亚州奥克兰，2018 年 2 月。USENIX协会。

[33] 权英镇、恩里克·芬格勒、泰勒·亨特、西蒙·彼得、埃米特

威切尔和托马斯·安德森。Strata：跨媒体文件系统。在

第 26 届操作系统原理研讨会论文集，SOSP '17,2017 年。

[34] 李昌曼、沈东浩、黄柱英和赵相妍。

F2FS：用于闪存的新文件系统。在《公约》的议事录中

第 13 届 USENIX 文件和存储技术会议，FAST'15，加利福尼亚州圣克拉拉，2015 年。

USENIX协会

第 19 届 USENIX 文件和存储技术会议 125

[35] Daan Leijen、Wolfram Schulte 和 Sebastian Burckhardt。设计

任务并行库。OOPSLA '09，第227-242页，纽约，纽约，美国，2009年。计算机协会。

[36] W. Li， Y. Yang， J. Chen， 和 D. Yuan.一种具有成本效益的机制

基于主动副本检查的云数据可靠性管理。

2012 年第 12 届 IEEE/ACM 集群、云和网格计算国际研讨会 （ccgrid 2012），第 564–571 页，2012 年。

[37] HPC 用户邮件列表。HPC 系统中断。https：

maillists.uci.edu/pipermail/hpc-users/2019-December/ 000095.html。

[38] M. Lu， T. Chiueh， 和 S. Lin.增量文件系统一致性

块级 CDP 系统的检查器。2008 年可靠分布式系统研讨会，第 157–162 页，2008 年 10 月。

[39] Ao 马， 克里斯·德拉加， 安德里亚·C. 阿帕奇-杜索， 雷姆齐·阿帕奇-

杜梭和马歇尔·柯克·麦库西克。Ffsck：快速的文件系统检查器。存储， 10（1）：2：1–2：28， 2014年1月.

[40] 马歇尔·麦库西克。改进 fsck 在 freebsd 中的性能。

;登录：， 38（2）， 2013.

[41] 马歇尔·柯克·麦库西克、威廉·乔伊、塞缪尔·莱夫勒和罗伯特·

法布里。Fsck- unix†文件系统检查程序。Unix System Manager's Manual-4.3 BSD Virtual VAX-11 版本，1986 年。

[42] 姆坦斯基。Mtanski/XFSprogs github.com/mtanski/xfsprogs/preadv2/repair。

https://github.com/mtanski/xfsprogs/tree/preadv2/ 维修，2015 年 2 月。

[43] 阿琼·纳拉扬和彼得·马蒂斯。我们为什么要建立 cockroachdb

在 RockSDB 之上。https://www.cockroachlabs.com/blog/ cockroachdb-on-rocksd/。

[44] 欧佳欣， 舒继武， 卢悠悠.高性能文件系统

TEM 用于非易失性主存储器。第十一届欧洲计算机系统会议论文集，第 1-16 页，2016 年。

[45] 亨利·秦、李倩、杰奎琳·斯派瑟、彼得·克拉夫特和约翰·奥斯特-

呵呵。Arachne：核心感知线程管理。在《公约》的议事录中

第 12 届 USENIX 操作系统设计与实现会议

tation，OSDI'18，第 145-160 页，美国加利福尼亚州伯克利，2018 年。USENIX协会。

[46] 奥马尔·桑多瓦尔。 Btrfs filesys中的错误调查-

泰姆。https://courses.cs.washington.edu/courses/cse551/ 15sp/projects/osandov.pdf。

[47] 里克·惠勒。fs_mark。https://sourceforge.net/projects/ fsmark/.

[48] 马修·威尔科克斯和罗斯·兹维斯勒。Linux DAX。https://www。

kernel.org/doc/Documentation/filesystems/dax.txt。

[49] 徐健和史蒂文·斯旺森。Nova：一个日志结构的文件系统

混合易失性/非易失性主存储器。在14日的会议记录中

Usenix 文件和存储技术会议，FAST'16，加利福尼亚州圣克拉拉，2016 年。

[50] 徐健和史蒂文·斯旺森。NOVA：一个日志结构的文件系统

混合易失性/非易失性主存储器。在《公约》的议事录中

第 14 届 Usenix 文件和存储技术会议，FAST'16,2016 年。

[51] Mai Zheng、Joseph Tucek、Feng Qin、Mark Lillibridge、Bill W. Zhao 和 Elizabeth S. Yang。电源故障下固态硬盘的可靠性分析。

ACM Trans. Comput.系统，34（4）：10：1–10：28,2016 年 11 月。

第 19 届 USENIX 文件和存储技术会议

USENIX协会