Robust transmission of data utilizing encoded data slices

• US 10,042,705 B2
• Filed: 11/09/2016
• Issued: 08/07/2018
• 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 H
• Application Number:
  US15/347,605
• Publication Number:
  US 20170060675A1
• Time in Patent Office: 636 Days
• Field of Search: 707693
• 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 includes receiving a random order of encoded data slices, and de-randomizing the random order of encoded data slices to produce a plurality of sets of a transmit number of encoded data slices. The method further includes dividing the plurality of sets of transmit number of encoded data slices into collections of sets of the transmit number of encoded data slices. For a collection of sets of transmit number of encoded data slices of the collections of sets of the transmit number of encoded data slices, the method further includes concurrently decoding the sets of the transmit number of encoded data slices of the collection of sets of transmit number of encoded data slices to produce a collection of data segments and combining the collection of data segments into the one or more data partitions. The method further includes combining the plurality of data partitions into the data object.

Claims

1. A method for execution by a computing device of a dispersed storage network (DSN), the method comprises:

receiving a random order of encoded data slices;

de-randomizing the random order of encoded data slices to produce a plurality of sets of a transmit number of encoded data slices, wherein the transmit number is within a range of a decode threshold number and a total number;

dividing the plurality of sets of transmit number of encoded data slices into collections of sets of the transmit number of encoded data slices;

for a collection of sets of transmit number of encoded data slices of the collections of sets of the transmit number of encoded data slices;

concurrently decoding, in accordance with a dispersed storage error encoding function, the sets of the transmit number of encoded data slices of the collection of sets of transmit number of encoded data slices to produce a collection of data segments, wherein the collection of data segments includes one or more data segments of a plurality of data segments from one or more data partitions of a plurality of data partitions of a data object; and

combining the collection of data segments into the one or more data partitions; and

combining the plurality of data partitions into the data object.

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:

receiving an encoded data slice error rate that indicates a number of consecutive encoded data slices of the random order of encoded data slices that can be lost without compromising the concurrently decoding of the sets of the transmit number of encoded data slices for the collection of the sets of transmit number of encoded data slices; and

when the encoded data slice error rate has been exceeded, sending a request to increase the transmit number.

4. The method of claim 1 further comprises:

receiving an encoded data slice error rate that indicates a number of consecutive encoded data slices of the random order of encoded data slices that can be lost without compromising the concurrent decoding of the sets of the transmit number of encoded data slices for the collection of sets of transmit number of encoded data slices; and

when, from collection of sets of transmit number of encoded data slices to collection of sets of transmit number of encoded data slices, the number of consecutive encoded data slices of the random order of encoded data slices that are lost is less than the encoded data slice error rate, sending a request to decrease the transmit number.

5. The method of claim 1 further comprises:

receiving, in an order corresponding to the randomized ordering, a plurality of sets of slice names with the random order of encoded data slices, wherein a plurality of sets of slices names is generated for a plurality of sets of encoded data slices of the collection of data segments.

6. The method of claim 1 further comprises:

while decoding a set of the transmit number of encoded data slices of the collection of sets of transmit number of encoded data slices, determining that a decoded threshold number of encoded data slices of the transmit number of encoded data slices is not received; and

when determined that the decoded threshold number of encoded data slices of the transmit number of encoded data slices is not received, requesting another encoded data slices of remaining encoded data slices of a set of encoded data slices from which the set of the transmit number of encoded data slices was derived.

7. The method of claim 1 further comprises:

while decoding a set of the transmit number of encoded data slices of the collection of sets of transmit number of encoded data slices, determining that a decoded threshold number of encoded data slices of the set of the transmit number of encoded data slices have been received prior to receiving all encoded data slices of the set of the transmit number of encoded data slices; and

when determined that decoded threshold number of encoded data slices of the set of the transmit number of encoded data slices have been received prior to receiving all encoded data slices of the set of the transmit number of encoded data slices, sending a message indicating that remaining encoded data slices of the set of transmit number of encoded data slices are not to be transmitted to the computing device.

8. A computing device of a dispersed storage network (DSN), the computing device comprises:

an interface;

memory; and

a processing module operably coupled to the memory and the interface, wherein the processing module is operable to;

receive a random order of encoded data slices;

de-randomize the random order of encoded data slices to produce a plurality of sets of a transmit number of encoded data slices, wherein the transmit number is within a range of a decode threshold number and a total number;

divide the plurality of sets of transmit number of encoded data slices into collections of sets of the transmit number of encoded data slices;

for a collection of sets of transmit number of encoded data slices of the collections of sets of the transmit number of encoded data slices;

concurrently decode, in accordance with a dispersed storage error encoding function, the sets of the transmit number of encoded data slices of the collection of sets of transmit number of encoded data slices to produce a collection of data segments, wherein the collection of data segments includes one or more data segments of a plurality of data segments from one or more data partitions of a plurality of data partitions of a data object; and

combine the collection of data segments into the one or more data partitions; and

combine the plurality of data partitions into the data object.

9. The computing device 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 computing device of claim 8, wherein the processing module is further operable to:

receive an encoded data slice error rate that indicates a number of consecutive encoded data slices of the random order of encoded data slices that can be lost without compromising the concurrently decoding of the sets of the transmit number of encoded data slices for the collection of the sets of transmit number of encoded data slices; and

when the encoded data slice error rate has been exceeded, send a request to increase the transmit number.

11. The computing device of claim 8, wherein the processing module is further operable to:

receive an encoded data slice error rate that indicates a number of consecutive encoded data slices of the random order of encoded data slices that can be lost without compromising the concurrent decoding of the sets of the transmit number of encoded data slices for the collection of sets of transmit number of encoded data slices; and

when, from collection of sets of transmit number of encoded data slices to collection of sets of transmit number of encoded data slices, the number of consecutive encoded data slices of the random order of encoded data slices that are lost is less than the encoded data slice error rate, send a request to decrease the transmit number.

12. The computing device of claim 8, wherein the processing module is further operable to:

receive, in an order corresponding to the randomized ordering, a plurality of sets of slice names with the random order of encoded data slices, wherein a plurality of sets of slices names is generated for a plurality of sets of encoded data slices of the collection of data segments.

13. The computing device of claim 8, wherein the processing module is further operable to:

while decoding a set of the transmit number of encoded data slices of the collection of sets of transmit number of encoded data slices, determine that a decoded threshold number of encoded data slices of the transmit number of encoded data slices is not received; and

when determined that the decoded threshold number of encoded data slices of the transmit number of encoded data slices is not received, request another encoded data slices of remaining encoded data slices of a set of encoded data slices from which the set of the transmit number of encoded data slices was derived.

14. The computing device of claim 8, wherein the processing module is further operable to:

while decoding a set of the transmit number of encoded data slices of the collection of sets of transmit number of encoded data slices, determine that a decoded threshold number of encoded data slices of the set of the transmit number of encoded data slices have been received prior to receiving all encoded data slices of the set of the transmit number of encoded data slices; and

when determined that decoded threshold number of encoded data slices of the set of the transmit number of encoded data slices have been received prior to receiving all encoded data slices of the set of the transmit number of encoded data slices, send a message indicating that remaining encoded data slices of the set of transmit number of encoded data slices are not to be transmitted to the computing device.