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

static interface

ConsistentHash.Hash<T> Hashes an object to some value.

Constructor Summary

ConsistentHash()

ConsistentHash(ConsistentHash.Hash<T> hash)

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

ConsistentHash(int defaultReplication)

Method Summary

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

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.

This is the only function that manipulates items.

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 pemutation is consistent, in the sense that small change to the consitent 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).