Package hudson.util

Class 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 Detail

      • ConsistentHash

        public ConsistentHash()

      • ConsistentHash

        public ConsistentHash​(int defaultReplication)

    • Method Detail

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

      • 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