Rebuilding a data revision in a dispersed storage network

• US 9,009,575 B2
• Filed: 06/18/2013
• Issued: 04/14/2015
• Est. Priority Date: 07/30/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Dhuse, Greg, Volvovski, Ilya, Mark, Zachary J., Vas, Sebastien, Baptist, Andrew
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US13/920,766
• Publication Number:
  US 20130283095A1
• Time in Patent Office: 665 Days
• Field of Search: 714/776, 714/779
• US Class Current: 714/776
• 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 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0863 involving passwords or one-time passwords network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A method begins by a processing module identifying a set of encoded data slices that have been created in accordance with a dispersed storage error encoding function having a decode threshold equal to or less than half of a number encoded data slices in the set of encoded data slices. The method continues with the processing module identifying a first sub-set of encoded data slices having a non-current revision level and identifying a second sub-set of encoded data slices having a more-current revision level. When a number of encoded data slices of the second sub-set of encoded data slices is greater than or equal to the decode threshold and when a number of encoded data slices of the first sub-set of encoded data slices is less than the decode threshold, the method continues with the processing module facilitating rebuilding of the first sub-set of encoded data slices.

Claims

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

identifying a set of encoded data slices that have been created by encoding a data segment in accordance with a dispersed storage error encoding function having a decode threshold equal to or less than half of a number encoded data slices in the set of encoded data slices;

identifying a first sub-set of encoded data slices of the set of encoded data slices having a non-current revision level;

identifying a second sub-set of encoded data slices of the set of encoded data slices having a more-current revision level; and

when a number of encoded data slices of the second sub-set of encoded data slices is greater than or equal to the decode threshold and when a number of encoded data slices of the first sub-set of encoded data slices is less than the decode threshold, facilitating rebuilding of the first sub-set of encoded data slices using at least a decode threshold number of encoded data slices of the second sub-set of encoded slices.

2. The method of claim 1 further comprises:

when the number of encoded data slices of the first sub-set of encoded data slices is equal to or greater than the decode threshold, maintaining the first sub-set of encoded data slices thus allowing for reconstructing of the data segment from the first sub-set of encoded data slices or from the at least the decode threshold number of encoded data slices of the second sub-set of encoded slices.

3. The method of claim 1 further comprises at least one of:

when the number of encoded data slices of the second sub-set of encoded data slices is greater than or equal to the decode threshold and when the number of encoded data slices of the first sub-set of encoded data slices is greater than or equal to the decode threshold, determining whether to rebuild the first sub-set of encoded data slices based on the second sub-set of encoded data slices;

when the number of encoded data slices of the second sub-set of encoded data slices is less than the decode threshold and when the number of encoded data slices of the first sub-set of encoded data slices is greater than or equal to the decode threshold, determining whether to wait for storage units to become available to obtain the decode threshold number of encoded data slices of the second sub-set of encoded data slices or to use the first sub-set of encoded data slices to recapture the data segment having the non-current revision level; and

when the number of encoded data slices of the second sub-set of encoded data slices is less than the decode threshold and when the number of encoded data slices of the first sub-set of encoded data slices is less than the decode threshold, waiting for storage units to become available to obtain the decode threshold number of encoded data slices of the second sub-set of encoded data slices or to obtain the decode threshold number of encoded data slices of the first sub-set of encoded data slices.

4. The method of claim 1, wherein the identifying the first and second sub-sets of encoded data slices comprises:

sending, to storage units, a request to retrieve the set of encoded data slices;

receiving at least some of the set of encoded data slices to produce received encoded data slices;

determining a revision level for each of the received encoded data slices;

grouping the received encoded data slices based on the determined revision level; and

identifying the first sub-set of encoded data slices as a group of the received encoded data slices having the non-current revision level and identifying the second sub-set of encoded data slices as a group of the received encoded data slices having the more current revision level.

5. The method of claim 1 further comprises:

when the number of encoded data slices of the first sub-set of encoded data slices is less than the decode threshold, deleting the first sub-set of encoded data slices.

6. The method of claim 1, wherein the facilitating the rebuilding of the encoded data slices of the first sub-set of encoded data slices comprises:

requesting, from storage units storing the at least the decode threshold number of encoded data slices of the second sub-set of encoded data slices having the more current revision level, a set of partial rebuilding information regarding the at least the decode threshold number of encoded data slices of the second sub-set of encoded slices having the more current revision level;

sending, by the storage units, the set of partial rebuilding information to other storage units; and

rebuilding, by the other storage units, the first sub-set of encoded data slices based on the set of partial rebuilding information.

7. The method of claim 1, wherein the facilitating the rebuilding of the first sub-set of encoded data slices comprises:

retrieving the at least the decode threshold number of encoded data slices of the second sub-set of encoded slices from storage units;

reconstructing the data segment based on the at least the decode threshold number of encoded data slices of the second sub-set of encoded slices and the dispersed storage error encoding function to produce a reconstructed data segment;

encoding the reconstructed data segment in accordance with the dispersed storage error encoding function to produce a set of rebuilt encoded data slices;

