检测重复文件的最快算法

Question

在我的 2 TB 硬盘存储图像中查找重复项的过程中，我对 fslint 和 fslint-gui 工具的长时间运行感到惊讶。
因此，我分析了核心工具findup的内部结构，该工具使用超长管道实现为编写得非常好的和文档化的 shell 脚本。本质上它基于查找和散列（md5 和 SHA1）。作者表示它比我无法相信的任何其他替代方案都快。所以我发现检测重复文件的主题很快滑向散列和比较散列，在我看来这不是最好和最快的方法。

所以通常的算法似乎是这样工作的：

• 生成所有文件的排序列表（路径、大小、ID）
• 将大小完全相同的文件分组
• 计算具有相同大小的所有文件的哈希值并比较哈希值
• 相同意味着相同的文件 - 发现重复

有时通过首先使用具有更高冲突概率的更快哈希算法（如 md5）来提高速度，然后如果哈希相同，则使用第二个更慢但更少类似碰撞的算法来证明重复项。另一个改进是首先只散列一小块以整理出完全不同的文件。

所以我认为这个方案在两个不同的方面被打破：

• 重复的候选者再次从慢速硬盘读取（第一个块）并再次（完整的 md5）和再次（sha1）
• 通过使用散列而不是逐字节比较文件，我们引入了（低）假阴性概率
• 哈希计算比逐字节比较慢很多

我发现一个（Windows）应用程序通过不使用这种常见的散列方案来说明速度很快。

我的想法和意见完全错误吗？

[更新]

似乎有人认为散列可能比比较更快。但这似乎是对“哈希表加速事物”的一般使用的误解。但是要生成文件的哈希，第一次文件需要逐字节读取。因此，一方面有逐字节比较，它只比较每个重复候选函数的这么多字节，直到第一个不同的位置。并且有一个哈希函数，它从这么多字节中生成一个 ID - 如果前 10k 是相同的，可以说是 1 TB 的前 10k 字节或完整 TB。因此，假设我通常没有准备好计算并自动更新的所有文件哈希表，我需要计算哈希并读取重复候选的每个字节。逐字节比较不'

[更新2]

我得到了第一个答案，它再次朝着这个方向发展：“哈希通常是一个好主意”，因此（不是那么错误）试图通过（恕我直言）错误的论点来合理化哈希的使用。“哈希更好或更快，因为您可以稍后重用它们”不是问题。“假设许多（比如 n 个）文件具有相同的大小，要找出哪些是重复的，您需要进行 n * (n-1) / 2 次比较以对它们进行成对测试。使用强哈希，你只需要对它们每个散列一次，总共给你 n 个散列。” 也偏向于哈希和错误（恕我直言）。为什么可以' t 我只是从每个相同大小的文件中读取一个块并在内存中进行比较？如果我必须比较 100 个文件，我会打开 100 个文件句柄并从每个文件句柄并行读取一个块，然后在内存中进行比较。这比用这 100 个文件更新一个或多个复杂的慢哈希算法要快得多。

[更新3]

鉴于对“人们应该始终使用哈希函数，因为它们非常好！”的巨大偏见！我通读了一些关于哈希质量的 SO 问题，例如： 哪种哈希算法最适合唯一性和速度？由于糟糕的设计和生日悖论，常见的哈希函数比我们认为的更经常产生冲突。测试集包含：“216,553 个英文单词的列表（小写），数字“1”到“216553”（想想邮政编码，以及一个糟糕的哈希如何摧毁 msn.com）和 216,553 个“随机”（即类型4 uuid) GUID”。这些微小的数据集产生于大约 100 到近 20k 次碰撞。因此，仅基于散列在（不）相等性上测试数百万个文件可能根本不是一个好主意。

我想我需要修改1并用“cmp”替换管道的 md5/sha1 部分，然后测量时间。我让你更新。

[更新 4] 感谢所有反馈。慢慢地，我们正在转换。背景是我在我的机器 md5 上运行 fslints findup 时观察到的，其中包含数百个图像。这花了很长时间，硬盘像地狱一样旋转。所以我想知道“这个疯狂的工具在破坏我的 HDD 并在逐字节比较时花费大量时间是什么鬼”是 1) 每字节比任何哈希或校验和算法便宜，2) 与逐字节比较我可以尽早返回第一个差异，因此我可以通过读取完整文件和计算完整文件的哈希值来节省大量时间，而不是浪费 HDD 带宽和时间。我仍然认为那是正确的 - 但是：我想我没有意识到 1:1 比较（如果 (file_a[i] != file_b[i]) 返回 1;）可能比每字节散列更便宜。但是当需要相互比较更多文件时，使用 O(n) 进行复杂性明智的散列可能会获胜。我已经在我的列表中设置了这个问题，并计划用 cmp 替换 findup 的 fslint 的 md5 部分，或者增强 pythons filecmp.py compare lib，它一次只将 2 个文件与多个文件选项进行比较，可能还有一个 md5hash 版本。所以谢谢大家。通常情况就像你们说的：最好的方法（TM）完全取决于情况：HDD vs SSD，相同长度文件的可能性，重复文件，典型文件大小，CPU性能与内存与磁盘，单个与多核等。而且我了解到我应该更频繁地考虑使用散列 - 但我是一名嵌入式开发人员，大部分时间资源非常有限;-) s fslint 与 cmp 或增强 python filecmp.py compare lib，它一次只比较 2 个文件与多个文件选项，可能还有 md5hash 版本。所以谢谢大家。通常情况就像你们说的：最好的方法（TM）完全取决于情况：HDD vs SSD，相同长度文件的可能性，重复文件，典型文件大小，CPU性能与内存与磁盘，单个与多核等。而且我了解到我应该更频繁地考虑使用散列 - 但我是一名嵌入式开发人员，大部分时间资源非常有限;-) s fslint 与 cmp 或增强 python filecmp.py compare lib，它一次只比较 2 个文件与多个文件选项，可能还有 md5hash 版本。所以谢谢大家。通常情况就像你们说的：最好的方法（TM）完全取决于情况：HDD vs SSD，相同长度文件的可能性，重复文件，典型文件大小，CPU性能与内存与磁盘，单个与多核等。而且我了解到我应该更频繁地考虑使用散列 - 但我是一名嵌入式开发人员，大部分时间资源非常有限;-) 最好的方法 (TM) 完全取决于情况：HDD 与 SSD、相同长度文件的可能性、重复文件、典型文件大小、CPU 性能与内存与磁盘、单核与多核等。而且我了解到我应该更频繁地考虑使用散列 - 但我是一名嵌入式开发人员，大部分时间资源非常有限;-) 最好的方法 (TM) 完全取决于情况：HDD 与 SSD、相同长度文件的可能性、重复文件、典型文件大小、CPU 性能与内存与磁盘、单核与多核等。而且我了解到我应该更频繁地考虑使用散列 - 但我是一名嵌入式开发人员，大部分时间资源非常有限;-)

