Rebuilding encoded data slices in a dispersed storage network

• US 10,078,472 B2
• Filed: 12/30/2015
• Issued: 09/18/2018
• Est. Priority Date: 02/27/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Cocagne, Thomas Darrel
• Primary Examiner(s): Chung, Phung M
• Application Number:
  US14/984,024
• Publication Number:
  US 20160253240A1
• Time in Patent Office: 993 Days
• 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/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A method for a computing device to rebuild a plurality of to-be rebuilt encoded data slices in a dispersed storage network (DSN) begins with the computing device, for each set of encoded data slices of a plurality of sets of encoded data slices that includes at least one of the plurality of to-be rebuilt encoded data slices, determining a cumulative memory health for memory devices of storage units storing other encoded data slices of the respective set of encoded data slices and determining a probability of data loss. The method continues with the computing device prioritizing rebuilding based on the probability of data loss for each set of encoded data slices and rebuilding, in accordance with the prioritizing, a first to-be rebuilt encoded data slice of the plurality of to-be rebuilt encoded data slices to produce a first rebuilt encoded data slice.

Claims

1. A method for a computing device to rebuild a plurality of to-be rebuilt encoded data slices in a dispersed storage network (DSN), the method comprises:

for each set of encoded data slices of a plurality of sets of encoded data slices that includes at least one of the plurality of to-be rebuilt encoded data slices;

determining a cumulative memory health for memory devices of storage units storing other encoded data slices of a respective set of encoded data slices; and

determining a probability of data loss based on the cumulative memory health, respective dispersed storage error encoding parameters, and a number of encoded data slices requiring rebuilding in the respective set of encoded data slices;

prioritizing rebuilding of the plurality of to-be rebuilt encoded data slices based on the probability of data loss for each set of encoded data slices of the plurality of sets of encoded data slices; and

rebuilding, in accordance with the prioritizing, a first to-be rebuilt encoded data slice of the plurality of to-be rebuilt encoded data slices to produce a first rebuilt encoded data slice.

2. The method of claim 1, wherein the determining the cumulative memory health comprises:

for each of the memory devices of the storage units storing the other encoded data slices, determining whether a respective memory device is in a soft failure mode or a non-failure mode;

for each memory device in the soft failure mode, determining a soft failure mode level; and

calculating the cumulative memory health based on a ratio of memory devices in the soft failure mode to the memory devices in the non-failure mode and weighting the ratio based on the soft failure modes levels.

3. The method of claim 1, wherein the determining the probability of data loss comprises:

determining a number corresponding to the other encoded data slices;

determining a total number of encoded data slices in the respective set of encoded data slices from the dispersed storage error encoding parameters;

determining a decode threshold number of encoded data slices of the respective set of encoded data slices from the dispersed storage error encoding parameters;

determining a current redundancy number of encoded data slices based on the total number minus the decode threshold number and minus the number of encoded data slices requiring rebuilding; and

weighting the current redundancy number based on the cumulative memory health to produce the probability of data loss.

4. The method of claim 1 further comprises:

for a set of encoded data slices of the plurality of sets of encoded data slices having multiple encoded data slices requiring rebuilding;

determining a first probability of data loss based on the cumulative memory health, the respective dispersed storage error encoding parameters, and the multiple encoded data slices requiring rebuilding in the respective set of encoded data slices; and

determining a second probability of data loss based on the cumulative memory health, the respective dispersed storage error encoding parameters, and the multiple encoded data slices requiring rebuilding less one of the multiple encoded data slices requiring rebuilding;

rebuilding the one of the multiple encoded data slices requiring rebuilding in accordance with the first probability of data loss; and

rebuilding a second one of the multiple encoded data slices requiring rebuilding in accordance with the second probability of data loss.

5. The method of claim 1 further comprises:

identifying a new memory device with one of the storage units based on a favorable memory health of the new memory device for storing the first rebuilt encoded data slice.

6. The method of claim 1 further comprises:

identifying new to-be rebuilt encoded data slices;

updating the plurality of sets of encoded data slices to include each new set of encoded data slices including at least one of the new to-be rebuilt encoded data slices and to exclude sets of the plurality of sets of encoded data slices for which the at least one of the plurality of to-be rebuilt encoded data slices has been rebuilt to produce an updated plurality of sets of encoded data slices;

for each set of encoded data slices of the updated plurality of sets of encoded data slices;

determining a new cumulative memory health for memory devices of storage units storing other encoded data slices of the respective set of encoded data slices; and

