<p>The <a href="http://pdos.csail.mit.edu/papers/chord%3asigcomm01/chord_sigcomm.pdf" rel="nofollow">Chord</a> 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..</p>

CC BY-SA 2.5
2010-09-27T11:33:32.653Z
2010-09-27T11:33:32.653Z
kryptos
<p>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.</p>

<p>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.</p>

<p>Incidentally, if nodes were only ever added and not deleted, <a href="http://en.wikipedia.org/wiki/Low-discrepancy_sequence" rel="nofollow">low-discrepancy sequences</a> would be a better choice than hashing (such sequences are particularly simple in one dimension). But in the real world, nodes are added <em>and</em> 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.</p>

CC BY-SA 2.5
2010-09-27T05:54:47.500Z
2010-09-27T06:16:33.037Z
2010-09-27T06:16:33.037Z
Per Vognsen
<p>I am reading about Dynamo-like DHT data storage applications like cassandra and project voldemort. I was curious, say:</p>

<ul>
<li><p>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?</p></li>
<li><p>During the re-balancing process, there must be a data outage time. So, how to deal with that?</p></li>
</ul>

<p>I got something about <a href="http://wiki.github.com/voldemort/voldemort/voldemort-rebalancing">voldemort re-balancing</a> but I didn't really understand, how is the dynamic growth (addition of new nodes) in the cluster is handled?</p>

<p>Thanks</p>

CC BY-SA 4.0
2021-10-16T15:28:18.930Z
The [voldemort re-balancing](http://wiki.github.com/voldemort/voldemort/voldemort-rebalancing) wiki link above no longer works. I think it has moved here: [Rebalancing - Voldemort](https://www.project-voldemort.com/voldemort/rebalance.html).
Peter V. Mørch
<dc.distributed-comp><hash-function>
How is rebalancing of DHTs handled in case of failure or addition of new node?
zengr
# How is rebalancing of DHTs handled in case of failure or addition of new node?

(Asked by: username_0 on 2010-09-27)

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](http://wiki.github.com/voldemort/voldemort/voldemort-rebalancing) but I didn't really understand, how is the dynamic growth (addition of new nodes) in the cluster is handled?

Thanks

**Tags:** dc.distributed-comp, hash-function
> **Comments:**
> **username_1**: The [voldemort re-balancing](http://wiki.github.com/voldemort/voldemort/voldemort-rebalancing) wiki link above no longer works. I think it has moved here: [Rebalancing - Voldemort](https://www.project-voldemort.com/voldemort/rebalance.html).  

---

## 2 answers

### Answer by username_3 on 2010-09-27. Score: 7 | Accepted answer

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](http://en.wikipedia.org/wiki/Low-discrepancy_sequence) 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.


---

### Answer by username_2 on 2010-09-27. Score: 2

The [Chord](http://pdos.csail.mit.edu/papers/chord%3asigcomm01/chord_sigcomm.pdf) 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..


---

