Distributed data storage

• US 9,948,716 B2
• Filed: 10/26/2016
• Issued: 04/17/2018
• Est. Priority Date: 04/23/2010
• Status: Active Grant

• 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:
  US15/334,551
• Publication Number:
  US 20170048321A1
• Time in Patent Office: 538 Days
• Field of Search: None
• 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 a first response is received from a first storage node and comprises storage node information regarding the first storage node, a second response is received from a second storage node and comprises storage node information regarding the second storage node, and a third response is received from a third storage node and comprises storage node information regarding the third storage node;

deriving a first probability factor for the first storage node based at least in part on the storage node information comprised in the first response;

deriving a second probability factor for the second storage node based at least in part on the storage node information comprised in the second response;

deriving a third probability factor for the third storage node based at least in part on the storage node information comprised in the third response;

performing a probabilistic based selection based on at least the first, second, and third probability factors, wherein a probability of the first storage node being selected is dependent on the first probability factor derived from the storage node information comprised in the first response, a probability of the second storage node being selected is dependent on the second probability factor derived from the storage node information comprised in the second response, a probability of the third storage node being selected is dependent on the third probability factor derived from the storage node information comprised in the third response, and the probabilistic based selection results in at least the first and second storage nodes being selected to store the first data and the third storage node not being selected to store the first data;

sending a first unicast request to store the first data to the first storage node; and

sending a second unicast request to store the first data to the second storage node.

2. The method as in claim 1, further comprising ensuring that each of the first and second storage nodes have at least a predetermined level of geographic diversity.

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

4. The method as in claim 1, wherein the storage node information comprised in the first response received from the first storage node comprises geographical data associated with the first storage node.

5. The method as in claim 4, wherein the geographical data associated with the first storage node comprises latitude and longitude information associated with the first storage node.

6. The method as in claim 1, wherein the storage node information comprised in the first response received from the first storage node comprises a system load at the first storage node.

7. The method as in claim 1, wherein the storage node information comprised in the first response received from the first storage node comprises a system age corresponding to the first storage node.

8. The method as in claim 1, wherein the storage node information comprised in the first response received from the first storage node comprises an amount of free space at the first storage node.

9. The method as in claim 1, wherein the first probability factor is determined as a scalar product of a first vector associated with storage node information parameters that are associated with the first storage node and a second vector associated with weighting factors configured to apply individual weights to each of the storage node information parameters.

10. The method as in claim 1, wherein the storage node information comprised in the first response received from the first storage node comprises status information related to at least one disc at the first storage node.

11. 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 a first response is received from a first storage node and comprises storage node information regarding the first storage node, a second response is received from a second storage node and comprises storage node information regarding the second storage node, and a third response is received from a third storage node and comprises storage node information regarding the third storage node;

derive a first probability factor for the first storage node based at least in part on the storage node information comprised in the first response;

derive a second probability factor for the second storage node based at least in part on the storage node information comprised in the second response;

derive a third probability factor for the third storage node based at least in part on the storage node information comprised in the third response;

perform a probabilistic based selection based on at least the first, second, and third probability factors, wherein a probability of the first storage node being selected is dependent on the first probability factor derived from the storage node information comprised in the first response, a probability of the second storage node being selected is dependent on the second probability factor derived from the storage node information comprised in the second response, a probability of the third storage node being selected is dependent on the third probability factor derived from the storage node information comprised in the third response, and the probabilistic based selection results in at least the first and second storage nodes being selected to store the first data and the third storage node not being selected to store the first data;

send a first unicast request to store the first data to the first storage node; and

send a second unicast request to store the first data to the second storage node.

12. The server as in claim 11, further comprising ensuring that each of the first and second storage nodes have at least a predetermined level of geographic diversity.

13. 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 based on the first probability factor being twice the second probability factor.

14. The server as in claim 11, wherein the storage node information comprised in the first response received from the first storage node comprises geographical data associated with the first storage node.

15. The server as in claim 14, wherein the geographical data associated with the first storage node comprises latitude and longitude information associated with the first storage node.

16. The server as in claim 11, wherein the storage node information comprised in the first response received from the first storage node comprises a system load at the first storage node.

17. The server as in claim 11, wherein the storage node information comprised in the first response received from the first storage node comprises a system age corresponding to the first storage node.

18. The server as in claim 11, wherein the storage node information comprised in the first response received from the first storage node comprises an amount of free space at the first storage node.

19. The server as in claim 11, wherein the first probability factor is determined as a scalar product of a first vector associated with storage node information parameters that are associated with the first storage node and a second vector associated with weighting factors configured to apply individual weights to each of the storage node information parameters.

20. The server as in claim 11, wherein the storage node information comprised in the first response received from the first storage node comprises status information related to at least one disc at the first storage node.