USING DISPERSED QUEUES FOR REBUILDING FUNCTIONS AND PRIORITIZATION

• US 20180060351A1
• Filed: 11/06/2017
• Published: 03/01/2018
• Est. Priority Date: 12/05/2012
• Status: Abandoned Application

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Leggette, Wesley B., Resch, Jason K.
• Application Number:
  US15/804,069
• Publication Number:
  US 20180060351A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/182 Distributed file systems

Abstract

A method includes scanning, by a scanning module, from plurality of sets of encoded data slices to plurality of sets of encoded data slices, to identify encoded data slices that are in need of rebuilding. The method further includes adding, by the scanning module, the identified encoded data slices into a first level rebuilding queue. The method further includes analyzing, by an analyzing module, the identified encoded data slices based on a rebuilding prioritization function to establish a prioritization for the identified encoded data slices. The method further includes transferring, by the analyzing module, a first group of encoded data slices into a first priority rebuilding queue and a second group of encoded data slices into a second priority rebuilding queue based on the analyzing. The method further includes rebuilding, by a rebuilding module, the first and second group of encoded data slices based on a rebuilding prioritization protocol.

Claims

1. A method for execution by one or more computing devices in a dispersed storage network (DSN), the method comprises:

scanning, by a scanning module of a first computing device of the one or more computing devices, from one or more plurality of sets of encoded data slices to other one or more plurality of sets of encoded data slices, to identify encoded data slices that are in need of rebuilding;

adding, by the scanning module, the identified encoded data slices into a first level rebuilding queue;

analyzing, by an analyzing module of the first computing device or a second computing device of the one or more computing devices, the identified encoded data slices in the first level rebuilding queue based on a rebuilding prioritization function to establish a prioritization for at least some of the identified encoded data slices in the first level rebuilding queue;

transferring, by the analyzing module, a first group of encoded data slices in the first level rebuilding queue into a first priority rebuilding queue based on the analyzing;

transferring, by the analyzing module, a second group of encoded data slices in the first level rebuilding queue into a second priority rebuilding queue based on the analyzing, wherein the first rebuilding priority queue has priority over the second priority rebuilding queue; and

rebuilding, by a rebuilding module of the first computing device, the second computing device, or a third computing device of the one or more computing devices, the first and second group of encoded data slices based on a rebuilding prioritization protocol.

2. The method of claim 1, wherein the scanning comprises:

sending, by the scanning module, list requests to storage units of the DSN, wherein the list requests include a request to list slice names of encoded data slices being stored by the respective storage units;

receiving, by the scanning module, list responses from the storage units, wherein the list responses includes a list of slices names of encoded data slices that are stored by the respective storage units; and

interpreting, by the scanning module, the list of slices names of encoded data slices that are stored by the respective storage units to identify the encoded data slices that are in need of rebuilding.

3. The method of claim 1, wherein the rebuilding prioritization function comprises:

a loss of data risk analysis function that is executed on a set of encoded data slices by set of encoded data slices basis.

4. The method of claim 3 further comprises:

for a set of encoded data slices of the one or more plurality of sets of encoded data slices or of the other one or more plurality of sets of encoded data slices;

determining a pillar number, a decode threshold number, a number of encoded data slices in the set of encoded data slices that are in need of rebuilding;

determining a redundancy value based on a difference between the pillar number and the decode threshold number;

determining a slice risk value based on a difference between the redundancy value and the number of encoded data slices in the set of encoded data slices that are in need of rebuilding;

determining storage unit reliability of a set of storage units of the DSN that is storing the set of encoded data slices;

generating a loss of data risk indication based on the slice risk value and the storage unit reliability; and

when the loss of data risk indication is above a threshold, placing one or more encoded data slices of the set of encoded data slices that are in need of rebuilding in the first group of encoded data slices.

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

determining, by the rebuilding module, whether the time to rebuild the first group of encoded data slices will exceed a priority rebuild time threshold;

when the time to rebuild the first group of encoded data slices will exceed the priority rebuild time threshold, allocating, by the rebuilding module, a sub-group of the first group of encoded data slices to a second rebuilding module for rebuilding, wherein the second rebuilding module operates on the first computing device, the second computing device, the third computing device, or a fourth computing device of the one or more computing devices.

6. The method of claim 1, wherein the rebuilding prioritization protocol comprises one of:

rebuilding the first group of encoded data slices before rebuilding the second group of encoded data slices;

rebuilding the first and second group of encoded data slices in an imbalanced round robin manner that favors rebuilding the first group of encoded data slices; and

rebuilding the first and second group of encoded data slices in accordance with an anti-starvation protocol.

7. The method of claim 1 further comprises:

when an encoded data slice has been in the second group of encoded data slices for a predetermined period of time, re-analyzing the encoded data slice based on the rebuilding prioritization function to determine whether the encoded data slice should be moved to the first group of encoded data slices; and

when determined to move the encoded data slice to the first group of encoded data slices, transferring the encoded data slice to the first group of encoded data slices.

8. The method of claim 1 further comprises:

