Rebuilding data stored in a dispersed storage network

• US 10,108,492 B2
• Filed: 06/12/2014
• Issued: 10/23/2018
• Est. Priority Date: 07/30/2009
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg, Baptist, Andrew
• Primary Examiner(s): Vallecillo, Kyle
• Application Number:
  US14/302,582
• Publication Number:
  US 20140298135A1
• Time in Patent Office: 1,594 Days
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with 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]
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A method begins where a processing module queues, in a rebuild queue, identifiers of encoded data slices for rebuilding, where an encoded data slice is of a set of encoded data slices. The method continues with the processing module accessing the rebuild queue to retrieve a valid rebuild request and querying a storage unit of the set of storage units regarding a most current revision value of another encoded data slice of a most current dispersed storage error encoded revision level of a data segment. When a revision value of the encoded data slice compares favorably with the most current revision level of the other encoded data slice, the method continues with the processing module retrieving a decode threshold number of encoded data slices, reconstructing the data segment from the decode threshold number of encoded data slices, and generating a rebuilt encoded data slice from the reconstructed data segment.

Claims

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

queuing, in a rebuild queue, identifiers of encoded data slices for rebuilding, wherein an encoded data slice of the encoded data slices is of a set of encoded data slices, wherein a data segment is dispersed storage error encoded to produce the set of encoded data slices, wherein a decode threshold number of encoded data slices of the set of encoded data slices are required to recover the data segment, wherein the identifier of the encoded data slice includes a revision value corresponding to a revision level of the data segment, and wherein a set of storage units stores the set of encoded data slices;

accessing the rebuild queue based on the identifier of the encoded data slice to retrieve a valid rebuild request;

for the valid rebuild request, querying a storage unit of the set of storage units regarding a most current revision value of another encoded data slice of a most current dispersed storage error encoded revision level of the data segment, wherein an identifier for the other encoded data slice is not included in the rebuild queue; and

when the revision value of the encoded data slice compares favorably with the most current revision level of the other encoded data slice;

retrieving the decode threshold number of encoded data slices from at least some of the storage units of the set of storage units, wherein the decode threshold number of encoded data slices does not include the encoded data slice identified in the rebuild queue;

reconstructing the data segment from the decode threshold number of encoded data slices; and

generating a rebuilt encoded data slice from the reconstructed data segment.

2. The method of claim 1 further comprises:

queuing, in a slice queue, the rebuilt encoded data slice;

identifying one of the set of storage units to store the rebuilt encoded data slice to produce an identified storage unit;

determining whether to send the rebuilt encoded data slice to the identified storage unit; and

when the determination is to send the rebuilt encoded data slice to the identified storage unit, sending the rebuilt encoded data slice to the identified storage unit.

3. The method of claim 2, wherein the determining whether to send the rebuilt encoded data slice comprises:

requerying the storage unit of the set of storage units regarding the most current revision value of the other encoded data slice of the most current dispersed storage error encoded revision level of the data segment, wherein the identifier for the other encoded data slice is not included in the rebuild queue and is not in the slice queue; and

when the revision value of the encoded data slice compares favorably with the most current revision level of the other encoded data slice, sending the rebuilt encoded data slice to the identified storage unit.

4. The method of claim 3 further comprises:

when the revision value of the encoded data slice compares unfavorably with the most current revision level of the other encoded data slice, discarding the rebuilt encoded data slice.

5. The method of claim 1, wherein the querying the storage unit comprises:

sending a revision level listing request to the storage unit based on a slice name of the other encoded data slice;

receiving a revision level response that includes a list of revision levels of the other encoded data slice; and

ascertaining the most current revision value from the list of revision levels.

6. The method of claim 1, wherein the querying the storage unit comprises:

sending a most current revision level request to the storage unit based on a slice name of the other encoded data slice; and

receiving the most current revision value in response to the most current revision level request.

7. The method of claim 1 further comprises:

when the revision number of the encoded data slice compares unfavorably with the revision level of the other encoded data slice;

deleting the identifier of the encoded data slice from the rebuild queue.

8. The method of claim 1 further comprises:

determining the rebuild request to be valid based on the identifier being listed in the rebuild queue.

9. The method of claim 1 further comprises:

determining the rebuild request to be valid by;

determining whether the rebuild queue includes the encoded data slice with a second identifier that includes a different revision value corresponding to a more recent revision level of the data segment;

