Adjusting execution of tasks in a dispersed storage network

• US 9,588,686 B2
• Filed: 08/05/2014
• Issued: 03/07/2017
• Est. Priority Date: 10/03/2013
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew, Volvovski, Ilya, Kaczmarek, Joseph Martin, Vedpathak, Yogesh Ramesh
• Primary Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US14/452,475
• Publication Number:
  US 20150100966A1
• Time in Patent Office: 945 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/1458 by checking the subject access rights
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/6272 by registering files or documents with a third party
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2221/2149 Restricted operating environment
• 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/0611 in relation to response time
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0622 in relation to access
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/0637 Permissions
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0665 : at area level, e.g. provisioning of virtual or logical volumes
• 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/0682 : Tape device
• CPC Class Codes: G06F 3/0689 : Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G06F 9/4881 : Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: H04L 67/1001 : for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1095 : Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• 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/145 : avoiding end of session, e.g. keep-alive, heartbeats, resumption message or wake-up for inactive or interrupted session

Abstract

A method includes a set of execution units of a dispersed storage network (DSN) receiving sets of sub-task requests from a computing device and storing the sets of sub-task requests, where each execution unit stores a request of each of the sets of sub-task requests to produce a corresponding plurality of sub-task requests. The method continues with each execution unit generating sub-task estimation data and adjusting timing, sequencing, or processing of the corresponding plurality of sub-task requests based on the estimation data to produce a plurality of partial results, where, due to one or more difference factors from a list of difference factors, the execution units process pluralities of sub-task requests at difference paces, where the list of difference factors includes differences in amounts of data to be processed per sub-task request, processing capabilities, memory storage capabilities, and networking capabilities.

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:

receiving, over time and by a set of execution units of the DSN, a plurality of sets of sub-task requests from a computing device of the DSN, wherein the computing device generates a plurality of task requests, wherein a task request of the plurality of task requests includes a set of sub-task requests and wherein the computing device sends corresponding sets of sub-task requests to the set of execution units when task requests of the plurality of task requests are generated;

storing, by the set of execution units, the corresponding sets of sub-task requests, wherein each of a first, a second, and a third execution unit of the set of execution unit stores, respectively, a first, a second, and a third sub-task request of each of the corresponding sets of sub-task requests to produce, respectively, a first, a second, and a third plurality of sub-task requests;

respectively generating first, second, and third sub-task estimation data for the first, the second, and the third plurality of sub-task requests by the first, the second, and the third execution units;

determining, for each execution unit, an execution ready status for a selected sub-task request of the set of sub-task requests when each the set of execution units has resources available to process the selected sub-task request; and

respectively adjusting timing, sequencing, or processing of the first, the second, and the third plurality of sub-task requests by the first, the second, and the third execution units based on the first, the second, and the third sub-task estimation data and a corresponding execution ready status, to produce a first, a second, and a third plurality of partial results, wherein, due to one or more difference factors from a list of difference factors, the first, the second, and the third execution units process the first, the second, and the third plurality of sub-task requests at difference paces, wherein the list of difference factors includes differences in amounts of data to be processed per sub-task request, processing capabilities, memory storage capabilities, and networking capabilities, and wherein at least one partial result of the first, second, and third plurality of partial results is based on dispersed error encoded data stored in the DSN.

2. The method of claim 1 further comprises:

sending the first, the second, and the third plurality of partial results to the computing device, wherein the computing device compiles the first, the second, and the third plurality of partial results to produce a plurality of results.

3. The method of claim 1 further comprises:

respectively storing the first, the second, and the third plurality of sub-task requests in first, second, and third holding queues by the first, the second, and the third execution units; and

respectively transferring first, second, and third selected sub-task requests of the first, the second, and the third plurality of sub-task requests from the first, the second, and the third holding queues to first, second, and third execution queues prior to respectively executing the first, the second, and the third selected sub-task requests.

4. The method of claim 1 further comprises:

determining, by the first execution unit, the execution ready status for a first selected sub-task request of the first plurality of sub-task requests when the first execution unit has resources available to process the first selected sub-task request;

