Method for data retrieval from a distributed data storage system

• US 10,579,615 B2
• Filed: 05/30/2014
• Issued: 03/03/2020
• Est. Priority Date: 09/02/2011
• 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): Mejia, Anthony
• Application Number:
  US14/291,223
• Publication Number:
  US 20140279936A1
• Time in Patent Office: 2,104 Days
• Field of Search: 709230, 709231
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

There is provided a method and server for retrieving data from a data storage system including a plurality of storage nodes. The method may include sending a multicast message to at least a subset of the storage nodes. The multicast message may include a request for the subset of storage nodes to send the data. The multicast message may further include a data identifier, indicating the data to be retrieved. Moreover, the method may include receiving data from a first storage node of the subset of storage nodes. The data received from the first storage node may correspond to the requested data. At least the act of sending a multicast message or the act of receiving data from the first storage node may be performed on a condition that an estimated size of the data is less than a predetermined value.

Claims

1. A method for requesting data, the method comprising:

sending a multicast message that requests data to a plurality of storage nodes in a data storage system, wherein the data storage system operates without the use of permanent master storage nodes, and the multicast message includes a data identifier used to uniquely identify the requested data within the data storage system;

receiving a plurality of responses to the multicast message, wherein the plurality of responses comprise a first response from a first storage node and a second response from a second storage node, the first response comprises a first instance of the requested data and an indication of first version data associated with the first instance of the requested data, and the second response comprises a second instance of the requested data and an indication of second version data associated with the second instance of the requested data;

analyzing the first and second instances of the requested data to determine whether one or more of the first instance of the requested data or the second instance of the second data have met a desired integrity level;

determining that the first instance of the requested data corresponds to a correct version of the requested data based on the first version data being associated with a version of the requested data that is stored on a majority of the data storage nodes that store the requested data, wherein the first version data comprises a version number associated with the first instance of the requested data and an indication of an application programming interface (API) that last modified the first instance of the requested data; and

selecting the first instance of the requested data based on the first instance of the requested data being stored on a majority of the data storage nodes that store the requested data, and discarding the second instance of the requested data based on the second instance of the requested data being stored on less than a majority of the data storage nodes that store the requested data.

2. The method as in claim 1, wherein the plurality of responses to the multicast message further comprise a third response from a third storage node, and the third response comprises a third instance of the requested data and an indication that the first version data is associated with the third instance of the requested data.

3. The method as in claim 2, further comprising:

determining that each of the first instance of the requested data and the third instance of the requested data each meet the desired integrity level; and

selecting one of the first instance of the requested data or the third instance of the requested data, wherein the selection is based on additional criteria related to conditions at the first and third storage nodes.

4. The method as in claim 3, wherein the conditions at the first and third storage nodes comprise one or more of load conditions, geographical position, or system age of the first and third storage nodes.

5. The method as in claim 2, wherein the indication that the first version data is associated with the third instance of the requested data comprises third version data that comprises the same version number and indicates the same API as the first version data.

6. The method as in claim 1, wherein the first response comprising the first instance of the requested data and the second response comprising the second instance of the requested data are received in response to the multicast message on condition that a size of the requested data is less than a predetermined value.

7. A server for accessing a data storage system, the server comprising a processor configured, at least in part, to:

send a multicast message that requests data to a plurality of storage nodes in the data storage system, wherein the data storage system operates without the use of permanent master storage nodes, and the multicast message includes a data identifier used to uniquely identify the requested data within the data storage system;

receive a plurality of responses to the multicast message, wherein the plurality of responses comprise a first response from a first storage node and a second response from a second storage node, the first response comprises a first instance of the requested data and an indication of first version data associated with the first instance of the requested data, and the second response comprises a second instance of the requested data and an indication of second version data associated with the second instance of the requested data;

analyze the first and second instances of the requested data to determine whether one or more of the first instance of the requested data or the second instance of the second data have met a desired integrity level;