determining a new probability of data loss based on the new cumulative memory health, the respective dispersed storage error encoding parameters, and the number of encoded data slices requiring rebuilding in the respective set of encoded data slices;

updating prioritizing rebuilding of remaining to-be rebuilt encoded data slices of the plurality of to-be rebuilt encoded data slices and of the new to-be rebuilt encoded data slices based on the new probability of data loss for each set of encoded data slices of the updated plurality of sets of encoded data slices; and

rebuilding, in accordance with the updated prioritizing, a second to-be rebuilt encoded data slice of the remaining to-be rebuilt encoded data slices of the plurality of to-be rebuilt encoded data slices and of the new to-be rebuilt encoded data slices.

7. A non-transitory 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;

for each set of encoded data slices of a plurality of sets of encoded data slices that includes at least one of a plurality of to-be rebuilt encoded data slices;

determine a cumulative memory health for memory devices of storage units storing other encoded data slices of a respective set of encoded data slices; and

determine a probability of data loss based on the cumulative memory health, respective dispersed storage error encoding parameters, and a number of encoded data slices requiring rebuilding in the respective set of encoded data slices;

prioritize rebuilding of the plurality of to-be rebuilt encoded data slices based on the probability of data loss for each set of encoded data slices of the plurality of sets of encoded data slices; and

rebuild, in accordance with the prioritizing, a first to-be rebuilt encoded data slice of the plurality of to-be rebuilt encoded data slices to produce a first rebuilt encoded data slice.

8. The non-transitory computer readable storage medium of claim 7, 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 cumulative memory health by:

for each of the memory devices of the storage units storing the other encoded data slices, determining whether a respective memory device is in a soft failure mode or a non-failure mode;

for each memory device in the soft failure mode, determining a soft failure mode level; and

calculating the cumulative memory health based on a ratio of memory devices in the soft failure mode to the memory devices in the non-failure mode and weighting the ratio based on the soft failure modes levels.

9. The non-transitory computer readable storage medium of claim 7, 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 probability of data loss by:

determining a number corresponding to the other encoded data slices;

determining a total number of encoded data slices in the respective set of encoded data slices from the dispersed storage error encoding parameters;

determining a decode threshold number of encoded data slices of the respective set of encoded data slices from the dispersed storage error encoding parameters;

determining a current redundancy number of encoded data slices based on the total number minus the decode threshold number and minus the number of encoded data slices requiring rebuilding; and

weighting the current redundancy number based on the cumulative memory health to produce the probability of data loss.

10. The non-transitory computer readable storage medium of claim 7 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;

for a set of encoded data slices of the plurality of sets of encoded data slices having multiple encoded data slices requiring rebuilding;

determine a first probability of data loss based on the cumulative memory health, the respective dispersed storage error encoding parameters, and the multiple encoded data slices requiring rebuilding in the respective set of encoded data slices; and

determine a second probability of data loss based on the cumulative memory health, the respective dispersed storage error encoding parameters, and the multiple encoded data slices requiring rebuilding less one of the multiple encoded data slices requiring rebuilding;

rebuild the one of the multiple encoded data slices requiring rebuilding in accordance with the first probability of data loss; and

rebuild a second one of the multiple encoded data slices requiring rebuilding in accordance with the second probability of data loss.

11. The non-transitory computer readable storage medium of claim 7 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;

identify a new memory device with one of the storage units based on a favorable memory health of the new memory device for storing the first rebuilt encoded data slice.

12. The non-transitory computer readable storage medium of claim 7 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;

identify new to-be rebuilt encoded data slices;

update the plurality of sets of encoded data slices to include each new set of encoded data slices including at least one of the new to-be rebuilt encoded data slices and to exclude sets of the plurality of sets of encoded data slices for which the at least one of the plurality of to-be rebuilt encoded data slices has been rebuilt to produce an updated plurality of sets of encoded data slices;

for each set of encoded data slices of the updated plurality of sets of encoded data slices;

determine a new cumulative memory health for memory devices of storage units storing other encoded data slices of the respective set of encoded data slices; and

determine a new probability of data loss based on the new cumulative memory health, the respective dispersed storage error encoding parameters, and the number of encoded data slices requiring rebuilding in the respective set of encoded data slices;

update prioritizing rebuilding of remaining to-be rebuilt encoded data slices of the plurality of to-be rebuilt encoded data slices and of the new to-be rebuilt encoded data slices based on the new probability of data loss for each set of encoded data slices of the updated plurality of sets of encoded data slices; and