感谢您的所有努力！马塞尔

Answer 1

最快的重复数据删除算法取决于几个因素：

1. 找到近似重复的频率有多高？如果非常频繁地找到数百个具有完全相同内容和一个字节差异的文件，这将使强散列更具吸引力。如果很难找到超过一对大小相同但内容不同的文件，则可能不需要散列。
2. 从磁盘读取的速度有多快，文件有多大？如果从磁盘读取非常慢或文件非常小，那么单遍散列，无论加密强度如何，都将比使用弱散列进行小遍传递快，然后仅当弱散列匹配时才进行更强传递。
3. 您打算运行该工具多少次？如果您要多次运行它（例如，为了持续进行重复数据删除），那么构建一个包含每个文件的路径、大小和 strong_hash 的索引可能是值得的，因为您会不需要在工具的后续运行中重建它。
4. 你想检测重复的文件夹吗？如果你想这样做，你可以构建一个Merkle 树（本质上是文件夹内容 + 元数据的递归哈希）；并将这些哈希值也添加到索引中。
5. 您如何处理文件权限、修改日期、ACL 和其他排除实际内容的文件元数据？这与算法速度没有直接关系，但在选择如何处理重复项时会增加额外的复杂性。

因此，没有单一的方法可以回答最初的问题。什么时候最快？

假设两个文件具有相同的大小，通常没有最快的方法来检测它们是否重复，而不是逐字节比较它们（即使从技术上讲，你会逐块比较它们，因为读取块时文件系统比单个字节更有效）。

假设许多（比如n）文件具有相同的大小，要找到哪些是重复的，您需要进行n * (n-1) / 2比较以对它们进行成对测试。使用强散列，您只需要对每个散列进行一次n散列，即可获得总散列。即使k散列比逐字节比较花费的时间多出许多倍，但散列在k > (n-1)/2. 哈希可能产生假阳性（虽强散列将只与天文低概率这样做），但在测试那些逐字节才会增加k至多1. k=3，你只要提前n>=7; 更保守的k=2，你达到收支平衡n=3. 在实践中，我希望 k 非常接近 1：从磁盘读取可能比散列读取的任何内容的成本更高。

多个文件具有相同大小的概率随着文件数量的平方而增加（查找生日悖论）。因此，在一般情况下，可以预期散列是一个非常好的主意。如果您再次运行该工具，这也是一个显着的加速，因为它可以重用现有索引而不是重新构建它。因此，将 1 个新文件与 1M 个现有的、不同的、相同大小的索引文件进行比较，预计在索引中进行 1 次哈希 + 1 次查找，而在无哈希、无索引的情况下进行 1M 次比较：估计为 1M 次快点！

请注意，您可以使用多级散列重复相同的参数：如果您使用非常快的散列，例如第一个、中央和最后一个 1k 字节，散列将比比较文件快得多（k < 1上面） - 但是您会期待冲突，并在找到时使用强散列和/或逐字节比较进行第二次传递。这是一个权衡：您打赌会有差异，这将节省您进行完整哈希或完整比较的时间。我认为一般来说这是值得的，但“最佳”答案取决于机器的具体情况和工作量。

[更新]

OP似乎给人的印象是

• 哈希计算很慢
• 快速散列产生冲突
• 散列的使用总是需要读取完整的文件内容，因此对于第 1 个字节不同的文件来说是多余的。

我添加了这一部分来反驳这些论点：

• 强散列 (sha1)每字节大约需要5 个周期来计算，或者在现代 CPU 上每字节大约需要 15ns。旋转硬盘或固态硬盘的磁盘延迟分别约为 75k ns 和 5M ns。您可以在开始从 SSD 读取数据的时间内散列 1k 数据。更快的非加密散列meowhash可以每个周期散列 1 个字节。主内存延迟大约为 120 ns - 完成单个访问非缓存内存请求所需的时间很容易有 400 个周期。
• 2018 年，SHA-1 中唯一已知的冲突来自于shattered项目，该项目占用了大量资源进行计算。其他强散列算法的速度并不慢，但也更强大（SHA-3）。
• 你总是可以散列文件的一部分而不是全部；并存储部分散列，直到遇到冲突，这时您将计算越来越大的散列，直到在真正重复的情况下，您将对整个事物进行散列。这为您提供了更快的索引构建。

我的观点并不是说散列是最终目的。正是对于这个应用程序，它非常有用，而不是真正的瓶颈：真正的瓶颈在于实际遍历和读取文件系统的一部分，这比任何散列或与其进行的比较要慢得多。内容。