Weighted load balancing method on data access nodes

The weighted load balancing method on data access nodes comprising the following steps:

• Step 1:
• create a new routing table by updating an old routing table;
• when adding, removing nodes or changing a weight of nodes, move virtual nodes from a first node that has a decreased number of virtual nodes to a second node that has an increased number of virtual nodes;
• wherein a system which has n virtual nodes and m nodes whose identifiers and weights in turn are ID1, ID2, ID3, . . . , IDm and W1, W2, W3, . . . , Wm;
• When adding a node with identifier IDm+1, a proportion of data that needs to be shifted is
• W
• m
• +
• 1
• ÷
• ∑
• k
• =
• 1
• m
• +
• 1
• ⁢
• ⁢
• (
• W
• k
• )
• ;
• When removing a node with an identifier IDi having Iϵ[1, m], the proportion of data needs to be shifted is
• W
• i
• ÷
• ∑
• k
• =
• 1
• m
• ⁢
• ⁢
• (
• W
• k
• )
• ;
• When replacing the weight of nodes with new values Q1, Q2, Q3, . . . , Qm, the proportion of data needs to be shifted is
• ∑
• k
• =
• 1
• m
• ⁢
• 
• Q
• k
• ÷
• Q
• -
• W
• k
• ÷
• W
• 
• ÷
• 2
• ;
• In which m is the total number of nodes before adding or removing;
• Wm+1 is the weight of the added node;
• Wi is the weight of the removed node;
• Q is the new total weight;
• W is the old total weight;
• Qk is the new weight of node IDk;
• Wk is the old weight of node IDk;
• Step 2:
• store the old routing table (before being updated) on an array A1 and the new routing table (after being updated on step 1) on an array A2;
• Step 3:
• block access to records that need to be moved to another node:
• Wherein the block access to records comprises, for read access with key K, perform a hash function F(x) to calculate a value I=F(K);
• read a record corresponding to key K from the node having identifier A1[I] then return result;
• For write access with key K, perform the hash function F(x) to calculate the value I=F(K);
• if A1[I]=A2[I], the record corresponding to key K is not being moved, write record to the node having identifier A1[I] then return success code;
• if A1[I]≠A2[I], the record corresponding to key K is being moved, deny write access and return an error code;
• Step 4:
• copy records from the old node to the new node:
• for each key K, perform the hash function F(x) to calculate value I=F(K);
• if A1[I]≠A2[I], copy the record corresponding to key K from the node having identifier A1[I] to the node having identifier A2[I];
• if A1[I]=A2[I], the record corresponding to key K does not need to be moved;
• Step 5:
• after copying all records that need to be moved, all read/write access is performed using the new routing table A2:
• for each read/write access with key K, perform the hash function F(x) to calculate value I=F(K);
• the record corresponding to key K is accessed on node having identifier A2[I];
• Step 6:
• clean duplicated records:
• for each key K, perform the hash function F(x) to calculate value I=F(K);
• if A1[I]≠A2[I], remove the record corresponding to key K from node having identifier A1[I];
• if A1[I]=A2[I], the record corresponding to key K is not duplicated.