如果哈希是CPU绑定,如何检查大文件的身份?

对于小文件哈希是好的,但与巨大的,你可以很容易地发现md5sum是CPU绑定。 有没有哈希algorithm可以在多个核心上扩展? 任何解决方法? 想法? 什么? 🙂

  • 可以“增量”备份吗?
  • 为什么有些网站只有一个base64哈希码的TXTlogging?
  • 6 Solutions collect form web for “如果哈希是CPU绑定,如何检查大文件的身份?”

    我自己现在最好的解决scheme是:

    parallel --block=512M --pipepart -a …HUGEFILE… --progress --recend '' \ -k -j …NUMofProcessesSay4… md5sum | md5sum

    – 应当指出的是:

    1. 产生的md5哈希不是文件,而是md5的部分,但它仍然可以让你比较复制品是否与原点相同
    2. 它也不是很好,特别是当你使用pipe而不是文件作为input时
    3. parallel--pipepart我发现不支持磁盘分区

    所以我很想听听别的方法。

    不幸的是,MD5是一个线性过程,其状态取决于之前的所有input。 换句话说,你不能真正的并行化它。 此外,我不知道有任何真正的哈希alg不以这种方式运作。

    你可以做什么(根据你的回答,你正在做的)是分割源文件,并同时计算每个块的md5sum。

    如果你不能/不这样做,你必须使用更快的散列函数,如xxHash , CityHash或SpookyHash

    其他想法(也许适用于你的意图用法):如果你需要比MD5快的东西(尽pipe是单线程的),你可以使用CRC32(由最近的CPU硬件加速)进行第一次快速传递,采用MD5 / SHA1第二次通过似乎相同的文件。

    几乎没有四处处理整个文件。 对于广泛部署和快速的algorithm,MD4或CRC32可能是您最好的select(虽然CRC32将远没有MD4那么有效)。

    testingselectalgorithm的各种实现将有所帮助。 如果你能find一个经过很好testing的asm实现,它可能会改善其C / C ++表亲的性能。

    如果你真的不关心互操作性,通过将文件拆分为块(不需要在磁盘上完成,你只需从特定的偏移量开始读取)并分别处理每个块,就可以很容易地在多个内核之间进行散列(这将导致严重的磁盘抖动,但会降低性能,特别是对于机械磁盘)。 每个块都会有不同的散列值(尽pipe这样做有其他的好处,比如指向破碎的块),但是总是可以将它们散列在一起以获取最终值。

    这个 Gist可能是Python中的一个好东西。

    这里的大部分答案已经解决了大多数哈希algorithm的线性特性。 虽然我确定存在一些真正的可扩展哈希algorithm,但是更简单的解决scheme是简单地将数据拆分成更小的部分,并分别对每个哈希进行散列。

    考虑一下BitTorrent的方法:当一个Torrent被创build时,所有的文件被分割成“块”,每个块单独散列,每个散列logging在.torrent文件中。 这是允许对等体逐步validation传入的数据,而不必等待整个文件先完成下载。 错误也可以基于每个块来校正,而不是要求重新传输整个文件。 除了物stream优势之外,这种方法还允许散列跨多个核心扩展 – 如果8个核心可用,则可以同时散列8个块。

    如果你devise你的validation过程来处理一些数据子集,例如某些固定大小的块,你可以把每个块散列在一个单独的核上,从而消除了大量的stream水线延迟。 显然,这种方法有一个很小的时间/内存权衡:散列的每个额外的实例有一些相关的开销,主要是内存的forms,尽pipe这是最小的,除非你运行数百个实例。

    你可以使用md5deep来进行散列和散列深度。 它使用-j标志支持multithreading。 默认情况下,它会为每个核心创build一个哈希线程。 它还有一个标志,可以在散列之前将文件分割成几部分,但不会在单个文件上使用多个线程。 我已经使用这个获得了50万个文件的sha256,它工作得很好。 它也有一个recursion的闪光,使处理大型目录树更容易。

    这是它的手册页http://md5deep.sourceforge.net/md5deep.html和git回购https://github.com/jessek/hashdeep

    Ubuntu和Debian的软件包名称是md5deep,并包含hashdeep。

    devise一个可以在多个内核上扩展的散列algorithm是很容易的,只是最有名的散列algorithm倾向于专门devise来防止这种散列algorithm,以便像查找散列冲突这样的任务尽可能慢。

    不强制串行处理的哈希函数可能适合您,但这取决于您对哈希函数的期望属性。 因此,我不认为你提供了足够的信息来提出一个好的build议。

    正如其他人所build议的那样,你可以构造一个散列函数作为原始文件中某个给定大小的每个块的连接散列的哈希。 只要块大小足以使个别块的散列难以逆转,对于大多数目的而言,这可能足够好。 这应该有多大取决于这些块的内容是如何可预测的。 如果你能够估计熵,并select一个块大小,使得你得到128块比特的熵每块,这应该是足够的大多数的目的(和过度的安全不是主要关注的问题)。

    从安全的angular度来看,你关心的是块级别的熵度,因为否则find一个块的冲突就足以使恶意的actor能够replace部分内容并得到相同的最终hash。

    或许值得注意的是,拥有固定的块大小意味着MD5的主要弱点是无关紧要的 – 黑客无法为块添加额外的数据。

    如果您的需要是防止自然发生的散列冲突而不是恶意散列冲突,那么您无疑可以使用更快的校验和function。 密码安全散列通常被devise为计算速度慢。

    使用可选散列树模式的绞线function组中的函数可能适合您。 然后再一次,CRC32可能是你所需要的。

    服务器问题集锦,包括 Linux(Ubuntu, Centos,Debian等)和Windows Server服务器.