代码之家 › 专栏 › 技术社区 › DanO Roman

什么哈希算法是可并行的?基于多核cpu的大文件哈希优化

checksum sha1 parallel-processing md5 hash

DanO Roman · 技术社区 · 16 年前

我对优化一些大文件的哈希(优化挂钟时间)感兴趣。I/O已经得到了充分的优化,I/O设备(本地SSD)的容量只有25%左右,而其中一个CPU内核已经完全耗尽。

我有更多的核心可用,在未来可能会有更多的核心。到目前为止,如果我碰巧需要同一个文件的多个散列,比如说一个MD5和一个SHA256,我只能访问更多的内核。我可以使用相同的I/O流来提供两个或更多的散列算法,而且我可以免费获得更快的算法(甚至可以达到挂钟时间)。据我所知,大多数散列算法,每一个新的位都会改变整个结果,而且并行处理本身就很有挑战性/不可能。

有没有主流的哈希算法可以并行化?
是否有可并行化的非主流哈希(并且至少有一个示例实现可用)?

由于未来的CPU将趋向于更多的内核和时钟速度的稳定,有没有办法提高文件哈希的性能(除了液氮冷却超频?)或它本身是不可并行的?

3 回复 | 直到 16 年前

sblom 16 年前

实际上在这方面有很多研究正在进行。美国国家标准与技术研究所(nationalstituteofstandards&Technology)目前正在举办一场设计下一代政府级哈希函数的竞赛。这方面的大多数建议都是可并行的。

举个例子: http://www.schneier.com/skein1.2.pdf

维基百科对竞赛现状的描述: http://en.wikipedia.org/wiki/SHA-3

Thomas Pornin 16 年前

不过,我对这个概念还是有点怀疑。它有点简洁,但只有在读取数据的速度比单个核处理数据的速度快的情况下,才能提供性能提升,而且,给定正确的函数和正确的实现,单个核每秒可以散列相当多的数据。分布在多个核心上的树散列需要将数据发送到适当的核心,而1.6gb/s并不是有史以来最小的带宽。

SHA-256和SHA-512速度不是很快。在SHA-3候选处理器中,假设采用64位模式的x86处理器,其中一些可以实现高速(在我的2.4 GHz Intel Core2 Q6600上超过300 MB/s,单核——这也是我可以从SHA-1获得的),例如宝马、沙巴勒或斯金。从密码学的角度来说,这些设计有点太新了,但是MD5和SHA-1在密码学上已经“坏了”(在MD5的情况下相当有效,而理论上是SHA-1),所以任何第二轮的SHA-3候选都应该是好的。

Luke404 16 年前

你没说你要做什么。如果你不想与外界交换,而只是为了内部使用,只需将每个文件分成块,计算并存储所有校验和。然后,只需向每个内核抛出一个块,就可以使用多个内核。

另一方面,如果您需要外部世界的哈希值,因为您可以从其他答复中看到,使用“标准”哈希值是不可能的(例如,如果您希望发送SHA1哈希值,以便其他人使用不同的工具进行检查),所以您必须找其他地方。比如在存储文件时计算散列值,以便以后检索,或者在后台使用“空闲”内核计算散列值,并存储起来以便以后检索。

更好的解决方案取决于您的约束条件以及您可以在哪里投入空间、时间或cpu能力。