Rebuilding slices of a set of encoded data slices

• US 9,703,812 B2
• Filed: 05/01/2013
• Issued: 07/11/2017
• Est. Priority Date: 11/24/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Resch, Jason K.
• Primary Examiner(s): McNally, Michael S
• Assistant Examiner(s): NGUYEN, TRONG H
• Application Number:
  US13/874,560
• Publication Number:
  US 20130238932A1
• Time in Patent Office: 1,532 Days
• Field of Search: 714 2, 714 62, 714 622, 714 624, 714 632, 714 48, 714 54, 714710, 714746, 714747, 714755, 714758, 714760, 714764, 714799, 726 4, 726 17, 726 21, 726 27- 30, 713165, 713167, 713193-194
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 21/80 in storage media based on magnetic or optical technology, e.g. disks with sectors preventing unauthorised reproduction or copying of disc-type recordable media G11B20/00
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A method begins with a processing module initiating a rebuilding process for an encoded data slice of a set of encoded data slices and generating rebuilding information from one or more other encoded data slices of the set of encoded data slices. The method continues with the processing module creating a rebuilt encoded data slice for the encoded data slice based on the rebuilding information. The method continues with the processing module determining whether another encoded data slice of the set of encoded data slices requires rebuilding and when the other encoded data slice requires rebuilding, the method continues with the processing module creating another rebuilt encoded data slice for the other encoded data slice based on the rebuilding information without initiating another rebuilding process for the other encoded data slice.

Claims

1. A method for execution by a computing device within a dispersed storage network (DSN), the method comprises:

initiating a rebuilding process for a first encoded data slice of a set of encoded data slices, wherein a data segment is encoded using an error coding dispersal storage function to produce the set of encoded data slices;

generating rebuilding information from one or more encoded data slices of the set of encoded data slices, wherein the one or more encoded data slices excludes the first encoded data slice, and wherein the rebuilding information is sufficient to create a rebuilt first encoded data slice and at least a rebuilt second encoded data slice;

commencing creation of the rebuilt first encoded data slice based on the rebuilding information;

subsequent to the commencing of the creation of the rebuilt first encoded data slice, identifying a second encoded data slice of the set of encoded data slices that requires rebuilding, the second encoded data slice not previously identified as a slice which requires rebuilding, wherein the identifying the second encoded data slice of the set of encoded data slices that requires rebuilding occurs before the creation of the rebuilt first encoded data slice is complete; and

responsive to the identifying, creating the rebuilt second encoded data slice for the second encoded data slice based on the rebuilding information without initiating another rebuilding process for the second encoded data slice.

2. The method of claim 1, wherein the initiating the rebuilding process comprises:

identifying a storage error regarding the first encoded data slice;

issuing read commands to storage units of the DSN, wherein one of the read commands includes a request to read one of the one or more encoded data slices of the set of encoded data slices stored by one of the storage units; and

receiving the one or more encoded data slices from one or more of the storage units.

3. The method of claim 1, wherein the generating the rebuilding information comprises:

retrieving a decode threshold number of encoded data slices of the set of encoded data slices, which excludes the first encoded data slice; and

storing the decode threshold number of encoded data slices as the rebuilding information.

4. The method of claim 3, wherein the commencing of the creation of the rebuilt first encoded data slice comprises:

decoding the decode threshold number of encoded data slices in accordance with the error coding dispersal storage function to produce a recovered data segment;

encoding the recovered data segment using the error coding dispersal storage function to produce a new set of encoded data slices; and

selecting an encoded data slice of the new set of encoded data slices as the rebuilt first encoded data slice.

5. The method of claim 1, wherein the generating the rebuilding information comprises:

retrieving a decode threshold number of encoded data slices of the set of encoded data slices, which excludes the first encoded data slice;

decoding the decode threshold number of encoded data slices in accordance with the error coding dispersal storage function to produce a recovered data segment; and

storing the recovered data segment as the rebuilding information.

6. The method of claim 5, wherein the creating the rebuilt first encoded data slice comprises:

encoding the recovered data segment using the error coding dispersal storage function to produce a new set of encoded data slices; and

