Assigning storage responsibility in a distributed data storage system with replication

1. A method for assigning storage responsibility in a distributed data storage system with replication, wherein the storage system includes a plurality of storage nodes that store data objects according to write requests and read requests from application nodes that are separate from the storage nodes, and the storage nodes and the application nodes communicate via a network, and where each storage node has one or more partitions and each partition is associated with a unique token using a 1:1 mapping, the method comprising:

calculating a first number of tokens assigned to a first storage node in the plurality of storage nodes for primary level of responsibility for storing data objects associated with any of the first number of tokens, wherein the first number is greater than one;

assigning the first number of tokens to the first storage node for primary level of responsibility by populating a data location table with identifiers of the first storage node, the data location table storing mappings between tokens and levels of responsibility of the storage nodes for storing data objects associated with the tokens;

calculating a second number of tokens assigned to a second storage node in the plurality of storage nodes for primary level of responsibility for storing data objects associated with any of the second number of tokens, wherein the second number is greater than one;

assigning the second number of tokens to the second storage node for primary responsibility by further populating the data location table with identifiers of the second storage node;

calculating a third number of tokens out of the second number of tokens, the third number of tokens assigned to the first storage node for secondary level of responsibility and assigned to the second storage node for primary level of responsibility for storing data objects associated with any of the third number of tokens, wherein the third number is greater than one;

assigning the third number of tokens to the first storage node for secondary responsibility by further populating the data location table with identifiers of the first storage node; and

storing and retrieving data objects from the plurality of storage nodes according to the tokens associated with the data objects and according to the mappings stored in the data location table.

2. The method of claim 1 , wherein the first number is an integer number.

3. The method of claim 1 , wherein assigning the first number of tokens to the first storage node for primary level of responsibility by populating the data location table with identifiers of the first storage node comprises:

identifying a first row of the data location table associated with primary responsibility level; and

populating a number of entries in the first row with the identifiers of the first storage node, wherein the number of entries is equivalent to the first number of tokens.

4. The method of claim 3 , wherein assigning the second number of tokens to the second storage node for primary level of responsibility by further populating the data location table with identifiers of the second storage node comprises:

identifying the first row of the data location table associated with primary responsibility level; and

populating a number of entries in the first row with the identifiers of the second storage node, wherein the number of entries is equivalent to the second number of tokens.

5. The method of claim 3 , wherein assigning the third number of tokens to the first storage node for secondary responsibility by further populating the data location table with identifiers of the first storage node comprises:

identifying a second row of the data location table associated with secondary responsibility level; and

populating a number of entries in the second row with the identifiers of the first storage node, wherein the number of entries is equivalent to the third number of tokens.

6. The method of claim 1 , further comprising:

calculating additional numbers of tokens assigned to additional storage nodes in the plurality of storage nodes for primary level of responsibility for storing data objects associated with any of the additional number of tokens; and

assigning the additional numbers of tokens to the additional storage nodes for primary level of responsibility by further populating the data location table with identifiers of the additional storage nodes.

7. The method of claim 1 , further comprising:

calculating additional numbers of tokens assigned to unique storage nodes in the plurality of storage nodes for secondary level of responsibility where a unique storage node is associated with a column of the data location table and identifiers of storage nodes in previously-populated row entries associated with the column; and

assigning the additional numbers of tokens to the unique storage nodes for secondary responsibility.

8. The method of claim 7 , wherein the unique storage node associated with the column is different from the storage nodes identified by the identifiers of storage nodes in the previously-populated row entries associated with the column.

9. A method for updating storage responsibility in a distributed data storage system with replication, wherein the storage system includes a plurality of storage nodes that store data objects according to write requests and read requests from application nodes that are separate from the storage nodes, and the storage nodes and the application nodes communicate via a network, and where each storage node has one or more partitions and each partition is associated with a unique token using a 1:1 mapping, the method comprising:

in response to the storage system initially including a first set of storage nodes and being modified such that the storage system includes a second set of storage nodes after modification:

