Distributed data storage

• US 9,503,524 B2
• Filed: 09/12/2014
• Issued: 11/22/2016
• Est. Priority Date: 04/23/2010
• Status: Expired due to Fees

• Current Assignee: Compuverde AB (Pure Storage, Inc.)
• Original Assignee: Compuverde AB (Pure Storage, Inc.)
• Inventors: Bernbo, Stefan, Melander, Christian, Persson, Roger, Petersson, Gustav
• Primary Examiner(s): COX, NATISHA D
• Application Number:
  US14/485,502
• Publication Number:
  US 20140379845A1
• Time in Patent Office: 802 Days
• Field of Search: 709/213
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: H04L 12/1845 broadcast or multicast in a specific location, e.g. geocast protocols for adapting network applications to user terminal location H04L67/52; services specially adapted for wireless communication networks making use of the location of users or terminals H04W4/02
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

The present invention relates to a distributed data storage system comprising a plurality of storage nodes. Using unicast and multicast transmission, a server application may write data in the storage system. When writing data, at least two storage nodes are selected based in part on a randomized function, which ensures that data is sufficiently spread to provide efficient and reliable replication of data in case a storage node malfunctions.

Claims

1. A method for a device to write data in a data storage system, the method comprising:

sending a multicast storage query, the multicast storage query indicating a request to store first data in the data storage system;

receiving a plurality of responses to the multicast storage query, wherein each of the plurality of responses is received from a respective storage node of a plurality of storage nodes, and each of the plurality of responses indicates storage node information regarding the respective storage node that sent the response;

determining a respective probability factor for each storage node that sent one of the plurality of responses, wherein each respective probability factor is determined based at least in part on the storage node information included in the response to the multicast storage query that is received from the respective storage node;

selecting a subset of storage nodes from the plurality of storage nodes that sent the plurality of responses, wherein the subset is selected based on the determined probability factors, and at least one storage node with a lowest determined probability factor of the determined probability factors is excluded from the subset;

performing a probabilistic based selection that results in at least two storage nodes from the subset of storage nodes being selected to store the first data, wherein when performing the probabilistic based selection a probability of selecting a given storage node from the subset of storage nodes is determined based on the probability factor determined for the given storage node; and

sending the first data to the at least two storage nodes.

2. The method as in claim 1, wherein multiple storage nodes that sent responses to the multicast storage query are excluded from the subset based on the multiple storage nodes having the lowest determined probability factors of the storage nodes that sent the plurality of responses.

3. The method as in claim 1, wherein the subset of storage nodes correspond to the storage nodes that have a highest determined probability factors of the plurality of storage nodes that sent responses to the multicast storage query.

4. The method as in claim 1, wherein a first storage node is determined to have a first probability factor, a second storage node is determined to have a second probability factor, and the first probability factor is twice the second probability factor.

5. The method as in claim 4, wherein the first storage node has twice the probability of being selected during the probabilistic based selection than the second storage node.

6. The method as in claim 1, further comprising performing a subsequent selection of storage nodes for writing second data, wherein performing the subsequent selection comprises:

after performing the probabilistic based selection of two or more storage nodes from a second subset of storage nodes for storing the second data based on probability factors of storage nodes in the second subset, determining a level of geographic diversity between at least two of the two or more selected storage nodes lack a requisite level of geographical diversity;

removing at least one of the at least two selected storage nodes that lack the requisite level of geographic diversity from the second subset; and

re-performing the probabilistic based selection from the second subset with the at least one of the at least two storage nodes removed.

7. The method as in claim 1, wherein each respective probability factor corresponds to a weighted score determined based on a plurality of storage node parameters, and at least one of the storage node parameters is indicated in a response to the multicast storage query.

8. A server for writing data in a data storage system, the server comprising at least a processor configured to:

send a multicast storage query, the multicast storage query indicating a request to store first data in the data storage system;

receive a plurality of responses to the multicast storage query, wherein each of the plurality of responses is received from a respective storage node of a plurality of storage nodes, and each of the plurality of responses indicates storage node information regarding the respective storage node that sent the response;

determine a respective probability factor for each storage node that sent one of the plurality of responses, wherein each respective probability factor is determined based at least in part on the storage node information included in the response to the multicast storage query that is received from the respective storage node;

