Robust transmission of data utilizing encoded data slices

• US 9,503,513 B2
• Filed: 08/05/2013
• Issued: 11/22/2016
• Est. Priority Date: 10/08/2012
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Alnafoosi, Ahmad, Resch, Jason K.
• Primary Examiner(s): Dwivedi, Mahesh
• Application Number:
  US13/959,077
• Publication Number:
  US 20140101116A1
• Time in Patent Office: 1,205 Days
• Field of Search: 707/693
• 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 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 concurrently encoding a collection of data segments to produce sets of encoded data slices, where each set includes a total number of encoded data slices and where a decode threshold number of encoded data slices is required to recover a corresponding data segment. The method continues with the processing module determining a transmit number to be initially greater than the decode threshold number and less than the total number. The method continues with the processing module selecting a transmit number of encoded data slices from each set of encoded data slices to produce sets of transmit encoded data slices. The method continues with the processing module randomizing ordering of the sets of transmit encoded data slices to produce a random order of encoded data slices and transmitting encoded data slices of the random order of encoded data slices.

Claims

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

dividing the data for transmission into a plurality of data partitions, wherein a data partition includes a plurality of data segments; and

for a collection of data segments that includes one or more data segments of the plurality of data segments from one or more of the plurality of data partitions;

concurrently encoding the collection of data segments in accordance with a dispersed storage error encoding function to produce a plurality of sets of encoded data slices, wherein a set of encoded data slices of the plurality of sets of encoded data slices includes a total number of encoded data slices and corresponds to a data segment of the collection of data segments and wherein a decode threshold number of encoded data slices of the set of encoded data slices is required to recover the corresponding data segment;

determining a transmit number to be initially greater than the decode threshold number and less than the total number;

selecting a transmit number of encoded data slices from each of the plurality of sets of encoded data slices to produce a plurality of sets of transmit encoded data slices;

randomizing ordering of the plurality of sets of transmit encoded data slices to produce a random order of encoded data slices; and

transmitting encoded data slices of the random order of encoded data slices, wherein an encoded data slice error rate corresponds to a number of data segments per data partition and the transmit number minus the decode threshold.

2. The method of claim 1, wherein the collection of data segments comprises one of:

the plurality of data segments of one of the plurality of data partitions;

first data segments of the plurality of data segments of a given number of data partitions of the plurality of data partitions;

second data segments of the plurality of data segments of the given number of data partitions; and

a data segment of a given number of data segments of the plurality of data segments of the given number of data partitions.

3. The method of claim 1 further comprises:

coordinating with a recipient regarding the dispersed storage error encoding function;

sending an indication of the transmit number to the recipient;

generating a plurality of sets of slices names for the plurality of sets of encoded data slices, wherein a slice name of the plurality of sets of slice names uniquely identifies an encoded data slice to a particular data segment of the collection of data segments; and

sending, in an order corresponding to the randomized ordering, the plurality of sets of slice names with the random order of encoded data slices.

4. The method of claim 1 further comprises:

receiving feedback from a recipient of the transmitted encoded data slices;

interpreting the feedback to determine whether an adjustment should be made regarding the robust transmission; and

when the adjustment should be made, determining at least one of;

an increase in the number of data segments per data partition;

a decrease in the number of data segments per data partition;

an increase to the transmit number; and

a decrease to the transmit number.

5. The method of claim 1 further comprises:

receiving feedback from a recipient of the transmitted encoded data slices;

interpreting the feedback to determine, for a data segment of the collection of data segments, that at least one more encoded data slice of the set of encoded data slices of the data segment is to be transmitted to the recipient such that the recipient has the decode threshold number of encoded data slices to recover the data segment;

identifying the at least one more encoded data slice from a remaining subset of encoded data slices corresponding to the encoded data slices between the transmit number and the total number; and

interrupting the transmitting of the encoded data slices of the random order of encoded data slices to send the at least one more encoded data slice.

6. The method of claim 1 further comprises:

receiving, from a recipient, feedback regarding accurate receipt of encoded data slices corresponding to the data segment of the collection of data segments;

interpreting the feedback to determine, for the data segment, whether the recipient has received the decode threshold number of encoded data slices for the data segment and whether at least one encoded data slice of the transmit number of encoded data slices for the data segment remain to be transmitted; and

when the recipient has received the decode threshold number of encoded data slices for the data segment and the at least one encoded data slice of the transmit number of encoded data slices remains to be transmitted, removing the at least one encoded data slice from the random order of encoded data slices.

7. The method of claim 1 further comprises:

receiving, from a recipient, feedback regarding accurate receipt of encoded data slices corresponding to the data segment of the collection of data segments;