calculating second numbers of tokens assigned to various storage nodes in the second set of storage nodes for various levels of responsibility for storing data objects associated with the second numbers of tokens, wherein the second numbers are all greater than one;

calculating differences between first numbers of tokens assigned to various storage nodes in the first set of storage nodes and the second numbers of tokens assigned to various storage nodes in the second set of storage nodes, the first numbers of tokens determined from a data location table and wherein the first numbers are all greater than one, the data location table storing mappings between tokens and levels of responsibility of the storage nodes for storing data objects associated with the tokens, each data object associated with a token; and

transferring responsibility for tokens between the first set of storage nodes and the second set of storage nodes by populating and de-populating the data location table with identifiers of storage nodes in the first set of storage nodes and identifiers of storage nodes in the second set of storage nodes based on the calculated differences.

10. The method of claim 9 , wherein a difference between numbers of tokens assigned to various storage nodes in the first set of storage nodes and numbers of tokens assigned to various storage nodes in the second set of storage nodes is an integer number.

11. The method of claim 9 , wherein transferring tokens between the first set of storage nodes and the second set of storage nodes based on the calculated differences comprises:

identifying a particular storage node with primary responsibility level in the first set of storage nodes and with primary responsibility level in the second set of storage nodes;

determining whether a token difference associated with the particular storage node and primary responsibility level indicates that the particular storage node has responsibility for more tokens than it should;

responsive to determining the token difference associated with the particular storage node and primary responsibility level indicates that the particular storage node has responsibility for more tokens than it should, identifying a second storage node with primary responsibility level in the first set of storage nodes and with primary responsibility level in the second set of storage nodes;

determining whether a token difference associated with the second storage node and primary responsibility level indicates that the second storage node has responsibility for fewer tokens than it should;

responsive to determining that the token difference associated with the second storage node indicates that the second storage node has responsibility for fewer tokens than it should, identifying a shared unique storage node of the particular storage node and the second storage node, the shared unique storage node having secondary responsibility level for tokens assigned to the particular storage node having primary responsibility level and for tokens assigned to the second storage node having primary responsibility level;

determining whether a token difference associated with the shared unique storage node having secondary responsibility level indicates that the shared unique storage node has responsibility for more tokens than it should where the particular storage node has primary responsibility level and that the shared unique storage node has responsibility for fewer tokens than it should where the second storage node has primary responsibility level; and

responsive to determining the token difference associated with the shared unique storage node having secondary responsibility level indicates that the shared unique storage node has responsibility for more tokens than it should where the particular storage node has primary responsibility level and that the shared unique storage node has responsibility for fewer tokens than it should where the second storage node has primary responsibility level, reassigning one or more tokens from the second storage node to the first storage node.

12. The method of claim 9 , further comprising:

sending the updated data location table to an affected storage node in the first set of storage nodes, the affected storage node being a storage node assigned a different number of tokens in the second set of storage nodes than in the first set of storage nodes.

13. The method of claim 12 , further comprising:

receiving a notification from the affected storage node that an update process is complete, where the update process is complete if assignment of tokens in the data location table associated with the affected storage node matches assignment of tokens in the updated data location table.

14. The method of claim 13 , further comprising:

responsive to receiving the notification, sending the updated data location table to additional storage nodes in the second set of storage nodes.

15. The method of claim 13 , further comprising:

responsive to receiving the notification, sending the updated data location table to application nodes that use the distributed data storage system.

16. A non-transitory computer-readable storage medium storing computer program modules for assigning storage responsibility in a distributed data storage system with replication, wherein the storage system includes a plurality of storage nodes that store data objects according to write requests and read requests from application nodes that are separate from the storage nodes, and the storage nodes and the application nodes communicate via a network, and where each storage node has one or more partitions and each partition is associated with a unique token using a 1:1 mapping, the computer program modules executable to perform steps comprising:

