Why Java's Object.hashCode() is unsafe for use in distributed systems
martin.kleppmann.com
martin.kleppmann.com
The contract Object.hashCode() does not require a stable results between processes; it _only_ requires a stable result during a single run of an application.
So if you need a stable distributed hash, the article recommends using a different method than Object.hashCode(), for instance DistributedObject.stableHash(). Using Object.hashCode() can bite you since not all implementations will have stable over multiple runs.
Your comment qualifies as being "wrong", because of one part: "...it will work fine for Strings and HashMaps and all the standard java objects...". In fact hashCode() is stable for a very small subset of the types that ship with standard Java, and even in some of those cases there are caveats. Arrays come pretty standard with Java, but...
boolean alwaysFalse(int[] a) { return a.hashCode() == a.clone().hashCode(); }(And FWIW arrays are a weird corner of Java as far as I'm concerned; every codebase I've worked on avoids them as much as possible)
a.clone().equals(a) HAS to be false in that case. It's more than a bit of a given if a.hashCode() != a.clone().hashCode().
> you can't use Array as a thing to route on any more than you can use Object
Oh, sure you can. You just need to use java.util.Arrays's methods for "equals" and "hashCode" (or potentially deepHashCode).
Also, ArrayList does work.
Yes, that is totally F'd up.
> The point is that in standard java objects with value semantics have stable hashCode implementations, and this is not true in general
Value semantics are pretty rare in Java. I'm not even sure what you really mean there. Pass-by-value is doesn't happen with Java objects. I could see you referring to immutable types, but that doesn't include any of the collection classes. I'm guessing you mean "primitive type wrappers and collections".
It'd make more sense if you said something like, "pretty much anything that overrides Object.equals(Object)"... because that's the way it is supposed to work. They are rare in standard class library, because there is little business logic there. In practice, anything that resembles an identifier, and therefore all keys, tends to do the override though. Indeed, most of what people tend to call "business objects" tend to do the override. That's why the convention is there. Most importantly: almost all overrides do so in a fashion that is stable across processes. That's also why distributed frameworks can and should employ the convention/protocol.
That equals/hashCode methods in Object are following the Smalltalk trick of having protocol defined in Object even though you shouldn't really use it without subclassing. The Object method isn't a "reference implementation" of the protocol, but rather a placeholder (one they forgot to override in Array objects, and then tried to backdoor in with java.util.Arrays).
There is no convention that hashCode() should be stable across processes; the only thing that could reasonably define such a convention is the javadoc of Object#hashCode, which explicitly states otherwise. More pragmatically, there is an important set of objects, widely used in distributed systems, whose implementation of hashCode() is not stable across processes (namely protocol buffers objects). So distributed frameworks can't and shouldn't assume hashCode() is stable across processes.
Value semantics are a case where the identity shouldn't really exist at all, as all that matters is equivalence. There is a lot of room there in between where equivalence has meaning but identity can still play a role.
Arguably in Java only the native types (which aren't part of the Java standard library) really embody this, with their wrappers and String barely getting a nod, and Collections totally don't fit the bill. IIRC part of the language definition refers to the fact that all object have reference semantics.
Protocol Buffers are meant to be used like as a memento [http://en.wikipedia.org/wiki/Memento_pattern]. At most you should have a wrapper object providing behaviours like equivalence (in fact with Hadoop, I do this all the time with them, which is kind of a must anyway as Protocol Buffers don't implement Writable, let alone WritableComparable, etc.). Protocol Buffers very much don't have behaviour beyond serialization, which is exactly why they shouldn't have equivalence implementations. Consequently, if you are invoking equals(), hashCode(), etc. on them, "you are doing it wrong".
You're right though that there isn't a strict convention about hashCode() being stable across processes. It's more like a corollary that stems from implementing equals(Object) in terms of an object's equivalence. When you define equivalence for an object, you implement equals(Object) to represent that notion. Because of the contract that hashCode() has with equals(Object), the only cases where hashCode() shouldn't be stable across processes is where the objects actually aren't equivalent across processes.
This should fit quite well with the objectives of a distributed system. In particular, if you are defining something as a "key", it must have a very clear notion of equivalence for it, and in that context it not only should be stable across processes, it needs to be stable across the entire system. If you don't implement that logic in equals(Object), you're violating that contract. This means your hashCode() method needs to reflect that stability across processes. I can come up with some ways of screwing up hashCode() in that context while still avoiding breaking the contracts, but they're all contrived and in practice I've never seen anyone actually do that.
Seriously, if you are running in to these issues, you have bigger problems in the design.
To be clear: "embody this" meant "Value Semantics", not the in-between space.
Seriously, it's just a bad article.
int computeHash(byte[] serializedBytes) {
return serializeBytes.hashCode();
}
[Yes, it won't be screwed up if also you use your own hash.]
The problem with serialization is you lose the semantics of the object. The "same values to the same sequence of bytes" is a tighter constraint than you might think. The same "values" might have multiple representations which are logically identical but might still be relevant in any number of ways (for example, additional information that has nothing to do with identity).
It's strange that you disregard that in an aside, as it's his entire point.
Personally, I prefer to implement hashes on the values inside the object, and not its serialization. They are unrelated concepts, and it helps to keep the concepts separate in the implementation. But for the purposes of routing in a distributed system - which is what the post is about - it's an acceptable solution.
Perhaps I misunderstood as to what his point was.
If it is his entire point, I'd wish he'd not add in the bit about serialization. It just confuses the point.
To be honest, what the point of the article is strikes me as confused, because he's crossing the gamut of a variety of topics even in his summary at the end. Maybe you can help me understand my reading comprehension problem. Looking at the summary I see a variety of points that aren't really related:
1) Don't use the implementation of Object.hashCode() for your distributed hash table. Okay, this should not be news to anyone who is at all proficient with Java. It also doesn't require a long article. I'm not sure if another article needs to be written. If one must, you can just say, "Object.equals() doesn't provide magical equivalence powers; it's a place holder for when you implement equivalence. BTW, as you'd expect, the Java standard library documents its equivalence semantics whenever it overrides the method itself." You don't even have to mention hashCode().
2) Your serialization framework ought to be how you implement equivalence. Umm, no. That couples the concepts serialization with equivalence. It is essentially arguing that you ought to implement equals() by first serializing both objects and then comparing their output! I'd argue they are related in the same manner as the articles description of the relationship between Object.hashCode()'s implementation and doing good distributed partition. Serialized equivalence is correlated with logical equivalence just enough to create a huge mess. Hadoop wanders about as close to this as one should by providing hooks for doing comparisons of objects without deserializing them. One should really, really NOT go down this road.
3) Since Object.hashCode()'s implementation doesn't provide equivalence, you should not use overrides of that implementation for your partitioning. That's just stupid, even beyond the confusion of interface and implementation. You're going to need equivalence logic for your keys. Are you really going to create your own "T.equivalent(T)" method whose behaviour is distinct from "T.equals(T)"? What does it mean when those two don't have the same value? This suggests a lack of understanding as to why Object.hashCode(Object) is there in the first place.
4) Your distributed system needs its own hash function, but not necessarily a secure one. Talk about getting it backwards. Built in hash mechanisms generally work fine for short circuiting equivalence tests and already make a pretty reasonable effort to deal with poor programming. In the end, using a different hash function might only help if there is a lot of entropy in the key that is being lost by the existing one, which tends to only occur with large numbers of reasonably large keys (ironically, String.hashCode() makes some pretty good trade offs here as compared to a generic hash function). This tends to be an issue that you never encounter, and to the extent that you do, it's just an optimization issue, rather than the logical one the article described. The only major hurdle that is (wisely) left on the table by built in hash tables is the security one. For tackling that you are best off using an HMAC (designed to address that space of problem) instead of a bare hash. MD5 really isn't the right choice for any case where you have a choice about your hash function, and SHA-1 really isn't any more either, so mentioning them in the article is just silly.
5) Implementations of hashCode() generally work great for in-process hash tables, but are lousy for distributed systems. For the vast majority of hashCode() implementations, if it provides a good in-process partition input, it provides a good out-of-process partition input. Along with its corresponding equals(Object) method, the implementation of Object.hashCode() is, by design, an exceptional case and shouldn't normally get invoked.
6) Form parameters sent to Java web servers are a great example of this problem, and they wisely avoid the DoS problem by limiting the number of keys. Ummm no. First, the form parameters sent to a Java web server are no more a distributed systems problem than any other user provided data shoved in to a lookup table. It's a pure trusted systems problem. The only thing 'distributed' about it is that it tends to involve a network somewhere. In fact, a web server ought to be worried about DoS problems that have nothing to do with hash tables (like, the memory footprint of the form data). Given their solution to these DoS exposures and the context, they really ought to just shove the parameters in to some kind of efficient tree.
It's true that relying on hashCode to remain stable across arbitrary objects is brittle, but this is not the case for String.
String.hashCode explicitly guarantees consistency across processes by specifying how the hash code is computed, this is something that can be safely relied upon. (Same for Integer, Long, Float and Double)
* TreeBins use a special form of comparison for search and
* related operations (which is the main reason we cannot use
* existing collections such as TreeMaps). TreeBins contain
* Comparable elements, but may contain others, as well as
* elements that are Comparable but not necessarily Comparable<T>
* for the same T, so we cannot invoke compareTo among them. To
* handle this, the tree is ordered primarily by hash value, then
* by getClass().getName() order, and then by Comparator order
* among elements of the same class. On lookup at a node, if
* non-Comparable, both left and right children may need to be
* searched in the case of tied hash values. (This corresponds to
* the full list search that would be necessary if all elements
* were non-Comparable and had tied hashes.)Edit: actually, Java's String.hashCode() has exactly the same problem — prepending null chars doesn't change the hash code. And because the hash function is actually part of the Java standard library docs, it will probably never be changed (unlike Ruby's).
http://mail.openjdk.java.net/pipermail/core-libs-dev/2012-Ma...
[As an aside, I dislike this sort of utility base class, but it's a small price to pay for avoiding awful bugs related to hashcodes being inconsistent with equals, etc.]
I also argue that computing a hash on a serialization of an object graph is problematic as well. What are the rules for computing the hash of a serialization of a set of Strings? Must one sort the Strings before serializing them to ensure that any two Sets with the same values have the same hashcode? Sets are not required to maintain an ordering and equals() on sets ignores order (but not on SortedSet), so I would expect my "distributed" hashcode to be the same for any Set containing the same Strings. Such a scheme couples my serialization scheme tightly with my rules for equivalence. As I like to use serialization schemes written by others when possible and I don't want to eat the cost of serialization whenever I want a consistent hashcode, I'd prefer to decouple these ideas.
Recently, I've gone a step further with our domain objects and have written a generator of builders and instances using dynamic proxies (just the out-of-the-box JDK 1.3 era stuff). Developers just define interfaces, and unit tests enforce rules about what objects may be contained within the object graphs. This makes it really simple to implement things like round-trip JSON ser/deser. Because the realm of possibilities is so limited, it's easy to ensure correctness.
[As an aside, I'd love to have a DSL for such domain objects and then write a bunch of dynamic pieces parts for serialization, meta-stuff (creating a Guava function in a literate sort of way for any path through a domain object, etc.), builders, etc. I guess this is one step down the rabbit hole of model driven development, but I'm looking for something a bit lighter than, say, AndroMDA).]
Here's from Hibernate's WIKI on these two methods: https://community.jboss.org/wiki/EqualsAndHashCode
tl;dr: before writing an article advising people about writing a distributed routing framework, write a distributed routing framework. Also: if your "distributed system" is also a "trusted system", realize that fusing the two together requires some genuine expertise.
To paraphrase a comment about something I wrote the other day: "that article isn't even wrong".
The protobuf reference was just ridiculous. Protobufs are not a distributed system. They're a serialization framework that is intrinsically copying (append the same Protobuf twice to the a repeated field, and when you read it back, you get two distinct objects).
class Demo extends Object implements Cloneable {
}
boolean alwaysFalse(Demo a) {
return a.equals(a.clone());
}
From the article:
On strings, numbers and collection classes, hashCode()
always returns a consistent value, apparently even
across different JVM vendors. It’s like that despite the
documentation for hashCode() explicitly not guaranteeing
consistency across different processes...
The article then goes on:
The problem is that although the documentation says
hashCode() doesn’t provide a consistency guarantee,
the Java standard library behaves as if it did provide
the guarantee.
The only surprise in protobufs is that they don't generate their own equals()/hashCode() methods to provide more flexible equivalence relations; it becomes abundantly clear as to why once you try to answer the question "well just how would you do it without adding additional semantics (at the expense of complexity and performance) to the protocol buffer language?".
The Java spec is very clear that Object.equals(Object) provides object identity as the default implementation of equality. Java 101 covers the difference in both concept and protocol between identity and equality, with the former immutable while the latter can be user defined using by overriding Object.equals(Object). Next you learn that if you do override, you need to also override hashCode() accordingly. You learn this when you use the relevant classes for the first time.
It is outright weird for a Java developer to expect equivalence semantics (as opposed to identity) when invoking equals(Object) or hashCode() unless those semantics have been defined for an object's type.
This article is coming at it assbackwards from how anyone who has written a distributed routing framework in Java (or for that matter most other languages) ends up coming at it.
If you are writing a distributed routing framework, and long before you start thinking about hash algorithms, you need to define "equality and identity" semantics for your distributed objects. That invariably comes down for way to identify that two keys of some kind represent the same object. You might manage this entirely for the user, but typically you end up providing a user defined hooks because there are plenty of business rules for what is a unique identifier. In Java (as is the case in the afore mentioned Hadoop and Storm), that typically means your keys override Object.equals(Object), often with a framework provided type to tag tighter semantics.
When you overload Object.equals(Object), now you have to override Object.hashCode(). Sometimes this is missed during Java 101, but you tend not to get far in the Java world without having learned it. So once you have setup your equivalence relationship, how you correctly tackle Object.hashCode() becomes very, very straight forward.
In short: if you have reached the point where you are writing a distributed routing framework in Java that assumes Object.hashCode() is stable across the framework, you were almost certainly screwed long, long before you made that mistake.
Eventually, you get to the point where you realize that users might define a really bad hash, and you don't want to fail horribly when that happens. So, you might want to defend against it. Turns out, the JDK actually does defend against poor hashes. HashSet/HashMap/etc. tweak the hash when selecting buckets to avoid hashes with entropy in the wrong places (or more accurately, a lack of entropy in the right places ;-).
Then after that, you start to realize that not only are user defined hash functions likely bad in that sense, but if they have user defined data (in this case, "user" is not the developer, but the developer's "user"... so that means "incompetent" is no longer our scary adjective... it's now "untrustworthy") they are probably vulnerable to hash collision attacks. At that point, you are outside the scope of what Java's hashCode() is intended to address, so you really have to go a bit further.
There are basically four approaches, and the article appears to miss all of them (or at least glosses over them like the author doesn't see how it all fits together).
1) Don't use a hash lookup for user provided keys. Use a tree. Consider a critbit tree. Most assume this sucks until they have either reflected on the matter a fair bit, or have been schooled painfully by experience.
2) Don't let the end user define the keys.
3) Don't let the end user control/have full insight in to the hashCode() calculation. Typically this involves using an HMAC as your underlying hash function rather than a straight hash. For real security, you use an HMAC with a random "password" (kept from the user) for each hash table.
4) Letting the hash go unmodified, but randomizing bucket assignment somehow (a shared secret or a secret per hash) and blocking a user who generates more than N distinct keys (key1.equals(keys2) is false) whose hashCode()'s are equivalent, where N is a fixed number or ideally, a ratio based on their total # of keys.
What generally doesn't work is simply using a "better" hash. In some cases a simple secure (and by that I definitely don't mean MD5, and really also not SHA-1 ;-) hash can work. It works only if the user never, ever has a way to determine what the hash of a given key is (that means they can never see it or side effects of it... even in the network stack). It also means your hash function is so computationally expensive that the tree approach is likely far more efficient.
What also doesn't work is using a serialization framework to serialize the bytes in a deterministic way (it isn't clear, but it reads like the author might think protobufs are guaranteed to be deterministic, which they aren't). Serialization frameworks are, by their very nature, a horrid way to add unpredictable entropy to your data (and determinism just makes it worse). That is tantamount to padding your data with a secret in a very non-cryptographically sound way. It depends not only on keeping said secret, but also keeping the use of the serialization framework secret (effectively the "cryptographic protocol"). If you think you can keep a secret from an attacker, then save yourself the trouble and just XOR your keys with it before you hash. ;-)
In short: at no point along the way in the process should you be encountering problems where you get the wrong idea about how hashCode() works and how to use it properly in your distributed routing framework.