public class ConsistentHash<T> extends Object
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 http://en.wikipedia.org/wiki/Consistent_hashing for references, and http://tom-e-white.com/2007/11/consistent-hashing.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.
Modifier and Type | Class and Description |
---|---|
static interface |
ConsistentHash.Hash<T>
Hashes an object to some value.
|
Constructor and Description |
---|
ConsistentHash() |
ConsistentHash(ConsistentHash.Hash<T> hash) |
ConsistentHash(ConsistentHash.Hash<T> hash,
int defaultReplication) |
ConsistentHash(int defaultReplication) |
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 SHA-256, 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 SHA-256, then calls
lookup(int) . |
void |
remove(T node)
Removes the node entirely.
|
public ConsistentHash()
public ConsistentHash(int defaultReplication)
public ConsistentHash(ConsistentHash.Hash<T> hash)
public ConsistentHash(ConsistentHash.Hash<T> hash, int defaultReplication)
public int countAllPoints()
public void add(T node)
public void addAll(T... nodes)
add(Object)
with all the arguments.public void addAll(Collection<? extends T> nodes)
add(Object)
with all the arguments.public void addAll(Map<? extends T,Integer> nodes)
add(Object,int)
with all the arguments.public void remove(T node)
add(node,0)
public void add(T node, int replica)
public T lookup(int queryPoint)
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.
public T lookup(String queryPoint)
lookup(int)
.public Iterable<T> list(int queryPoint)
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
Copyright © 2004–2021. All rights reserved.