calculating a first number of tokens assigned to a first storage node in the plurality of storage nodes for primary level of responsibility for storing data objects associated with any of the first number of tokens, wherein the first number is greater than one;

assigning the first number of tokens to the first storage node for primary level of responsibility by populating a data location table with identifiers of the first storage node, the data location table storing mappings between tokens and levels of responsibility of the storage nodes for storing data objects associated with the tokens;

calculating a second number of tokens assigned to a second storage node in the plurality of storage nodes for primary level of responsibility for storing data objects associated with any of the second number of tokens, wherein the second number is greater than one;

assigning the second number of tokens to the second storage node for primary responsibility by further populating the data location table with identifiers of the second storage node;

calculating a third number of tokens out of the second number of tokens, the third number of tokens assigned to the first storage node for secondary level of responsibility and assigned to the second storage node for primary level of responsibility for storing data objects associated with any of the third number of tokens, wherein the third number is greater than one;

assigning the third number of tokens to the first storage node for secondary responsibility by further populating the data location table with identifiers of the first storage node; and

storing and retrieving data objects from the plurality of storage nodes according to the tokens associated with the data objects and according to the mappings stored in the data location table, each data object associated with a token.

17. The computer-readable storage medium of claim 16 , wherein assigning the first number of tokens to the first storage node for primary level of responsibility by further populating the data location table with identifiers of the first storage node comprises:

identifying a first row of the data location table associated with primary responsibility level; and

populating a number of entries in the first row with the identifiers of the first storage node, wherein the number of entries is equivalent to the first number of tokens.

18. The computer-readable storage medium of claim 17 , wherein assigning the second number of tokens to the second storage node for primary level of responsibility by further populating the data location table with identifiers of the second storage node comprises:

identifying a first row of the data location table associated with primary responsibility level; and

populating a number of entries in the first row with the identifiers of the second storage node, wherein the number of entries is equivalent to the second number of tokens.

19. The computer-readable storage medium of claim 16 , wherein assigning the third number of tokens to the first storage node for secondary responsibility by further populating the data location table with identifiers of the first storage node comprises:

identifying a second row of the data location table associated with secondary responsibility level; and

populating a number of entries in the second row with the identifiers of the first storage node, wherein the number of entries is equivalent to the third number of tokens.

20. A system for assigning storage responsibility in a distributed data storage system with replication, wherein the storage system includes a plurality of storage nodes that store data objects according to write requests and read requests from application nodes that are separate from the storage nodes, and the storage nodes and the application nodes communicate via a network, and where each storage node has one or more partitions and each partition is associated with a unique token using a 1:1 mapping, the system comprising:

a non-transitory computer-readable storage medium storing computer program modules executable to perform steps comprising:

calculating a first number of tokens assigned to a first storage node in the plurality of storage nodes for primary level of responsibility for storing data objects associated with any of the first number of tokens, wherein the first number is greater than one;

assigning the first number of tokens to the first storage node for primary level of responsibility by populating a data location table with identifiers of the first storage node, the data location table storing mappings between tokens and level of responsibility of the storage nodes for storing data objects associated with the tokens;

calculating a second number of tokens assigned to a second storage node in the plurality of storage nodes for primary level of responsibility for storing data objects associated with any of the second number of tokens, wherein the second number is greater than one;

assigning the second number of tokens to the second storage node for primary responsibility by further populating the data location table with identifiers of the second storage node;

calculating a third number of tokens out of the second number of tokens, the third number of tokens assigned to the first storage node for secondary level of responsibility and assigned to the second storage node for primary level of responsibility for storing data objects associated with any of the third number of tokens, wherein the third number is greater than one;

assigning the third number of tokens to the first storage node for secondary responsibility by further populating the data location table with identifiers of the first storage node; and

storing and retrieving data objects from the plurality of storage nodes according to the tokens associated with the data objects and according to the mappings stored in the data location table, each data object associated with a token; and

a computer processor for executing the computer program modules.