Comments on Tom White: Consistent Hashing

Hello. Thanks a lot to Tom for the article and to ...

2011-07-08T08:05:32.733+01:00

Hello. Thanks a lot to Tom for the article and to John Cormie for finding the bug.
There is a still another issue in the implementation that may result in not good distribution of keys between nodes. Particularly this code:

for (int i = 0; i < numberOfReplicas; i++) {
circle.put(hashFunction.hash(node.toString() + i),
node);
}

In here, we take nodes's string representation, append integer value and use the resultant "virtual node" as a parameter for hash function. The problem is that for nodes of numeric types (Long, Integer e.t.c) or any other types whose toString() method implementation returns string that ends with a number there is a "increased" probability for different nodes to be mapped to same postion on the circle.
Let me explain by example.
Assume we have 20 nodes which are represented by strings as "node1", "node2", "node3", ..., "node19" and "node20". And we use 100 replicas for each node. So following "virtual nodes" are generated by code above for "node1":

"node1" + 0 = "node10"
...
"node1" + 10 = "node110"
"node1" + 11 = "node111"
"node1" + 12 = "node112"
...
"node1" + 99 = "node199"

At the same time for "node11" we have:

"node11" + 0 = "node110"
"node11" + 1 = "node111"
"node11" + 2 = "node112"
...

As you can see from text in bold, different combination of "node" and postfix resulted in same "virtual nodes" i.e collisions on circle.
In our example 90 "virtual nodes" of "node1" will collide with "virtual nodes" of other nodes, with 10 nodes of each node from "node11" to "node19".

To solve this problem we can use some separator while generating "virtual node":

hashFunction.hash(node.toString() + ":" + i

With this we will have:

"node1" + : + 10 = "node1:10"

"node11" + : + 1 = "node11:0"

The nodes do not collide anymore.

Also do not forget to use separator while removing node.

Wonderful though i missed the concept of ring in t...

2011-01-03T09:50:42.796Z

Wonderful though i missed the concept of ring in the implementation

Thanks so much for explaining the concept so clear...

2011-01-02T18:48:37.540Z

Thanks so much for explaining the concept so clearly for us people not blessed with enough smarts to read a technical paper and understand lemmas, theorems, math to grasp a concept!

May I request you to explain again in simple terms what vector clocks are?

Thanks again

In response to John Cormie about the collisions: ...

2010-02-26T02:51:14.943Z

In response to John Cormie about the collisions:

All you need is a list of node as the value paired for the hash, in the circle,
and a comparator for the nodes that cannot return 0.

When 2 nodes collide to a same hash, put them both in the list, in ascending order. The "smaller" node is first and has precedence. When you remove a node, you make sure to remove the right one from the list and leave the other alone.

This is a good time to drop the generics and us an object in the circle values (node vs single-linked-list of nodes), to save some memory.

great article, and the japanese translation from m...

2009-09-19T03:19:44.453+01:00

great article, and the japanese translation from morrita is cool!!!

I have written a small test app that tells me how ...

2009-05-31T01:40:20.304+01:00

I have written a small test app that tells me how many nodes should be relocated in the event of a node addition, by comparing the same dataset over 2 hashsets.

It consistently reports that nearly all nodes should be moved ... am I doing something wrong ?

http://pastebin.com/f459047ef

Nice explanation of consistent hashing, but there ...

2009-01-31T21:51:00.000Z

Nice explanation of consistent hashing, but there is a subtle bug in the implementation. The problem is hash collisions. Suppose two different nodes x and y have replicas that hash to the same Integer key in "circle". The sequence of calls "add(x); add(y);" will clobber one of x's replicas, and a later call to remove(y) will clear y's replica from "circle" without restoring x's.

One consequence of this bug is that as nodes come and go you may slowly lose replicas. A more serious consequence is that if two clients notice changes to the set of nodes in a different order (very possible in a distributed system), clients will no longer agree on the key to node mapping. For example, suppose nodes x and y have replicas that collide as above, and node x fails around the same time that new (replacement?) node y comes online. In response, suppose that ConsistentHash client A invokes add(y) ... remove(x) and that another client B does the same but in the reverse order. From now on, the set of keys corresponding to the clobbered replica will map to node y at B, while A will map them somewhere else.

How likely are collisions? If we model hashing as a random function, expect a collision after only about 2^(32/2) = 65536 insertions with Integer sized keys (http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem). If numberOfReplicas is set to the suggested 200 replicas per node, we expect a collision in a system with only 328 nodes.

This site has talks lots about the cache with its ...

2008-07-29T04:53:00.000+01:00

This site has talks lots about the cache with its advantages, thanks for the topic, it will lots of gain for to the visitors for this site.

Naorei
==============================
http://community.widecircles.com

Hi. Do you have any clue of how to create an algor...

2008-01-03T20:37:00.000Z

Hi. Do you have any clue of how to create an algorithm which tracks the history of joins/leves of members and delivers the same node for the same key if it previously looked it up. Perhaps I'm explaining this in bad terms but something like a (in memory or persistent) database in cojunction with a consistent hash.

perhaps:
public Address getAddress(key)
{
if(lookedUpMap.containsKey(key))
{
return (Address)lookedUpMap.get(key)
}
else
{
Address a = get(key);
lookedUpMap.put(key, a);
return a;
}
}

Then it is up to the client to check if the previously stored node is reachable at this very moment.

An extension to this cache would be to return a Set which size is equal to the nr of replicas of each key/value.

If a value is stored on two or more nodes then the possibilty for that at least one of the servers is up increases a lot. I'm building a distributed storage solution and the data cannnot be lost just because the cache "recalculates" the hash :)

Ahhh enough already I will implement something like this :)

Cool! I'm as we speak creating a distributed cachi...

2007-12-25T09:37:00.000Z

Cool! I'm as we speak creating a distributed caching and searching system which uses JGroups for membership. The biggest problem I faced was this exact thing. What to do on the member-joined/leaved events and for the system to be able to know at all times to which node to send what command :)

The caching system is strictly following the Map (and SortedMap) interface and a bunch of implementations have been implemented. LFU, LRU, MRU, Diskbased B+Tree (jdbm), ehcache wrapper, memcached java client wrapper, hibernate support...
I like the Map interface since it is quite clean..

The impl I'm working on now is a cache/persister which uses HDFS as persistance layer. See how that turns out. The line between a cache and a persistence engine is fine.

And of course all caches must be searchable = My own indexer/searcher + Lucene free text index/search, ohh and all must be able to work in a distributed environment.. fuck it is a big task.

morrita - Glad you enjoyed the post and thanks for...

2007-12-02T22:26:00.000Z

morrita - Glad you enjoyed the post and thanks for the translation! Tom

good article!
i've made Japanese translation fo...

2007-12-01T06:06:00.000Z

good article!
i've made Japanese translation for your article. which is available at
http://www.hyuki.com/yukiwiki/wiki.cgi?ConsistentHashing .
if you have any trouble, please let me know.
thank you for your work.