Identifying a potentially compromised encoded data slice

• US 9,146,810 B2
• Filed: 02/06/2015
• Issued: 09/29/2015
• Est. Priority Date: 01/31/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K., Leggette, Wesley, Motwani, Manish
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Ahmed, Enam
• Application Number:
  US14/615,966
• Publication Number:
  US 20150154074A1
• Time in Patent Office: 235 Days
• Field of Search: 714/776
• US Class Current: 1/1
• 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/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• 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 selecting a data segment and verifying integrity values of encoded data slices generated by encoding the data segment. When integrity values of a decode threshold number of encoded data slices are affirmatively verified, the method continues with the DS processing module verifying an integrity value of the data segment. When the integrity value of the data segment is affirmatively verified, the method continues with the DS processing module generating a new set of encoded data slices. The method continues with the DS processing module verifying concurrency of the set of encoded data slices with the new set of encoded data slices and for each encoded data slice having a negative concurrency verification, flagging the encoded data slice as being potentially compromised.

Claims

1. A method for determining a compromised encoded slice in a dispersed storage network that is configured with a plurality of dispersed storage units, comprising:

retrieving a first threshold combination of encoded slices from a first set of dispersed storage devices of the dispersed storage network to reconstruct a segment, in which the segment is dispersed error encoded to produce n number of encoded slices and stored in the plurality of dispersed storage units, and in which at least a threshold number of the n number of encoded slices are needed to reconstruct the segment, where the threshold number is less than n;

reconstructing the segment from the retrieved first threshold combination of encoded slices;

verifying integrity of the reconstructed segment from the first threshold combination of encoded slices;

when the reconstruction of the retrieved first threshold combination of encoded slices is negatively verified, replacing one of the encoded slices of the retrieved first threshold combination of encoded slices with one of the encoded slices of the segment stored in one of the dispersed storage units that is not an encoded slice forming the first threshold combination of encoded slices, in order to form a second threshold combination of encoded slices;

reconstructing the segment from the retrieved second threshold combination of encoded slices;

verifying integrity of the reconstructed segment from the second threshold combination of encoded slices; and

when the reconstruction of the retrieved second threshold combination of encoded slices is negatively verified, returning to the first threshold combination of encoded slices and replacing a second of the encoded slices of the retrieved first threshold combination of encoded slices to reconstruct the segment for verification and continue replacing other encoded slices of the retrieved first threshold combination of encoded slices one at a time to form other threshold combination of encoded slices, until affirmative verification is achieved to recover the segment.

2. The method of claim 1, further including identifying a last replaced encoded slice when the affirmative verification is achieved and flagging the last replaced encoded slice as a compromised encoded slice.

3. The method of claim 1, further including encoding a set of encoded slices from the reconstructed retrieved threshold combination of encoded slices that results in the affirmative verification and comparing the set of encoded slices to the encoded slices stored in the plurality of dispersed storage units to identify one or more compromised encoded slices.

4. The method of claim 1, wherein the n number of encoded slices are encoded data slices.

5. The method of claim 1, wherein the n number of encoded slices are encoded task slices.

6. The method of claim 1, wherein when replacing one of the encoded slices of the first threshold combination of encoded slices with one of the encoded slices of the segment stored in one of the dispersed storage units that is not an encoded slice forming the first threshold combination of encoded slices, a same encoded slice is used for replacement of one of the encoded slices of the first threshold combination of encoded slices.

7. The method of claim 1, wherein when replacing one of the encoded slices of the first threshold combination of encoded slices with one of the encoded slices of the segment stored in one of the dispersed storage units that is not an encoded slice forming the first threshold combination of encoded slices, a same or different encoded slice is selected for replacement of one of the encoded slices of the first threshold combination of encoded slices.

8. The method of claim 1, wherein when all of the first combination of encoded slices is replaced one at a time and only the negative verification is achieved, returning to the first threshold combination of encoded slices to replace two encoded slices at a time to form other threshold combination of encoded slices to reconstruct the segment for verification, until affirmative verification is achieved to recover the segment.

9. The method of claim 8, wherein when all of the first combination of encoded slices is replaced two at a time and only the negative verification is achieved, returning to the first threshold combination of encoded slices to replace three encoded slices at a time to form other threshold combination of encoded slices to reconstruct the segment for verification, until affirmative verification is achieved to recover the segment.

