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?



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.


The Chord paper provides the theoretical underpinnings of the ring overlay strategy. In particular, the nature of the overlay network that connects the nodes determines the amount of state and query complexity required to efficiently locate a node and its neighbors. There are other examples of DHT's with different overlay topologies like CAN (content addressable networks) with uses a Hypercube overlay and Viceroy which uses a butterfly etc..


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.