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 is 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 MD5 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 http://en.wikipedia.org/wiki/Consistent_hashing for references, and http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	ConsistentHash.Hash<T> Hashes an object to some value.

Constructor Summary

Constructors

Constructor and Description
ConsistentHash()
ConsistentHash(ConsistentHash.Hash<T> hash)
ConsistentHash(ConsistentHash.Hash<T> hash, int defaultReplication)
ConsistentHash(int defaultReplication)

Method Summary

Modifier and Type	Method and Description
void	add(T node) Adds a new node with the default number of replica.
void	add(T node, int replica) Adds a new node with the given number of replica.
void	addAll(Collection<? extends T> nodes) Calls add(Object) with all the arguments.
void	addAll(Map<? extends T,Integer> nodes) Calls add(Object,int) with all the arguments.
void	addAll(T... nodes) Calls add(Object) with all the arguments.
int	countAllPoints()
Iterable<T>	list(int queryPoint) Creates a permutation of all the nodes for the given data point.
Iterable<T>	list(String queryPoint) Takes a string, hash it with MD5, then calls list(int).
T	lookup(int queryPoint) Looks up a consistent hash with the given data point.
T	lookup(String queryPoint) Takes a string, hash it with MD5, then calls lookup(int).
void	remove(T node) Removes the node entirely.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

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

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 MD5, 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 MD5, then calls list(int).