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

[Tristan Tarrant (JIRA)]

     [ https://issues.jboss.org/browse/ISPN-3729?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Tristan Tarrant updated ISPN-3729:
----------------------------------
    Fix Version/s:     (was: 9.0.0.Alpha2)


> 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: Core
>    Affects Versions: 6.0.0.Final
>            Reporter: Dan Berindei
>            Assignee: Dan Berindei
>
> 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 "lose" segments to another existing node (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 was sent by Atlassian JIRA
(v6.4.11#64026)