分布式环境下慎用Java的hashCode

你可能知道，哈希函数有很多不同的用途：

• 网络和存储系统使用它们（以校验和的形式）来检测数据的意外损坏。
• 密码系统使用它们来检测数据的恶意损坏并实现签名。
• 密码验证系统使用它们来增加从数据库中提取明文密码的难度。
• 编程语言将它们用于哈希映射，以确定密钥放置在哪个哈希桶中。
• 分布式系统使用它们来确定集群中的哪个worker应该处理大型作业的一部分。

所有这些目的都有不同的要求，不同的哈希函数用于各种目的。例如，CRC32可以很好地检测以太网中的比特损坏，因为它在硬件中实现起来非常快速和简单，但它对加密目的毫无用处。SHA-1可以很好地保护消息的完整性免受攻击者的攻击，因为它在加密方面是安全的，计算速度也相当快；但如果你正在存储密码，你最好使用像bcrypt这样的东西，它故意运行缓慢，以使暴力攻击更难。

不管怎样，那都是旧闻了。今天我想谈谈第4点和第5点，以及为什么它们也彼此非常不同。

哈希表的哈希值

我们一直在编程语言中使用哈希表（字典），没有三思而后行。当你在哈希表中插入一个项目时，该语言会为键计算一个哈希码（一个整数），使用该数字选择哈希表中的一个bucket（对于大小为n的表，通常为mod n），然后将键和值放入该bucket中。如果那里已经有一个值（哈希冲突），链表通常会将键和值存储在同一个哈希桶中。例如，在Ruby中：

$ ruby --version
ruby 1.8.7 (2011-06-30 patchlevel 352) [i686-darwin11.0.0]

$ pry
[1] pry(main)> hash_table = {'answer' => 42}
=> {"answer"=>42}
[2] pry(main)> 'answer'.hash
=> -1246806696
[3] pry(main)> 'answer'.hash
=> -1246806696
[4] pry(main)> ^D

$ pry
[1] pry(main)> 'answer'.hash
=> -1246806696
[2] pry(main)> "don't panic".hash
=> -464783873
[3] pry(main)> ^D

当你将键“answer”添加到哈希表中时，Ruby会在内部调用该字符串对象的#hash方法。该方法返回一个任意数字，如上所述，同一字符串的数字总是相同的。不同的字符串通常有不同的哈希码。偶尔你可能会得到两个具有相同哈希码的密钥，但在正常操作中不太可能发生大量冲突。

上面例子的问题是：当我退出Ruby（^D）并重新启动它，并计算同一字符串的哈希值时，我仍然得到相同的结果。但是为什么这是一个问题，你说，这不就是哈希函数应该做的吗好吧，问题是我现在可以戴上我的邪恶天才帽，生成一个所有字符串都有相同哈希码的列表：

$ pry
[1] pry(main)> "a".hash
=> 100
[2] pry(main)> "\0a".hash
=> 100
[3] pry(main)> "\0\0a".hash
=> 100
[4] pry(main)> "\0\0\0a".hash
=> 100
[5] pry(main)> "\0\0\0\0a".hash
=> 100
[6] pry(main)> "\0\0\0\0\0a".hash
=> 100

世界上任何运行相同版本Ruby的服务器都会得到相同的哈希值。这意味着我可以向您的服务器发送一个特制的web请求，其中请求参数包含许多具有相同哈希码的字符串。您的web框架可能会将参数解析为哈希表，无论哈希表有多大，它们最终都会出现在同一个哈希桶中。每当你想访问参数时，你现在必须迭代一长串哈希冲突，而你的快速O（1）哈希表查找突然变成了爬行缓慢的O（n）。

我只需要向你的服务器发出少量这些邪恶的请求，我就让它屈服了。这种类型的拒绝服务攻击早在2003年就有描述，但直到去年Java、Ruby、Python、PHP和Node.js突然争先恐后地解决了这个问题，它才广为人知。

解决方案是让哈希码在一个进程中保持一致，但在不同的进程中保持不同。例如，这是Ruby中的一个更新版本，其中修复了该漏洞：

$ ruby --version
ruby 1.9.3p125 (2012-02-16 revision 34643) [x86_64-darwin11.3.0]

