neo4j/neo4j — pull request #3637 by chrisvest (2014-12-10 09:33:49+00:00)
Title: Reduce the probability if false dead-locks on index entries

Our locking API works on tuples of a ResourceType and an opaque resource id, represented as a 64 bit long.
This works great for node and relationships, as the resource id is just the record id.
Schema index entries, however, are actually tuples of label, property key and the indexed value.
Therefore, when we take a lock on an index entry, we produce a hash of the index entry tuple and take a lock on the hashed value.
It turns out that the hash function we previously used for these index entries, was quite prone to producing collisions.
Especially amongst values that are close to each other in an ordered sequence.
In the test I've added here, I saw a collision ratio of about 10%.
The new hash function is much more robust, and shows a 0% collision ratio, which only makes sense since we're dealing with a mere 25 million entries.
A sample set size that is practically microscopic compared to the space that is available to us in 64 bits.
If the 64 bit state space was all the sand in Sahara, our test would have looked at 2.5 million tons of sand (not as informative as I would have liked, but I had fun calculating it).