Determining task distribution in a distributed computing system

• US 10,303,521 B2
• Filed: 11/02/2016
• Issued: 05/28/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/341,722
• Publication Number:
  US 20170052828A1
• Time in Patent Office: 937 Days
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• 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/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 21/602 Providing cryptographic facilities or services
• 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 2211/1028 Distributed, i.e. distributed RAID systems with parity
• 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/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• 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: 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: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources
• 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 method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), by selecting a number of distributed storage and task execution (DST) EX units to favorably execute partial tasks of the corresponding tasks. The method continues by determining task partitioning based on one or more of distributed computing capabilities of the selected DST EX units. The method continues by determining processing parameters of the data based on the task partitioning. The method continues by partitioning the task(s) based on the task partitioning to produce the partial tasks. The method continues by processing the data in accordance with the processing parameters to produce slice groupings and sending the slice groupings and corresponding partial tasks to the DST EX units in accordance with a pillar mapping.

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 and storing data;

receiving a corresponding task(s) to be executed on the stored data;

selecting a number of distributed storage and task execution (DST EX) units to favorably execute partial tasks of the corresponding task(s), wherein the partial tasks are processed in parallel to complete an overall task within a desired task execution time period;

determining task partitioning based on one or more of distributed computing capabilities of the selected DST EX units;

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

partitioning the task(s) based on the task partitioning to produce the partial tasks;

processing the data in accordance with the processing parameters to produce slice groupings, wherein the slice groupings include groups of encoded data slices; and

sending the slice groupings and corresponding partial tasks to the DST EX units in accordance with a pillar mapping.

2. The method of claim 1, wherein the selecting includes selecting either a number of simultaneous computing resources to complete the task in a favorable timeframe, or based on an actual capability of the DST EX units.

3. The method of claim 1, wherein the determining task partitioning includes:

aligning tasks with DST EX unit capabilities and where subsequent computing tasks are assigned.

4. The method of claim 1, wherein the determining processing parameters includes:

determining how to process is based on the task partitioning and a number of the DST EX units.

5. The method of claim 1, wherein the processing includes partitioning into chunksets and chunks.

6. The method of claim 5 further comprises determining a chunk size to process includes determining a number of chunks for k parallel processing, where the chunkset is k number of contiguous chunks.

7. The method of claim 6, wherein the data for processing is arranged as N chunksets.

8. The method of claim 1, wherein the pillar mapping includes rotation of data and error coded data to the DST EX units based on a lookup.

9. The method of claim 8, wherein the rotation is based on a round robin sequence.

10. The method of claim 1, wherein pillar mapping includes selecting all slices per row to the selected DST EX unit in accordance with a DST EX unit selection scheme.

11. The method of claim 10, wherein the selection scheme includes parity slices sent to a different DST EX unit for each chunkset to achieve a processing load leveling.

12. A computing device of a group of computing devices of a dispersed storage network (DSN), the computing device comprises:

an interface;

a local memory; and

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

receive and store data;

receive a corresponding task(s) to be executed on the stored data;

select a number of distributed storage and task execution (DST EX) units to favorably execute partial tasks of the corresponding task(s), wherein the partial tasks are processed in parallel to complete an overall task within a desired task execution time period;

determine task partitioning based on one or more of distributed computing capabilities of the selected DST EX units;

determine processing parameters of the data based the task partitioning;

partition the task(s) based on the task partitioning to produce partial tasks;

process the data in accordance with the processing parameters to produce slice groupings, wherein the slice groupings include groups of encoded data slices; and

send the slice groupings and corresponding partial tasks to the DST EX units in accordance with a pillar mapping.

13. The computing device of claim 12, wherein the selecting includes selecting either a number of simultaneous computing resources to complete the task in a favorable timeframe, or based on an actual capability of the DST EX units.

14. The computing device of claim 12, wherein the determining task partitioning includes:

aligning tasks with DST EX unit capabilities and where subsequent computing tasks are assigned.

15. The computing device of claim 12, wherein the determining processing parameters includes:

determining how to process is based on the task partitioning and a number of the DST EX units.

16. The computing device of claim 12, wherein the processing includes partitioning into chunksets and chunks.

17. The computing device of claim 16 further comprises determining a chunk size to process including determining a number of chunks for k parallel processing, where the chunkset is k number of contiguous chunks.

18. The computing device of claim 17, wherein the data for processing is arranged as N chunksets.

19. The computing device of claim 12, wherein the pillar mapping includes rotation of data and error coded data to the DST EX units based on a lookup.

20. The computing device of claim 19, wherein the rotation is based on a round robin sequence.