Data transmission utilizing partitioning and dispersed storage error encoding

• US 9,112,535 B2
• Filed: 10/03/2011
• Issued: 08/18/2015
• Est. Priority Date: 10/06/2010
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Gladwin, S. Christopher
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US13/251,566
• Publication Number:
  US 20120089889A1
• Time in Patent Office: 1,415 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1028 Adjacent errors, e.g. error in n-bit (n>1) wide storage units, i.e. package error
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 45/24 Multipath

Abstract

A method begins by a first device obtaining data for transmission to a second device and partitioning the data to produce a plurality of data portions. The method continues with the first device dispersed storage error encoding the plurality of data portions using a plurality of sets of error coding dispersal storage function parameters to produce a plurality of sets of encoded data slices and transmitting the plurality of sets of encoded data slices to the second device via a network. The method continues with a second device receiving at least a decode threshold number of encoded data slices and dispersed storage error decoding the at least a decode threshold number of encoded data slices to produce a decoded data portion for each set of the plurality of sets of encoded data slices. The method continues with the second device recapturing the data from a plurality of decoded data portions.

Claims

1. A method comprises:

obtaining, by a first device, data for transmission to a second device;

partitioning, by the first device, the data in accordance with a data partitioning scheme to produce a plurality of data portions;

dispersed storage error encoding, by the first device, the plurality of data portions using a plurality of sets of error coding dispersal storage function parameters to produce a plurality of sets of encoded data slices, wherein a first set of error coding dispersal storage function parameters includes a first decode threshold number and a first total number and a second set of error coding dispersal storage function parameters includes a second decode threshold number and a second total number;

transmitting, by the first device, the plurality of sets of encoded data slices to the second device via a network;

for each set of the plurality of sets of encoded data slices;

receiving, by the second device, at least a decode threshold number of encoded data slices of the set of encoded data slices in accordance with a corresponding one of the plurality of sets of error coding dispersal storage function parameters, wherein the decode threshold number is less than a total number of encoded data slices in the set of encoded data slices and is a minimum number of encoded data slices needed to recover the corresponding data portion;

determining whether an encoded data slice of the at least a decode threshold number of encoded data slices includes a bit error;

when the encoded data slice includes the bit error, discarding the encoded data slice from the at least a decode threshold number of encoded data slices to produce an updated set of encoded data slices;

determining whether the updated set of encoded data slices includes at least a decodable number of encoded data slices;

when the updated set of encoded data slices includes at least a decodable number of encoded data slices, dispersed storage error decoding the at least a decode threshold number of encoded data slices including dispersed storage error decoding the updated set of encoded data slices; and

when the updated set of encoded data slices does not includes at least a decodable number of encoded data slices, utilizing data filler for the corresponding data portion; and

when the encoded data slice does not include the bit error, dispersed storage error decoding, by the second device, the at least a decode threshold number of encoded data slices using the corresponding one of the plurality of sets of error coding dispersal storage function parameters to produce a decoded data portion; and

recapturing, by the second device, the data from a plurality of decoded data portions in accordance with the data partitioning scheme.

2. The method of claim 1 further comprises:

providing, by the first device, an indication of the data partitioning scheme and the plurality of sets of error coding dispersal storage function parameters to the second device.

3. The method of claim 1 further comprises at least one of:

selecting, by the first device, the data partitioning scheme by determining a data characterization based on at least one of a data analysis, received data characterization information, a predetermination, a message, a look up, and a comparison of the data to other characterized data; and

selecting, by the first device, the data partitioning scheme based on at least one of the data characterization, a lookup, a partitioning policy, a predetermination, a message, and a previous data partitioning approach.

4. The method of claim 1, wherein the partitioning the data comprises:

partitioning the data into a first data portion and a second data portion, wherein the first data portion includes higher priority content of the data than the second data portion.

5. The method of claim 1 further comprises at least one of:

