Distributed computing in a distributed storage and task network

• US 9,298,548 B2
• Filed: 12/06/2012
• Issued: 03/29/2016
• Est. Priority Date: 12/12/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Leggette, Wesley, Baptist, Andrew, Dhuse, Greg, Resch, Jason K., Volvovski, Ilya, Motwani, Manish, Gladwin, S. Christopher, Grube, Gary W., Shirley, Thomas Franklin Jr.
• Primary Examiner(s): Blair, April Y
• Assistant Examiner(s): GANDHI, DIPAKKUMAR B
• Application Number:
  US13/707,428
• Publication Number:
  US 20130151925A1
• Time in Patent Office: 1,209 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• 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 2211/1028 Distributed, i.e. distributed RAID systems with parity
• 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 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• 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/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 selecting a set of distributed storage and task (DST) execution units for executing a task and determining dispersed storage error coding parameters for data. The method continues with the DS processing module dispersed storage error encoding the data in accordance with the parameters to produce a plurality of encoded data blocks and grouping the plurality of encoded data blocks into a plurality of encoded data block groupings. The method continues with the DS processing module partitioning the task into a set of partial tasks, outputting at least some of the plurality of encoded data block groupings to the set of DST execution units, and outputting the set of partial tasks to the set of DST execution units for execution of the set of partial tasks on the at least some of plurality of encoded data block groupings.

Claims

1. A method for distributed computing of a task on data, the method comprises:

selecting a set of distributed storage and task (DST) execution units for executing the task based on at least one of the task and DST execution unit capability information;

determining dispersed storage error coding parameters for the data based on information regarding the set of DST execution units;

dispersed storage error encoding the data in accordance with the dispersed storage error coding parameters to produce a plurality of encoded data blocks;

grouping the plurality of encoded data blocks into a plurality of encoded data block groupings in accordance with the dispersed storage error encoding;

partitioning the task into a set of partial tasks based on at least one of the DST execution unit capability information and the information regarding the set of DST execution units;

outputting at least some of the plurality of encoded data block groupings to the set of DST execution units; and

outputting the set of partial tasks to the set of DST execution units for execution of the set of partial tasks on the at least some of the plurality of encoded data block groupings.

2. The method of claim 1 further comprises:

identifying a superset of DST execution units for storing the plurality of encoded data block groupings, wherein the superset of DST execution units includes the set of DST execution units; and

outputting other encoded data block groupings of the plurality of encoded data block groupings to other DST execution units of the superset of DST execution units, wherein the superset of DST execution units stores the plurality of encoded data block groupings.

3. The method of claim 1, wherein the selecting the set of DST execution units comprises:

determining execution requirements of the task;

analyzing, in light of the execution requirements, the DST execution unit capability information for a plurality of DST execution units;

identifying DST execution units of the plurality of DST execution units that have capabilities corresponding to the execution requirements; and

selecting the set of DST execution units from the identified DST execution units.

4. The method of claim 1, wherein the grouping the plurality of encoded data blocks further comprises:

grouping the plurality of encoded data blocks into the plurality of encoded data block groupings based on at least one of the DST execution unit capability information and the information regarding the set of DST execution units, wherein a first grouping of encoded data blocks of the plurality of encoded data block groupings includes less encoded data blocks than a second grouping of encoded data blocks of the plurality of encoded data block groupings.

5. The method of claim 1, wherein the partitioning the task into the set of partial tasks comprises one of:

replicating the task for each of the set of DST execution units to produce the set of partial tasks;

identifying sub-tasks of the task and producing the set of partial tasks based on the identified sub-tasks; and

identifying the sub-tasks of the task and replicating the identified sub-tasks for each of the set of DST execution units to produce the set of partial tasks.

6. The method of claim 1, wherein the outputting the at least some of the plurality of encoded data block groupings comprises:

generating an encryption key for an encoded data block grouping of the at least some of the plurality of encoded data block groupings associated with a selected DST execution unit of the set of DST execution units based on one or more of a corresponding DST execution unit identifier, a Diffie Hellman exchange with the selected DST execution unit, a data identifier associated with the data, and a retrieved key;

encrypting the encoded data block grouping using the encryption key to produce an encrypted encoded data block grouping; and

outputting the encrypted encoded data block grouping to the selected DST execution unit.

7. A dispersed storage (DS) module comprises:

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

select a set of distributed storage and task (DST) execution units for executing a task on data based on at least one of the task and DST execution unit capability information;

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

determine dispersed storage error coding parameters for the data based on information regarding the set of DST execution units;

dispersed storage error encoding the data in accordance with the dispersed storage error coding parameters to produce a plurality of encoded data blocks; and

grouping the plurality of encoded data blocks into a plurality of encoded data block groupings in accordance with the dispersed storage error encoding;

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

partition the task into a set of partial tasks based on at least one of the DST execution unit capability information and the information regarding the set of DST execution units; and

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

output at least some of the plurality of encoded data block groupings to the set of DST execution units; and

output the set of partial tasks to the set of DST execution units for execution of the set of partial tasks on the at least some of the plurality of encoded data block groupings.

8. The DS module of claim 7 further comprises:

the first module further functions to identify a superset of DST execution units for storing the plurality of encoded data block groupings, wherein the superset of DST execution units includes the set of DST execution units; and

the fourth module further functions to output other encoded data block groupings of the plurality of encoded data block groupings to other DST execution units of the superset of DST execution units, wherein the superset of DST execution units stores the plurality of encoded data block groupings.

9. The DS module of claim 7, wherein the first module functions to select the set of DST execution units by:

determining execution requirements of the task;

analyzing, in light of the execution requirements, the DST execution unit capability information for a plurality of DST execution units;

identifying DST execution units of the plurality of DST execution units that have capabilities corresponding to the execution requirements; and

selecting the set of DST execution units from the identified DST execution units.

10. The DS module of claim 7, wherein the second module functions to group the plurality of encoded data blocks further by:

grouping the plurality of encoded data blocks into the plurality of encoded data block groupings based on at least one of the DST execution unit capability information and the information regarding the set of DST execution units, wherein a first grouping of encoded data blocks of the plurality of encoded data block groupings includes less encoded data blocks than a second grouping of encoded data blocks of the plurality of encoded data block groupings.

11. The DS module of claim 7, wherein the third module functions to partition the task into a set of partial tasks by one of:

replicating the task for each of the set of DST execution units to produce the set of partial tasks;

identifying sub-tasks of the task and producing the set of partial tasks based on the identified sub-tasks; and

identifying the sub-tasks of the task and replicating the identified sub-tasks for each of the set of DST execution units to produce the set of partial tasks.

12. The DS module of claim 7, wherein the fourth module functions to output the at least some of the plurality of encoded data block groupings by:

generating an encryption key for an encoded data block grouping of the at least some of the plurality of encoded data block groupings associated with a selected DST execution unit of the set of DST execution units based on one or more of a corresponding DST execution unit identifier, a Diffie Hellman exchange with the selected DST execution unit, a data identifier associated with the data, and a retrieved key;

encrypting the encoded data block grouping using the encryption key to produce an encrypted encoded data block grouping; and

outputting the encrypted encoded data block grouping to the selected DST execution unit.