determining, by the first execution unit, an execution not ready status for the first selected sub-task request of the first plurality of sub-task requests when the first execution unit does not have the resources available to process the first selected sub-task request;

determining, by the second execution unit, the execution ready status for a second selected sub-task request of the second plurality of sub-task requests when the second execution unit has resources available to process the second selected sub-task request;

determining, by the second execution unit, an execution not ready status for the second selected sub-task request of the second plurality of sub-task requests when the second execution unit does not have the resources available to process the second selected sub-task request;

determining, by the third execution unit, the execution ready status for a third selected sub-task request of the third plurality of sub-task requests when the third execution unit has resources available to process the third selected sub-task request; and

determining, by the third execution unit, an execution not ready status for the third selected sub-task requests of the third plurality of sub-task requests when the third execution unit does not have the resources available to process the third selected sub-task request.

5. The method of claim 4 further comprises:

when a quorum of the first, the second, and the third execution units exists, wherein a quorum is reached when two of the first, the second, and the third selected sub-task requests have the execution ready status;

executing, by the quorum of the first, the second, and the third execution units, two of the first, the second, or the third selected sub-task requests to produce two of a first, a second, and a third partial results of the first, the second, and the third plurality of partial results.

6. The method of claim 5 further comprises:

for the first, the second, or the third execution unit not in the quorum of execution units, deleting the respective first, the second, and the third selected sub-task requests when the two of the first, the second, and the third partial results have been produced and the remaining one of the first, the second, and the third selected sub-task requests has the execution not ready status.

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;

receive, over time and by a set of execution units of the DSN, a plurality of sets of sub-task requests from a computing device of the DSN, wherein the computing device generates a plurality of task requests, wherein a task request of the plurality of task requests includes a set of sub-task requests and wherein the computing device sends corresponding sets of sub-task requests to the set of execution units when task requests of the plurality of task requests are generated;

store, by the set of execution units, the corresponding sets of sub-task requests, wherein each of a first, a second, and a third execution unit of the set of execution unit stores, respectively, a first, a second, and a third sub-task request of each of the corresponding sets of sub-task requests to produce, respectively, a first, a second, and a third plurality of sub-task requests;

respectively generate first, second, and third sub-task estimation data for the first, the second, and the third plurality of sub-task requests by the first, the second, and the third execution units;

determine, for each execution unit, an execution ready status for a selected sub-task request of the set of sub-task requests when each the set of execution units has resources available to process the selected sub-task request; and

respectively adjust timing, sequencing, or processing of the first, the second, and the third plurality of sub-task requests by the first, the second, and the third execution units based on the first, the second, and the third sub-task estimation data and a corresponding execution ready status, to produce a first, a second, and a third plurality of partial results, wherein, due to one or more difference factors from a list of difference factors, the first, the second, and the third execution units process the first, the second, and the third plurality of sub-task requests at difference paces, wherein the list of difference factors includes differences in amounts of data to be processed per sub-task request, processing capabilities, memory storage capabilities, and networking capabilities, and wherein at least one partial result of the first, second, and third plurality of partial results is based on dispersed error encoded data stored in the DSN.

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

send the first, the second, and the third plurality of partial results to the computing device, wherein the computing device compiles the first, the second, and the third plurality of partial results to produce a plurality of results.

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

respectively store the first, the second, and the third plurality of sub-task requests in first, second, and third holding queues by the first, the second, and the third execution units; and

respectively transfer first, second, and third selected sub-task requests of the first, the second, and the third plurality of sub-task requests from the first, the second, and the third holding queues to first, second, and third execution queues prior to respectively executing the first, the second, and the third selected sub-task requests.

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;

determine, by the first execution unit, the execution ready status for a first selected sub-task request of the first plurality of sub-task requests when the first execution unit has resources available to process the first selected sub-task request;

determine, by the first execution unit, an execution not ready status for the first selected sub-task request of the first plurality of sub-task requests when the first execution unit does not have the resources available to process the first selected sub-task request;

determine, by the second execution unit, the execution ready status for a second selected sub-task request of the second plurality of sub-task requests when the second execution unit has resources available to process the second selected sub-task request;