interpreting the feedback to determine, for the data segment, whether the recipient will receive the decode threshold number of encoded data slices for the data segment based on a remaining number of encoded data slices of the transmit number of encoded data slices for the data segment that have not been transmitted;

when the recipient will not receive the decode threshold number of encoded data slices for the data segment based on the remaining number of encoded data slices of the transmit number of encoded data slices for the data segment, identifying at least one more encoded data slice from a remaining subset of encoded data slices corresponding to the encoded data slices between the transmit number and the total number; and

adding the at least one more encoded data slice to the random order of encoded data slices.

8. A data slice layer transmit module comprises:

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

divide data for transmission into a plurality of data partitions, wherein a data partition includes a plurality of data segments;

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

for a collection of data segments that includes one or more data segments of the plurality of data segments from one or more of the plurality of data partitions;

concurrently encode the collection of data segments in accordance with a dispersed storage error encoding function to produce a plurality of sets of encoded data slices, wherein a set of encoded data slices of the plurality of sets of encoded data slices includes a total number of encoded data slices and corresponds to a data segment of the collection of data segments and wherein a decode threshold number of encoded data slices of the set of encoded data slices is required to recover the corresponding data segment;

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

determine a transmit number to be initially greater than the decode threshold number and less than the total number;

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

select a transmit number of encoded data slices from each of the plurality of sets of encoded data slices to produce a plurality of sets of transmit encoded data slices;

randomizing ordering of the plurality of sets of transmit encoded data slices to produce a random order of encoded data slices; and

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

transmit encoded data slices of the random order of encoded data slices, wherein an encoded data slice error rate corresponds to a number of data segments per data partition and the transmit number minus the decode threshold.

9. The data slice layer transmit module of claim 8, wherein the collection of data segments comprises one of:

the plurality of data segments of one of the plurality of data partitions;

first data segments of the plurality of data segments of a given number of data partitions of the plurality of data partitions;

second data segments of the plurality of data segments of the given number of data partitions; and

a data segment of a given number of data segments of the plurality of data segments of the given number of data partitions.

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

the processing module further functions to;

coordinate with a recipient regarding the dispersed storage error encoding function; and

send an indication of the transmit number to the recipient;

the one or more encoding modules further functions to;

generate a plurality of sets of slices names for the plurality of sets of encoded data slices, wherein a slice name of the plurality of sets of slice names uniquely identifies an encoded data slice to a particular data segment of the collection of data segments; and

the transmit buffer module further functions to;

send, in an order corresponding to the randomized ordering, the plurality of sets of slice names with the random order of encoded data slices.

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

the processing module further functions to;

receive feedback from a recipient of the transmitted encoded data slices;

interpret the feedback to determine whether an adjustment should be made regarding the transmission; and

when the adjustment should be made, determine at least one of;

an increase in the number of data segments per data partition;

a decrease in the number of data segments per data partition;

an increase to the transmit number; and

a decrease to the transmit number.

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

the processing module further functions to;

receive feedback from a recipient of the transmitted encoded data slices;

interpret the feedback to determine, for the data segment of the collection of data segments, that at least one more encoded data slice of the set of encoded data slices of the data segment is to be transmitted to the recipient such that the recipient has the decode threshold number of encoded data slices to recover the data segment;

identify the at least one more encoded data slice from a remaining subset of encoded data slices corresponding to the encoded data slices between the transmit number and the total number; and

interrupt the transmitting of the encoded data slices of the random order of encoded data slices to send the at least one more encoded data slice.

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

the processing module further functions to;

receive, from a recipient, feedback regarding accurate receipt of encoded data slices corresponding to the data segment of the collection of data segments;

interpret the feedback to determine, for the data segment, whether the recipient has received the decode threshold number of encoded data slices for the data segment and whether at least one encoded data slice of the transmit number of encoded data slices for the data segment remain to be transmitted; and

when the recipient has received the decode threshold number of encoded data slices for the data segment and the at least one encoded data slice of the transmit number of encoded data slices remains to be transmitted, remove the at least one encoded data slice from the random order of encoded data slices.

14. The data slice layer transmit module of claim 8 further comprises:

the processing module further functions to;

receive, from a recipient, feedback regarding accurate receipt of encoded data slices corresponding to the data segment of the collection of data segments;

interpret the feedback to determine, for the data segment, whether the recipient will receive the decode threshold number of encoded data slices for the data segment based on a remaining number of encoded data slices of the transmit number of encoded data slices for the data segment that have not been transmitted;

when the recipient will not receive the decode threshold number of encoded data slices for the data segment based on the remaining number of encoded data slices of the transmit number of encoded data slices for the data segment, identify at least one more encoded data slice from a remaining subset of encoded data slices corresponding to the encoded data slices between the transmit number and the total number; and

add the at least one more encoded data slice to the random order of encoded data slices.