selecting some rebuilt encoded data slices of the set of rebuilt encoded data slices as a rebuilt sub-set of encoded data slices; and

writing the rebuilt sub-set of encoded data slices to other storage units.

8. The method of claim 1, wherein the identifying the set of encoded data slices comprises at least one of:

initiating the identifying when availability status of one or more storage units storing one or more encoded data slices of the set of encoded data slices changes; and

initiating the identifying when receiving a write request for the more-current revision level of the set of encoded data slices.

9. A computer comprises:

an interface;

a memory; and

a processing module operable to;

identify a set of encoded data slices that have been created by encoding a data segment in accordance with a dispersed storage error encoding function having a decode threshold equal to or less than half of a number encoded data slices in the set of encoded data slices;

identify a first sub-set of encoded data slices of the set of encoded data slices having a non-current revision level;

identify a second sub-set of encoded data slices of the set of encoded data slices having a more-current revision level; and

when a number of encoded data slices of the second sub-set of encoded data slices is greater than or equal to the decode threshold and when a number of encoded data slices of the first sub-set of encoded data slices is less than the decode threshold, facilitate rebuilding of the first sub-set of encoded data slices using at least a decode threshold number of encoded data slices of the second sub-set of encoded slices.

10. The computer of claim 9 further comprises:

the processing module further operable to;

when the number of encoded data slices of the first sub-set of encoded data slices is equal to or greater than the decode threshold, maintain the first sub-set of encoded data slices thus allowing for reconstructing of the data segment from the first sub-set of encoded data slices or from the at least the decode threshold number of encoded data slices of the second sub-set of encoded slices.

11. The computer of claim 9 further comprises at least one of:

the processing module further operable to;

when the number of encoded data slices of the second sub-set of encoded data slices is greater than or equal to the decode threshold and when the number of encoded data slices of the first sub-set of encoded data slices is greater than or equal to the decode threshold, determine whether to rebuild the first sub-set of encoded data slices based on the second sub-set of encoded data slices;

the processing module further operable to;

when the number of encoded data slices of the second sub-set of encoded data slices is less than the decode threshold and when the number of encoded data slices of the first sub-set of encoded data slices is greater than or equal to the decode threshold, determine whether to wait for storage units to become available to obtain the decode threshold number of encoded data slices of the second sub-set of encoded data slices or to use the first sub-set of encoded data slices to recapture the data segment having the non-current revision level; and

the processing module further operable to;

when the number of encoded data slices of the second sub-set of encoded data slices is less than the decode threshold and when the number of encoded data slices of the first sub-set of encoded data slices is less than the decode threshold, wait for storage units to become available to obtain the decode threshold number of encoded data slices of the second sub-set of encoded data slices or to obtain the decode threshold number of encoded data slices of the first sub-set of encoded data slices.

12. The computer of claim 9, wherein the processing module functions to identify the first and second sub-sets of encoded data slices by:

sending, via the interface to storage units, a request to retrieve the set of encoded data slices;

receiving, via the interface, at least some of the set of encoded data slices to produce received encoded data slices;

determining a revision level for each of the received encoded data slices;

grouping the received encoded data slices based on the determined revision level; and

identifying the first sub-set of encoded data slices as a group of the received encoded data slices having the non-current revision level and identifying the second sub-set of encoded data slices as a group of the received encoded data slices having the more current revision level.

13. The computer of claim 9 further comprises:

the processing module further operable to;

when the number of encoded data slices of the first sub-set of encoded data slices is less than the decode threshold, delete the first sub-set of encoded data slices.

14. The computer of claim 9, wherein the processing module functions to facilitate the rebuilding of the encoded data slices of the first sub-set of encoded data slices by:

requesting, via the interface, from storage units storing the at least the decode threshold number of encoded data slices of the second sub-set of encoded data slices having the more current revision level, a set of partial rebuilding information regarding the at least the decode threshold number of encoded data slices of the second sub-set of encoded slices having the more current revision level, wherein the requesting causes;

sending, by the storage units, the set of partial rebuilding information to other storage units; and

rebuilding, by the other storage units, the first sub-set of encoded data slices based on the set of partial rebuilding information.

15. The computer of claim 9, wherein the processing module functions to facilitate the rebuilding of the first sub-set of encoded data slices by:

retrieving the at least the decode threshold number of encoded data slices of the second sub-set of encoded slices from storage units;

reconstructing the data segment based on the at least the decode threshold number of encoded data slices of the second sub-set of encoded slices and the dispersed storage error encoding function to produce a reconstructed data segment;

encoding the reconstructed data segment in accordance with the dispersed storage error encoding function to produce a set of rebuilt encoded data slices;

selecting some rebuilt encoded data slices of the set of rebuilt encoded data slices as a rebuilt sub-set of encoded data slices; and

writing the rebuilt sub-set of encoded data slices to other storage units.

16. The computer of claim 9, wherein the processing module functions to identify the set of encoded data slices by at least one of:

initiating the identifying when availability status of one or more storage units storing one or more encoded data slices of the set of encoded data slices changes; and

initiating the identifying when receiving a write request for the more-current revision level of the set of encoded data slices.