SELECTING STORAGE UNITS TO REBUILD AN ENCODED DATA SLICE

• US 20140331100A1
• Filed: 07/20/2014
• Published: 11/06/2014
• Est. Priority Date: 11/24/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Dhuse, Greg, Baptist, Andrew, Resch, Jason K.
• Granted Patent: US 9,270,298 B2
• Time in Patent Office: Days
• US Class Current: 714/752
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• 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: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H03M 13/1105 Decoding

Abstract

A method begins with a processing module of a dispersed storage network (DSN) identifying an encoded data slice of a set of encoded data slices that requires rebuilding and identifying storage units of the DSN that store the set of encoded data slices. The method continues with the processing module determining a rebuilding metric regarding the identified encoded data slice and selecting a sub-set of the storage units for retrieving a decode threshold number of encoded data slices of the set of encoded data slices based on the rebuilding metric. When the decode threshold number of encoded data slices have been retrieved, the method continues with the processing module decoding the decode threshold number of encoded data slices to produce a reconstructed data segment and generating a rebuilt encoded data slice from the reconstructed data segment.

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:

identifying an encoded data slice of a set of encoded data slices that requires rebuilding;

identifying storage units of the DSN that store the set of encoded data slices;

determining a rebuilding metric regarding the identified encoded data slice;

selecting a sub-set of the storage units for retrieving a decode threshold number of encoded data slices of the set of encoded data slices based on the rebuilding metric, wherein a data segment of data was error encoded to produce the set of encoded data slices, wherein the decode threshold number of encoded data slices is required to recover the data segment, and wherein the decode threshold number of encoded data slices does not include the identified encoded data slice;

when the decode threshold number of encoded data slices have been retrieved, decoding the decode threshold number of encoded data slices to produce a reconstructed data segment; and

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

2. The method of claim 1 further comprises:

the determining the rebuilding metric including determining response attributes of the storage units regarding encoded data slice retrievals; and

selecting the sub-set of storage units based on favorable response attributes.

3. The method of claim 2, wherein one of the response attributes for one of the storage units comprises one or more of:

a ping time response;

historical read response times;

geographic proximity to the one or more computing devices;

data throughput;

reliability; and

up-time.

4. The method of claim 1, wherein the determining the rebuilding metric comprises:

accessing a look up table based on the identified encoded data slice to determine an optimized rebuilding process as the rebuilding metric.

5. The method of claim 1 further comprises:

when the decode threshold number of encoded data slices have not been retrieved within a given time period;

modifying the rebuilding metric; and

selecting a new sub-set of the storage units for retrieving the decode threshold number of encoded data slices based on the modified rebuilding metric.

6. The method of claim 1, wherein the generating the rebuilt encoded data slice comprises:

dispersed storage error encoding the reconstructed data segment to produce a new set of encoded data slices; and

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

7. The method of claim 1, wherein the generating the rebuilt encoded data slice comprises:

encoding the reconstructed data segment to produce the rebuilt encoded data slice.

8. The method of claim 1 further comprises:

outputting, for storage in one of the storage units, the rebuilt encoded data slice.

9. A computer readable storage medium comprises:

at least one memory section that stores operational instructions that, when executed by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), causes the one or more computing devices to;

identify an encoded data slice of a set of encoded data slices that requires rebuilding;

identify storage units of the DSN that store the set of encoded data slices;

determine a rebuilding metric regarding the identified encoded data slice;

select a sub-set of the storage units for retrieving a decode threshold number of encoded data slices of the set of encoded data slices based on the rebuilding metric, wherein a data segment of data was error encoded to produce the set of encoded data slices, wherein the decode threshold number of encoded data slices is required to recover the data segment, and wherein the decode threshold number of encoded data slices does not include the identified encoded data slice;

when the decode threshold number of encoded data slices have been retrieved, decode the decode threshold number of encoded data slices to produce a reconstructed data segment; and

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

10. The computer readable storage medium of claim 9 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

determine the rebuilding metric to include determining response attributes of the storage units regarding encoded data slice retrievals; and

select the sub-set of storage units based on favorable response attributes.

11. The computer readable storage medium of claim 10, wherein one of the response attributes for one of the storage units comprises one or more of:

a ping time response;

historical read response times;

geographic proximity to the one or more computing devices;

data throughput;

reliability; and

up-time.

12. The computer readable storage medium of claim 9, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to determine the rebuilding metric by:

accessing a look up table based on the identified encoded data slice to determine an optimized rebuilding process as the rebuilding metric.

13. The computer readable storage medium of claim 9 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

when the decode threshold number of encoded data slices have not been retrieved within a given time period;

modify the rebuilding metric; and

select a new sub-set of the storage units for retrieving the decode threshold number of encoded data slices based on the modified rebuilding metric.

14. The computer readable storage medium of claim 9, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to generate the rebuilt encoded data slice by:

dispersed storage error encoding the reconstructed data segment to produce a new set of encoded data slices; and

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

15. The computer readable storage medium of claim 9, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to generate the rebuilt encoded data slice by:

encoding the reconstructed data segment to produce the rebuilt encoded data slice.

16. The computer readable storage medium of claim 9 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

output, for storage in one of the storage units, the rebuilt encoded data slice.

17. A computing device of a dispersed storage network (DSN), wherein the computing device comprises:

an interface; and

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

identify an encoded data slice of a set of encoded data slices that requires rebuilding;

identify storage units of the DSN that store the set of encoded data slices;

determine a rebuilding metric regarding the identified encoded data slice;

select a sub-set of the storage units for retrieving a decode threshold number of encoded data slices of the set of encoded data slices based on the rebuilding metric, wherein a data segment of data was error encoded to produce the set of encoded data slices, wherein the decode threshold number of encoded data slices is required to recover the data segment, and wherein the decode threshold number of encoded data slices does not include the identified encoded data slice;

when the decode threshold number of encoded data slices have been retrieved, decode the decode threshold number of encoded data slices to produce a reconstructed data segment; and

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

18. The computing device of claim 17 further comprises:

the processing module is further operable to;

determine the rebuilding metric by determining response attributes of the storage units regarding encoded data slice retrievals; and

select the sub-set of storage units based on favorable response attributes.

19. The computing device of claim 18, wherein one of the response attributes for one of the storage units comprises one or more of:

a ping time response;

historical read response times;

geographic proximity to the one or more computing devices;

data throughput;

reliability; and

up-time.

20. The computing device of claim 17, wherein the processing module functions to determine the rebuilding metric by:

accessing a look up table based on the identified encoded data slice to determine an optimized rebuilding process as the rebuilding metric.

21. The computing device of claim 17 further comprises:

the processing module is further operable to;

when the decode threshold number of encoded data slices have not been retrieved within a given time period;

modify the rebuilding metric; and

select a new sub-set of the storage units for retrieving the decode threshold number of encoded data slices based on the modified rebuilding metric.

22. The computing device of claim 17, wherein the processing module functions to generate the rebuilt encoded data slice by:

dispersed storage error encoding the reconstructed data segment to produce a new set of encoded data slices; and

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

23. The computing device of claim 17, wherein the processing module functions to generate the rebuilt encoded data slice by:

encoding the reconstructed data segment to produce the rebuilt encoded data slice.

24. The computing device of claim 17 further comprises:

the processing module is further operable to;

output, via the interface, for storage in one of the storage units, the rebuilt encoded data slice.