Dispersed storage with coordinated execution and methods for use therewith

• US 9,998,538 B2
• Filed: 06/26/2014
• Issued: 06/12/2018
• Est. Priority Date: 08/29/2013
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Kazi, Asimuddin, Resch, Jason K.
• Primary Examiner(s): Doan, Duyen
• Application Number:
  US14/316,061
• Publication Number:
  US 20150067164A1
• Time in Patent Office: 1,447 Days
• Field of Search: 709225-226
• 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/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G11C 2029/4402 Internal storage of test result, quality data, chip identification, repair information
• CPC Class Codes: G11C 29/44 Indication or identification of errors, e.g. for repair
• 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]
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

A dispersed storage and task (DST) processing unit receives an access request. An estimated processing load, associated with the access request, is determined. A processing resource is selected based on the estimated processing load. A coordinated execution schedule is determined for a plurality of DST execution units. The access request is assigned to the processing resource in accordance with the coordinated execution schedule.

Claims

1. A method comprises:

sending, by a client module, an access request to a set of dispersed storage and task (DST) units, wherein the access request includes a first identity of a set of encoded data slices and a set of partial tasks, wherein a common task is divided into the set of partial tasks;

receiving, by each of at least some of the DST units, a second identity of a unique encoded data slice of the set of encoded data slices and a unique partial task of the set of partial tasks;

individually determining, by the each of at least some of the DST units, an estimated processing load associated with the second identity of the unique encoded data slice and the unique partial task;

individually selecting, by the each of at least some of the DST units, a processing resource based on the individual estimated processing load;

collectively determining, by the at least some of the DST units, a coordinated execution schedule based on the individual estimated processing loads;

executing, by the selected processing resource of each of at least some of the DST units, the unique partial task on the unique encoded data slice to produce a partial result; and

sending, by the at least some of the DST units, the partial results to the client module.

2. The method of claim 1 further comprising:

detecting an execution deviation in the coordinated execution schedule; and

updating the coordinated execution schedule in response to the execution deviation.

3. The method of claim 1 wherein the estimated processing load is determined based on at least one of:

an access type corresponding to the access request, or a quantity of data slices associated with the access request.

4. The method of claim 1 wherein the processing resource is selected from a plurality of processing resources, based on a capability of the processing resource.

5. The method of claim 1 wherein the coordinated execution schedule is determined based on at least one of:

an execution status associated with one or more current access requests, or a number of access requests in queue.

6. The method of claim 1 wherein the coordinated execution schedule is determined to coordinate commencement of execution of the partial tasks.

7. The method of claim 1 wherein the coordinated execution schedule is determined to coordinate estimated completion time of execution of the partial tasks.

8. A dispersed storage and task (DST) processing unit comprises:

a hardware memory;

an interface; and

at least one processing module operably coupled to the memory and the interface, wherein the at least one processing module is operable to;

receive, via the interface, a second identity of a unique encoded data slice of a set of encoded data slices and a unique partial task of a set of partial tasks, wherein an access request includes a first identity of the set of encoded data slices and the set of partial tasks, wherein a common task is divided into the set of partial tasks;

determine an estimated processing load associated with the second identity of the unique encoded data slice and the unique partial task;

select a processing resource based on the estimated processing load;

determine, in collaboration with other DST execution units, a coordinated schedule;

execute the unique partial task on the unique encoded data slice to produce a partial result; and

send, via the interface, the partial results to a client module.

9. The DST processing unit of claim 8 wherein the at least one processing module is further operable to:

detect an execution deviation in the coordinated execution schedule; and

update the coordinated execution schedule in response to the execution deviation.

10. The DST processing unit of claim 8 wherein the at least one processing module is operable to determine the estimated processing load based on at least one of:

an access type corresponding to the access request, or a quantity of data slices associated with the access request.

11. The DST processing unit of claim 8 wherein the at least one processing module is operable to select the processing resource from a plurality of processing resources based on a capability of the processing resource.

12. The DST processing unit of claim 8, wherein the at least one processing module is operable to determine the coordinated execution schedule based on at least one of:

an execution status associated with one or more current access requests, or a number of access requests in queue.

13. The DST processing unit of claim 8, wherein the at least one processing module is operable to determine the coordinated execution schedule to coordinate commencement of execution of at least some of the set of partial tasks.

14. The DST processing unit of claim 8, wherein the at least one processing module is operable to determine the coordinated execution schedule to coordinate an estimated completion time of execution of at least some of the set of partial tasks.

15. A non-transitory computer readable storage medium comprises:

a first memory section that stores operational instructions that, when executed by a client module of a dispersed storage and task (DST) network, causes the client module to;

send an access request to a set of dispersed storage and task (DST) units of the DST network, wherein the access request includes a first identity of a set of encoded data slices and a set of partial tasks, wherein a common task is divided into the set of partial tasks;

a second memory section that stores operational instructions that, when executed by each of at least some of the DST units, causes the each of at least some of the DST units to;

receive a second identity of a unique encoded data slice of the set of encoded data slices and a unique partial task of the set of partial tasks;

individually determine an estimated processing load associated with the second identity of the unique encoded data slice and the unique partial task;

individually select a processing resource based on the individual estimated processing load;

determine, in collaboration with other DST units of the at least some of the DST units, a coordinated execution schedule based on the individual estimated processing loads;

execute, by the selected processing resource of each of at least some of the DST units, the unique partial task on the unique encoded data slice to produce a partial result; and

send the partial results to the client module.

16. The non-transitory computer readable storage medium of claim 15 wherein the second memory section further stores operational instructions that, when executed by each of at least some of the DST units, causes the each of at least some of the DST units to:

detect an execution deviation in the coordinated execution schedule; and

update the coordinated execution schedule in response to the execution deviation.

17. The non-transitory computer readable storage medium of claim 15 wherein the estimated processing load is determined based on at least one of:

an access type corresponding to the access request, or a quantity of data slices associated with the access request.

18. The non-transitory computer readable storage medium of claim 15 wherein the coordinated execution schedule is determined based on at least one of:

an execution status associated with one or more current access requests, or a number of access requests in queue.

19. The non-transitory computer readable storage medium of claim 15 wherein the coordinated execution schedule is determined to coordinate commencement of execution of the partial tasks.

20. The non-transitory computer readable storage medium of claim 15 wherein the coordinated estimated completion time of execution of the partial tasks.