In previous posts, we learned about partitioning schemes for key-value pairs and secondary indexes, in all of these schemes there is a need for redistributing data either when there is a new node or a new partition. In this post, we are going to touch upon the techniques to do handle that data migration. 

The process of moving load from one node in the cluster to another is called rebalancing..

Some requirements for rebalancing – 

• After rebalancing, the load (data storage, read and write requests) should be shared fairly between the nodes in the cluster.

• While rebalancing is happening, the database should continue accepting reads and writes.

• No more data than necessary should be moved between nodes, to make rebalancing fast and to minimize the network and disk I/O load.

Strategies for Rebalancing

1. Fixed number of partitions – create many more partitions than there are nodes, and assign several partitions to each node. Only entire partitions are moved between nodes. if a node is added to the cluster, the new node can steal a few partitions from every existing node until partitions are fairly distributed once again. The number of partitions does not change, nor does the assignment of keys to partitions. The only thing that changes is the assignment of partitions to nodes. This change of assignment is not immediate—it takes some time to transfer a large amount of data over the network—so the old assignment of partitions is used for any reads and writes that happen while the transfer is in progress.

2. Dynamic partitioning – Key range–partitioned databases such as HBase and RethinkDB create partitions dynamically. When a partition grows to exceed a configured size (on HBase, the default is 10 GB), it is split into two partitions so that approximately half of the data ends up on each side of the split. Conversely, if lots of data is deleted and a partition shrinks below some threshold, it can be merged with an adjacent partition. This process is similar to what happens at the top level of a B-tree. 
   
   Each partition is assigned to one node, and each node can handle multiple partitions, like in the case of a fixed number of partitions. After a large partition has been split, one of its two halves can be transferred to another node in order to balance the load. In the case of HBase, the transfer of partition files happens through HDFS, the underlying distributed filesystem.
   
   An advantage of dynamic partitioning is that the number of partitions adapts to the total data volume. If there is only a small amount of data, a small number of partitions is sufficient, so overheads are small; if there is a huge amount of data, the size of each individual partition is limited to a configurable maximum.

3. Partitioning proportionally to nodes – make the number of partitions proportional to the number of nodes—in other words, to have a fixed number of partitions per node. In this case, the size of each partition grows proportionally to the dataset size while the number of nodes remains unchanged, but when you increase the number of nodes, the partitions become smaller again. Since a larger data volume generally requires a larger number of nodes to store, this approach also keeps the size of each partition fairly stable.

Operations: Automatic or Manual Rebalancing

Automatic rebalancing  – the system decides automatically when to move partitions from one node to another, without any administrator interaction. Fully automated rebalancing can be convenient, because there is less operational work to do for normal maintenance. However, it can be unpredictable. 

Rebalancing is an expensive operation, because it requires rerouting requests and moving a large amount of data from one node to another. If it is not done carefully, this process can overload the network or the nodes and harm the performance of other requests while the rebalancing is in progress. SO it’s better to have human in the loop ie use the manual rebalancing.

Manual rebalancing – the assignment of partitions to nodes is explicitly configured by an administrator, and only changes when the administrator explicitly reconfigures it.

Thanks for stopping by! Hope this gives you a brief overview in to rebalancing partitions. Eager to hear your thoughts and chat, please leave comments below and we can discuss.