Transferring a partial task in a distributed computing system

• US 10,140,177 B2
• Filed: 12/06/2012
• Issued: 11/27/2018
• Est. Priority Date: 01/31/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): Aponte, Francisco J
• Assistant Examiner(s): Alfred, Melissa A
• Application Number:
  US13/706,991
• Publication Number:
  US 20130198756A1
• Time in Patent Office: 2,182 Days
• Field of Search: None
• 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/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/2053 where persistent mass storage functionality or persistent mass storage control functionality is redundant error detection or correction in information storage based on relative movement between record carrier and transducer G11B20/18
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• 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 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• 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 begins by a dispersed storage (DS) processing module determining that partial task processing resources of a first DST execution unit are projected to be available. The method continues with the DS processing module ascertaining that partial task processing resources of a second DST execution unit are projected to be overburdened. The method continues with the DS processing module receiving, from the second DST execution unit, a partial task assigned to the second DST execution unit in accordance with a partial task allocation transfer policy to produce an allocated partial task and executing the allocated partial task.

Claims

1. A method comprises:

determining, by a first dispersed storage and task (DST) execution unit, whether partial task processing resources of the first DST execution unit are projected to be available, wherein the determining is based on;

comparing a number of partial tasks in a current snapshot of a first local task queue to a current queue threshold, and

determining a number of partial tasks in a projected snapshot of the first local task queue, and a projected queue threshold, wherein the determining is based at least partially on a first expected partial task performance factor and a first expected partial task allocation factor,

wherein the first expected partial task performance factor is based on either when the first DST execution unit will perform one or more of the partial tasks in the projected snapshot of the first local task queue or how long the first DST execution unit will take to perform one or more of the partial tasks in the projected snapshot of the first local task queue, and wherein the first expected partial task allocation factor is based on the number of partial tasks in the first local task queue and the types of partial tasks in the first local task queue;

when partial task processing resources of the first DST execution unit are projected to be available, determining, whether partial task processing resources of a second DST execution unit are projected to be overburdened, wherein the determining is based on;

comparing a number of partial tasks in a current snapshot of a second local task queue to a current queue threshold associated with the second local task queue, and

determining a number of partial tasks in a projected snapshot of the second local task queue, and a projected queue threshold for the second local task queue, wherein the determining is based at least partially on a second expected partial task performance factor and a second expected partial task allocation factor,

wherein the second expected partial task performance factor is based on when the second DST execution unit will perform one or more of the partial tasks in the projected snapshot of the second local task queue or how long the second DST execution unit will take to perform one or more of the partial tasks in the projected snapshot of the second local task queue, and wherein the second expected partial task allocation factor is based on the number of partial tasks in the second local task queue and the types of partial tasks in the second local task queue;

when partial task processing resources of the second DST execution unit are projected to be overburdened, receiving, by the first DST execution unit, a partial task of a set of partial tasks from the second DST execution unit, wherein the partial task is associated with a data portion, wherein the data portion includes a plurality of data partitions, wherein each of the plurality of data partitions comprises a group of encoded data slices and further wherein the first DST execution unit and the second DST execution unit are each assigned at least one partial task of the set of partial tasks to perform on the group of encoded data slices; and

executing, by the first DST execution unit, the partial task to produce a partial resultant.

2. The method of claim 1, wherein the determining that the partial task processing resources of the second DST execution unit are projected to be overburdened comprises:

ascertaining whether a number of partial tasks in a current snapshot of the second local task queue compares unfavorably to a current queue threshold;

ascertaining whether a number of partial tasks in a projected snapshot of the second local task queue compares unfavorably to a projected queue threshold that is based on at least one of the second expected partial task performance factor and the second expected partial task allocation factor; and

when at least one of the number of partial tasks in the current snapshot of the second local task queue compares unfavorably to the current queue threshold and the number of partial tasks in the projected snapshot of the second local task queue compares unfavorably to the projected queue threshold, indicating that the partial task processing resources of the second DST execution unit are projected to be overburdened.

3. The method of claim 1, wherein the receiving the partial task comprises:

determining unexecuted partial tasks assigned to the second DST execution unit;

selecting the partial task from the unexecuted partial tasks based on execution capabilities of the first DST execution unit and the second expected partial task performance factor; and

receiving, from the second DST execution unit, a corresponding data group corresponding to the partial task.

4. The method of claim 1 further comprises:

identifying the second DST execution unit based on a common task criteria with the first DST execution unit, wherein the common task criteria includes one or more of a common site, a common amount of data, a common task allocation unit, and a common data partition.

5. The method of claim 1, wherein the executing the partial task comprises:

updating the first local task queue to include the partial task;

updating the first expected partial task performance factor based on the allocated partial task; and

updating the first expected partial task allocation factor based on the allocated partial task.

6. The method of claim 1 further comprises:

updating the second local task queue by removing the partial task;

updating the second expected partial task performance factor based on removing the partial task; and