determine, by the second execution unit, an execution not ready status for the second selected sub-task requests of the second plurality of sub-task requests when the second execution unit does not have the resources available to process the second selected sub-task request;

determine, by the third execution unit, the execution ready status for a third selected sub-task request of the third plurality of sub-task requests when the third execution unit has resources available to process the third selected sub-task request; and

determine, by the third execution unit, an execution not ready status for the third selected sub-task requests of the third plurality of sub-task requests when the third execution unit does not have the resources available to process the third selected sub-task request.

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

when a quorum of the first, the second, and the third execution units exists, wherein a quorum is reached when two of the first, the second, and the third selected sub-task requests have the execution ready status;

execute, by the quorum of the first, the second, and the third execution units, two of the first, the second, or the third selected sub-task requests to produce two of a first, a second, and a third partial results of the first, the second, and the third plurality of partial results.

12. The non-transitory computer-readable storage medium of claim 11 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 the first, the second, or the third execution unit not in the quorum of execution units, delete the respective first, the second, and the third selected sub-task requests when the two of the first, the second, and the third partial results have been produced and the remaining one of the first, the second, and the third selected sub-task requests has the execution not ready status.

13. An execution unit of a dispersed storage network (DSN), the execution unit comprises:

an interface;

a memory; and

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

receive, over time via the interface, a plurality of sub-task requests from a computing device of the DSN, wherein a plurality of sets of sub-task requests includes the plurality of sub-task requests, wherein the computing device generates a plurality of task requests, wherein a task request of the plurality of task requests includes a set of sub-task requests, wherein the computing device sends corresponding sets of sub-task requests to a set of execution units of the DSN when task requests of the plurality of task requests are generated and wherein the set of execution units includes the execution unit;

store, in the memory, a corresponding sub-task request of each of the corresponding sets of sub-task requests to produce the plurality of sub-task requests;

generate sub-task estimation data for the plurality of sub-task requests;

determine, for each execution unit, an execution ready status for a selected sub-task request of the set of sub-task requests when each the set of execution units has resources available to process the selected sub-task request; and

adjust timing, sequencing, or processing of the plurality of sub-task requests based on the sub-task estimation data and a corresponding execution ready status, to produce a plurality of partial results, wherein, due to one or more difference factors from a list of difference factors, the execution unit process the plurality of sub-task requests at difference paces, wherein the list of difference factors includes differences in amounts of data to be processed per sub-task request, processing capabilities, memory storage capabilities, and networking capabilities, and wherein at least one partial result of a first, second, and third plurality of the partial results is based on dispersed error encoded data stored in the DSN.

14. The execution unit of claim 13, wherein the processing module further functions to:

send, via the interface, the plurality of partial results to the computing device, wherein the computing device compiles the plurality of partial results to produce a plurality of results.

15. The execution unit of claim 13, wherein the processing module further functions to:

store the plurality of sub-task requests in a holding queue of the memory; and

transfer selected sub-task requests of the plurality of sub-task requests from the holding queue to an execution queue prior to executing the selected sub-task requests.

16. The execution unit of claim 13, wherein the processing module further functions to:

determine the execution ready status for a selected sub-task request of the plurality of sub-task requests when the execution unit has resources available to process the selected sub-task request; and

determine an execution not ready status for the selected sub-task request of the plurality of sub-task requests when the execution unit does not have the resources available to process the selected sub-task request.

17. The execution unit of claim 16, wherein the processing module further functions to:

when a quorum of the execution unit and another execution unit of the set of execution units exists, wherein a quorum is reached when the execution unit has the execution ready status for the selected sub-task request and the other execution has the execution ready status for a corresponding second selected sub-task request of the set of sub-task requests and wherein the set of sub-task requests includes the selected sub-task request and the second selected sub-task request;

execute the selected sub-task requests to produce a partial result of the plurality of partial results.

18. The execution unit of claim 17, wherein the processing module further functions to:

when another quorum is reached without inclusion of the execution unit, delete the selected sub-task request when other partial results have been produced and the selected sub-task requests has the execution not ready status.