Reproducing data utilizing a zero information gain function

• US 8,782,494 B2
• Filed: 09/12/2012
• Issued: 07/15/2014
• Est. Priority Date: 10/04/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): BRITT, CYNTHIA H
• Application Number:
  US13/612,043
• Publication Number:
  US 20130086451A1
• Time in Patent Office: 671 Days
• Field of Search: 714/763, 714/758, 714/770, 714/774, 714/781, 714/804
• US Class Current: 714/770
• 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/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H03M 11/08 by operating selected combinations of multifunction keys
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• 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/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• 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 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]

Abstract

A method begins by a dispersed storage (DS) processing module receiving a zero information gain (ZIG) encoded data slice and a subset of encoded data slices of a set of encoded data slices. The method continues with the DS processing module generating a set of ZIG encoded data slices using a ZIG function and corresponding ones of the subset of encoded data slices, wherein the set of ZIG encoded data slices represents additional components of recovery information of a first encoded data slice. The method continues with the DS processing module recreating the first encoded data slice from the ZIG encoded data slice and the set of ZIG encoded data slices. The method continues with the DS processing module decoding the subset of encoded data slices and the first encoded data slice using a dispersed storage error coding function to reproduce data.

Claims

1. A method for execution by a processing module of a computing device, the method comprises:

receiving a subset of encoded data slices of a set of encoded data slices, wherein a data segment of data was encoded using an encoding matrix of a dispersed storage error coding function to produce the set of encoded data slices, wherein the data segment can be recreated from a decode threshold number of encoded data slices of the set of encoded data slices using a decoding matrix of the dispersed storage error coding function, wherein the subset of encoded data slices includes less than the decode threshold number of encoded data slices of the subset of encoded data slices and does not include a first or a second encoded data slice of the set of encoded data slices;

receiving a partial encoded data slice corresponding to the first encoded data slice, wherein the partial encoded data slice is generated based on the second encoded data slice and a section of the encoding matrix that corresponds to the first encoded data slice;

generating additional partial encoded data slices corresponding to the first encoded data slice based on the subset of encoded data slices and the section of the encoding matrix that corresponds to the first encoded data slice;

recreating the first encoded data slice from the partial encoded data slice and the additional partial encoded data slices; and

decoding the subset of encoded data slices and the first encoded data slice using the decoding matrix to reproduce the data segment.

2. The method of claim 1 further comprises:

prior to recreating the first encoded data slice, de-obfuscating the partial encoded data slice utilizing an obfuscation function.

3. The method of claim 1 further comprises:

the subset of encoded data slices does not include the first, the second, or a third encoded data slice of the set of encoded data slices, wherein the partial encoded data slice is generated based on the second and third encoded data slices and the section of the encoding matrix that corresponds to the first encoded data slice;

receiving a second partial encoded data slice corresponding to the fourth encoded data slice, wherein the second partial encoded data slice is generated based on the second and the third encoded data slice and a section of the encoding matrix that corresponds to the fourth encoded data slice;

generating second additional partial encoded data slices corresponding to the fourth encoded data slice based on the subset of encoded data slices and the section of the encoding matrix that corresponds to the fourth encoded data slice;

recreating the fourth encoded data slice from the second partial encoded data slice and the second additional partial encoded data slices; and

decoding the subset of encoded data slices, the first encoded data slice, and the fourth encoded data slice using the decoding matrix to reproduce the data segment.

4. The method of claim 1, wherein generating one of the additional partial encoded data slices comprises:

generating a first decoding matrix for the first encoded data slice based on the encoding matrix;

encoding a corresponding one of the subset of encoded data slices using the first decoding matrix to produce a vector; and

encoding the vector using, as the section of the encoding matrix, a row of the encoding matrix that corresponds to the first encoded data slice to produce the one of the additional partial encoded data slices.

5. The method of claim 4, wherein the generating the decoding matrix comprises:

reducing the encoding matrix to produce a square matrix based on the first encoded data slice and the subset of encoded data slices; and

inverting the square matrix to produce the decoding matrix.

6. The method of claim 1, wherein the decoding the subset of encoded data slices and the first encoded data slice comprises:

generating a received slice matrix from the first encoded data slice and the subset of encoded data slices;

generating a data matrix based on the received slice matrix and the decoding matrix; and

creating the data segment from the data matrix.

7. The method of claim 6 further comprises:

obtaining the encoding matrix;

reducing the encoding matrix based on rows associated with the subset of encoded data slices and the first encoded data slice to produce a square matrix; and

inverting the square matrix to produce the decoding matrix.

8. The method of claim 1, wherein the recreating the first encoded data slice from the partial encoded data slice and the additional partial encoded data slices comprises one of:

exclusive ORing the partial encoded data slice and the additional partial encoded data slices to produce the first encoded data slice; and

rebuilding the first encoded data slice based on the partial encoded data slice and the additional partial encoded data slices in accordance with a dispersed storage error coding function.

9. A dispersed storage (DS) module comprises:

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

receive a subset of encoded data slices of a set of encoded data slices, wherein a data segment of data was encoded using an encoding matrix of a dispersed storage error coding function to produce the set of encoded data slices, wherein the data segment can be recreated from a decode threshold number of encoded data slices of the set of encoded data slices using a decoding matrix of the dispersed storage error coding function, wherein the subset of encoded data slices includes less than the decode threshold number of encoded data slices of the subset of encoded data slices and does not include a first or a second encoded data slice of the set of encoded data slices; and

receive a partial encoded data slice corresponding to the first encoded data slice, wherein the partial encoded data slice is generated based on the second encoded data slice and a section of the encoding matrix that corresponds to the first encoded data slice;

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

generate additional partial encoded data slices corresponding to the first encoded data slice based on the subset of encoded data slices and the section of the encoding matrix that corresponds to the first encoded data slice;

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

recreate the first encoded data slice from the partial encoded data slice and the additional partial encoded data slices; and

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

decode the subset of encoded data slices and the first encoded data slice using the decoding matrix to reproduce the data.

10. The DS module of claim 9 further comprises:

prior to recreating the first encoded data slice, the third module further functions to de-obfuscate the partial encoded data slice utilizing an obfuscation function.

11. The DS module of claim 9 further comprises:

the subset of encoded data slices does not include the first, the second, or a third encoded data slice of the set of encoded data slices, wherein the partial encoded data slice is generated based on the second and third encoded data slices and the section of the encoding matrix that corresponds to the first encoded data slice;

the first module further causes the computing device to receive a second partial encoded data slice corresponding to the fourth encoded data slice, wherein the second partial encoded data slice is generated based on the second and the third encoded data slice and a section of the encoding matrix that corresponds to the fourth encoded data slice;

the second module further causes the computing device to generate second additional partial encoded data slices corresponding to the fourth encoded data slice based on the subset of encoded data slices and the section of the encoding matrix that corresponds to the fourth encoded data slice;

the third module further causes the computing device to recreate the fourth encoded data slice from the second partial encoded data slice and the second additional partial encoded data slices; and

the fourth module further causes the computing device to decode the subset of encoded data slices, the first encoded data slice, and the fourth encoded data slice using the decoding matrix to reproduce the data segment.

12. The DS module of claim 9, wherein the second module functions to generate one of the additional partial encoded data slices by:

generating a first decoding matrix for the first encoded data slice based on the encoding matrix;

encoding a corresponding one of the subset of encoded data slices using the first decoding matrix to produce a vector; and

encoding the vector using, as the section of the encoding matrix, a row of the encoding matrix that corresponds to the first encoded data slice to produce the one of the additional partial encoded data slices.

13. The DS module of claim 12, wherein the second module functions to generate the decoding matrix by:

reducing the encoding matrix to produce a square matrix based on the first encoded data slice and the subset of encoded data slices; and

inverting the square matrix to produce the decoding matrix.

14. The DS module of claim 9, wherein the fourth module functions to decode the subset of encoded data slices and the first encoded data slice by:

generating a received slice matrix from the first encoded data slice and the subset of encoded data slices;

generating a data matrix based on the received slice matrix and the decoding matrix; and

creating the data segment from the data matrix.

15. The DS module of claim 14 further comprises:

the fourth module further functions to;

obtain the encoding matrix;

reduce the encoding matrix based on rows associated with the subset of encoded data slices and the first encoded data slice to produce a square matrix; and

invert the square matrix to produce the decoding matrix.

16. The DS module of claim 9, wherein the third module functions to recreate the first encoded data slice from the partial encoded data slice and the additional partial encoded data slices by one of:

exclusive ORing the partial encoded data slice and the additional partial encoded data slices to produce the first encoded data slice; and

rebuilding the first encoded data slice based on the partial encoded data slice and the additional partial encoded data slices in accordance with a dispersed storage error coding function.