Optimally apportioning rebuilding resources

• US 10,498,823 B2
• Filed: 12/11/2017
• Issued: 12/03/2019
• Est. Priority Date: 01/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Khadiwala, Ravi V., Wozniak, Ethan S., Resch, Jason K., Cocagne, Thomas D.
• Primary Examiner(s): Alphonse, Fritz
• Application Number:
  US15/837,401
• Publication Number:
  US 20180103102A1
• Time in Patent Office: 722 Days
• Field of Search: 714759, 714762, 714758
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• 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]

Abstract

A distributed storage network (DSN) stores encoded data slices in storage units based on DSN address ranges. A rebuilding module selects a range of addresses for potential rebuilding activities. A rebuilding activity capacity level for the address range is determined, and using that information a maximum number of rebuilding modules to be assigned to the selected address range is determined. Distributed agreement protocol (DAP) function weights of the plurality of potential rebuilding modules are determined, and those weights are used by the DAP function to produce a rank ordered list of rebuilding module identifiers. Top ranked rebuilding modules are selected for use in rebuilding activities within the selected address range.

Claims

1. A method for use in a distributed storage network (DSN) storing encoded data slices in one or more storage units based on DSN address ranges of the encoded data slices, the method comprising:

selecting, by a processor and associated memory configured to implement a rebuilding module of a plurality of rebuilding modules, a selected DSN address range of a plurality of DSN address ranges for potential rebuilding activities;

determining, by the rebuilding module, a rebuilding activity capacity level for the selected DSN address range;

determining, by the rebuilding module, a maximum number of rebuilding modules for assignment to the selected DSN address range based on the rebuilding activity capacity level;

identifying, by the rebuilding module, distributed agreement protocol (DAP) function weights of the plurality of rebuilding modules

performing, by the rebuilding module, a DAP function on a representation of the DSN address range utilizing the DAP function weights of the plurality of rebuilding modules to produce a rank ordered list of rebuilding module identifiers; and

in response to a rebuilding module identifier of the rebuilding module being included within a top-ranked number of rebuilding module identifiers of the rank ordered list, facilitate, by the rebuilding module, rebuilding activities within the DSN address range.

2. The method of claim 1, wherein determining the rebuilding activity capacity level for the selected DSN address range includes:

determining a rebuild capacity of storage units storing encoded data slices within the selected DSN address range.

3. The method of claim 1, wherein determining the rebuilding activity capacity level for the selected DSN address range includes:

evaluating historical rebuilding capacity levels associated with the selected DSN address range.

4. The method of claim 1, wherein determining the rebuilding activity capacity level for the selected DSN address range includes:

initiating a rebuild test; and

interpreting test results of the rebuild test.

5. The method of claim 1, wherein facilitating rebuilding activities includes:

identifying one or more rebuilding tasks; and

initiating execution of the one or more rebuilding tasks.

6. The method of claim 5, further comprising:

updating historical records to include actual rebuilding activity loading levels corresponding to execution of the one or more rebuilding tasks.

7. The method of claim 5, further comprising:

updating the DAP function weights associated with the rebuilding module to reflect an updated rebuilding activity capacity level.

8. A distributed storage network (DSN) storing encoded data slices in one or more storage units based on DSN address ranges of the encoded data slices, the DSN comprising:

a plurality of processing devices, each including a processor and an associated memory, configured to implement a plurality of rebuilding modules;

at least one rebuilding module of the plurality of rebuilding modules configured to;

select a selected DSN address range of a plurality of DSN address ranges for potential rebuilding activities;

determine a rebuilding activity capacity level for the selected DSN address range;

determine a maximum number of rebuilding modules for assignment to the selected DSN address range based on the rebuilding activity capacity level;

identify distributed agreement protocol (DAP) function weights of the plurality of rebuilding modules perform a DAP function on a representation of the DSN address range utilizing the DAP function weights of the plurality of rebuilding modules to produce a rank ordered list of rebuilding module identifiers; and

in response to a rebuilding module identifier of the at least one rebuilding module being included within a top-ranked number of rebuilding module identifiers of the rank ordered list, facilitate, by the at least one rebuilding module, rebuilding activities within the DSN address range.

9. The distributed storage network (DSN) of claim 8, wherein the at least one rebuilding module is further configured to:

determine a rebuild capacity of storage units storing encoded data slices within the selected DSN address range.

10. The distributed storage network (DSN) of claim 8, wherein the at least one rebuilding module is further configured to:

evaluate historical rebuilding capacity levels associated with the selected DSN address range.

11. The distributed storage network (DSN) of claim 8, wherein the at least one rebuilding module is configured to determine the rebuilding activity capacity level for the selected DSN address range by:

initiating a rebuild test; and

interpreting test results of the rebuild test.

12. The distributed storage network (DSN) of claim 8, wherein the at least one rebuilding module is further configured to:

identify one or more rebuilding tasks; and

initiate execution of the one or more rebuilding tasks.

13. The distributed storage network (DSN) of claim 12, wherein the at least one rebuilding module is further configured to:

update historical records to include actual rebuilding activity loading levels corresponding to execution of the one or more rebuilding tasks.

14. The distributed storage network (DSN) of claim 12, wherein the at least one rebuilding module is further configured to:

update the DAP function weights associated with the at least one rebuilding module to reflect an updated rebuilding activity capacity level.

15. A rebuilding module included in a distributed storage network (DSN) storing encoded data slices in one or more storage units based on DSN address ranges of the encoded data slices, the rebuilding module comprising:

a processor and an associated memory configured to;

select a selected DSN address range of a plurality of DSN address ranges for potential rebuilding activities;

determine a rebuilding activity capacity level for the selected DSN address range;

determine a maximum number of rebuilding modules for assignment to the selected DSN address range based on the rebuilding activity capacity level;

identify distributed agreement protocol (DAP) function weights of the plurality of rebuilding modules perform a DAP function on a representation of the DSN address range utilizing the DAP function weights of the plurality of rebuilding modules to produce a rank ordered list of rebuilding module identifiers; and

in response to a rebuilding module identifier of the at least one rebuilding module being included within a top-ranked number of rebuilding module identifiers of the rank ordered list, facilitate, by the at least one rebuilding module, rebuilding activities within the DSN address range.

16. The rebuilding module of claim 15, wherein the at least one rebuilding module is further configured to:

evaluate historical rebuilding capacity levels associated with the selected DSN address range.

17. The rebuilding module of claim 15, wherein the at least one rebuilding module is configured to determine the rebuilding activity capacity level for the selected DSN address range by:

initiating a rebuild test; and

interpreting test results of the rebuild test.

18. The rebuilding module of claim 15, wherein the at least one rebuilding module is further configured to:

identify one or more rebuilding tasks; and

initiate execution of the one or more rebuilding tasks.

19. The rebuilding module of claim 18, wherein the at least one rebuilding module is further configured to:

update historical records to include actual rebuilding activity loading levels corresponding to execution of the one or more rebuilding tasks.

20. The rebuilding module of claim 18, wherein the at least one rebuilding module is further configured to:

update the DAP function weights associated with the at least one rebuilding module to reflect an updated rebuilding activity capacity level.