Distributed storage time synchronization based on retrieval delay

• US 9,369,526 B2
• Filed: 06/30/2014
• Issued: 06/14/2016
• Est. Priority Date: 12/29/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Resch, Jason K., Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): Herzog, Madhuri
• Application Number:
  US14/319,159
• Publication Number:
  US 20140317349A1
• Time in Patent Office: 715 Days
• Field of Search: 726 1- 4, 726/21, 726 26- 30, 713164-167, 713189-194, 707687-699, 709201-203, 709217-229
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• 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]
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A method begins with a processing module receiving a data retrieval request and obtaining a real-time indicator corresponding to when the data retrieval request was received. The method continues with the processing module determining a time-based data access policy based on the data retrieval request and the real-time indicator and accessing a plurality of dispersed storage (DS) units in accordance with the time-based data access policy to retrieve encoded data slices. The method continues with the processing module decoding the threshold number of encoded data slices in accordance with an error coding dispersal storage function when a threshold number of the encoded data slices have been retrieved.

Claims

1. A method for synchronizing arrival of data slices when retrieved from distributed storage units with different transmission delays from the distributed storage units, comprising:

determining transmission time delays from a plurality of distributed storage units that are configured to store n number of encoded data slices of a data segment by having a respective distributed storage unit store a respective one of the n encoded data slices of the data segment and in which at least a threshold number k of the n encoded data slices are needed to reconstruct the data segment, where k is less than n;

selecting, by use of a processor, a set of distributed storage units based on the transmission time delays;

determining a longest transmission time delay from respective transmission time delays for the selected set of distributed storage units;

determining corresponding additional time delay value to add to the respective transmission time delays for the selected set of distributed storage units, in order to synchronize total delay for the respective ones of the selected set of distributed storage units to substantially coincide with the longest transmission time delay, in order for the encoded data slices from the selected set of distributed storage units to arrive at a destination substantially at a same time; and

transmitting corresponding additional time delay values to the selected set of distributed storage units along with a retrieval command, in which the corresponding additional time delay values are to be utilized at the selected set of distributed storage units to delay sending respective encoded data slices at the selected set of distributed storage units for an additional time period determined by the corresponding additional time delay value.

2. The method of claim 1, wherein when selecting the set of distributed storage units, all of the plurality of distributed storage units are selected as the selected set of distributed storage units.

3. The method of claim 1, wherein when selecting the set of distributed storage units, a subset of the plurality of distributed storage units is selected as the selected set of distributed storage units.

4. The method of claim 1, wherein when selecting the set of distributed storage units, a subset of the plurality of distributed storage units is selected as the selected set of distributed storage units and the subset is selected based on shortest transmission time delays.

5. The method of claim 1, wherein when selecting the set of distributed storage units, k number of distributed storage units are selected as the selected set of distributed storage units.

6. The method of claim 1, wherein when selecting the set of distributed storage units, k number of distributed storage units are selected as the selected set of distributed storage units and the k number of distributed storage units are selected based on shortest transmission time delays.

7. The method of claim 1, wherein when transmitting the corresponding additional time delay values to the selected set of distributed storage units, a timer is to be used at the selected set of distributed storage units, in which the timer is initiated with the retrieval command and expires at an end of a time period determined by the corresponding additional time delay value, in order to transmit the encoded data slices from respective distributed storage units.

8. A method for synchronizing arrival of data slices when retrieved from distributed storage units with different transmission delays from the distributed storage units, comprising:

determining transmission time delays from a plurality of distributed storage units to a processing unit, having a processor, in which the plurality of distributed storage units are configured to store n number of encoded data slices of a data segment by having a respective distributed storage unit store a respective one of the n encoded data slices of the data segment and in which at least a threshold number k of the n encoded data slices are needed to reconstruct the data segment, where k is less than n;

selecting, by use of the processor, a set of distributed storage units based on the transmission time delays;

determining a longest transmission time delay from respective transmission time delays for the selected set of distributed storage units;

determining corresponding additional time delay value to add to the respective transmission time delays for the selected set of distributed storage units, in order to synchronize total delay for the respective ones of the selected set of distributed storage units to substantially coincide with the longest transmission time delay in order for the encoded data slices from the selected set of distributed storage units to arrive at the processing unit substantially at a same time; and

