How is rebalancing of DHTs handled in case of failure or addition of new node? I am reading about Dynamo-like DHT data storage applications like cassandra and project voldemort. I was curious, say:


A new node is added to the cluster (since all the nodes are full) then the whole DHTs load factor will be messed up, so the DHT needs a re-balancing. So, how is that handled? Any optimized method/algo to do that?
During the re-balancing process, there must be a data outage time. So, how to deal with that?


I got something about voldemort re-balancing but I didn't really understand, how is the dynamic growth (addition of new nodes) in the cluster is handled?

Thanks
That's the whole purpose of consistent hashing. When you add a new node, you compute its hash key, find the two nearest neighbors on the hash ring and link the node in between them. When the hash function has good statistics, you expect a uniform distribution of hash keys, resulting in good load balancing. You don't have to redistribute the existing keys. Removal of nodes works analogously.

In summary, there's no global coordination to achieve even coverage of the key space. That is an emergent property of the hash function. The only coordination is local in the form of linking and unlinking nodes into the circular list of nodes on the ring.

Incidentally, if nodes were only ever added and not deleted, low-discrepancy sequences would be a better choice than hashing (such sequences are particularly simple in one dimension). But in the real world, nodes are added and deleted in an unpredictable pattern. Hashing is better able to cope with those conditions; the trade-off is worse discrepancy in the monotone growth case. Using a low-discrepancy sequence would also require new nodes to coordinate with a key manager, though no existing keys need to be redistributed.