Distributed data storage

• US 8,850,019 B2
• Filed: 06/30/2011
• Issued: 09/30/2014
• Est. Priority Date: 04/23/2010
• Status: Active Grant

• Current Assignee: Compuverde AB (Pure Storage, Inc.)
• Original Assignee: ILT Innovations AB
• Inventors: Bernbo, Stefan, Melander, Christian, Persson, Roger, Petersson, Gustav
• Primary Examiner(s): Algibhah, Hamza
• Assistant Examiner(s): COX, NATISHA D
• Application Number:
  US13/174,350
• Publication Number:
  US 20120084383A1
• Time in Patent Office: 1,188 Days
• Field of Search: 709/213
• US Class Current: 709/226
• 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 writing data to a data storage system comprising a plurality of data storage nodes, the method being employed in a server running an application which accesses data in the data storage system via a communication network, and comprising:

the server sending a multicast storage query to a plurality of said storage nodes via the communication network, the multicast storage query comprising a data identifier for data to be stored;

the server receiving a plurality of responses from a number of said storage nodes via the communication network, the responses including storage node information respectively relating to each storage node;

the server selecting a subset of the responding storage nodes that satisfy a primary criteria based on geographical separation for further evaluation, wherein at least one responding storage node is removed from the selection process as lacking a requisite level of geographical separation;

for each storage node in the subset, the server determining a respective probability factor, wherein each respective probability factor is determined based at least in part on the respective storage node information included in a respective response;

the server randomly selecting at least two storage nodes from the subset of storage nodes that satisfied the primary criteria, wherein the probability of a respective storage node being randomly selected depends on its respective probability factor; and

the server sending the data to the at least two selected storage nodes via the communication network.

2. A method according to claim 1, wherein storage node information includes geographic data relating to the geographic position a responding storage node.

3. A method according to claim 2, wherein the geographic position includes latitude and longitude of the responding storage node.

4. A method according to claim 1, wherein the at least one responding storage node is removed from the selection process as lacking the requisite level of geographical separation based on another storage node in a same storage group as the at least one responding storage node being selected for further evaluation.

5. A method according to claim 1, wherein the storage node information includes system age for the responding storage node.

6. A method according to claim 1, wherein the storage node information includes system load or disk load for the responding storage node.

7. A method according to claim 1, wherein the data identifier for the data to be stored comprises a universally unique identifier (UUID), and a number of bits of the UUID are used to specify a disk to be used on a data storage node for storing the data corresponding to the data identifier.

8. A method according to claim 1, wherein at least three nodes are selected.

9. A method according to claim 1, wherein a list of storage nodes successfully storing the data is sent to the selected storage nodes.

10. A method according to claim 7, wherein each of the plurality of responses comprises status information for a disk at a respective storage node that corresponds to the disk specified by the UUID, and the status information for the specified disk is used at least in part to determine the respective probability factor for the respective storage node.

11. A server adapted for writing data to a data storage system comprising a plurality of data storage nodes by sending and receiving messages over a communication network, the server comprising at least memory and a processor configured to:

send a multicast storage query to a plurality of said storage nodes via the communication network, the multicast storage query comprising a data identifier for data to be stored;

receive a plurality of responses from a subset of said storage nodes, the responses including storage node information respectively relating to each storage node;

identify a number of storage groups that have a requisite geographic diversity and select a given storage node in the subset from each identified storage group for further evaluation;

determine a respective probability factor for each storage node selected from one of the storage groups, wherein each respective probability factor is determined based at least in part on the respective storage node information included in a respective response;

randomly select at least two storage nodes from the storage nodes selected from the storage groups, wherein the probability of a respective storage node being randomly selected depends on its respective probability factor; and

send the data to the at least two selected storage nodes via the communication network.

15. The server of claim 11, wherein the data identifier for the data to be stored comprises a universally unique identifier (UUID), and a number of bits of the UUID are used to specify a disk to be used on a data storage node for storing the data corresponding to the data identifier.

16. The server of claim 15, wherein each of the plurality of responses comprises status information for a disk at a respective storage node that corresponds to the disk specified by the UUID, and the status information for the specified disk is used at least in part to determine the respective probability factor for the respective storage node.

12. A method for writing data to a data storage system comprising a plurality of data storage nodes, the method being employed in a server running an application which accesses data in the data storage system via a communication network, the server comprising:

the server sending a multicast storage query to a plurality of said storage nodes via the communication network, the multicast storage query comprising a data identifier for data to be stored;

the server receiving a plurality of responses from a subset of said storage nodes via the communication network, the responses including storage node information respectively relating to each storage node;

the server removing at least one storage node in the subset from the selection process based on the at least one storage node lacking a desired level of geographic diversity as compared to remaining storage nodes in the subset;

the server determining, based on an algorithm, for each of the remaining storage nodes in the subset, a corresponding probability factor based at least in part on the corresponding storage node information included the corresponding response;

the server randomly selecting at least two storage nodes from the remaining storage nodes with the desired levels of geographic diversity, wherein the probability of a storage node being randomly selected depends on its respective probability factor; and

the server sending the data to the at least two selected storage nodes via the communication network.

13. The method according to claim 12, further comprising the server removing at least a second storage node in the subset from the selection process based on the second storage node having a probability factor that is lower than the remaining storage nodes in the subset.

14. The method according to claim 12, wherein the at least one storage node is removed after a first selection process yielded a set of storage nodes that lacked a given level of geographic diversity.

17. The method of claim 12, wherein the data identifier for the data to be stored comprises a universally unique identifier (UUID), and a number of bits of the UUID are used to specify a disk to be used on a data storage node for storing the data corresponding to the data identifier.

18. The method of claim 17, wherein each of the plurality of responses comprises status information for a disk at a respective storage node that corresponds to the disk specified by the UUID, and the status information for the specified disk is used at least in part to determine the respective probability factor for the respective storage node.