Sending a zero information gain formatted encoded data slice

• US 8,856,617 B2
• Filed: 09/12/2012
• Issued: 10/07/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): Rizk, Sam
• Application Number:
  US13/612,116
• Publication Number:
  US 20130086452A1
• Time in Patent Office: 755 Days
• Field of Search: 714/763, 714/785
• US Class Current: 714/763
• 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 determining whether to send an encoded data slice of set of encoded data slices in accordance with a zero information gain (ZIG) format. When the encoded data slice is to be sent in accordance with the ZIG format, the method continues with the DS processing module selecting a partial encoding threshold number of encoded data slices of the set of encoded data slices, wherein the partial encoding threshold number of encoded data slices does not include the encoded data slice and generating a set of ZIG encoded data slices based on a ZIG function and the partial encoding threshold number of encoded data slices, wherein the set of ZIG encoded data slices represents recovery information of the encoded data slice. The method continues with the DS processing module outputting the set of ZIG encoded data slices.

Claims

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

determining, by the computing device, whether to send an encoded data slice of a set of encoded data slices in accordance with a zero information gain (ZIG) format, wherein data is encoded using a dispersed storage error coding function to produce the set of encoded data slices, and wherein the data can be recreated from a decode threshold number of encoded data slices of the set of encoded data slices;

when the encoded data slice is to be sent in accordance with the ZIG format;

selecting a partial encoding threshold number of encoded data slices of the set of encoded data slices, wherein the partial encoding threshold number of encoded data slices does not include the encoded data slice; and

generating a set of ZIG encoded data slices based on a ZIG function and the partial encoding threshold number of encoded data slices, wherein the set of ZIG encoded data slices represents recovery information of the encoded data slice and wherein generating a ZIG encoded data slice of the set of ZIG encoded data slices includes;

generating a decoding matrix for the encoded data slice based on an encoding matrix of the dispersed storage error coding function; and

generating the ZIG encoded data slice based on the decoding matrix and on a first encoded data slice of the partial encoding threshold number of encoded data slices; and

outputting the set of ZIG encoded data slices.

2. The method of claim 1, wherein the determining whether to send the encoded data slice in the ZIG format comprises at least one of:

receiving an error message with regards to a previous transmission of the encoded data slice;

determining that the encoded data slice is of a first priority type;

receiving a request for transmission of the encoded data slice; and

determining that a slice name associated with the encoded data slice is on a list.

3. The method of claim 1, wherein the selecting the partial encoding threshold number of encoded data slices comprises:

selecting a subset of encoded data slices of the set of encoded data slices to fulfill the decode threshold number of encoded data slices requirement for recreating the data, wherein the selecting the subset of encoded data slices includes at least one of;

selecting at least one of the subset of encoded data slices to include encoded error code blocks; and

selecting at least one other of the subset of encoded data slices to include encoded data blocks.

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

reducing the encoding matrix to produce a square matrix based on the partial encoding threshold number of encoded data slices; and

inverting the square matrix to produce the decoding matrix.

5. The method of claim 1, wherein the generating the ZIG encoded data slice based on the decoding matrix and on the encoded data slice comprises:

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

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

6. The method of claim 1, wherein the generating the ZIG encoded data slice of the set of ZIG encoded data slices comprises:

generating a decoding matrix for the encoded data slice based on an encoding matrix of the dispersed storage error coding function; and

generating the ZIG encoded data slice by;

generating a first initial ZIG encoded data slice based on the decoding matrix and on a first encoded data slice of the partial encoding threshold number of encoded data slices;

generating a second initial ZIG encoded data slice based on the decoding matrix and on a second encoded data slice of the partial encoding threshold number of encoded data slices; and

combining the first and second initial ZIG encoded data slices to produce the ZIG encoded data slice.

7. The method of claim 1, wherein the outputting the set of ZIG encoded data slices comprises at least one of:

outputting a first one of the set of ZIG encoded data slices on a first path and outputting a second one of the set of ZIG encoded data slices on a second path;

