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

Minimize the number of moved segments for SyncConsistentHashFactory

    XMLWordPrintable

Details

    • Bug
    • Resolution: Done
    • Major
    • 11.0.0.Final
    • 6.0.0.Final
    • Core
    • None

    Description

      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.

      Attachments

        Issue Links

          Activity

            People

              dberinde@redhat.com Dan Berindei (Inactive)
              dberinde@redhat.com Dan Berindei (Inactive)
              Votes:
              1 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: