Decoding data streams in a distributed storage network

• US 10,235,237 B2
• Filed: 06/21/2017
• Issued: 03/19/2019
• Est. Priority Date: 09/06/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): Rizk, Samir W
• Application Number:
  US15/629,134
• Publication Number:
  US 20170286212A1
• Time in Patent Office: 636 Days
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• 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/24568 Data stream processing; Continuous queries
• CPC Class Codes: H03M 13/1148 Structural properties of the code parity-check or generator matrix
• CPC Class Codes: H03M 13/1505 Golay Codes
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
• 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: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 65/765 intermediate

Abstract

A method begins by a dispersed storage (DS) processing module receiving one or more pairs of coded values and continues with the DS processing module creating a received coded matrix from the one or more pairs of coded values, followed by the generation of a data matrix. When a decode threshold number of pairs of coded values are included in a first plurality of data blocks corresponding to a data stream from the data matrix and the decode threshold number of pairs of coded values are determined to be valid, the decode threshold number of pairs of coded values are decoded. The method continues with the generation of a second data matrix and the data stream is extracted from the second data matrix.

Claims

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

receiving, by the computing device, one or more pairs of coded values, wherein a pair of coded values of the one or more pairs of coded values includes a coded value corresponding to one of a first plurality of data segments and a coded value corresponding to the one of a second plurality of data segments and wherein each of a first data stream and a second data stream are segmented to produce the first plurality of data segments corresponding to the first data stream and the second plurality of data segments corresponding to the second data stream;

creating, by a processing module of the one or more processing modules, a received coded matrix from the one or more pairs of coded values;

generating, by the processing module, a first data matrix from the received coded matrix and an encoding matrix;

identifying, by the processing module, a first plurality of data blocks of the first data matrix that correspond to the first data stream;

determining, by the processing module, whether the first plurality of data blocks includes a decode threshold number of pairs of coded values; and

when the first plurality of data blocks includes a decode threshold number of pairs of coded values, determining whether the decode threshold number of pairs of coded values are valid;

decoding, by the processing module, the decode threshold number of pairs of coded values;

generating, by the processing module, a second data matrix; and

extracting, by the processing module, the first data stream from the second data matrix.

2. The method of claim 1 further comprises:

identifying a second plurality of data blocks of the first data matrix that correspond to the second data stream;

determining whether the second plurality of data blocks includes a decode threshold number of pairs of coded values; and

when the second plurality of data blocks includes a decode threshold number of pairs of coded values, determining whether the decode threshold number of pairs of coded values are valid;

decoding the decode threshold number of pairs of coded values to

generating a third data matrix; and

extracting the second data stream from the third data matrix.

3. The method of claim 1, wherein the identifying a first plurality of data blocks of the first data matrix that correspond to the first data stream is based on at least one of an encoding scheme, a decoding scheme, a number of data streams, a desired data stream indicator, a data stream position indicator, and a message.

4. The method of claim 1, wherein the first data matrix is an encoded data slice matrix.

5. The method of claim 4, wherein the second data matrix is at least a portion of an encoded data slice matrix.

6. The method of claim 1 further comprises:

generating a fourth matrix before extracting the first data stream from the second data matrix, wherein the fourth matrix is based on at least a portion of the second matrix.

7. The method of claim 1, wherein the determining whether the decode threshold number of pairs of coded values are valid is based on whether a value calculated from a decoded data selection associated with the first data block compares favorably to a received value for the first data block.

8. A computing device comprises:

a network interface;

memory; and

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

receive one or more pairs of coded values, wherein a pair of coded values of the one or more pairs of coded values includes a coded value corresponding to one of a first plurality of data segments and a coded value corresponding to the one of a second plurality of data segments and wherein each of a first data stream and a second data stream are segmented to produce the first plurality of data segments corresponding to the first data stream and the second plurality of data segments corresponding to the second data stream;

create a received coded matrix from the one or more pairs of coded values;

generate a first data matrix from the received coded matrix and an encoding matrix;

identify a first plurality of data blocks of the first data matrix that correspond to the first data stream;

determine whether the first plurality of data blocks includes a decode threshold number of pairs of coded values; and

when the first plurality of data blocks includes a decode threshold number of pairs of coded values, determine whether the decode threshold number of pairs of coded values are valid;

decode the decode threshold number of pairs of coded values;

generate a second data matrix; and

extract the first data stream from the second data matrix.

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

identify a second plurality of data blocks of the first data matrix that correspond to the second data stream;

determine whether the second plurality of data blocks includes a decode threshold number of pairs of coded values; and

when the second plurality of data blocks includes a decode threshold number of pairs of coded values, determine whether the decode threshold number of pairs of coded values are valid;

decode the decode threshold number of pairs of coded values to

generate a third data matrix; and

extract the second data stream from the third data matrix.

10. The computing device of claim 8, wherein the first plurality of data blocks of the first data matrix that correspond to the first data stream is identified based on at least one of an encoding scheme, a decoding scheme, a number of data streams, a desired data stream indicator, a data stream position indicator, and a message.

11. The computing device of claim 10 further comprises:

generate a fourth matrix before extracting the first data stream from the second data matrix, wherein the fourth matrix is based on at least a portion of the second matrix.

12. The computing device of claim 8, wherein, the first data matrix is an encoded data slice matrix.

13. The computing device of claim 8, wherein the second data matrix is at least a portion of an encoded data slice matrix.

14. The computing device of claim 8, wherein the determine whether the decode threshold number of pairs of coded values are valid is based on whether a value calculated from a decoded data selection associated with the first data block compares favorably to a received value for the first data block.

15. A non-transitory computer readable storage device comprises:

a first memory section that stores operational instruction that, when executed by a computing device, causes the computing device to;

receive one or more pairs of coded values, wherein a pair of coded values of the one or more pairs of coded values includes a coded value corresponding to one of a first plurality of data segments and a coded value corresponding to the one of a second plurality of data segments and wherein each of a first data stream and a second data stream are segmented to produce the first plurality of data segments corresponding to the first data stream and the second plurality of data segments corresponding to the second data stream;

a second memory section that stores operational instruction that, when executed by the computing device, causes the computing device to;

create a received coded matrix from the one or more pairs of coded values; and

generate a first data matrix from the received coded matrix and an encoding matrix;

a third memory section that stores operational instruction that, when executed by the computing device, causes the computing device to;

identify a first plurality of data blocks of the first data matrix that correspond to the first data stream;

determine whether the first plurality of data blocks includes a decode threshold number of pairs of coded values; and

when the first plurality of data blocks includes a decode threshold number of pairs of coded values, determine whether the decode threshold number of pairs of coded values are valid;

decode the decode threshold number of pairs of coded values;

generate a second data matrix; and

extract the first data stream from the second data matrix.

16. The non-transitory computer readable storage device of claim 15, wherein the third memory section further stores operational instruction that, when executed by the computing device, causes the computing device to:

identify a second plurality of data blocks of the first data matrix that correspond to the second data stream;

determine whether the second plurality of data blocks includes a decode threshold number of pairs of coded values; and

when the second plurality of data blocks includes a decode threshold number of pairs of coded values, determine whether the decode threshold number of pairs of coded values are valid;

decode the decode threshold number of pairs of coded values to

generate a third data matrix; and

extract the second data stream from the third data matrix.

17. The non-transitory computer readable storage device of claim 15, wherein the third memory section further stores operational instruction that, when executed by the computing device, causes the computing device to:

generate the first data matrix based on at least one of an encoding scheme, a decoding scheme, a number of data streams, a desired data stream indicator, a data stream position indicator, and a message.

18. The non-transitory computer readable storage device of claim 15, wherein the third memory section further stores operational instruction that, when executed by the computing device, causes the computing device to:

generate a fourth matrix before extracting the first data stream from the second data matrix, wherein the fourth matrix is based on at least a portion of the second matrix.

19. The non-transitory computer readable storage device of claim 15, wherein the third memory section further stores operational instruction that, when executed by the computing device, causes the computing device to:

determine whether the decode threshold number of pairs of coded values are valid based on whether a value calculated from a decoded data selection associated with the first data block compares favorably to a received value for the first data block.