Package hudson.util

Class ConsistentHash<T>

java.lang.Object
hudson.util.ConsistentHash<T>
public class ConsistentHash<T> extends Object
Consistent hash.

This implementation is concurrency safe; additions and removals are serialized, but look up can be performed concurrently even when modifications are in progress.

Since typical hash functions we use in Object.hashCode() isn't random enough to evenly populate the 2^32 ring space, we only ask the user to give us an injective function to a string, and then we use SHA-256 to create random enough distribution.

This consistent hash implementation is consistent both to the addition/removal of Ts, as well as increase/decrease of the replicas.

See the Wikipedia page for references, and this blog post is probably a reasonable depiction. If we trust his experiments, creating 100 replicas will reduce the stddev to 10% of the mean for 10 nodes.

Since:
1.302
Author:
Kohsuke Kawaguchi

  • Constructor Details

    • ConsistentHash

      public ConsistentHash()

    • ConsistentHash

      public ConsistentHash(int defaultReplication)

    • ConsistentHash

      public ConsistentHash(ConsistentHash.Hash<T> hash)

    • ConsistentHash

      public ConsistentHash(ConsistentHash.Hash<T> hash, int defaultReplication)

  • Method Details

    • countAllPoints

      public int countAllPoints()

    • add

      public void add(T node)
      Adds a new node with the default number of replica.

    • addAll

      public void addAll(T... nodes)
      Calls add(Object) with all the arguments.

    • addAll

      public void addAll(Collection<? extends T> nodes)
      Calls add(Object) with all the arguments.

    • addAll

      public void addAll(Map<? extends T,Integer> nodes)
      Calls add(Object,int) with all the arguments.

    • remove

      public void remove(T node)
      Removes the node entirely. This is the same as add(node,0)

    • add

      public void add(T node, int replica)
      Adds a new node with the given number of replica.

    • lookup

      public T lookup(int queryPoint)
      Looks up a consistent hash with the given data point.

      The whole point of this class is that if the same query point is given, it's likely to return the same result even when other nodes are added/removed, or the # of replicas for the given node is changed.

      Returns:
      null if the consistent hash is empty. Otherwise always non-null.

    • lookup

      public T lookup(String queryPoint)
      Takes a string, hash it with SHA-256, then calls lookup(int).

    • list

      public Iterable<T> list(int queryPoint)
      Creates a permutation of all the nodes for the given data point.

      The returned permutation is consistent, in the sense that small change to the consistent hash (like addition/removal/change of replicas) only creates a small change in the permutation.

      Nodes with more replicas are more likely to show up early in the list

    • list

      public Iterable<T> list(String queryPoint)
      Takes a string, hash it with SHA-256, then calls list(int).