transmitting, from the processing unit, corresponding additional time delay values to the selected set of distributed storage units along with a retrieval command, in which the corresponding additional time delay values are to be utilized at the selected set of distributed storage units to delay sending respective encoded data slices from the selected set of distributed storage units for an additional time period determined by the corresponding additional time delay value.

9. The method of claim 8, wherein when selecting the set of distributed storage units, all of the plurality of distributed storage units are selected as the selected set of distributed storage units.

10. The method of claim 8, wherein when selecting the set of distributed storage units, a subset of the plurality of distributed storage units is selected as the selected set of distributed storage units.

11. The method of claim 8, wherein when selecting the set of distributed storage units, a subset of the plurality of distributed storage units is selected as the selected set of distributed storage units and the subset is selected based on shortest transmission time delays.

12. The method of claim 8, wherein when selecting the set of distributed storage units, k number of distributed storage units are selected as the selected set of distributed storage units.

13. The method of claim 8, wherein when selecting the set of distributed storage units, k number of distributed storage units are selected as the selected set of distributed storage units and the k number of distributed storage units are selected based on shortest transmission time delays.

14. The method of claim 8, wherein when transmitting the corresponding additional time delay values to the selected set of distributed storage units, a timer is to be used at the selected set of distributed storage units, in which the timer is initiated with the retrieval command and expires at an end of a time period determined by the corresponding additional time delay value, in order to transmit the encoded data slices from respective distributed storage units.

15. A method for synchronizing arrival of data slices when retrieved from distributed storage units with different transmission delays from the distributed storage units, comprising:

determining a first set of transmission time delays from a plurality of distributed storage units communicating with a first processing unit that has a first processor, in which the plurality of distributed storage units are configured to store n number of encoded data slices of a data segment, by having a respective distributed storage unit store a respective one of the n encoded data slices of the data segment, and in which at least a threshold number k of the n encoded data slices are needed to reconstruct the data segment, where k is less than n, and the first set of transmission time delays pertain to transmitting the n encoded slices from the plurality of distributed storage units to the first processing unit;

communicating between the first processing unit and a second processing unit, which has a second processor, to receive at the first processing unit a second set of transmission time delays from the second processing unit, in which the second processing unit is also configured to receive the stored n encoded data slices from the plurality of distributed storage units and the second set of transmission time delays pertain to transmitting the n encoded slices from the plurality of distributed storage units to the second processing unit;

selecting a set of distributed storage units based on the first set and second set of transmission time delays;

determining a longest transmission time delay from respective transmission time delays for the selected set of distributed storage units;

determining corresponding additional time delay value to add to the respective first and second sets of transmission time delays for the selected set of distributed storage units, in order to synchronize total delay for the respective ones of the selected set of distributed storage units to substantially coincide with the longest transmission time delay, in order for the encoded data slices from the selected set of distributed storage units to arrive at the first and second processing units substantially at a same time; and

communicating the corresponding additional time delay value to the second processing unit from the first processing unit in order to time manage transmission of the n encoded data slices from the plurality of distributed storage units to the first and second processing units, but in which the selected set of distributed storage units delay transmission by a time period determined by the corresponding additional time delay values to synchronize arrival of the encoded slices from the selected set of distributed storage units at the first and second processing units substantially at a same time.

16. The method of claim 15, wherein when selecting the set of distributed storage units, all of the plurality of distributed storage units are selected as the selected set of distributed storage units.

17. The method of claim 15, wherein when selecting the set of distributed storage units, a subset of the plurality of distributed storage units is selected as the selected set of distributed storage units.

18. The method of claim 15, wherein when selecting the set of distributed storage units, a subset of the plurality of distributed storage units is selected as the selected set of distributed storage units and the subset is selected based on shortest transmission time delays.

19. The method of claim 15, wherein when selecting the set of distributed storage units, k number of distributed storage units are selected as the selected set of distributed storage units.

20. The method of claim 15, wherein when selecting the set of distributed storage units, k number of distributed storage units are selected as the selected set of distributed storage units and the k number of distributed storage units are selected based on shortest transmission time delays.