rebuild, in accordance with the updated prioritizing, a second to-be rebuilt encoded data slice of the remaining to-be rebuilt encoded data slices of the plurality of to-be rebuilt encoded data slices and of the new to-be rebuilt encoded data slices.

13. A computing device of a group of computing devices of a dispersed storage network (DSN), the computing device comprises:

an interface;

a local memory; and

a processing module operably coupled to the interface and the local memory, wherein the processing module functions to;

for each set of encoded data slices of a plurality of sets of encoded data slices that includes at least one of a plurality of to-be rebuilt encoded data slices;

determine a cumulative memory health for memory devices of storage units storing other encoded data slices of a respective set of encoded data slices; and

determine a probability of data loss based on the cumulative memory health, respective dispersed storage error encoding parameters, and a number of encoded data slices requiring rebuilding in the respective set of encoded data slices;

prioritize rebuilding of the plurality of to-be rebuilt encoded data slices based on the probability of data loss for each set of encoded data slices of the plurality of sets of encoded data slices; and

rebuild, in accordance with the prioritizing, a first to-be rebuilt encoded data slice of the plurality of to-be rebuilt encoded data slices to produce a first rebuilt encoded data slice.

14. The computing device of claim 13, wherein the processing module functions to determine the cumulative memory health by:

for each of the memory devices of the storage units storing the other encoded data slices, determining whether a respective memory device is in a soft failure mode or a non-failure mode;

for each memory device in the soft failure mode, determining a soft failure mode level; and

calculating the cumulative memory health based on a ratio of memory devices in the soft failure mode to the memory devices in the non-failure mode and weighting the ratio based on the soft failure modes levels.

15. The computing device of claim 13, wherein the processing module functions to determine the probability of data loss by:

determining a number corresponding to the other encoded data slices;

determining a total number of encoded data slices in the respective set of encoded data slices from the dispersed storage error encoding parameters;

determining a decode threshold number of encoded data slices of the respective set of encoded data slices from the dispersed storage error encoding parameters;

determining a current redundancy number of encoded data slices based on the total number minus the decode threshold number and minus the number of encoded data slices requiring rebuilding; and

weighting the current redundancy number based on the cumulative memory health to produce the probability of data loss.

16. The computing device of claim 13, wherein the processing module further functions to:

for a set of encoded data slices of the plurality of sets of encoded data slices having multiple encoded data slices requiring rebuilding;

determine a first probability of data loss based on the cumulative memory health, the respective dispersed storage error encoding parameters, and the multiple encoded data slices requiring rebuilding in the respective set of encoded data slices; and

determine a second probability of data loss based on the cumulative memory health, the respective dispersed storage error encoding parameters, and the multiple encoded data slices requiring rebuilding less one of the multiple encoded data slices requiring rebuilding;

rebuild the one of the multiple encoded data slices requiring rebuilding in accordance with the first probability of data loss; and

rebuild a second one of the multiple encoded data slices requiring rebuilding in accordance with the second probability of data loss.

17. The computing device of claim 13, wherein the processing module further functions to:

identify a new memory device with one of the storage units based on a favorable memory health of the new memory device for storing the first rebuilt encoded data slice.

18. The computing device of claim 13, wherein the processing module further functions to:

identify new to-be rebuilt encoded data slices;

update the plurality of sets of encoded data slices to include each new set of encoded data slices including at least one of the new to-be rebuilt encoded data slices and to exclude sets of the plurality of sets of encoded data slices for which the at least one of the plurality of to-be rebuilt encoded data slices has been rebuilt to produce an updated plurality of sets of encoded data slices;

for each set of encoded data slices of the updated plurality of sets of encoded data slices;

determine a new cumulative memory health for memory devices of storage units storing other encoded data slices of the respective set of encoded data slices; and

determine a new probability of data loss based on the new cumulative memory health, the respective dispersed storage error encoding parameters, and the number of encoded data slices requiring rebuilding in the respective set of encoded data slices;

update prioritizing rebuilding of remaining to-be rebuilt encoded data slices of the plurality of to-be rebuilt encoded data slices and of the new to-be rebuilt encoded data slices based on the new probability of data loss for each set of encoded data slices of the updated plurality of sets of encoded data slices; and

rebuild, in accordance with the updated prioritizing, a second to-be rebuilt encoded data slice of the remaining to-be rebuilt encoded data slices of the plurality of to-be rebuilt encoded data slices and of the new to-be rebuilt encoded data slices.