transferring, by the analyzing module, a third group of encoded data slices in the first level rebuilding queue into a third priority rebuilding queue based on the analyzing, wherein the second rebuilding priority queue has priority over the third priority rebuilding queue; and

rebuilding, by the rebuilding module, the first, second, and third group of encoded data slices based on a rebuilding prioritization protocol.

9. A computer readable memory device comprises:

a first memory section that stores operational instructions that, when executed by one or more computing devices in a dispersed storage network (DSN), causes a scanning module of a first computing device of the one or more computing devices to;

scan, from one or more plurality of sets of encoded data slices to other one or more plurality of sets of encoded data slices, to identify encoded data slices that are in need of rebuilding;

add the identified encoded data slices into a first level rebuilding queue;

a second memory section that stores operational instructions that, when executed by the one or more computing devices, causes an analyzing module of the first computing device or a second computing device of the one or more computing devices to;

analyze the identified encoded data slices in the first level rebuilding queue based on a rebuilding prioritization function to establish a prioritization for at least some of the identified encoded data slices in the first level rebuilding queue;

transfer a first group of encoded data slices in the first level rebuilding queue into a first priority rebuilding queue based on the analyzing;

transfer a second group of encoded data slices in the first level rebuilding queue into a second priority rebuilding queue based on the analyzing, wherein the first rebuilding priority queue has priority over the second priority rebuilding queue; and

a third memory section that stores operational instructions that, when executed by the one or more computing devices, causes a rebuilding module of the first computing device, the second computing device, or a third computing device of the one or more computing devices to;

rebuild the first and second group of encoded data slices based on a rebuilding prioritization protocol.

10. The computer readable memory device of claim 9, wherein the first memory section further stores operational instructions that causes the scanning module to scan by:

sending list requests to storage units of the DSN, wherein the list requests include a request to list slice names of encoded data slices being stored by the respective storage units;

receiving list responses from the storage units, wherein the list responses includes a list of slices names of encoded data slices that are stored by the respective storage units; and

interpreting the list of slices names of encoded data slices that are stored by the respective storage units to identify the encoded data slices that are in need of rebuilding.

11. The computer readable memory device of claim 9, wherein the rebuilding prioritization function comprises:

a loss of data risk analysis function that is executed on a set of encoded data slices by set of encoded data slices basis.

12. The computer readable memory device of claim 11, wherein the third memory section further stores operational instructions that causes the rebuilding module to rebuild by:

for a set of encoded data slices of the one or more plurality of sets of encoded data slices or of the other one or more plurality of sets of encoded data slices;

determining a pillar number, a decode threshold number, a number of encoded data slices in the set of encoded data slices that are in need of rebuilding;

determining a redundancy value based on a difference between the pillar number and the decode threshold number;

determining a slice risk value based on a difference between the redundancy value and the number of encoded data slices in the set of encoded data slices that are in need of rebuilding;

determining storage unit reliability of a set of storage units of the DSN that is storing the set of encoded data slices;

generating a loss of data risk indication based on the slice risk vale and the storage unit reliability; and

when the loss of data risk indication is above a threshold, placing one or more encoded data slices of the set of encoded data slices that are in need of rebuilding in the first group of encoded data slices.

13. The computer readable memory device of claim 9, wherein the third memory section further stores operational instructions that causes the rebuilding module to rebuild by:

determining whether the time to rebuild the first group of encoded data slices will exceed a priority rebuild time threshold;

when the time to rebuild the first group of encoded data slices will exceed the priority rebuild time threshold, allocating a sub-group of the first group of encoded data slices to a second rebuilding module for rebuilding, wherein the second rebuilding module operates on the first computing device, the second computing device, the third computing device, or a fourth computing device of the one or more computing devices.

14. The computer readable memory device of claim 9, wherein the rebuilding prioritization protocol comprises one of:

rebuilding the first group of encoded data slices before rebuilding the second group of encoded data slices;

rebuilding the first and second group of encoded data slices in an imbalanced round robin manner that favors rebuilding the first group of encoded data slices; and

rebuilding the first and second group of encoded data slices in accordance with an anti-starvation protocol.

15. The computer readable memory device of claim 9, wherein the second memory section further stores operational instructions that causes the analyzing module to:

when an encoded data slice has been in the second group of encoded data slices for a predetermined period of time, re-analyze the encoded data slice based on the rebuilding prioritization function to determine whether the encoded data slice should be moved to the first group of encoded data slices; and

when determined to move the encoded data slice to the first group of encoded data slices, transfer the encoded data slice to the first group of encoded data slices.

16. The computer readable memory device of claim 9 further comprises:

the second memory section further stores operational instructions that causes the analyzing module to;

transfer a third group of encoded data slices in the first level rebuilding queue into a third priority rebuilding queue based on the analyzing, wherein the second rebuilding priority queue has priority over the third priority rebuilding queue; and

the third memory section further stores operational instructions that causes the rebuilding module to;

rebuild the first, second, and third group of encoded data slices based on a rebuilding prioritization protocol.