CUMULATIVE BALANCE ALGORITHM FOR CONSISTENT HASHING TOKEN SELECTION
For hash token selection a cumulative balance placement algorithm may take a list of new nodes to be added and allocate new virtual nodes to a token range to ensure that when adding M new nodes, the distance between two virtual nodes for the same new node will be at least M−1 virtual nodes. This node balancing improves the operation of the system as a whole by more efficient utilization of each node.
1 . A method for hash token selection comprising:
identifying new nodes to be added to existing nodes;
generating virtual nodes to correspond with the nodes; and
assigning each of the virtual nodes to the nodes in a round robin structure.
2 . The method of claim 1 , wherein the virtual nodes correspond with the new nodes.
3 . The method of claim 2 , wherein the round robin structure corresponds with each of the virtual nodes being assigned to a corresponding one of the new nodes sequentially.
4 . The method of claim 2 , wherein the round robin structure allocates the virtual nodes to a token range.
5 . The method of claim 4 , wherein when adding M new nodes, a distance between two of the virtual nodes for one of the new nodes is at least M−1 virtual nodes.
6 . The method of claim 5 , wherein the round robin structure comprises assigning node 1 a 0th index virtual node, and assigning node 2 a 1st index virtual node.
7 . The method of claim 1 , wherein the generating or assigning considers a determination of configurations.
8 . The method of claim 7 , wherein the configurations comprise at least one of a number of the nodes, a source of the nodes, a protection scheme, a node capacity, or a hash table assignment.
9 . A method for cumulative balance selection comprising:
identifying nodes to be rebalanced among existing nodes;
generating virtual nodes to correspond with the identified nodes; and
assigning each of the virtual nodes to the nodes in a round robin structure such that node M will get the (M−1)th index virtual node.
10 . The method of claim 9 , wherein the round robin structure allocates the virtual nodes to a token range.
11 . The method of claim 10 , wherein when adding M new nodes, a distance between two of the virtual nodes for one of the new nodes is at least M−1 virtual nodes.
12 . The method of claim 11 , wherein the round robin structure comprises assigning node 1 a 0th index virtual node, and assigning node 2 a 1st index virtual node.
13 . The method of claim 9 , wherein the virtual nodes correspond with the identified nodes.
14 . The method of claim 9 , wherein the round robin structure corresponds with each of the virtual nodes being assigned to a corresponding one of the identified nodes sequentially.
15 . The method of claim 10 , wherein the generating or assigning considers a determination of configurations.
16 . The method of claim 15 , wherein the configurations comprise at least one of a number of the nodes, a source of the nodes, a protection scheme, a node capacity, or a hash table assignment.