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

Minimize the number of moved segments for SyncConsistentHashFactory

This issue belongs to an archived project. You can view it, but you can't modify it. Learn more

XMLWordPrintable

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

      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.

              dberinde@redhat.com Dan Berindei (Inactive)
              dberinde@redhat.com Dan Berindei (Inactive)
              Archiver:
              rhn-support-adongare Amol Dongare

                Created:
                Updated:
                Resolved:
                Archived: