TRANSFERRING A PARTIAL TASK IN A DISTRIBUTED COMPUTING SYSTEM

• US 20130198756A1
• Filed: 12/06/2012
• Published: 08/01/2013
• Est. Priority Date: 01/31/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: GRUBE, GARY W., MARKISON, TIMOTHY W.
• Granted Patent: US 10,140,177 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• 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 for execution by a first distributed storage and task (DST) execution unit of a distributed computing system, the method comprises:

determining that partial task processing resources of the first DST execution unit are projected to be available based on a first local task queue, a first expected partial task performance factor, and a first expected partial task allocation factor, wherein the first DST execution unit is one of a set of DST execution units, wherein the set of DST execution units is assigned to perform tasks on large amounts of data, wherein each of the large amounts of data is partitioned into data partitions, wherein each of the data partitions is further divided into data groups, wherein each of the tasks is divided into a set of partial tasks, and wherein various DST execution units of the set of DST execution units are assigned various partial tasks of various ones of the sets of partial tasks to perform on various ones of the data groups of various ones of the data partitions of various ones of the large amounts of data;

ascertaining that partial task processing resources of a second DST execution unit of the set of DST execution units are projected to be overburdened based on a second local task queue, a second expected partial task performance factor, and a second expected partial task allocation factor;

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.

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

determining that a current snapshot of the first local task queue compares favorably to a current queue threshold;

determining that 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 current snapshot of the first local task queue compares favorably to the current queue threshold and the projected snapshot of the first local task queue compares favorably to the projected queue threshold, indicating that the partial task processing resources of the first DST execution unit are projected to be available.

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

ascertaining that a current snapshot of the second local task queue compares unfavorably to a current queue threshold;

ascertaining that 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 current snapshot of the second local task queue compares unfavorably to the current queue threshold and 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.

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

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

selecting one of 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, the selected partial task and a corresponding data group.

5. 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 large amount of data, a common task allocation unit, and a common data partition.

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

updating the first local task queue to include the allocated 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.

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

8. A method for execution by a first distributed storage and task (DST) execution unit of a distributed computing system, the method comprises:

receiving assignment of executing first partial tasks on first contiguous data slice groups of a first partition of a plurality of data partitions, wherein the first DST execution unit is one of a set of DST execution units, wherein a large amount of data is divided into the plurality of data partitions, wherein each data partition is dispersed storage error encoded to produce a set of data slice groups, wherein a first sub-set of the set of data slice groups includes contiguous data slice groups and a second sub-set of the set of data slice groups includes error coded data slice groups;

determining a first expected partial task performance factor based on a comparison of the first partition of the plurality of data partitions to the plurality of data partitions;

determining that partial task processing resources of the first DST execution unit are projected to be available based on the assignment of the first contiguous data slice groups, the first expected partial task performance factor, and a first expected partial task allocation factor;

ascertaining that partial task processing resources of a second DST execution unit of the set of DST execution units are projected to be overburdened based on assignment of second contiguous data slice groups assigned to the second DST unit, a second expected partial task performance factor, and a second expected partial task allocation factor;

receiving, from the second DST execution unit, a partial task and a corresponding one of the second contiguous data slice groups in accordance with a partial task allocation transfer policy; and

executing the partial task on the corresponding one of the second contiguous data slice groups.

9. The method of claim 8, wherein the receiving the partial task comprises:

determining that the partial task regarding the corresponding one of the second contiguous data slice groups is pending execution by the second DST execution unit; and

requesting the partial task and the corresponding one of the second contiguous data slice groups.

10. The method of claim 8 further comprises:

determining the second expected partial task performance factor based on a comparison of a second partition of the plurality of data partitions to the plurality of data partitions, wherein the second DST execution unit is assigned to execute second partial tasks on second contiguous data slice groups of the second partition of the plurality of data partitions.

11. A dispersed storage (DS) module of first distributed storage and task (DST) execution unit of a distributed computing system comprises:

a first module, when operable within a computing device, causes the computing device to;

determine that partial task processing resources of the first DST execution unit are projected to be available based on a first local task queue, a first expected partial task performance factor, and a first expected partial task allocation factor, wherein the first DST execution unit is one of a set of DST execution units, wherein the set of DST execution units is assigned to perform tasks on large amounts of data, wherein each of the large amounts of data is partitioned into data partitions, wherein each of the data partitions is further divided into data groups, wherein each of the tasks is divided into a set of partial tasks, and wherein various DST execution units of the set of DST execution units are assigned various partial tasks of various ones of the sets of partial tasks to perform on various ones of the data groups of various ones of the data partitions of various ones of the large amounts of data;

a second module, when operable within the computing device, causes the computing device to;

ascertain that partial task processing resources of a second DST execution unit of the set of DST execution units are projected to be overburdened based on a second local task queue, a second expected partial task performance factor, and a second expected partial task allocation factor;

a third module, when operable within the computing device, causes the computing device to;

receive, 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

a fourth module, when operable within the computing device, causes the computing device to;

execute the allocated partial task.

12. The DS module of claim 11, wherein the first module functions to determine that the partial task processing resources of the first DST execution unit are projected to be available by:

determining that a current snapshot of the first local task queue compares favorably to a current queue threshold;

determining that 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 current snapshot of the first local task queue compares favorably to the current queue threshold and the projected snapshot of the first local task queue compares favorably to the projected queue threshold, indicating that the partial task processing resources of the first DST execution unit are projected to be available.

13. The DS module of claim 11, wherein the second module functions to ascertain that the partial task processing resources of the second DST execution unit of the set of DST execution units are projected to be overburdened by:

ascertaining that a current snapshot of the second local task queue compares unfavorably to a current queue threshold;

ascertaining that 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 current snapshot of the second local task queue compares unfavorably to the current queue threshold and 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.

14. The DS module of claim 11, wherein the third module functions to receive the partial task by:

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

selecting one of 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, the selected partial task and a corresponding data group.

15. The DS module of claim 11 further comprises:

the second module further functions 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 large amount of data, a common task allocation unit, and a common data partition.

16. The DS module of claim 11, wherein the fourth module functions to execute the partial task by:

updating the first local task queue to include the allocated 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.

17. The DS module of claim 11 further comprises:

the third module further functions 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.

18. A dispersed storage (DS) module of a first distributed storage and task (DST) execution unit of a distributed computing system comprises:

a first module, when operable within a computing device, causes the computing device to;

receive assignment of executing first partial tasks on first contiguous data slice groups of a first partition of a plurality of data partitions, wherein the first DST execution unit is one of a set of DST execution units, wherein a large amount of data is divided into the plurality of data partitions, wherein each data partition is dispersed storage error encoded to produce a set of data slice groups, wherein a first sub-set of the set of data slice groups includes contiguous data slice groups and a second sub-set of the set of data slice groups includes error coded data slice groups;

a second module, when operable within the computing device, causes the computing device to;

determine a first expected partial task performance factor based on a comparison of the first partition of the plurality of data partitions to the plurality of data partitions; and

determine that partial task processing resources of the first DST execution unit are projected to be available based on the assignment of the first contiguous data slice groups, the first expected partial task performance factor, and a first expected partial task allocation factor;

a third module, when operable within the computing device, causes the computing device to;

ascertain that partial task processing resources of a second DST execution unit of the set of DST execution units are projected to be overburdened based on assignment of second contiguous data slice groups assigned to the second DST unit, a second expected partial task performance factor, and a second expected partial task allocation factor; and

a fourth module, when operable within the computing device, causes the computing device to;

receive, from the second DST execution unit, a partial task and a corresponding one of the second contiguous data slice groups in accordance with a partial task allocation transfer policy; and

execute the partial task on the corresponding one of the second contiguous data slice groups.

19. The DS module of claim 18, wherein the fourth module functions to receive the partial task by:

determining that the partial task regarding the corresponding one of the second contiguous data slice groups is pending execution by the second DST execution unit; and

requesting the partial task and the corresponding one of the second contiguous data slice groups.

20. The DS module of claim 18 further comprises:

the third module further functions to determine the second expected partial task performance factor based on a comparison of a second partition of the plurality of data partitions to the plurality of data partitions, wherein the second DST execution unit is assigned to execute second partial tasks on second contiguous data slice groups of the second partition of the plurality of data partitions.