Distributed storage and computing of interim data

• US 9,584,359 B2
• Filed: 06/13/2013
• Issued: 02/28/2017
• Est. Priority Date: 12/12/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew, Dhuse, Greg, Leggette, Wesley, Resch, Jason K.
• Primary Examiner(s): LAMARRE, GUY J
• Application Number:
  US13/917,058
• Publication Number:
  US 20130275545A1
• Time in Patent Office: 1,356 Days
• Field of Search: 714/764, 711/168, 709/215
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 67/01 Protocols
• 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]
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A method begins by a set of distributed storage and task (DST) execution units receiving a set of partial tasks and data, where a partial task of the set of partial tasks includes a common task and a unique partial sub-task. The method continues with the set of DST execution units executing the common task on the data to produce a set of preliminary partial results. The method continues with a first DST execution unit of the set of DST execution units generating first interim data based on the at least some of the set of preliminary partial results. The method continues with the first DST execution unit executing a first unique partial sub-task on at least one of a first portion of the data and the first interim data to produce a first partial result.

Claims

1. A method comprises:

receiving, from a distributed storage and task (DST) client module via a network and by a set of DST execution units, a set of partial tasks and data, wherein a partial task of the set of partial tasks includes a common task and a unique partial sub-task, wherein the set of DST execution units includes processing circuitry configured to perform at least one of the set of partial tasks on the data;

executing, by the set of DST execution units, the common task on the data to produce a set of preliminary partial results;

generating, by a first DST execution unit of the set of DST execution units, first interim data based on the at least some of the set of preliminary partial results;

executing, by the first DST execution unit, a first unique partial sub-task on at least one of;

a first portion of the data or the first interim data to produce a first partial result; and

transmitting, by the set of DST execution units, a plurality of partial results that includes the first partial result from the first DST execution unit and a second partial result from a second DST execution unit to the DST client module to be processed by the DST client module to produce a result corresponding to the at least one of the set of partial tasks performed on the data.

2. The method of claim 1 further comprises:

receiving, by the first DST execution unit, a first partial task of the set of partial tasks and the first portion of the data, wherein the first partial task includes the common task and the first unique partial sub-task;

receiving, by the second DST execution unit, a second partial task of the set of partial tasks and a second portion of the data, wherein the second partial task includes the common task and a second unique partial sub-task; and

receiving, by a third DST execution unit, a third partial task of the set of partial tasks and a third portion of the data, wherein the third partial task includes the common task and a third unique partial sub-task.

3. The method of claim 2 further comprises at least one of:

allocating the data into the first, second, and third portions of the data based on a time parameter;

allocating the data into the first, second, and third portions of the data based on a geographic parameter;

or

allocating the data into the first, second, and third portions of the data based on a source parameter.

4. The method of claim 2, wherein the executing the common task on the data to produce the set of preliminary partial results comprises:

executing, by the first DST execution unit, the common task on the first portion of the data to produce a first preliminary partial result of the set of preliminary partial results;

executing, by the second DST execution unit, the common task on the second portion of the data to produce a second preliminary partial result of the set of preliminary partial results; and

executing, by the third DST execution unit, the common task on the third portion of the data to produce a third preliminary partial result of the set of preliminary partial results.

5. The method of claim 4, wherein the generating the first interim data comprises:

processing at least one of the first, second, or third preliminary partial results to produce the first interim data.

6. The method of claim 1 further comprises:

the common task corresponding to a function to identify a common characteristic of portions of the data; and

the unique partial sub-task corresponding to a function to uniquely categorize the common characteristic of the portions of the data based on a unique parameter.

7. The method of claim 1 further comprises:

generating, by the second DST execution unit of the set of DST execution units, second interim data based on the at least some of the set of preliminary partial results; and

generating, by a third DST execution unit of the set of DST execution units, third interim data based on the at least some of the set of preliminary partial results.

8. The method of claim 7 further comprises:

generating, by the first DST execution unit, first partial redundancy data based on the first interim data;

generating, by the second DST execution unit, second partial redundancy data based on the second interim data;

generating, by the third DST execution unit, third partial redundancy data based on the third interim data; and

generating, by a fourth DST execution unit of the set of DST execution units, redundancy data for the first, second, and third interim data based on the first, second, and third partial redundancy data.

9. A distributed computing system comprises:

a set of modules associated with a set of distributed storage and task (DST) execution units, wherein the set of modules includes processing circuitry configured to perform at least one of a set of partial tasks on data, and wherein the set of modules is configured to;

receive, from a distributed storage and task (DST) client module via a network the set of partial tasks and the data, wherein a partial task of the set of partial tasks includes a common task and a unique partial sub-task; and

execute the common task on the data to produce a set of preliminary partial results, wherein a first module of the set of modules is configured to;

generate first interim data based on the at least some of the set of preliminary partial results;

facilitate storage of the first interim data in memory associated with a first DST execution unit;

execute a first unique partial sub-task on at least one of;

a first portion of the data or the first interim data to produce a first partial result;

output, via an interface associated with the first DST execution unit, the first partial result; and

transmit a plurality of partial results that includes the first partial result from the first DST execution unit and a second partial result from a second DST execution unit to the DST client module to be processed by the DST client module to produce a result corresponding to the at least one of the set of partial tasks performed on the data.

10. The distributed computing system of claim 9 further comprises:

the first module further functions to receive, via the interface associated with the first DST execution unit, a first partial task of the set of partial tasks and the first portion of the data, wherein the first partial task includes the common task and the first unique partial sub-task;

a second module of the set of modules functions to receive, via an interface associated with ft the second DST execution unit, a second partial task of the set of partial tasks and a second portion of the data, wherein the second partial task includes the common task and a second unique partial sub-task; and

a third module of the set of modules functions to receive, via an interface associated with a third DST execution unit, a third partial task of the set of partial tasks and a third portion of the data, wherein the third partial task includes the common task and a third unique partial sub-task.

11. The distributed computing system of claim 10 further comprises:

the set of modules is further configured to;

allocate the data into the first, second, and third portions of the data based on a time parameter;

allocate the data into the first, second, and third portions of the data based on a geographic parameter; and

allocate the data into the first, second, and third portions of the data based on a source parameter.

12. The distributed computing system of claim 10, wherein the set of modules functions to execute the common task on the data to produce the set of preliminary partial results by:

executing, by the first module, the common task on the first portion of the data to produce a first preliminary partial result of the set of preliminary partial results;

executing, by the second module, the common task on the second portion of the data to produce a second preliminary partial result of the set of preliminary partial results; and

executing, by the third module, the common task on the third portion of the data to produce a third preliminary partial result of the set of preliminary partial results.

13. The distributed computing system of claim 12, wherein the first module generates the first interim data by:

processing at least one of the first, second, or third preliminary partial results to produce the first interim data.

14. The distributed computing system of claim 9 further comprises:

the common task corresponding to a function to identify a common characteristic of portions of the data; and

the unique partial sub-task corresponding to a function to uniquely categorize the common characteristic of the portions of the data based on a unique parameter.

15. The distributed computing system of claim 9 further comprises:

a second module of the set of modules functions to generate second interim data based on the at least some of the set of preliminary partial results; and

a third module of the set of modules functions to generate third interim data based on the at least some of the set of preliminary partial results.

16. The distributed computing system of claim 15 further comprises:

the first module further functions to generate first partial redundancy data based on the first interim data;

the second module further functions to generate second partial redundancy data based on the second interim data;

the third module further functions to generate third partial redundancy data based on the third interim data; and

a fourth module of the set of modules functions to generate redundancy data for the first, second, and third interim data based on the first, second, and third partial redundancy data.