determine that the first instance of the requested data corresponds to a correct version of the requested data based on the first version data being associated with a version of the requested data that is stored on a majority of the data storage nodes that store the requested data, wherein the first version data comprises a version number associated with the first instance of the requested data and an indication of an application programming interface (API) that last modified the first instance of the requested data; and

select the first instance of the requested data based on the first instance of the requested data being stored on a majority of the data storage nodes that store the requested data, and discarding the second instance of the requested data based on the second instance of the requested data being stored on less than a majority of the data storage nodes that store the requested data.

8. The server as in claim 7, wherein the plurality of responses to the multicast message further comprise a third response from a third storage node, and the third response comprises a third instance of the requested data and an indication that the first version data is associated with the third instance of the requested data.

9. The server as in claim 8, wherein the processor is further configured to:

determine that each of the first instance of the requested data and the third instance of the requested data each meet the desired integrity level; and

select one of the first instance of the requested data or the third instance of the requested data, wherein the selection is based on additional criteria related to conditions at the first and third storage nodes.

10. The server as in claim 9, wherein the conditions at the first and third storage nodes comprise one or more of load conditions, geographical position, or system age of the first and third storage nodes.

11. The server as in claim 8, wherein the indication that the first version data is associated with the third instance of the requested data comprises third version data that comprises the same version number and indicates the same API as the first version data.

12. The server as in claim 7, wherein the first response comprising the first instance of the requested data and the second response comprising the second instance of the requested data are received in response to the multicast message on condition that a size of the requested data is less than a predetermined value.

17. The server as in claim 7, wherein:

the API is one of at least two APIs implemented by the server; and

each of the APIs supports read and write requests to the data storage system.

13. A storage node of a data storage system, the storage node comprising a processor configured, at least in part, to:

send a multicast message that requests data to a plurality of other storage nodes in the data storage system, wherein the data storage system operates without the use of permanent master storage nodes, and the multicast message includes a data identifier used to uniquely identify the requested data within the data storage system;

receive a plurality of responses to the multicast message, wherein the plurality of responses comprise a first response from a first storage node and a second response from a second storage node, the first response comprises a first instance of the requested data and an indication of first version data associated with the first instance of the requested data, and the second response comprises a second instance of the requested data and an indication of second version data associated with the second instance of the requested data;

analyze the first and second instances of the requested data to determine whether one or more of the first instance of the requested data or the second instance of the second data have met a desired integrity level;

determine that the first instance of the requested data corresponds to a correct version of the requested data based on the first version data being associated with a version of the requested data that is stored on a majority of the data storage nodes that store the requested data, wherein the first version data comprises a version number associated with the first instance of the requested data and an indication of an application programming interface (API) that last modified the first instance of the requested data; and

select the first instance of the requested data based on the first instance of the requested data being stored on a majority of the data storage nodes that store the requested data, and discarding the second instance of the requested data based on the second instance of the requested data being stored on less than a majority of the data storage nodes that store the requested data.

14. The storage node as in claim 13, wherein the plurality of responses to the multicast message further comprise a third response from a third storage node, and the third response comprises a third instance of the requested data and an indication that the first version data is associated with the third instance of the requested data.

15. The storage node as in claim 14, wherein the processor is further configured to:

determine that each of the first instance of the requested data and the third instance of the requested data each meet the desired integrity level; and

select one of the first instance of the requested data or the third instance of the requested data, wherein the selection is based on additional criteria related to conditions at the first and third storage nodes.

16. The storage node as in claim 15, wherein the conditions at the first and third storage nodes comprise one or more of load conditions, geographical position, or system age of the first and third storage nodes.

18. The storage node as in claim 14, wherein the indication that the first version data is associated with the third instance of the requested data comprises third version data that comprises the same version number and indicates the same API as the first version data.

19. The storage node as in claim 13, wherein the first response comprising the first instance of the requested data and the second response comprising the second instance of the requested data are received in response to the multicast message on condition that a size of the requested data is less than a predetermined value.