Adaptive rebuilding rates based on sampling and inference

• US 10,180,880 B2
• Filed: 08/25/2017
• Issued: 01/15/2019
• Est. Priority Date: 07/31/2013
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Khadiwala, Ravi V., Resch, Jason K.
• Primary Examiner(s): Kamran, Mehran
• Application Number:
  US15/686,980
• Publication Number:
  US 20180004604A1
• Time in Patent Office: 508 Days
• Field of Search: 718103
• CPC Class Codes: G06F 11/07 Responding to the occurrence of a fault, e.g. fault tolerance
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 11/3034 where the computing system component is a storage system, e.g. DASD based or network based digital input from or digital output to record carriers G06F3/06; digital recording or reproducing G11B20/18; 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], H04L67/1097
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• 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 method for execution by one or more processing modules of a dispersed storage network (DSN), the method begins by monitoring an encoded data slice access rate to produce an encoded data slice access rate for an associated rebuilding rate of a set of rebuilding rates. The method continues by applying a learning function to the encoded data slice access rate based on a previous encoded data slice access rate associated with the rebuilding rate to produce an updated previous encoded data slice access rate of a set of previous encoded data slice access rates. The method continues by updating a score value associated with the updated previous encoded data slice access rate and the rebuilding rate and selecting a slice access scheme based on the updated score value where a rebuild rate selection will maximize a score value associated with an expected slice access rate.

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:

monitoring an encoded data slice access rate to produce an observed encoded data slice access rate for an associated rebuilding rate of a set of rebuilding rates;

applying a learning rate function to the observed encoded data slice access rate based on a previous observed encoded data slice access rate associated with the rebuilding rate to produce an updated previous observed encoded data slice access rate of a set of previous observed encoded data slice access rates, where the set of previous observed encoded data slice access rates corresponds to the set of rebuilding rates;

updating a score value associated with the updated previous observed encoded data slice access rate and the rebuilding rate, wherein the score value is calculated as;

((N*rebuild rate)+encoded data slice access rate)², where N is a multiplier of the rebuild rate; and

selecting an encoded data slice access scheme based on the updated score value where a rebuild rate selection will maximize a score value associated with an expected encoded data slice access rate; and

rebuilding the encoded data slice in DSN storage using the encoded data slice access scheme.

2. The method of claim 1 further comprising updating the rebuilding rate by determining an encoded data slice access demand rate and a rebuilding access demand rate.

3. The method of claim 1, wherein the encoded data slice access scheme is a priority encoded data slice access when an encoded data slice access demand rate is much greater than a rebuilding access demand rate.

4. The method of claim 1, wherein the encoded data slice access scheme is a rebuilding priority scheme when a rebuilding access demand rate is much greater than an encoded data slice access demand rate.

5. The method of claim 1, wherein the encoded data slice access scheme is a compromise scheme when a rebuilding access demand rate is substantially similar to an encoded data slice access demand rate.

6. The method of claim 5 further comprising selecting a rebuilding rate of the set of rebuilding rates that is less than a rebuilding access demand rate and maximizes a score value associated with an expected slice access rate.

7. The method of claim 1, wherein the score value is calculated as:

((3*rebuild rate)+encoded data slice access rate)².

8. The method of claim 1, wherein the learning rate function is calculated as:

updated score=(old score)*(1−

learning rate)+(new score*learning rate).

9. The method of claim 1, wherein rebuilding access requests includes one or more of a list range request, a list digest of a range request, a read slice request, or a write rebuilt slice request.

10. The method of claim 1, wherein slice access requests include at least one of a read request, a write request, a delete request, or a list request.

11. The method of claim 1, wherein the monitoring includes at least one of:

performing a test, initiating a query, or receiving access rate information.

12. The method of claim 1, wherein determining to update the rebuilding rate for a storage unit is based on one or more of:

detecting an end of a time interval, receiving a request, receiving an error message, or detecting an unfavorable slice access rate.

13. The method of claim 1, wherein determining a slice access demand rate and rebuilding access demand rate is based on one or more of:

interpreting a queue, receiving a request, or accessing a historical record.

14. The method of claim 1, wherein selecting an encoded data slice access scheme is based on one or more of:

a predetermination, detecting that a demand rate is much greater than a demand threshold level, or receiving a request.

15. 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;

monitor an encoded data slice access rate to produce an observed encoded data slice access rate for an associated rebuilding rate of a set of rebuilding rates;

apply a learning rate function to the observed encoded data slice access rate based on a previous observed encoded data slice access rate associated with the rebuilding rate to produce an updated previous observed encoded data slice access rate of a set of previous observed encoded data slice access rates, where the set of previous observed encoded data slice access rates corresponds to the set of rebuilding rates;

update a score value associated with the updated previous observed encoded data slice access rate and the rebuilding rate, wherein the score value is calculated as;

((N*rebuild rate)+encoded data slice access rate)², where N is a multiplier of the rebuild rate; and

select an encoded data slice access scheme based on the updated score value where a rebuild rate selection will maximize a score value associated with an expected encoded data slice access rate; and

rebuild the encoded data slice in DSN storage using the encoded data slice access scheme.

16. The computing device of claim 15, wherein the encoded data slice access scheme is any of:

a priority encoded data slice access when an encoded data slice access demand rate is much greater than a rebuilding access demand rate;

a rebuilding priority scheme when a rebuilding access demand rate is much greater than an encoded data slice access demand rate;

or a compromise scheme when a rebuilding access demand rate is substantially similar to an encoded data slice access demand rate.

17. The computing device of claim 15, wherein the learning rate function is calculated as:

updated score=(old score)*(1−

learning rate)+(new score*learning rate).

18. An integrity processing unit for determining a rate to rebuild encoded data slices, stored within a dispersed storage network (DSN), the integrity processing unit 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;

at each time interval T, select a rebuild rate at which to rebuild data from a range of possible rebuild rates while monitoring an aggregate rate of I/O operations processed in T;

calculate a score value based on the rebuild rate and an I/O rate, the calculating providing a score value for each of a set of possible rebuild rates, the score value calculated as ((N*rebuild rate)+I/O rate)², where N is a multiplier of the rebuild rate;

find a sum total of all the score values for each score value in the set;

divide each score value by this sum total to get weighted probabilities;

wherein, for each time interval T, the integrity processing unit uses the weighted probabilities for a selection of a next rebuild rate to use; and

rebuild the data in DSN storage using the next rebuild rate.