What is a consistent hash function?
A consistent hash function is one which changes minimally as the
range of function changes.
What's the advantage of such functions?
This is ideal when set of buckets change over time. Two users with
inconsistent but overlapping sets of buckets will map items to the
same bucket with high probability. So this eliminates the need of
"maintaining" a consistent "state" among all
nodes in a network. The algorithm can be used for making consistent
assignments or relationships between different sets of data in such a
way that if we add or remove items, the algorithm can be recalculated
on any machine and produce the same results.
Theory
A view V is a set of buckets where user is aware. A client uses a
consistent hash function,
f(V,i), maps an object to one of the
buckets in the view. Say, assign each of hash buckets to random
points on mod
2^n circle (virtually!) where hash
key
size = n. The hash of object= closest clockwise bucket. These
small sets of buckets lie near the object. In this case, all the
buckets get roughly same number of items. When
kth bucket is added
only a
1/k fraction of items move. This means when new node is added
only minimum reshuffle is needed, which is the advantage of having a
view. There can be a hash structure for the key lookup (a balanced
tree) which stores the hash of all nodes (in the view). When a
new node is added its hash value is added to the table.
Suppose there are two nodes A and B three objects 1–3 (mapped to
a hash-function’s result range). The objects 3 and 1 are mapped to
node A, object 2 to node B. When a node leaves the system, data will
get mapped to their adjacent node (in clockwise direction) and when a
node enters the system it will get hashed onto the ring and will
overtake objects.
As an example, (refer
link1,
link2), the circle denotes a range of key values. Say, the points in circle represents 64 bit numbers. Hash the data to get the 64 bit number, which is a point in the circle. Take the IPs of nodes and hash them into 64 bit number and point in the circle. Associate the data to the nodes in the clockwise direction (ie. closest, which can be retrieved from the node in the hash structure). When a new node is inserted into the hash tree, the data will always be assigned to the closest one only. Everything between this number and one that's next in the ring and that has
been picked by a different node previously, is now belong to this node.
The basic idea of consistent hash function is to hash both objects
and buckets using the same function. It's one of the best ways to
implement APIs that can dynamically scale out and rebalanced. The
client applications can calculate which node to contact in order to
request or write the data with no metadata server required.
Used by
memcached cluster.
Typically, multiple memcached daemons are started, on different hosts. The clients are passed a list of memcached addresses (IP address and port) and pick one daemon for a given key. This is done via consistent hashing, which always maps the same key K to the same memcached server S. When a server crashes, or a new server is added, consistent hashing makes sure that the ensuing rehashing is minimal. Which means that most keys still map to the same servers, but keys hashing to a removed server are rehashed to a new server. - from A memcached implementation in JGroups
Amazon's Dynamo uses consistent hashing along with replication as a partitioning scheme.
Data is partitioned and replicated using consistent hashing [10], and consistency is facilitated by object versioning [12]. The consistency among replicas during updates is maintained by a quorum-like technique and a decentralized replica synchronization protocol. - from Dynamo: Amazon's Highly Available Key-value Store
Data of a
Cassandra table gets partitioned and distributed among
the nodes by a consistent hashing function.
Cassandra partitions data across the cluster using consistent hashing [11] but uses an order preserving hash function to do so. In consistent hashing the output range of a hash function is treated as a circular space or "ring" (i.e. the largest hash value wraps around to the smallest hash value). Each node in the system is as-signed a random value within this space which represents its position on the ring. Each data item identified by a key is assigned to a node by hashing the data item's key to yield its position on the ring, and then walking the ring clockwise to fi nd the first node with a position larger than the item's position. This node is deemed the coordinator for this key. The application specifi es this key and the Cassandra uses it to route requests. Thus, each node becomes responsible for the region in the ring between it and its predecessor node on the ring. The principal advantage of consistent hashing is that departure or arrival of a node only aff ects its immediate neighbors and other nodes remain una ffected. - from Cassandra - A Decentralized Structured Storage System
Voldemort automatic sharding of data. Nodes can
be added or removed from a database
cluster, and the system adapts automatically.
Voldemort automatically detects and recovers failed nodes. [
refer]
References:
http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf
http://sharplearningcurve.com/blog/2010/09/27/consistent-hashing/
http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html