selecting, by the first device, the plurality of sets of error coding dispersal storage function parameters by determining a data characterization based on at least one of a data analysis, received data characterization information, a predetermination, a message, a look up, a comparison of the data to other characterized data, and the data partitioning approach; and

selecting, by the first device, the plurality of sets of error coding dispersal storage function parameters based on at least one of the data characterization, the data partitioning approach, a reliability requirement, a performance requirement, a lookup, a data encoding policy, a predetermination, a message, and a previous data encoding approach.

6. A method for receiving data, wherein the data has been encoded into a plurality of sets of encoded data slices using a plurality of sets of error coding dispersal storage function parameters and a data partitioning scheme, the method comprises:

for each set of the plurality of sets of encoded data slices;

receiving, via a network, at least a decode threshold number of encoded data slices of the set of encoded data slices in accordance with a corresponding one of the plurality of sets of error coding dispersal storage function parameters, wherein the decode threshold number is less than a total number of encoded data slices in the set of encoded data slices and is a minimum number of encoded data slices needed to recover the corresponding data portion;

determining whether an encoded data slice of the at least a decode threshold number of encoded data slices includes a bit error;

when the encoded data slice includes the bit error, discarding the encoded data slice from the at least a decode threshold number of encoded data slices to produce an updated set of encoded data slices;

determining whether the updated set of encoded data slices includes at least a decodable number of encoded data slices;

when the updated set of encoded data slices includes at least a decodable number of encoded data slices, dispersed storage error decoding the at least a decode threshold number of encoded data slices including dispersed storage error decoding the updated set of encoded data slices; and

when the updated set of encoded data slices does not includes at least a decodable number of encoded data slices, utilizing data filler for the corresponding data portion; and

when the encoded data slice does not include the bit error, dispersed storage error decoding the at least a decode threshold number of encoded data slices using the corresponding one of the plurality of sets of error coding dispersal storage function parameters to produce a decoded data portion; and

recapturing the data from a plurality of decoded data portions in accordance with the data partitioning scheme.

7. The method of claim 6 further comprises:

receiving an indication of the data partitioning scheme and the plurality of sets of error coding dispersal storage function parameters from a transmitting entity.

8. A computer comprises:

an interface;

a memory; and

a processing module operable to;

for each set of a plurality of sets of encoded data slices, wherein data has been encoded into the plurality of sets of encoded data slices using a plurality of sets of error coding dispersal storage function parameters and a data partitioning scheme;

receive, via the interface, at least a decode threshold number of encoded data slices of the set of encoded data slices in accordance with a corresponding one of the plurality of sets of error coding dispersal storage function parameters, wherein the decode threshold number is less than a total number of encoded data slices in the set of encoded data slices and is a minimum number of encoded data slices needed to recover the corresponding data portion;

determine whether an encoded data slice of the at least a decode threshold number of encoded data slices includes a bit error;

when the encoded data slice includes the bit error, discarding the encoded data slice from the at least a decode threshold number of encoded data slices to produce an updated set of encoded data slices;

determine whether the updated set of encoded data slices includes at least a decodable number of encoded data slices;

when the updated set of encoded data slices includes at least a decodable number of encoded data slices, dispersed storage error decode the at least a decode threshold number of encoded data slices including dispersed storage error decoding the updated set of encoded data slices; and

when the updated set of encoded data slices does not includes at least a decodable number of encoded data slices, utilize data filler for the corresponding data portion; and

when the encoded data slice does not include the bit error, dispersed storage error decode the at least a decode threshold number of encoded data slices using the corresponding one of the plurality of sets of error coding dispersal storage function parameters to produce a decoded data portion; and

recapture the data from a plurality of decoded data portions in accordance with the data partitioning scheme.

9. The computer of claim 8, wherein the processing module further functions to:

receive, via the interface, an indication of the data partitioning scheme and the plurality of sets of error coding dispersal storage function parameters from a transmitting entity.