Partial task allocation in a dispersed storage network

• US 10,346,218 B2
• Filed: 02/28/2017
• Issued: 07/09/2019
• Est. Priority Date: 12/12/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Dhuse, Greg R., Gladwin, S. Christopher, Grube, Gary W., Leggette, Wesley B., Motwani, Manish, Resch, Jason K., Shirley, Jr., Thomas F., Volvovski, Ilya
• Primary Examiner(s): Kanaan, Simon P
• Application Number:
  US15/444,952
• Publication Number:
  US 20170168874A1
• Time in Patent Office: 861 Days
• 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/1451 by selection of backup contents
• CPC Class Codes: G06F 11/2058 using more than 2 mirrored copies
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• 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/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• 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 2221/2107 File encryption
• 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/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• 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/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: G06F 9/5077 : Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: G06F 9/5083 : Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/52 : Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H03M 13/09 : Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1515 : Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 : using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1017 : based on a round robin mechanism
• 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 processing system in a dispersed storage and a task (DST) network operates by receiving data and a corresponding task; identifying candidate DST execution units for executing partial tasks of the corresponding task; receiving distributed computing capabilities of the candidate DST execution units; selecting a subset of DST execution units of the candidate DST execution units to favorably execute the partial tasks of the corresponding task; determining task partitioning of the corresponding task into the partial tasks based on one or more of the distributed computing capabilities of the subset of DST execution units; determining processing parameters of the data based on the task partitioning; partitioning the tasks based on the task partitioning to produce the partial tasks; processing the data in accordance with the processing parameters to produce slice groupings; and sending the slice groupings and the partial tasks to the subset of DST execution units.

Claims

1. A method for execution by a processing system of a dispersed storage and task (DST) processing unit that includes a processor, the method comprises:

receiving data and a corresponding task;

identifying candidate DST execution units for executing partial tasks of the corresponding task;

receiving distributed computing capabilities of the candidate DST execution units;

selecting a subset of DST execution units of the candidate DST execution units to favorably execute the partial tasks of the corresponding task;

determining task partitioning of the corresponding task into the partial tasks based on one or more of the distributed computing capabilities of the subset of DST execution units;

determining processing parameters of the data based on the task partitioning;

partitioning the tasks based on the task partitioning to produce the partial tasks;

processing the data in accordance with the processing parameters to produce slice groupings; and

sending the slice groupings and the partial tasks to the subset of DST execution units.

2. The method of claim 1, wherein the distributed computing capabilities are received by one or more of:

a query, a lookup, or a message.

3. The method of claim 1, wherein selecting the subset of DST execution units includes selecting the candidate DST execution units associated with favorable distributed computing capabilities.

4. The method of claim 1, wherein the distributed computing capabilities include one or more of:

a processing capability level, a memory capacity level, a network access level, a bandwidth capability level, an availability level, or a reliability level.

5. The method of claim 1, wherein selecting the subset of DST execution units includes identifying a number of simultaneous compute resources to execute the task in a favorable timeframe based on the distributed computing capabilities of the candidate DST execution units.

6. The method of claim 1, wherein determining the task partitioning of the corresponding task into the partial tasks is further based on the processing parameters, and an estimated next data processing destination.

7. The method of claim 1, wherein determining the task partitioning of the corresponding task into the partial tasks includes aligning the corresponding task with other current tasks and potential future tasks.

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

at least one processor;

a memory that stores operational instructions, that when executed by the at least one processor cause the processing system to perform operations including;

receiving data and a corresponding task;

identifying candidate DST execution units for executing partial tasks of the corresponding task;

receiving distributed computing capabilities of the candidate DST execution units;

selecting a subset of DST execution units of the candidate DST execution units to favorably execute the partial tasks of the corresponding task;

determining task partitioning of the corresponding task into the partial tasks based on one or more of the distributed computing capabilities of the subset of DST execution units;

determining processing parameters of the data based on the task partitioning;

partitioning the tasks based on the task partitioning to produce the partial tasks;

processing the data in accordance with the processing parameters to produce slice groupings; and

sending the slice groupings and the partial tasks to the subset of DST execution units.

9. The processing system of claim 8, wherein the distributed computing capabilities are received by one or more of:

a query, a lookup, or a message.

10. The processing system of claim 8, wherein selecting the subset of DST execution units includes selecting the candidate DST execution units associated with favorable distributed computing capabilities.

11. The processing system of claim 8, wherein the distributed computing capabilities include one or more of:

a processing capability level, a memory capacity level, a network access level, a bandwidth capability level, an availability level, or a reliability level.

12. The processing system of claim 8, wherein selecting the subset of DST execution units includes identifying a number of simultaneous compute resources to execute the task in a favorable timeframe based on the distributed computing capabilities of the candidate DST execution units.

13. The processing system of claim 8, wherein determining the task partitioning of the corresponding task into the partial tasks is further based on the processing parameters, and an estimated next data processing destination.

14. The processing system of claim 8, wherein determining the task partitioning of the corresponding task into the partial tasks includes aligning the corresponding task with other current tasks and potential future tasks.

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

at least one memory section that stores operational instructions that, when executed by a processing system of a dispersed storage and task (DST) network that includes a processor and a memory, causes the processing system to perform operations including;

receiving data and a corresponding task;

identifying candidate DST execution units for executing partial tasks of the corresponding task;

receiving distributed computing capabilities of the candidate DST execution units;

selecting a subset of DST execution units of the candidate DST execution units to favorably execute the partial tasks of the corresponding task;

determining task partitioning of the corresponding task into the partial tasks based on one or more of the distributed computing capabilities of the subset of DST execution units;

determining processing parameters of the data based on the task partitioning;

partitioning the tasks based on the task partitioning to produce the partial tasks;

processing the data in accordance with the processing parameters to produce slice groupings; and

sending the slice groupings and the partial tasks to the subset of DST execution units.

16. The non-transitory computer readable storage medium of claim 15, wherein selecting the subset of DST execution units includes selecting the candidate DST execution units associated with favorable distributed computing capabilities.

17. The non-transitory computer readable storage medium of claim 15, wherein the distributed computing capabilities include one or more of:

a processing capability level, a memory capacity level, a network access level, a bandwidth capability level, an availability level, or a reliability level.

18. The non-transitory computer readable storage medium of claim 15, wherein selecting the subset of DST execution units includes identifying a number of simultaneous compute resources to execute the task in a favorable timeframe based on the distributed computing capabilities of the candidate DST execution units.

19. The non-transitory computer readable storage medium of claim 15, wherein determining the task partitioning of the corresponding task into the partial tasks is further based on the processing parameters, and an estimated next data processing destination.

20. The non-transitory computer readable storage medium of claim 15, wherein determining the task partitioning of the corresponding task into the partial tasks includes aligning the corresponding task with other current tasks and potential future tasks.