poige Asked: 2016-06-27 02:59:43 +0800 CST2016-06-27 02:59:43 +0800 CST 2016-06-27 02:59:43 +0800 CST 如果散列受 CPU 限制，如何检查大文件的身份？ 772 对于小文件，散列是可以的，但是对于大文件，你可以很容易地发现md5sum它是 CPU 限制的。是否有任何散列算法能够在多核上横向扩展？任何解决方法？想法？任何事物？:) hash multi-core big-data 7 个回答 Voted Best Answer poige 2016-06-27T06:49:52+08:002016-06-27T06:49:52+08:00 我自己目前最好的解决方案是： parallel --block=512M --pipepart -a …HUGEFILE… --progress --recend '' \ -k -j …NUMofProcessesSay4… md5sum | md5sum - 应当指出的是： 生成的 md5 哈希不是文件的，而是其部分的 md5，但它仍然允许您比较副本是否与原点相同 它的性能也不是很好，特别是当您使用pipe而不是文件作为输入时 parallel我--pipepart发现不支持磁盘分区 所以我也很想听听其他方式。 shodanshok 2016-06-30T04:02:27+08:002016-06-30T04:02:27+08:00 不幸的是，MD5 是一个线性过程，其状态取决于所有先前的输入。换句话说，你不能真正并行化它。此外，我不知道任何不以这种方式运行的真正哈希算法。 您可以做的（并且，根据您的回答，您正在做的）是拆分源文件并同时计算每个块的 md5sum。 如果你不能/不想这样做，你必须使用更快的哈希函数，如xxHash、CityHash或SpookyHash 其他想法（也许它适用于您的预期用途）：如果您需要比 MD5 更快的东西（尽管是单线程），您可以使用 CRC32（由最近的 CPU 硬件加速）进行第一次快速通过，诉诸 MD5 /SHA1 对看似相同的文件进行第二次传递。 Gary 2016-06-27T05:22:20+08:002016-06-27T05:22:20+08:00 几乎没有办法处理整个文件。对于广泛部署的快速算法，MD4 或 CRC32 可能是您最好的选择（尽管 CRC32 的效率将远低于 MD4）。 测试您选择的算法的各种实现将有所帮助。如果您能找到一个经过良好测试的 asm 实现，它可能会提高其 C/C++ 表亲的性能。 如果您并不真正关心互操作性，则可以通过将文件分成块（不需要在磁盘上完成，您只需从特定偏移量开始读取）并分别处理每个块来轻松实现跨多个内核的散列（这会导致严重的磁盘抖动，降低性能，尤其是机械磁盘）。您最终会为每个块使用单独的哈希（尽管这有其他优点，例如将您指向损坏的块），但您始终可以将它们哈希在一起以获得一个最终值。 这个Gist 可能是 Python 的一个好的开始。 tfrederick74656 2016-07-04T11:22:34+08:002016-07-04T11:22:34+08:00 这里的大多数答案都解决了大多数散列算法的线性性质。虽然我确信存在一些真正的可扩展散列算法，但更简单的解决方案是将数据简单地分成更小的部分，并单独散列。 考虑一下 BitTorrent 方法：创建 Torrent 时，所有文件都被分割成“块”，每个块单独散列，并且每个散列记录在 .torrent 文件中。这就是允许对等方增量验证传入数据的原因，而无需先等待整个文件完成下载。也可以在每个块的基础上纠正错误，而不需要重新传输整个文件。除了逻辑上的好处之外，这种方法还允许散列跨多个核心扩展——如果有 8 个核心可用，则可以同时散列 8 个块。 如果你设计你的验证过程来处理数据的一些子集，例如一些固定大小的块，你可以在一个单独的核心上散列每个块，从而消除管道中的大量延迟。显然，这种方法有一个小的时间/内存权衡：每个额外的散列实例都有一些与之相关的开销，主要是内存的形式，尽管除非您运行数百个实例，否则这是最小的。 Jack O'Connor 2018-10-02T09:14:04+08:002018-10-02T09:14:04+08:00 我正在研究一个树散列项目，该项目专为这个问题而设计：大文件的现成并行散列。它现在可以工作了，尽管它还没有经过审查，而且审查的变化很可能会导致最终摘要的变化。也就是说，它非常快：https ://github.com/oconnor663/bao Jason 2016-07-04T10:47:18+08:002016-07-04T10:47:18+08:00 您可以为此使用 md5deep 并为其他哈希使用 hashdeep。-j它支持带有标志的多线程。默认情况下，它将为每个核心创建一个哈希线程。它还有一个标志，可以在散列之前将文件分成几部分，但不会在单个文件上使用多个线程。我已经用它来获取半百万个文件的 sha256 并且效果很好。它还具有递归闪存，可以更轻松地处理大型目录树。 这是它的手册页http://md5deep.sourceforge.net/md5deep.html和 git repo https://github.com/jessek/hashdeep ubuntu 和 debian 中的包名是 md5deep，包含 hashdeep。 mc0e 2016-07-04T23:01:55+08:002016-07-04T23:01:55+08:00 设计一种可在多核上扩展的散列算法很容易，只是最知名的散列算法往往是专门为防止这种情况而设计的，以便使查找散列冲突等任务尽可能慢。 不强制串行处理的散列函数可能适合您，但这取决于您对散列函数的期望属性。因此，我认为您没有提供足够的信息来做出好的建议。 正如其他人所建议的那样，您可以构造一个散列函数作为原始中某个给定大小的每个块的连接散列的散列。只要块大小足够大，难以反转单个块的哈希值，这对于大多数用途来说可能足够好。这应该有多大取决于这些块的内容的可预测性。如果您能够估计熵，并选择一个块大小，以便每个块获得 128 位以上的熵，那么对于大多数目的来说这应该足够了（对于许多安全性不是主要问题的情况来说，这应该是多余的）。 从安全的角度来看，您关心块级别的熵程度，因为否则发现单个块的冲突足以使恶意行为者替换部分内容并获得相同的最终哈希。 可能值得注意的是，具有固定块大小意味着 MD5 的主要弱点是无关紧要的——黑客无法将额外的数据附加到块中。 如果您的需求是防止自然发生的哈希冲突而不是恶意冲突，那么您无疑可以负担得起使用更快的校验和函数。加密安全的哈希通常被设计为计算缓慢。 使用可选哈希树模式的 skein 函数组中的函数可能适合您。再说一遍，CRC32 可能就是您所需要的。
我自己目前最好的解决方案是：
parallel --block=512M --pipepart -a …HUGEFILE… --progress --recend '' \ -k -j …NUMofProcessesSay4… md5sum | md5sum- 应当指出的是：
pipe而不是文件作为输入时parallel我--pipepart发现不支持磁盘分区所以我也很想听听其他方式。
不幸的是，MD5 是一个线性过程，其状态取决于所有先前的输入。换句话说，你不能真正并行化它。此外，我不知道任何不以这种方式运行的真正哈希算法。
您可以做的（并且，根据您的回答，您正在做的）是拆分源文件并同时计算每个块的 md5sum。
如果你不能/不想这样做，你必须使用更快的哈希函数，如xxHash、CityHash或SpookyHash
其他想法（也许它适用于您的预期用途）：如果您需要比 MD5 更快的东西（尽管是单线程），您可以使用 CRC32（由最近的 CPU 硬件加速）进行第一次快速通过，诉诸 MD5 /SHA1 对看似相同的文件进行第二次传递。
几乎没有办法处理整个文件。对于广泛部署的快速算法，MD4 或 CRC32 可能是您最好的选择（尽管 CRC32 的效率将远低于 MD4）。
测试您选择的算法的各种实现将有所帮助。如果您能找到一个经过良好测试的 asm 实现，它可能会提高其 C/C++ 表亲的性能。
如果您并不真正关心互操作性，则可以通过将文件分成块（不需要在磁盘上完成，您只需从特定偏移量开始读取）并分别处理每个块来轻松实现跨多个内核的散列（这会导致严重的磁盘抖动，降低性能，尤其是机械磁盘）。您最终会为每个块使用单独的哈希（尽管这有其他优点，例如将您指向损坏的块），但您始终可以将它们哈希在一起以获得一个最终值。
这个Gist 可能是 Python 的一个好的开始。
这里的大多数答案都解决了大多数散列算法的线性性质。虽然我确信存在一些真正的可扩展散列算法，但更简单的解决方案是将数据简单地分成更小的部分，并单独散列。
考虑一下 BitTorrent 方法：创建 Torrent 时，所有文件都被分割成“块”，每个块单独散列，并且每个散列记录在 .torrent 文件中。这就是允许对等方增量验证传入数据的原因，而无需先等待整个文件完成下载。也可以在每个块的基础上纠正错误，而不需要重新传输整个文件。除了逻辑上的好处之外，这种方法还允许散列跨多个核心扩展——如果有 8 个核心可用，则可以同时散列 8 个块。
如果你设计你的验证过程来处理数据的一些子集，例如一些固定大小的块，你可以在一个单独的核心上散列每个块，从而消除管道中的大量延迟。显然，这种方法有一个小的时间/内存权衡：每个额外的散列实例都有一些与之相关的开销，主要是内存的形式，尽管除非您运行数百个实例，否则这是最小的。
我正在研究一个树散列项目，该项目专为这个问题而设计：大文件的现成并行散列。它现在可以工作了，尽管它还没有经过审查，而且审查的变化很可能会导致最终摘要的变化。也就是说，它非常快：https ://github.com/oconnor663/bao
您可以为此使用 md5deep 并为其他哈希使用 hashdeep。
-j它支持带有标志的多线程。默认情况下，它将为每个核心创建一个哈希线程。它还有一个标志，可以在散列之前将文件分成几部分，但不会在单个文件上使用多个线程。我已经用它来获取半百万个文件的 sha256 并且效果很好。它还具有递归闪存，可以更轻松地处理大型目录树。这是它的手册页http://md5deep.sourceforge.net/md5deep.html和 git repo https://github.com/jessek/hashdeep
ubuntu 和 debian 中的包名是 md5deep，包含 hashdeep。
设计一种可在多核上扩展的散列算法很容易，只是最知名的散列算法往往是专门为防止这种情况而设计的，以便使查找散列冲突等任务尽可能慢。
不强制串行处理的散列函数可能适合您，但这取决于您对散列函数的期望属性。因此，我认为您没有提供足够的信息来做出好的建议。
正如其他人所建议的那样，您可以构造一个散列函数作为原始中某个给定大小的每个块的连接散列的散列。只要块大小足够大，难以反转单个块的哈希值，这对于大多数用途来说可能足够好。这应该有多大取决于这些块的内容的可预测性。如果您能够估计熵，并选择一个块大小，以便每个块获得 128 位以上的熵，那么对于大多数目的来说这应该足够了（对于许多安全性不是主要问题的情况来说，这应该是多余的）。
从安全的角度来看，您关心块级别的熵程度，因为否则发现单个块的冲突足以使恶意行为者替换部分内容并获得相同的最终哈希。
可能值得注意的是，具有固定块大小意味着 MD5 的主要弱点是无关紧要的——黑客无法将额外的数据附加到块中。
如果您的需求是防止自然发生的哈希冲突而不是恶意冲突，那么您无疑可以负担得起使用更快的校验和函数。加密安全的哈希通常被设计为计算缓慢。
使用可选哈希树模式的 skein 函数组中的函数可能适合您。再说一遍，CRC32 可能就是您所需要的。