outputting to a receiving entity in support of a communication with the receiving entity;

outputting to a dispersed storage network (DSN) memory for storage therein;

outputting to at least one intermediary device.

8. The method of claim 1, wherein the outputting further comprises:

prior to outputting the set of ZIG encoded data slices, obfuscating at least one ZIG encoded data slice of the set of ZIG encoded data slices utilizing an obfuscation function.

9. A dispersed storage (DS) module comprises:

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

determine whether to send an encoded data slice of a set of encoded data slices in accordance with a zero information gain (ZIG) format, wherein data is encoded using a dispersed storage error coding function to produce the set of encoded data slices, and wherein the data can be recreated from a decode threshold number of encoded data slices of the set of encoded data slices;

a second module, when operable within the computing device and when the encoded data slice is to be sent in accordance with the ZIG format, causes the computing device to;

select a partial encoding threshold number of encoded data slices of the set of encoded data slices, wherein the partial encoding threshold number of encoded data slices does not include the encoded data slice; and

generate a set of ZIG encoded data slices based on a ZIG function and the partial encoding threshold number of encoded data slices, wherein the set of ZIG encoded data slices represents recovery information of the encoded data slice and wherein generating a ZIG encoded data slice of the set of ZIG encoded data slices includes;

generating a decoding matrix for the encoded data slice based on an encoding matrix of the dispersed storage error coding function; and

generating the ZIG encoded data slice based on the decoding matrix and on a first encoded data slice of the partial encoding threshold number of encoded data slices; and

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

output the set of ZIG encoded data slices.

10. The DS module of claim 9, wherein the first module functions to determine whether to send the encoded data slice in the ZIG format by at least one of:

receiving an error message with regards to a previous transmission of the encoded data slice;

determining that the encoded data slice is of a first priority type;

receiving a request for transmission of the encoded data slice; and

determining that a slice name associated with the encoded data slice is on a list.

11. The DS module of claim 9, wherein the second module functions to select the partial encoding threshold number of encoded data slices by:

selecting a subset of encoded data slices of the set of encoded data slices to fulfill the decode threshold number of encoded data slices requirement for recreating the data, wherein the selecting the subset of encoded data slices includes at least one of;

selecting at least one of the subset of encoded data slices to include encoded error code blocks; and

selecting at least one other of the subset of encoded data slices to include encoded data blocks.

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

reducing the encoding matrix to produce a square matrix based on the partial encoding threshold number of encoded data slices; and

inverting the square matrix to produce the decoding matrix.

13. The DS module of claim 9, wherein the second module functions to generate the ZIG encoded data slice based on the decoding matrix and on the encoded data slice by:

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

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

14. The DS module of claim 9, wherein the second module functions to generate the ZIG encoded data slice of the set of ZIG encoded data slices by:

generating a decoding matrix for the encoded data slice based on an encoding matrix of the dispersed storage error coding function; and

generating the ZIG encoded data slice by;

generating a first initial ZIG encoded data slice based on the decoding matrix and on a first encoded data slice of the partial encoding threshold number of encoded data slices;

generating a second initial ZIG encoded data slice based on the decoding matrix and on a second encoded data slice of the partial encoding threshold number of encoded data slices; and

combining the first and second initial ZIG encoded data slices to produce the ZIG encoded data slice.

15. The DS module of claim 9, wherein the third module functions to output the set of ZIG encoded data slices by at least one of:

outputting a first one of the set of ZIG encoded data slices on a first path and outputting a second one of the set of ZIG encoded data slices on a second path;

outputting to a receiving entity in support of a communication with the receiving entity;

outputting to a dispersed storage network (DSN) memory for storage therein; and

outputting to at least one intermediary device.

16. The DS module of claim 9, wherein the third module further functions to output by:

prior to outputting the set of ZIG encoded data slices, obfuscating at least one ZIG encoded data slice of the set of ZIG encoded data slices utilizing an obfuscation function.