updating the second expected partial task allocation factor based on removing the partial task.

7. A first dispersed storage and task (DST) execution unit comprises:

a communications interface;

a memory; and

a processing circuitry;

where the memory includes instructions for causing the processing circuitry to;

determine whether partial task processing resources of the first DST execution unit are projected to be available, wherein the partial task processing resources of the first DST execution unit are projected to be available when a number of partial tasks in a current snapshot of a first local task queue does not exceed a current queue threshold, and a projected queue threshold based on a first expected partial task performance factor and a first expected partial task allocation factor indicates that a projected number of partial tasks in a snapshot of the first local task queue would not exceed the projected queue threshold,

wherein the first expected partial task performance factor is based on when the first DST execution unit will perform one or more of the partial tasks in the projected snapshot of the first local task queue or how long the first DST execution unit will take to perform one or more of the partial tasks in the projected snapshot of the first local task queue, and wherein the first expected partial task allocation factor is based on the number of partial tasks in the first local task queue and the types of partial tasks in the first local task queue;

when partial task processing resources of the first DST execution unit are projected to be available, determine whether partial task processing resources of a second DST execution unit are projected to be overburdened, wherein the partial task processing resources of the second DST execution unit are projected to be available when a number of partial tasks in a current snapshot of a second local task queue does not exceed a current queue threshold, and a projected queue threshold based on a second expected partial task performance factor and a second expected partial task allocation factor indicates that a number of partial tasks in a projected snapshot of the first local task queue will exceed the projected queue threshold,

wherein the second expected partial task performance factor is based on when the second DST execution unit will perform one or more of the partial tasks in the projected snapshot of the second local task queue or how long the second DST execution unit will take to perform one or more of the partial tasks in the projected snapshot of the second local task queue, and wherein the second expected partial task allocation factor is based on the number of partial tasks in the second local task queue and the types of partial tasks in the second local task queue;

when partial task processing resources of the second DST execution unit are projected to be overburdened, receive a partial task of a set of partial tasks from the second DST execution unit, wherein the partial task is associated with a data portion, wherein the data portion includes a plurality of data partitions, wherein each of the plurality of data partitions includes a group of encoded data slices and further wherein the first DST execution unit and the second DST execution unit are each assigned at least one partial task of the set of partial tasks to perform on the group of encoded data slices; and

execute the partial task to produce a partial resultant.

8. The first DST execution unit of claim 7, wherein the memory further comprises instructions for causing the processing circuitry to:

determine that a number of partial tasks in a current snapshot of the first local task queue compares favorably to a current queue threshold;

determine that a number of partial tasks in a projected snapshot of the first local task queue compares favorably to a projected queue threshold that is based on at least one of the first expected partial task performance factor and the first expected partial task allocation factor; and

when the number of partial tasks in the current snapshot of the first local task queue compares favorably to the current queue threshold and the number of partial tasks in the projected snapshot of the first local task queue compares favorably to the projected queue threshold, indicate that the partial task processing resources of the first DST execution unit are projected to be available.

9. The first DST execution unit of claim 7, wherein the memory further comprises instructions for causing the processing circuitry to:

ascertain whether a number of partial tasks in a current snapshot of the second local task queue compares unfavorably to a current queue threshold;

ascertain whether a number of partial tasks in a projected snapshot of the second local task queue compares unfavorably to a projected queue threshold that is based on at least one of the second expected partial task performance factor and the second expected partial task allocation factor; and

when at least one of the number of partial tasks in a current snapshot of the second local task queue compares unfavorably to the current queue threshold and the number of partial tasks in a projected snapshot of the second local task queue compares unfavorably to the projected queue threshold, indicate that the partial task processing resources of the second DST execution unit are projected to be overburdened.

10. The first DST execution unit of claim 7, wherein the memory further comprises instructions for causing the processing circuitry to:

determine unexecuted partial tasks assigned to the second DST execution unit;

select the partial task from the unexecuted partial tasks based on execution capabilities of the first DST execution unit and the second expected partial task performance factor; and

receive, from the second DST execution unit, a corresponding data group corresponding to the partial task.

11. The first DST execution unit of claim 7, wherein the memory further comprises instructions for causing the processing circuitry to identify the second DST execution unit based on a common task criteria with the first DST execution unit, wherein the common task criteria includes one or more of a common site, a common amount of data, a common task allocation unit, and a common data partition.

12. The first DST execution unit of claim 7, wherein the memory further comprises instructions for causing the processing circuitry to:

update the first local task queue to include the partial task;

update the first expected partial task performance factor based on the allocated partial task; and

update the first expected partial task allocation factor based on the allocated partial task.

13. The first DST execution unit of claim 7, wherein the memory further comprises instructions for causing the processing circuitry to:

update the second local task queue by removing the partial task;

update the second expected partial task performance factor based on removing the partial task; and

update the second expected partial task allocation factor based on removing the partial task.