determining whether the rebuild queue includes another encoded data slice of the set of encoded data slices with a third identifier that includes the different revision value corresponding to a more recent revision level of the data segment;

when the rebuild queue includes the encoded data slice with a second identifier or includes the other encoded data slice with the third identifier, indicating that the rebuild request is invalid; and

when the rebuild queue does not include the encoded data slice with a second identifier and does not include the other encoded data slice with the third identifier, indicating that the rebuild request is valid.

10. A non-transitory computer readable storage medium having accessible therefrom a set of instructions interpretable by a processing module, the set of instructions being configured to cause the processing module to carry out operations for:

queuing, in a rebuild queue, identifiers of encoded data slices for rebuilding, wherein an encoded data slice of the encoded data slices is of a set of encoded data slices, wherein a data segment is dispersed storage error encoded to produce the set of encoded data slices, wherein a decode threshold number of encoded data slices of the set of encoded data slices are required to recover the data segment, wherein the identifier of the encoded data slice includes a revision value corresponding to a revision level of the data segment, and wherein a set of storage units stores the set of encoded data slices;

accessing the rebuild queue based on the identifier of the encoded data slice to retrieve a valid rebuild request;

for the valid rebuild request, querying a storage unit of the set of storage units regarding a most current revision value of another encoded data slice of a most current dispersed storage error encoded revision level of the data segment, wherein an identifier for the other encoded data slice is not included in the rebuild queue; and

when the revision value of the encoded data slice compares favorably with the most current revision level of the other encoded data slice;

retrieving the decode threshold number of encoded data slices from at least some of the storage units of the set of storage units, wherein the decode threshold number of encoded data slices does not include the encoded data slice identified in the rebuild queue;

reconstructing the data segment from the decode threshold number of encoded data slices; and

generating a rebuilt encoded data slice from the reconstructed data segment.

11. The storage medium of claim 10, wherein the set of instructions further being configured to cause the processing module to carry out operations for:

queuing, in a slice queue, the rebuilt encoded data slice;

identifying one of the set of storage units to store the rebuilt encoded data slice to produce an identified storage unit;

determining whether to send the rebuilt encoded data slice to the identified storage unit; and

when the determination is to send the rebuilt encoded data slice to the identified storage unit, sending the rebuilt encoded data slice to the identified storage unit.

12. The storage medium of claim 11, wherein the set of instructions further causes the processing module to carry out operations for the determining whether to send the rebuilt encoded data slice by:

requerying the storage unit of the set of storage units regarding the most current revision value of the other encoded data slice of the most current dispersed storage error encoded revision level of the data segment, wherein the identifier for the other encoded data slice is not included in the rebuild queue and is not in the slice queue; and

when the revision value of the encoded data slice compares favorably with the most current revision level of the other encoded data slice, sending the rebuilt encoded data slice to the identified storage unit.

13. The storage medium of claim 12, wherein the set of instructions further being configured to cause the processing module to carry out operations for:

when the revision value of the encoded data slice compares unfavorably with the most current revision level of the other encoded data slice, discarding the rebuilt encoded data slice.

14. The storage medium of claim 10, wherein the set of instructions further causes the processing module to carry out operations for the querying the storage unit by:

sending a revision level listing request to the storage unit based on a slice name of the other encoded data slice;

receiving a revision level response that includes a list of revision levels of the other encoded data slice; and

ascertaining the most current revision value from the list of revision levels.

15. The storage medium of claim 10, wherein the set of instructions further causes the processing module to carry out operations for the querying the storage unit by:

sending a most current revision level request to the storage unit based on a slice name of the other encoded data slice; and

receiving the most current revision value in response to the most current revision level request.

16. The storage medium of claim 10, wherein the set of instructions further being configured to cause the processing module to carry out operations for:

when the revision number of the encoded data slice compares unfavorably with the revision level of the other encoded data slice;

deleting the identifier of the encoded data slice from the rebuild queue.

17. The storage medium of claim 10, wherein the set of instructions further being configured to cause the processing module to carry out operations for:

determining the rebuild request to be valid based on the identifier being listed in the rebuild queue.

18. The storage medium of claim 10, wherein the set of instructions further being configured to cause the processing module to carry out operations for:

determining the rebuild request to be valid by;

determining whether the rebuild queue includes the encoded data slice with a second identifier that includes a different revision value corresponding to a more recent revision level of the data segment;

