Recovering data from corrupted encoded data slices

• US 9,298,542 B2
• Filed: 09/16/2013
• Issued: 03/29/2016
• Est. Priority Date: 10/30/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Peake, Andrew George, Resch, Jason K.
• Primary Examiner(s): KUDIRKA, JOSEPH R
• Application Number:
  US14/027,823
• Publication Number:
  US 20140122440A1
• Time in Patent Office: 925 Days
• US Class Current: 1/1
• 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/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 12/14 Protection against unauthorised use of memory or access to memory
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

A method begins by a dispersed storage (DS) processing module receiving a set of encoded data slices, where some of the encoded data slices have an integrity issue such that less than a decode threshold number of encoded data slices have valid integrity. The method continues with the DS processing module creating partial coded matrices from the set of encoded data slices and generating partial decoding matrices. The method continues with the DS processing module generating a test data matrix based on the partial coded matrices and the partial decoding matrices, encoding the test data matrix into a set of test encoded data slices, and generating integrity information for the set of test encoded data slices. When the integrity information is valid, the method continues with the DS processing module utilizing the test data matrix as a data matrix and converting the data matrix into a recovered data segment.

Claims

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

receiving a set of encoded data slices, wherein some encoded data slices of the set of encoded data slices have an integrity issue such that less than a decode threshold number of encoded data slices have valid integrity;

creating a received coded matrix from the set of encoded data slices;

creating a plurality of partial coded matrices from the received coded matrix, wherein each of the plurality of partial coded matrices includes at least one encoded data block from at least one of the some of the encoded data slices having the integrity issue;

generating a plurality of partial decoding matrices from a decoding matrix;

generating a test data matrix based on the plurality of partial coded matrices and the plurality of partial decoding matrices;

encoding the test data matrix into a set of test encoded data slices;

generating integrity information for the set of test encoded data slices;

when the integrity information is valid, utilizing the test data matrix as a data matrix; and

converting the data matrix into a recovered data segment.

2. The method of claim 1, wherein the creating the received coded matrix comprises:

separating each encoded data slice of the set of encoded data slices into encoded data blocks; and

arranging the encoded data blocks of the set of encoded data slices into the received coded matrix in accordance with a dispersed storage error encoding function.

3. The method of claim 1 further comprises:

the creating the plurality of partial coded matrices including;

creating a first partial coded matrix of the plurality of partial coded matrices from a first group of encoded data blocks of the received coded matrix; and

creating a second partial coded matrix of the plurality of partial coded matrices from a second group of encoded data blocks of the received coded matrix; and

the generating the plurality of partial decoding matrices including;

generating a first partial decoding matrix from a first group of matrix coefficients of the decoding matrix, wherein the first group of matrix coefficients have a correlation to the first group of encoded data blocks; and

generating a second partial decoding matrix from a second group of matrix coefficients of the decoding matrix, wherein the second group of matrix coefficients have a correlation to the second group of encoded data blocks.

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

matrix multiplying a first partial coded matrix of the plurality of partial coded matrices with a first partial decoding matrix of the plurality of partial decoding matrices to produce a first partial test data matrix;

matrix multiplying a second partial coded matrix of the plurality of partial coded matrices with a second partial decoding matrix of the plurality of partial decoding matrices to produce a second partial test data matrix; and

combining the first and second partial test data matrices to produce the test data matrix.

5. The method of claim 1 further comprises:

generating an integrity value for each test encoded data slice of the set of test encoded data slices to produce integrity values as the integrity information;

retrieving a valid integrity value for each encoded data slice of the set of encoded data slices to produce valid integrity values; and

comparing the integrity values with the valid integrity values to determine whether the integrity information is valid.

6. The method of claim 1 further comprises:

when the integrity information is not valid;

creating a second plurality of partial coded matrices from the received coded matrix, wherein each of the second plurality of partial coded matrices includes at least one different encoded data block from the at least one of the some of the encoded data slices having the integrity issue;