selecting an encoded data slice of the new set of encoded data slices as the rebuilt first encoded data slice.

7. The method of claim 1, wherein the generating the rebuilding information comprises:

receiving partially rebuilt slices from storage units of the DSN; and

storing the partially rebuilt slices as the rebuilding information.

8. The method of claim 7, wherein the creating the rebuilt first encoded data slice comprises:

creating the rebuilt first encoded data slice based on the partially rebuilt slices.

9. The method of claim 1 further comprises:

outputting the rebuilt first encoded data slice for storage in the DSN; and

outputting the rebuilt second encoded data slice for storage in the DSN.

10. A computing device within a dispersed storage network (DSN), the computing device comprises:

a memory;

an interface; and

a processing module operable to;

initiate, via the interface, a rebuilding process for a first encoded data slice of a set of encoded data slices, wherein a data segment is encoded using an error coding dispersal storage function to produce the set of encoded data slices;

generate rebuilding information from one or more encoded data slices of the set of encoded data slices, wherein the one or more encoded data slices excludes the first encoded data slice, and wherein the rebuilding information is sufficient to create a rebuilt first encoded data slice and at least a rebuilt second encoded data slice;

commence creation of the rebuilt first encoded data slice based on the rebuilding information;

subsequent to the commencing of the creation of the rebuilt first encoded data slice, identify a second encoded data slice of the set of encoded data slices that requires rebuilding, the second encoded data slice not previously identified as a slice which requires rebuilding, wherein the identifying the second encoded data slice of the set of encoded data slices that requires rebuilding occurs before the creation of the rebuilt first encoded data slice is complete; and

responsive to the identifying, create the rebuilt second encoded data slice for the second encoded data slice based on the rebuilding information without initiating another rebuilding process for the second encoded data slice.

11. The computing device of claim 10, wherein the processing module functions to initiate the rebuilding process by:

identifying a storage error regarding the first encoded data slice;

issuing, via the interface, read commands to storage units of the DSN, wherein one of the read commands includes a request to read one of the one or more encoded data slices of the set of encoded data slices stored by one of the storage units; and

receiving, via the interface, the one or more encoded data slices from one or more of the storage units.

12. The computing device of claim 10, wherein the processing module functions to generate the rebuilding information by:

retrieving, via the interface, a decode threshold number of encoded data slices of the set of encoded data slices, which excludes the first encoded data slice; and

storing, in the memory, the decode threshold number of encoded data slices as the rebuilding information.

13. The computing device of claim 12, wherein the processing module functions to commence the creation of the rebuilt first encoded data slice by:

decoding the decode threshold number of encoded data slices in accordance with the error coding dispersal storage function to produce a recovered data segment;

encoding the recovered data segment using the error coding dispersal storage function to produce a new set of encoded data slices; and

selecting an encoded data slice of the new set of encoded data slices as the rebuilt first encoded data slice.

14. The computing device of claim 10, wherein the processing module further functions to generate the rebuilding information by:

retrieving, from the memory, a decode threshold number of encoded data slices of the set of encoded data slices, which excludes the first encoded data slice;

decoding the decode threshold number of encoded data slices in accordance with the error coding dispersal storage function to produce a recovered data segment; and

storing, in the memory, the recovered data segment as the rebuilding information.

15. The computing device of claim 14, wherein the processing module further functions to create the rebuilt first encoded data slice by:

encoding the recovered data segment using the error coding dispersal storage function to produce a new set of encoded data slices; and

selecting an encoded data slice of the new set of encoded data slices as the rebuilt first encoded data slice.

16. The computing device of claim 10, wherein the processing module further functions to generate the rebuilding information by:

receiving, via the interface, partially rebuilt slices from storage units of the DSN; and

storing, in the memory, the partially rebuilt slices as the rebuilding information.

17. The computing device of claim 16, wherein the processing module further functions to create the rebuilt first encoded data slice by:

creating the rebuilt first encoded data slice based on the partially rebuilt slices.

18. The computing device of claim 10, wherein the processing module is further operable to:

output, via the interface, the rebuilt first encoded data slice for storage in the DSN; and

output, via the interface, the rebuilt second encoded data slice for storage in the DSN.