10. The method of claim 1, wherein when all of the first combination of encoded slices is replaced one at a time and only the negative verification is achieved, selecting a new threshold combination of encoded slices of the segment stored in the dispersed storage units to form a revised first combination of encoded slices for reconstruction and verification to achieve the affirmative verification.

11. An apparatus for determining a compromised encoded slice in a dispersed storage network that is configured with a plurality of dispersed storage units, comprising:

an interface for retrieving encoded slices from the dispersed storage units of the dispersed storage network; and

a processor, configured with the interface, to;

retrieve a first threshold combination of encoded slices from a first set of dispersed storage devices of the dispersed storage network to reconstruct a segment, in which the segment is dispersed error encoded to produce n number of encoded slices and stored in the plurality of dispersed storage units, and in which at least a threshold number of the n number of encoded slices are needed to reconstruct the segment, where the threshold number is less than n,

reconstruct the segment from the retrieved first threshold combination of encoded slices;

verify integrity of the reconstructed segment from the first threshold combination of encoded slices;

when the reconstruction of the retrieved first threshold combination of encoded slices is negatively verified, replacing one of the encoded slices of the retrieved first threshold combination of encoded slices with one of the encoded slices of the segment stored in one of the dispersed storage units that is not an encoded slice forming the first threshold combination of encoded slices, in order to form a second threshold combination of encoded slices;

reconstruct the segment from the retrieved second threshold combination of encoded slices;

verify integrity of the reconstructed segment from the second threshold combination of encoded slices; and

when the reconstruction of the retrieved second threshold combination of encoded slices is negatively verified, returning to the first threshold combination of encoded slices and to replace a second of the encoded slices of the retrieved first threshold combination of encoded slices to reconstruct the segment for verification and continue to replace other encoded slices of the retrieved first threshold combination of encoded slices one at a time to form other threshold combination of encoded slices, until affirmative verification is achieved to recover the segment.

12. The apparatus of claim 11, wherein the processor further identifies a last replaced encoded slice when the affirmative verification is achieved and flags the last replaced encoded slice as a compromised encoded slice.

13. The apparatus of claim 11, wherein the processor further encodes a set of encoded slices from the reconstructed retrieved threshold combination of encoded slices that results in the affirmative verification and compares the set of encoded slices to the encoded slices stored in the plurality of dispersed storage units to identify one or more compromised encoded slices.

14. The apparatus of claim 11, wherein the n number of encoded slices are encoded data slices.

15. The apparatus of claim 11, wherein the n number of encoded slices are encoded task slices.

16. The apparatus of claim 11, wherein when the processor replaces one of the encoded slices of the first threshold combination of encoded slices with one of the encoded slices of the segment stored in one of the dispersed storage units that is not an encoded slice forming the first threshold combination of encoded slices, a same encoded slice is used for replacement of one of the encoded slices of the first threshold combination of encoded slices.

17. The apparatus of claim 11, wherein when the processor replaces one of the encoded slices of the first threshold combination of encoded slices with one of the encoded slices of the segment stored in one of the dispersed storage units that is not an encoded slice forming the first threshold combination of encoded slices, a same or different encoded slice is selected for replacement of one of the encoded slices of the first threshold combination of encoded slices.

18. The apparatus of claim 11, wherein when the processor replaces all of the first combination of encoded slices one at a time and only the negative verification is achieved, the processor returns to the first threshold combination of encoded slices to replace two encoded slices at a time to form other threshold combination of encoded slices to reconstruct the segment for verification, until affirmative verification is achieved to recover the segment.

19. The apparatus of claim 18, wherein when the processor replaces all of the first combination of encoded slices two at a time and only the negative verification is achieved, the processor returns to the first threshold combination of encoded slices to replace three encoded slices at a time to form other threshold combination of encoded slices to reconstruct the segment for verification, until affirmative verification is achieved to recover the segment.

20. The apparatus of claim 11, wherein when the processor replaces all of the first combination of encoded slices one at a time and only the negative verification is achieved, the processor selects a new threshold combination of encoded slices of the segment stored in the dispersed storage units to form a revised first combination of encoded slices for reconstruction and verification to achieve the affirmative verification.