Uploaded image for project: 'Infinispan'
  1. Infinispan
  2. ISPN-3729

Minimize the number of moved segments for SyncConsistentHashFactory


    • Type: Bug
    • Status: Closed (View Workflow)
    • Priority: Major
    • Resolution: Done
    • Affects Version/s: 6.0.0.Final
    • Fix Version/s: 11.0.0.Final
    • Component/s: Core
    • Labels:


      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, 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.

        Gliffy Diagrams


            Issue Links



                • Assignee:
                  dan.berindei Dan Berindei
                  dan.berindei Dan Berindei
                • Votes:
                  1 Vote for this issue
                  3 Start watching this issue


                  • Created: