Verifying data integrity utilizing dispersed storage

• US 9,015,499 B2
• Filed: 08/05/2013
• Issued: 04/21/2015
• Est. Priority Date: 11/01/2010
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W., Resch, Jason K.
• Primary Examiner(s): Rashid, Harunur
• Assistant Examiner(s): HO, DAO Q
• Application Number:
  US13/959,688
• Publication Number:
  US 20130325820A1
• Time in Patent Office: 624 Days
• Field of Search: 719/193
• US Class Current: 713/193
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; 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], H04L67/1097
• CPC Class Codes: G06F 11/076 by exceeding a count or rate limit, e.g. word- or bit count limit
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

A method begins by a processing module retrieving at least a threshold number of error coded data slices of a set of error coded data slices from storage units of a dispersed storage network (DSN) and identifying, based on an intentional error pattern, error coded data slices that were intentionally altered to produce identified error coded data slices. The method continues with the processing module decoding the set of error coded data slices to produce a recovered data segment and encoding the recovered data segment using an altered dispersed storage error encoding function to produce a test set of error coded data slices for comparing with corresponding error coded data slices. When the test set of error coded data slices substantially match the corresponding error coded data slices, the method continues with the processing module indicating that the recovered data segment has not been corrupted.

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:

retrieving at least a threshold number of error coded data slices of a set of error coded data slices from storage units of the DSN, wherein a dispersed storage error encoding function has been altered to include an intentional error pattern to produce an altered dispersed storage error encoding function, wherein a data segment was encoded using the altered dispersed storage error encoding function to produce the set of error coded data slices, and wherein, as a result of the intentional error pattern, one or more error coded data slices of the set of error coded data slices is intentionally altered to include an error;

identifying, based on the intentional error pattern, error coded data slices of the at least a threshold number of error coded data slices that were intentionally altered to include the error to produce identified error coded data slices;

modifying the identified error coded data slices to extract the intentionally included error to produce adjusted error coded data slices;

decoding the adjusted error coded data slices and remaining ones of the at least a threshold number of error coded data slices using the dispersed storage error encoding function to produce a recovered data segment;

encoding the recovered data segment using the altered dispersed storage error encoding function to produce a test set of error coded data slices;

comparing the error coded data slices of the test set of error coded data slices with the error coded data slices of the at least a threshold number of error coded data slices; and

when, on a corresponding slice by slice basis, the error coded data slices of the test set of error coded data slices substantially match the error coded data slices of the at least a threshold number of error coded data slices, indicating that the recovered data segment has not been corrupted.

2. The method of claim 1 further comprises:

altering the dispersed storage error encoding function by;

converting the data segment into a data matrix;

generating a coded matrix from the data matrix and an encoding matrix, wherein the coded matrix includes encoded blocks;

inserting intentional error blocks into the coded matrix in accordance with the intentional error pattern; and

arranging the encoded blocks and the intentional error blocks into the set of error coded data slices.

3. The method of claim 2, wherein the modifying the identified error coded data slices comprises:

arranging the at least a threshold number of error coded data slices into a recovered coded matrix of the encoded blocks and the intentional error blocks; and

removing the intentional error blocks from the recovered coded matrix to produce the adjusted error coded data slices and the remaining ones of the at least a threshold number of error coded data slices.

4. The method of claim 1 further comprises:

altering the dispersed storage error encoding function by;

converting the data segment into a data matrix;

generating a coded matrix from the data matrix and an encoding matrix, wherein the coded matrix includes encoded blocks;

generating an intentional error data matrix in accordance with the intentional error pattern;

generating an intentional error coded matrix from the intentional error data matrix and the encoding matrix, wherein the intentional error coded matrix includes intentional error blocks; and

arranging the encoded blocks and the intentional error blocks into the set of error coded data slices.

5. The method of claim 4, wherein the modifying the identified error coded data slices comprises:

arranging the at least a threshold number of error coded data slices into a recovered coded matrix of the encoded blocks and the intentional error blocks; and

removing the intentional error blocks from the recovered coded matrix to produce the adjusted error coded data slices and the remaining ones of the at least a threshold number of error coded data slices.

6. The method of claim 1 further comprises:

altering the dispersed storage error encoding function to include the intentional error pattern to produce the altered dispersed storage error encoding function;

encoding the data segment using the altered dispersed storage error encoding function to produce the set of error coded data slices; and

transmitting the set of error coded data slices to the storage units of the DSN or to another device of the DSN.

7. The method of claim 1 further comprises:

repeating the retrieving, the identifying, the modifying, the decoding, the encoding, the comparing, and the indicating for another data segment, wherein the data segment and the other data segment are portions of a data object.

8. The method of claim 1 further comprises:

retrieving at least another threshold number of error coded data slices of another set of error coded data slices from the storage units, wherein the dispersed storage error encoding function has been altered to include a second intentional error pattern to produce a second altered dispersed storage error encoding function, wherein another data segment was encoded using the second altered dispersed storage error encoding function to produce the other set of error coded data slices, wherein, as a result of the second intentional error pattern, one or more error coded data slices of the other set of error coded data slices is intentionally altered to include an error, wherein the data segment and the other data segment are portions of a data object;

identifying, based on the second intentional error pattern, the error coded data slices of the at least a threshold number of error coded data slices that were intentionally altered to include the error to produce second identified error coded data slices;

modifying the second identified error coded data slices to extract the intentionally included error to produce second adjusted error coded data slices;

decoding the second adjusted error coded data slices and remaining ones of the at least a threshold number of error coded data slices using the dispersed storage error encoding function to produce a second recovered data segment;

encoding the second recovered data segment using the second altered dispersed storage error encoding function to produce a second test set of error coded data slices;

