ROBUST RECEPTION OF DATA UTILIZING ENCODED DATA SLICES

• US 20140101283A1
• Filed: 08/05/2013
• Published: 04/10/2014
• Est. Priority Date: 10/30/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K., Alnafoosi, Ahmad
• Granted Patent: US 9,667,701 B2
• Time in Patent Office: Days
• US Class Current: 709/217
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• 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
• 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 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

A method begins by a processing module receiving a random order of encoded data slices and interpreting slice names to de-randomize the encoded data slices into of sets of transmit encoded data slices. The method continues with the processing module determining whether a decode threshold number of encoded data slices of a set of transmit encoded data slices have been received. When not received, the method continues with the processing module determining whether a sufficient number of encoded data slices of the set of transmit encoded data slices are still to be received and waiting until the decode threshold number of encoded data slices are received when encoded data slices are still to be received. When the decode threshold number of encoded data slices are received, the method continues with the processing module decoding the decode threshold number of encoded data slices to recapture a corresponding data segment.

Claims

1. A method for robust reception of data by one or more processing modules of one or more computing devices, the method comprises:

receiving encoded data slices of a random order of encoded data slices, wherein each encoded data slice of the random order of encoded data slices has a unique slice name such that the random order of encoded data slices has a corresponding plurality of slice names, and wherein an encoded data slice error rate corresponds to a number of data segments per data partition and a transmit number minus a decode threshold number;

interpreting the corresponding plurality of slice names to de-randomize the random order of encoded data slices into a plurality of sets of transmit encoded data slices, wherein the plurality of sets of transmit encoded data slices corresponds to a plurality of sets encoded data slices, wherein the plurality of sets of encoded data slices is a dispersed storage error encoded version of a collection of data segments of a data portion of a plurality of data portions of the data, wherein one of the plurality of sets of transmit encoded data slices includes the transmit number of encoded data slices of a total number of encoded data slices of a corresponding one of the plurality of sets of encoded data slices; and

on a set by set basis and in accordance with a dispersed storage error encoding function;

determining whether the decode threshold number of encoded data slices of a set of transmit encoded data slices of the plurality of sets of transmit encoded data slices have been received;

when the decode threshold number of encoded data slices have not yet been received, determining whether a sufficient number of encoded data slices of the set of transmit encoded data slices are still to be received;

when the sufficient number of encoded data slices are still to be received, waiting until the decode threshold number of encoded data slices are received; and

when the decode threshold number of encoded data slices are received, decoding the decode threshold number of encoded data slices to recapture a corresponding data segment of the collection of data segments.

2. The method of claim 1, wherein the determining whether the sufficient number of encoded data slices is still to be received comprises:

identifying encoded data slices of the set of transmit encoded data slices that have been successfully received;

determining how many more encoded data slices are to be received based on the transmit number and a current order position in the receiving the random order of encoded data slices; and

when a sum of a number of encoded data slices that have been successfully received and a number of the more encoded data slices to be received is equal to or greater than the decode threshold number, indicating that the sufficient number of encoded data slices are still to be received.

3. The method of claim 1 further comprises:

when less than the sufficient number of encoded data slices are still to be received, sending a feedback message that requests one or more encoded data slices of the set of transmit encoded data slices to be transmitted.

4. The method of claim 1 further comprises:

when less than the sufficient number of encoded data slices are still to be received, sending a feedback message that includes a request for one or more encoded data slices of the set of transmit encoded data slices and slice names of encoded data slices that have been successfully received.

5. The method of claim 1 further comprises:

when the decode threshold number of encoded data slices have been received, determining whether one or more encoded data slices of the set of transmit encoded data slices are still to be received; and

when the one or more encoded data slices are still to be received, sending a feedback message requesting that the one or more encoded data slices not be sent.

6. The method of claim 1 further comprises:

recovering the plurality of data portions; and

combining the plurality of data portions to reproduce the data.

7. The method of claim 1, wherein the interpreting the corresponding plurality of slice names comprises:

