[infinispan-issues] [JBoss JIRA] (ISPN-3729) Minimize the number of moved segments for SyncConsistentHashFactory

[Dan Berindei (JIRA)]

Dan Berindei created ISPN-3729:
----------------------------------

             Summary: Minimize the number of moved segments for SyncConsistentHashFactory
                 Key: ISPN-3729
                 URL: https://issues.jboss.org/browse/ISPN-3729
             Project: Infinispan
          Issue Type: Bug
          Components: Distributed Cache
    Affects Versions: 6.0.0.Final
            Reporter: Dan Berindei
            Assignee: Dan Berindei
             Fix For: 7.0.0.Final


SyncConsistentHash uses an algorithm that's similar to consistent hashing, but when there is a collision (two nodes map to the same segment), the second node is moved to the next segment. Since the nodes are ordered by their UUID, that means it's possible for a joiner to change the mapping of existing nodes.

In order to make the load distribution more even, SyncConsistentHash also uses "virtual nodes": each node actually maps to multiple segments. This makes the number of collisions much higher (and implicitly, the number of extra moved segments).

Reading the original [consistent hashing paper|http://thor.cs.ucsb.edu/~ravenben/papers/coreos/kll%2B97.pdf], it looks like the collision handling should be done differently: a joiner should replace an existing node when it's "closer" to the segment boundary, but the existing node should never "move" to another segment (the property of monotonicity mentioned in the paper). We should investigate whether changing this would allow us to achieve better load balancing by using a much higher number of "virtual nodes" (without moving extra segments). If successful, we could even use SyncConsistentHashFactory as the default hash algorithm.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira