Encoding data utilizing a zero information gain function

• US 10,216,576 B2
• Filed: 03/18/2014
• Issued: 02/26/2019
• Est. Priority Date: 10/04/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): Lamarre, Guy J
• Assistant Examiner(s): Alshack, Osman M
• Application Number:
  US14/217,662
• Publication Number:
  US 20140201567A1
• Time in Patent Office: 1,806 Days
• Field of Search: 714752, 714763
• 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 encoding data using a dispersed storage error coding function to produce a set of encoded data slices. The method continues with the DS processing module encoding a first encoded data slice of the set of encoded data slices using a zero information gain (ZIG) function based on a second encoded data slice of the set of encoded data slices to produce a ZIG encoded data slice. The method continues with the DS processing module outputting the ZIG encoded data slice and a subset of encoded data slices of the set of encoded data slices, wherein the subset of encoded data slices includes less than a decode threshold number of encoded data slices and does not include the first or the second encoded data slice.

Claims

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

dispersed storage error encoding, by the processing module and in accordance with distributed data storage parameters, a data segment to produce a set of encoded data slices and a set of zero information gain (ZIG) encoded data slices, wherein the set of encoded data slices is encoded in accordance with a dispersed storage error encoding scheme and wherein the set of ZIG encoded data slices is encoded using a ZIG function and further wherein a first ZIG encoded data slice of the set of ZIG encoded data slices is generated by matrix multiplying a first decoding matrix and a first encoded data slice of the set of encoded data slices, wherein generating the first ZIG encoded data slice includes generating a first partial encoded data slice based on the first decoding matrix, the first encoded data slice and a row of the encoding matrix corresponding to the first encoded data slice, generating a second partial encoded data slice based on a second decoding matrix, a second encoded data slice and a row of the encoding matrix corresponding to the second encoded data slice, wherein the second encoded data slice is an encoded data slice of the set of encoded data slices and not included in the subset of encoded data slices, and combining the first and second partial encoded data slices to produce the first ZIG encoded data slice;

selecting, by the processing module, a first subset of encoded data slices from the set of encoded data slices, wherein the first subset of encoded data slices includes less than a threshold number of encoded data slices, and further wherein the threshold number of encoded data slices is required to recreate the data segment;

sending, by the processing module via an interface of the computing device, the subset of encoded data slices to a first memory within the DSN for storage therein; and

sending, by the processing module via the interface, the set of ZIG encoded data slices to a second memory within the DSN for storage therein.

2. The method of claim 1, wherein generating the first ZIG encoded data slice further comprises:

matrix multiplying the first decoding matrix and the first encoded data slice to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to the first encoded data slice to produce the first ZIG encoded data slice.

3. The method of claim 1 further comprises:

generating the first decoding matrix by;

reducing an encoding matrix to produce a square matrix that exclusively includes rows associated with the subset of encoded data slices and an encoded data slice being represented by the first ZIG encoded data slice; and

inverting the square matrix to produce the decoding matrix.

4. The method of claim 1, wherein the sending the set of ZIG encoded data slices comprises:

prior to sending, obfuscating the first ZIG encoded data slice using an obfuscating function.

5. The method of claim 4, wherein the obfuscating function comprises one of:

exclusive ORing the first ZIG encoded data slice with an obfuscating value;

masking the first ZIG encoded data slice;

encrypting the first ZIG encoded data slice; and

performing a deterministic function on the first ZIG encoded data slice.

6. A dispersed storage (DS) module of a dispersed storage network (DSN) comprises:

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

dispersed storage error encode in accordance with distributed data storage parameters, a data segment of data to produce a set of encoded data slices and a set of zero information gain (ZIG) encoded data slices, wherein the set of encoded data slices is encoded in accordance with a dispersed storage error encoding scheme and wherein the set of ZIG encoded data slices is encoded using a ZIG function, wherein a first ZIG encoded data slice of the set of ZIG encoded data slices is generated by matrix multiplying a first decoding matrix and a first encoded data slice of the set of encoded data slices and wherein the generating the first ZIG encoded data slice includes;

generating a first partial encoded data slice based on the first decoding matrix, the first encoded data slice and a row of the encoding matrix corresponding to the first encoded data slice;

generating a second partial encoded data slice based on a second decoding matrix, a second encoded data slice and a row of the encoding matrix corresponding to the second encoded data slice, wherein the second encoded data slice is an encoded data slice of the set of encoded data slices and not included in the subset of encoded data slices; and

combining the first and second partial encoded data slices to produce the first ZIG encoded data slice;

select a first subset of encoded data slices from the set of encoded data slices, wherein the first subset of encoded data slices includes less than a threshold number of encoded data slices, and further wherein the threshold number of encoded data slices is required to recreate the data segment; and

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

send, via an interface of the computing device, the subset of encoded data slices to a first memory within the DSN for storage therein; and

send, via the interface, the set of ZIG encoded data slices to a second memory within the DSN for storage therein.

7. The DS module of claim 6, wherein the first module, when operable within the computing device, further causes the computing device to generate the first ZIG encoded data slice by:

matrix multiplying the first decoding matrix and the first encoded data slice to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to the first encoded data slice to produce the first ZIG encoded data slice.

8. The DS module of claim 6, wherein the first module, when operable within the computing device, causes the computing device to generate the first decoding matrix by:

reducing an encoding matrix to produce a square matrix that exclusively includes rows associated with the subset of encoded data slices and an encoded data slice being represented by the first ZIG encoded data slice; and

inverting the square matrix to produce the decoding matrix.

9. The DS module of claim 6, wherein the second module, when operable within the computing device, further causes the computing device to send the set of ZIG encoded data slices by:

prior to sending, obfuscating the first ZIG encoded data slice using an obfuscating function.

10. The DS module of claim 9, wherein the obfuscating function comprises one of:

exclusive ORing the first ZIG encoded data slice with an obfuscating value;

masking the first ZIG encoded data slice;

encrypting the first ZIG encoded data slice; and

performing a deterministic function on the first ZIG encoded data slice.