select a subset of storage nodes from the plurality of storage nodes that sent the plurality of responses, wherein the subset is selected based on the determined probability factors, and at least one storage node with a lowest determined probability factor of the determined probability factors is excluded from the subset;

perform a probabilistic based selection that results in at least two storage nodes from the subset of storage nodes being selected to store the first data, wherein when performing the probabilistic based selection a probability of selecting a given storage node from the subset of storage nodes is determined based on the probability factor determined for the given storage node; and

sending the first data to the at least two storage nodes.

9. The server as in claim 8, wherein server is configured to exclude multiple storage nodes that sent responses to the multicast storage query from the subset based on the multiple storage nodes having the lowest determined probability factors of the storage nodes that sent the plurality of responses.

10. The server as in claim 8, wherein the subset of storage nodes correspond to the storage nodes that have a highest determined probability factors of the plurality of storage nodes that sent responses to the multicast storage query.

11. The server as in claim 8, wherein a first storage node is determined to have a first probability factor, a second storage node is determined to have a second probability factor, and the first probability factor is twice the second probability factor.

12. The server as in claim 11, wherein the first storage node has twice the probability of being selected during the probabilistic based selection than the second storage node.

13. The server as in claim 8, wherein the processor is further configured to perform a subsequent selection of storage nodes for writing second data by:

after performing the probabilistic based selection of two or more storage nodes from a second subset of storage nodes for storing the second data based on probability factors of storage nodes in the second subset, determining a level of geographic diversity between at least two of the two or more selected storage nodes lack a requisite level of geographical diversity;

removing at least one of the at least two selected storage nodes that lack the requisite level of geographic diversity from the second subset; and

re-performing the probabilistic based selection from the second subset with the at least one of the at least two storage nodes removed.

14. The server as in claim 8, wherein each respective probability factor corresponds to a weighted score determined based on a plurality of storage node parameters, and at least one of the storage node parameters is indicated in a response to the multicast storage query.

15. A device for writing data in a data storage system, the device comprising at least a processor configured to:

send a multicast storage query, the multicast storage query indicating a request to store first data in a data storage system;

receive a plurality of responses to the multicast storage query, wherein each of the plurality of responses is received from a respective storage node of a plurality of storage nodes, and each of the plurality of responses indicates storage node information regarding the respective storage node that sent the response;

determine a respective probability factor for each storage node that sent one of the plurality of responses, wherein each respective probability factor is determined after transmitting the multicast storage query based at least in part on the storage node information included in the response to the multicast storage query that is received from the respective storage node;

perform a probabilistic based selection that results in at least two storage nodes from the plurality of responsive storage nodes being selected to store the first data, wherein when performing the probabilistic based selection a probability of selecting a given storage node is determined based on the probability factor determined for the given storage node;

send the first data to the at least two storage nodes; and

perform a subsequent selection of storage nodes for writing second data by;

after selecting two or more storage nodes from a second subset of storage nodes for storing the second data based on probability factors of storage nodes in the second subset, determining a level of geographic diversity between at least two of the two or more selected storage nodes lack a requisite level of geographical diversity,

removing at least one of the at least two selected storage nodes that lack the requisite level of geographic diversity from the second subset, and

re-performing the selection from the second subset with the at least one of the at least two storage nodes removed.

16. The device as in claim 15, wherein the processor is configured to exclude one or more storage nodes that sent responses to the multicast storage query from the random selection based on the one or more storage nodes having the lowest determined probability factors of the storage nodes that sent the plurality of responses.

17. The device as in claim 15, wherein the processor is further configured to ensure that each of the at least two storage nodes that are randomly selected have a requisite level of geographic diversity.

18. The device as in claim 15, wherein a first storage node is determined to have a first probability factor, a second storage node is determined to have a second probability factor, the first probability factor is twice the second probability factor, and the first storage node has twice the probability of being selected during the probabilistic based selection than the second storage node.

19. The device as in claim 15, wherein each respective probability factor corresponds to a weighted score determined based on a plurality of storage node parameters, and at least one of the storage node parameters is indicated in a response to the multicast storage query.