comparing the error coded data slices of the second test set of error coded data slices with the error coded data slices of the at least another threshold number of error coded data slices; and

when, on a corresponding slice by slice basis, the error coded data slices of the second test set of error coded data slices substantially match the corresponding error coded data slices of the at least another threshold number of error coded data slices, indicating that the second recovered data segment has not been corrupted.

9. A dispersed storage network (DSN) comprises:

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

retrieve at least a threshold number of error coded data slices of a set of error coded data slices from storage units of the DSN, wherein a dispersed storage error encoding function has been altered to include an intentional error pattern to produce an altered dispersed storage error encoding function, wherein a data segment was encoded using the altered dispersed storage error encoding function to produce the set of error coded data slices, and wherein, as a result of the intentional error pattern, one or more error coded data slices of the set of error coded data slices is intentionally altered to include an error;

identify, based on the intentional error pattern, error coded data slices of the at least a threshold number of error coded data slices that were intentionally altered to include the error to produce identified error coded data slices;

modify the identified error coded data slices to extract the intentionally included error to produce adjusted error coded data slices; and

decode the adjusted error coded data slices and remaining ones of the at least a threshold number of error coded data slices using the dispersed storage error encoding function to produce a recovered data segment;

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

encode the recovered data segment using the altered dispersed storage error encoding function to produce a test set of error coded data slices; and

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

compare the error coded data slices of the test set of error coded data slices with the error coded data slices of the at least a threshold number of error coded data slices; and

when, on a corresponding slice by slice basis, the error coded data slices of the test set of error coded data slices substantially match the corresponding error coded data slices of the at least a threshold number of error coded data slices, indicate that the recovered data segment has not been corrupted.

10. The DSN of claim 9 further comprises:

the first module, when operable within the device, further causes the device to;

alter the dispersed storage error encoding function by;

converting the data segment into a data matrix;

generating a coded matrix from the data matrix and an encoding matrix, wherein the coded matrix includes encoded blocks;

inserting intentional error blocks into the coded matrix in accordance with the intentional error pattern; and

arranging the encoded blocks and the intentional error blocks into the set of error coded data slices.

11. The DSN of claim 10, wherein the first module functions to modify the identified error coded data slices by:

arranging the at least a threshold number of error coded data slices into a recovered coded matrix of the encoded blocks and the intentional error blocks; and

removing the intentional error blocks from the recovered coded matrix to produce the adjusted error coded data slices and the remaining ones of the at least a threshold number of error coded data slices.

12. The DSN of claim 9 further comprises:

the first module, when operable within the device, further causes the device to;

alter the dispersed storage error encoding function by;

converting the data segment into a data matrix;

generating a coded matrix from the data matrix and an encoding matrix, wherein the coded matrix includes encoded blocks;

generating an intentional error data matrix in accordance with the intentional error pattern;

generating an intentional error coded matrix from the intentional error data matrix and the encoding matrix, wherein the intentional error coded matrix includes intentional error blocks; and

arranging the encoded blocks and the intentional error blocks into the set of error coded data slices.

13. The DSN of claim 12, wherein the first module functions to modify the identified error coded data slices by:

arranging the at least a threshold number of error coded data slices into a recovered coded matrix of the encoded blocks and the intentional error blocks; and

removing the intentional error blocks from the recovered coded matrix to produce the adjusted error coded data slices and the remaining ones of the at least a threshold number of error coded data slices.

14. The DSN of claim 9 further comprises:

the first module, when operable within the device, further causes the device to;

alter the dispersed storage error encoding function to include the intentional error pattern to produce the altered dispersed storage error encoding function;

encode the data segment using the altered dispersed storage error encoding function to produce the set of error coded data slices; and

transmit the set of error coded data slices to the storage units of the DSN or to another device of the DSN.

15. The DSN of claim 9 further comprises:

the first module, when operable within the device, further causes the device to;

repeat the retrieve, the identify, the modify, and the decode for another data segment,

wherein the data segment and the other data segment are portions of a data object;

the second module, when operable within the device, further causes the device to;

repeat the encode for the other data segment; and

the third module, when operable within the device, further causes the device to;

repeat the compare and the indicate for the other data segment.

16. The DSN of claim 9 further comprises:

the first module, when operable within the device, further causes the device to;

retrieve at least another threshold number of error coded data slices of another set of error coded data slices from the storage units, wherein the dispersed storage error encoding function has been altered to include a second intentional error pattern to produce a second altered dispersed storage error encoding function, wherein another data segment was encoded using the second altered dispersed storage error encoding function to produce the other set of error coded data slices, wherein, as a result of the second intentional error pattern, one or more error coded data slices of the other set of error coded data slices is intentionally altered to include an error, wherein the data segment and the other data segment are portions of a data object;

identify, based on the second intentional error pattern, the error coded data slices of the at least a threshold number of error coded data slices that were intentionally altered to include the error to produce second identified error coded data slices;

modify the second identified error coded data slices to extract the intentionally included error to produce second adjusted error coded data slices; and

decode the second adjusted error coded data slices and remaining ones of the at least a threshold number of error coded data slices using the dispersed storage error encoding function to produce a second recovered data segment;

the second module, when operable within the device, further causes the device to;

encode the second recovered data segment using the second altered dispersed storage error encoding function to produce a second test set of error coded data slices; and

the third module, when operable within the device, further causes the device to;

compare the error coded data slices of the second test set of error coded data slices with the error coded data slices of the at least another threshold number of error coded data slices; and

when, on a corresponding slice by slice basis, the error coded data slices of the second test set of error coded data slices substantially match the error coded data slices of the at least another threshold number of error coded data slices, indicate that the second recovered data segment has not been corrupted.