$ pry
[1] pry(main)> 'answer'.hash
=> 968518855724416885
[2] pry(main)> 'answer'.hash
=> 968518855724416885
[3] pry(main)> ^D

$ pry
[1] pry(main)> 'answer'.hash
=> -150894376904371785
[2] pry(main)> ^D

当我退出Ruby并重新启动它，并要求提供相同字符串的哈希码时，我得到了一个完全不同的答案。这显然不是你想要的加密哈希或校验和，因为它会使它们变得无用——但对于哈希表来说，这是完全正确的。

分布式系统的哈希

现在让我们来谈谈分布式系统——在这种系统中，您有多个进程，可能在多台机器上，它们正在相互通信。如果你的东西太大，无法放在一台机器上（一台机器的磁盘上容纳的数据太多，一台机器CPU处理的请求太多，等等），你需要将其分散到多台机器上。

你怎么知道用哪台机器来处理给定的请求？除非你有一些更有意义的特定于应用程序的分区，否则哈希函数是一种简单有效的解决方案：对你请求的东西的名称、服务器的mod数进行哈希运算，这就是你的服务器号。（不过，如果你想改变机器的数量，一致性哈希可能是更好的选择。）

对于这种设置，你显然不想要一个哈希函数，在这个函数中，不同的进程可能会为同一个值计算不同的哈希码，因为你最终会将请求路由到错误的服务器。您不能使用与编程语言用于哈希表相同的哈希函数。

不幸的是，这正是Hadoop所做的。Storm，一个流处理框架，也是如此。两者都使用Java虚拟机的Object.hashCode（）方法。

我理解hashCode（）的用法——它非常诱人。对于字符串、数字和集合类，hashCode（）总是返回一致的值，显然即使在不同的JVM供应商之间也是如此。就像这样，尽管hashCode（）的文档明确地没有保证不同进程之间的一致性：

在Java应用程序的执行过程中，每当在同一个对象上多次调用hashCode方法时，只要对象上的equals比较中使用的信息没有被修改，该方法就必须始终返回相同的整数。此整数不需要在应用程序的一次执行到同一应用程序的另一次执行之间保持一致。

偶尔会出现一个大胆的库，它实际上在不同的进程中返回不同的hashCode（）值，例如Protocol Buffers，人们会感到非常困惑。

问题是，尽管文档中说hashCode（）不提供一致性保证，但Java标准库的行为就像它提供了保证一样。人们开始依赖它，由于Java社区对向后兼容性的评价很高，即使文档允许更改，它也可能永远不会更改。因此，JVM得到了两全其美的结果：一个对DoS攻击开放的哈希表实现，还有一个不能总是安全地用于进程之间通信的哈希函数(

因此…

所以我想问的是：如果你正在构建一个基于JVM的分布式框架，请不要将Java的hashCode（）用于需要跨不同进程工作的任何事情。因为当你把它和字符串和数字一起使用时，它看起来很好用，然后有一天，一个勇敢的人会使用（例如）一个protocol buffers对象，然后花几天时间用头撞墙，试图弄清楚为什么消息会被发送到错误的服务器。

你应该用什么来代替？首先，您可能需要将对象序列化为字节流（如果要通过网络发送，无论如何都需要这样做）。如果您使用的序列化总是将相同的值映射到相同的字节序列，则可以对该字节流进行哈希处理。MD5或SHA-1等加密哈希在许多情况下都是可以的，但如果你处理的是一个非常高吞吐量的服务，它可能会有点重。我听说过MurmurHash的好消息，它不是加密的，但很轻，并声称行为良好。

如果序列化并不总是为给定值生成相同的字节序列，那么您仍然可以在对象本身上定义哈希函数。请不要使用hashCode（）。进程内哈希表是可以的，但分布式系统是另一回事。

（哦，如果你想知道的话：看起来受Java hashCode冲突影响的web服务器不是通过更改为不同的哈希函数，而是通过限制参数的数量来解决这个问题：Tomcat、Jetty。）

原文地址：https://martin.kleppmann.com/2012/06/18/java-hashcode-unsafe-for-distributed-systems.html