linux - 磁盘 : Is it possible to process an arbitrary list of files in a seek-optimized manner? 上的 Ext4

Question

我在两级散列目录结构中对数百万个文件进行了重复数据删除存储。文件系统是磁盘上的 ext4 分区。文件的路径由其 MD5 散列值计算得出，如下所示:

e93ac67def11bbef905a7519efbe3aa7 -> e9/3a/e93ac67def11bbef905a7519efbe3aa7

当按顺序处理*文件列表(由存储在单独数据库中的元数据选择)时，我可以从字面上听到搜索产生的噪音(我假设是通过散列目录布局“随机化”)。

我的实际问题是: 如果它们存储在 ext4 分区上，是否有一种(通用的)方法以搜索优化的方式处理可能很长的潜在小文件列表在磁盘上(暗示使用 linux)？

这样的优化当然只有在小文件的份额足够大的情况下才有用。所以请不要太在意文件的大小分布。不失一般性，您实际上可以假设每个列表中只有小文件。

作为一个潜在的解决方案，我正在考虑按文件的物理磁盘位置或其他(启发式)标准对文件进行排序，这些标准可能与处理整个列表所需的查找操作的总量和长度相关。

关于文件类型和用例的说明(如果需要)

这些文件是多台台式机的去重备份。因此，您通常会在个人计算机上找到的任何文件都将包含在该分区中。然而，该处理将仅影响通过数据库选择的兴趣子集。

以下是一些用于说明的用例(列表并不详尽):

• 从媒体文件(ID3、EXIF 等)中提取元数据(文件可能很大，但只读取文件的一小部分，因此它们实际上变小了)
• 计算所有 JPEG 图像的较小版本以使用分类器处理它们
• 读取部分存储以进行压缩和/或加密(例如，将所有比 X 新且小于 Y 的文件放入 tar 存档中)
• 提取所有Word文档的标题
• 重新计算所有 MD5 哈希以验证数据完整性

---

在研究这个问题时，我了解到 FIIBMAP ioctl 命令(例如提到的 here )可能值得一试，因为文件不会四处移动，结果可能会与元数据一起存储。但我想只有当文件的 inode 的位置与内容的位置有些相关时，这才会作为排序标准。 ext4 也是这样吗？

---

*) 即打开每个文件并将文件头(任意字节数)或整个文件读入内存。

Answer 1

一个文件(尤其是当它足够大时)分散在磁盘上的几个 block 上(例如，在 ext2 维基页面的图中，它仍然与 ext4 有某种相关性，即使细节不同)。更重要的是，它可能在 page cache 中。 (因此不需要任何磁盘访问)。所以“按磁盘位置排序文件列表”通常没有任何意义。

我建议改为改进访问这些文件的代码。查看像 posix_fadvise(2) 这样的系统调用和 readahead(2) .

如果文件真的很小(每个只有数百字节)，使用其他东西(例如 sqlite 或一些真正的 RDBMS，如 PostGreSQL 或 gdbm ...)可能会更快。

顺便说一句，添加更多 RAM 可以扩大页面缓存大小，因此整体体验。用一些 SSD 替换 HDD 也会有所帮助。

(另见 linuxatemyram)

Is it possible to sort a list of files to optimize read speed / minimize seek times?

这真的不可能。文件系统碎片(实际上)对于 ext4 并不重要。当然，备份所有文件系统(例如在一些 tar 或 cpio 存档中)并按顺序恢复它(在使用 mkfs 创建新文件系统之后)可能会稍微减少碎片，但不会那么多。

您可以优化您的文件系统设置( block 大小、簇大小等...例如 mke2fs(8) 的各种参数)。另见 ext4(5) .

Is there a (generic) way to process a potentially long list of potentially small files in a seek-optimized manner.

如果列表不是太长(否则，将其分成数百个文件的 block )，您可能会 open(2)那里的每个文件并使用 readahead(2)在每个这样的文件描述符上(然后是 close(2) 它)。这会以某种方式预填充您的 page cache (并且内核可以重新排序所需的 IO 操作)。

^{(我不知道这对你的情况有多有效；你需要进行基准测试)}

我不确定您的问题是否有软件解决方案。您的问题可能与 IO 相关，因此瓶颈可能出在硬件上。

请注意，在大多数当前的硬盘上，CHS寻址(由内核使用)是由磁盘 Controller 处理的一些“逻辑”寻址，与物理几何不再有太大关系。了解 LBA , TCQ , NCQ (所以今天，内核对硬盘磁头的实际机械运动没有直接影响)。 I/O scheduling主要发生在硬盘本身(在内核中发生的不多)。