determining whether the rebuild queue includes another encoded data slice of the set of encoded data slices with a third identifier that includes the different revision value corresponding to a more recent revision level of the data segment;

when the rebuild queue includes the encoded data slice with a second identifier or includes the other encoded data slice with the third identifier, indicating that the rebuild request is invalid; and

when the rebuild queue does not include the encoded data slice with a second identifier and does not include the other encoded data slice with the third identifier, indicating that the rebuild request is valid.

19. A computing device comprises:

an interface;

memory; and

a processing module operably coupled to the interface and the memory, wherein the processing module is operable to;

queue, in a rebuild queue, identifiers of encoded data slices for rebuilding, wherein an encoded data slice of the encoded data slices is of a set of encoded data slices, wherein a data segment is dispersed storage error encoded to produce the set of encoded data slices, wherein a decode threshold number of encoded data slices of the set of encoded data slices are required to recover the data segment, wherein the identifier of the encoded data slice includes a revision value corresponding to a revision level of the data segment, and wherein a set of storage units stores the set of encoded data slices;

access the rebuild queue based on the identifier of the encoded data slice to retrieve a valid rebuild request;

for the valid rebuild request, query a storage unit of the set of storage units regarding a most current revision value of another encoded data slice of a most current dispersed storage error encoded revision level of the data segment, wherein an identifier for the other encoded data slice is not included in the rebuild queue; and

when the revision value of the encoded data slice compares favorably with the most current revision level of the other encoded data slice;

retrieve the decode threshold number of encoded data slices from at least some of the storage units of the set of storage units, wherein the decode threshold number of encoded data slices does not include the encoded data slice identified in the rebuild queue;

reconstruct the data segment from the decode threshold number of encoded data slices; and

generate a rebuilt encoded data slice from the reconstructed data segment.

20. The computing device of claim 19, wherein the processing module further functions to:

queue, in a slice queue, the rebuilt encoded data slice;

identify one of the set of storage units to store the rebuilt encoded data slice to produce an identified storage unit;

determine whether to send the rebuilt encoded data slice to the identified storage unit; and

when the determination is to send the rebuilt encoded data slice to the identified storage unit, send the rebuilt encoded data slice to the identified storage unit.

21. The computing device of claim 20, wherein the processing module further functions to determine whether to send the rebuilt encoded data slice by:

requerying the storage unit of the set of storage units regarding the most current revision value of the other encoded data slice of the most current dispersed storage error encoded revision level of the data segment, wherein the identifier for the other encoded data slice is not included in the rebuild queue and is not in the slice queue; and

when the revision value of the encoded data slice compares favorably with the most current revision level of the other encoded data slice, sending the rebuilt encoded data slice to the identified storage unit.

22. The computing device of claim 21, wherein the processing module further functions to:

when the revision value of the encoded data slice compares unfavorably with the most current revision level of the other encoded data slice, discard the rebuilt encoded data slice.

23. The computing device of claim 19, wherein the processing module further functions to query the storage unit by:

sending a revision level listing request to the storage unit based on a slice name of the other encoded data slice;

receiving a revision level response that includes a list of revision levels of the other encoded data slice; and

ascertaining the most current revision value from the list of revision levels.

24. The computing device of claim 19, wherein the processing module further functions to query the storage unit by:

sending a most current revision level request to the storage unit based on a slice name of the other encoded data slice; and

receiving the most current revision value in response to the most current revision level request.

25. The computing device of claim 19, wherein the processing module further functions to:

when the revision number of the encoded data slice compares unfavorably with the revision level of the other encoded data slice;

delete the identifier of the encoded data slice from the rebuild queue.

26. The computing device of claim 19, wherein the processing module further functions to:

determine the rebuild request to be valid based on the identifier being listed in the rebuild queue.

27. The computing device of claim 19, wherein the processing module further functions to:

determine the rebuild request to be valid by;

determining whether the rebuild queue includes the encoded data slice with a second identifier that includes a different revision value corresponding to a more recent revision level of the data segment;

determining whether the rebuild queue includes another encoded data slice of the set of encoded data slices with a third identifier that includes the different revision value corresponding to a more recent revision level of the data segment;

when the rebuild queue includes the encoded data slice with a second identifier or includes the other encoded data slice with the third identifier, indicating that the rebuild request is invalid; and

when the rebuild queue does not include the encoded data slice with a second identifier and does not include the other encoded data slice with the third identifier, indicating that the rebuild request is valid.