interpreting, for an encoded data slice of the plurality of encoded data slices, a corresponding slice name of the corresponding plurality of slice names to identify a segment identifier that ties the encoded data slice to one of the collection of data segments, a data object identifier that ties the encoded data slice to the data, and a slice identifier that uniquely identifies the encoded data slice in the set of transmit encoded data slices.

8. A data slice layer receive module comprises:

a receive buffer module, when operable within a computing device, causes the computing device to;

receive encoded data slices of a random order of encoded data slices, wherein each encoded data slice of the random order of encoded data slices has a unique slice name such that the random order of encoded data slices has a corresponding plurality of slice names, and wherein an encoded data slice error rate corresponds to a number of data segments per data partition and a transmit number minus a decode threshold number; and

interpret the corresponding plurality of slice names to de-randomize the random order of encoded data slices into a plurality of sets of transmit encoded data slices, wherein the plurality of sets of transmit encoded data slices corresponds to a plurality of sets encoded data slices, wherein the plurality of sets of encoded data slices is a dispersed storage error encoded version of a collection of data segments of a data portion of a plurality of data portions of data, wherein one of the plurality of sets of transmit encoded data slices includes the transmit number of encoded data slices of a total number of encoded data slices of a corresponding one of the plurality of sets of encoded data slices;

a processing module, when operable within the computing device, causes the computing device to;

on a set by set basis and in accordance with a dispersed storage error encoding function;

determine whether the decode threshold number of encoded data slices of a set of transmit encoded data slices of the plurality of sets of transmit encoded data slices have been received;

when the decode threshold number of encoded data slices have not yet been received, determine whether a sufficient number of encoded data slices of the set of transmit encoded data slices are still to be received; and

when the sufficient number of encoded data slices are still to be received, wait until the decode threshold number of encoded data slices are received; and

one or more decoding modules, when operable within the computing device, causes the computing device to;

when the decode threshold number of encoded data slices are received, decode the decode threshold number of encoded data slices to recapture a corresponding data segment of the collection of data segments.

9. The data slice layer receive module of claim 8, wherein the processing module functions to determine whether the sufficient number of encoded data slices are still to be received by:

identifying encoded data slices of the set of transmit encoded data slices that have been successfully received;

determining how many more encoded data slices are to be received based on the transmit number and a current order position in the receiving the random order of encoded data slices; and

when a sum of a number of encoded data slices that have been successfully received and a number of the more encoded data slices to be received is equal to or greater than the decode threshold number, indicating that the sufficient number of encoded data slices are still to be received.

10. The data slice layer receive module of claim 8 further comprises:

the processing module further functions to;

when less than the sufficient number of encoded data slices are still to be received, send a feedback message that requests one or more encoded data slices of the set of transmit encoded data slices to be transmitted.

11. The data slice layer receive module of claim 8 further comprises:

the processing module further functions to;

when less than the sufficient number of encoded data slices are still to be received, send a feedback message that includes a request for one or more encoded data slices of the set of transmit encoded data slices and slice names of encoded data slices that have been successfully received.

12. The data slice layer receive module of claim 8 further comprises:

the processing module further functions to;

when the decode threshold number of encoded data slices have been received, determine whether one or more encoded data slices of the set of transmit encoded data slices are still to be received; and

when the one or more encoded data slices are still to be received, send a feedback message requesting that the one or more encoded data slices not be sent.

13. The data slice layer receive module of claim 8 further comprises:

a data de-segmenting and de-partitioning module, when operable within the computing device, causes the computing device to;

recover the plurality of data portions; and

combine the plurality of data portions to reproduce data.

14. The data slice layer receive module of claim 8, wherein the receive buffer module functions to interpret the corresponding plurality of slice names by:

interpreting, for an encoded data slice of the plurality of encoded data slices, a corresponding slice name of the corresponding plurality of slice names to identify a segment identifier that ties the encoded data slice to one of the collection of data segments, a data object identifier that ties the encoded data slice to the data, and a slice identifier that uniquely identifies the encoded data slice in the set of transmit encoded data slices.