ariba.util.core
Class ConsistentHashRing<T>

java.lang.Object
  ariba.util.core.ConsistentHashRing<T>

Type Parameters:

T - - The type of nodes to maintain on the ring.

public class ConsistentHashRing<T>
extends java.lang.Object

The Consistent Hash Ring is a data structure that is used to load balance resources across several server nodes. This set of nodes can change over time, so by using a consistent hashing function, the resources can be balanced and as node membership changes, the location of resources does not need to be recomputed. The "ring" aspect of this structure is to divide a circle in to n arcs, one arc per node instance. Resources are then hashed into the arcs. As the number of arcs changes, the position on the ring of a resource does not change, just the node that owns the arc containing the resource.

The nodes are replicated multiple times on the ring, so that there is a more uniform distribution of resources per node, and also have a uniform distribution as nodes are removed from the ring.

The selection of the hashing function is important, and should be stable for each key (meaning re-hashing of the same key always returns the same hash value). The hash values calculated should also be uniformly distributed.

Nested Class Summary

static interface	ConsistentHashRing.HashFunction The HashFunction interface is used to implement the hashing function for the keys.
static class	ConsistentHashRing.MD5HashFunction A MD5 hash function which is a good alternative for uniform hashing.

Constructor Summary

ConsistentHashRing(ConsistentHashRing.HashFunction hashFunction, int numberOfReplicas, java.util.Collection<T> nodes)
Constructs a new hash ring.

ConsistentHashRing(int numberOfReplicas, java.util.Collection<T> nodes)
Constructs a new hash ring using MD5 hash function.

Method Summary

void	add(T node) Adds a node to the ring.
T	get(java.lang.Object key) Returns the node that is responsible for the given resource key.
void	remove(T node) Removes a node from the ring
java.util.Collection<T>	values() Returns the collection of values in the ring.

Methods inherited from class java.lang.Object

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

Constructor Detail

ConsistentHashRing

public ConsistentHashRing(int numberOfReplicas,
                          java.util.Collection<T> nodes)

Constructs a new hash ring using MD5 hash function.

Parameters:

numberOfReplicas - - the number of times each server should be hashed onto the ring.

nodes - - the initial collection of nodes to hash onto the ring.

ConsistentHashRing

public ConsistentHashRing(ConsistentHashRing.HashFunction hashFunction,
                          int numberOfReplicas,
                          java.util.Collection<T> nodes)

Constructs a new hash ring.

Parameters:

hashFunction - - the hashing function for the keys

numberOfReplicas - - the number of times each server should be hashed onto the ring.

nodes - - the initial collection of nodes to hash onto the ring.

Method Detail

add

public void add(T node)

Adds a node to the ring.

Parameters:

node -

remove

public void remove(T node)

Removes a node from the ring

Parameters:

node -

get

public T get(java.lang.Object key)

Returns the node that is responsible for the given resource key.

Parameters:

key - - the key of the resource to map onto the ring.

Returns:

the node which owns the resource, or null if the ring is empty.

values

public java.util.Collection<T> values()

Returns the collection of values in the ring.

Returns:

Collection of T