generating a second plurality of partial decoding matrices from the decoding matrix;

generating a second test data matrix based on the second plurality of partial coded matrices and the second plurality of partial decoding matrices;

encoding the second test data matrix into a second set of test encoded data slices;

generating second integrity information for the second set of test encoded data slices; and

when the second integrity information is valid, utilizing the second test data matrix as the data matrix.

7. A dispersed storage (DS) module comprises:

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

receive a set of encoded data slices, wherein some encoded data slices of the set of encoded data slices have an integrity issue such that less than a decode threshold number of encoded data slices have valid integrity; and

create a received coded matrix from the set of encoded data slices;

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

create a plurality of partial coded matrices from the received coded matrix, wherein each of the plurality of partial coded matrices includes at least one encoded data block from at least one of the some of the encoded data slices having the integrity issue;

generate a plurality of partial decoding matrices from a decoding matrix;

generate a test data matrix based on the plurality of partial coded matrices and the plurality of partial decoding matrices;

encode the test data matrix into a set of test encoded data slices;

generate integrity information for the set of test encoded data slices;

when the integrity information is valid, utilize the test data matrix as a data matrix; and

convert the data matrix into a recovered data segment.

8. The DS module of claim 7, wherein the receiving module functions to create the received coded matrix by:

separating each encoded data slice of the set of encoded data slices into encoded data blocks; and

arranging the encoded data blocks of the set of encoded data slices into the received coded matrix in accordance with a dispersed storage error encoding function.

9. The DS module of claim 7 further comprises:

the consensus decoding module functions to create the plurality of partial coded matrices by;

creating a first partial coded matrix of the plurality of partial coded matrices from a first group of encoded data blocks of the received coded matrix; and

creating a second partial coded matrix of the plurality of partial coded matrices from a second group of encoded data blocks of the received coded matrix; and

the consensus decoding module functions to generate the plurality of partial decoding matrices by;

generating a first partial decoding matrix from a first group of matrix coefficients of the decoding matrix, wherein the first group of matrix coefficients have a correlation to the first group of encoded data blocks; and

generating a second partial decoding matrix from a second group of matrix coefficients of the decoding matrix, wherein the second group of matrix coefficients have a correlation to the second group of encoded data blocks.

10. The DS module of claim 7, wherein the consensus decoding module functions to generate the test data matrix by:

matrix multiplying a first partial coded matrix of the plurality of partial coded matrices with a first partial decoding matrix of the plurality of partial decoding matrices to produce a first partial test data matrix;

matrix multiplying a second partial coded matrix of the plurality of partial coded matrices with a second partial decoding matrix of the plurality of partial decoding matrices to produce a second partial test data matrix; and

combining the first and second partial test data matrices to produce the test data matrix.

11. The DS module of claim 7 further comprises:

the consensus decoding module, when operable within the computing device, further functions to cause the computing device to;

generate an integrity value for each test encoded data slice of the set of test encoded data slices to produce integrity values as the integrity information;

retrieve a valid integrity value for each encoded data slice of the set of encoded data slices to produce valid integrity values; and

compare the integrity values with the valid integrity values to determine whether the integrity information is valid.

12. The DS module of claim 7 further comprises:

when the integrity information is not valid, the consensus decoding module, when operable within the computing device, further functions to cause the computing device to;

create a second plurality of partial coded matrices from the received coded matrix, wherein each of the second plurality of partial coded matrices includes at least one different encoded data block from the at least one of the some of the encoded data slices having the integrity issue;

generate a second plurality of partial decoding matrices from the decoding matrix;

generate a second test data matrix based on the second plurality of partial coded matrices and the second plurality of partial decoding matrices;

encode the second test data matrix into a second set of test encoded data slices;

generate second integrity information for the second set of test encoded data slices; and

when the second integrity information is valid, utilize the second test data matrix as the data matrix.