Redundant task execution in a distributed storage and task network

• US 9,195,684 B2
• Filed: 01/29/2013
• Issued: 11/24/2015
• Est. Priority Date: 03/02/2012
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): Tiv, Backhean
• Application Number:
  US13/753,404
• Publication Number:
  US 20130232184A1
• Time in Patent Office: 1,029 Days
• Field of Search: 709/201
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• 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/5083 Techniques for rebalancing the load in a distributed system
• 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 determining data block storage redundancy among a set of distributed storage and task (DST) execution units. The method continues with the DS processing module dispersed storage error encoding a data segment of data to produce a set of encoded data slices, where a first encoded data slice of the set of encoded data slices includes at least one redundant encoded data block in common with a second encoded data slice of the set of encoded data slices. The method continues with the DS processing module assigning a first partial task and a first encoded block processing order to a first DST execution unit regarding processing the first encoded data slice and assigning a second partial task and a second encoded block processing order to a second DST execution unit regarding processing the second encoded data slice.

Claims

1. A method for execution by a computer to manage distributed computing of a task, the method comprises:

determining a data block storage redundancy policy among a set of distributed storage and task (DST) execution units based on processing latency information of the set of DST execution units;

dispersed storage error encoding, in accordance with the data block storage redundancy, a data segment of data to produce a set of encoded data slices, wherein a first encoded data slice of the set of encoded data slices includes a first set of encoded data blocks, a second encoded data slice of the set of encoded data slices includes a second set of encoded data blocks, and at least one redundant encoded data block is included in both of the first and second sets of encoded data blocks;

assigning a set of partial tasks to the set of DST execution units regarding the set of encoded data slices;

assigning a first partial task of the set of partial tasks and a first encoded data block processing order to a first DST execution unit of the set of DST execution units regarding processing the first set of encoded data blocks of the first encoded data slice; and

assigning a second partial task of the set of partial tasks and a second encoded data block processing order to a second DST execution unit of the set of DST execution units regarding processing the second set of encoded data blocks of the second encoded data slice, wherein the first encoded data block processing order causes the first DST execution unit to execute the first partial task on the at least one redundant encoded data block when processing latency of the second DST execution unit is unfavorable to processing latency of the first DST execution unit and wherein the second encoded data block processing order causes the second DST execution unit to execute the second partial task on the at least one redundant encoded data block when the processing latency of the first DST execution unit is unfavorable to the processing latency of the second DST execution unit.

2. The method of claim 1, wherein the data block storage redundancy policy comprises at least one of:

an indication of a number of encoded data blocks to include in the at least one redundant encoded data block;

an indication of which DST execution units of the set of DST executions units are to have overlapping redundant encoded data blocks; and

an indication as to whether a DST execution unit of the set of DST execution units is to have overlapping redundant encoded data blocks with multiple DST execution units of the set of DST execution units.

3. The method of claim 1, wherein the processing latency information of the set of DST execution units comprises at least one of:

queues for each of the set of DST execution units regarding outstanding partial tasks for execution;

historical processing times for each of the set of DST execution units regarding processing various types of partial tasks;

network connection capabilities of each of the set of DST execution units;

processing resources of each of the set of DST execution units; and

predicted task execution response time for each of the set of DST execution units.

4. The method of claim 1, wherein the dispersed storage error encoding the data segment comprises:

arranging the data segment into a data matrix of data blocks;

encoding the data matrix with an encoding matrix to produce an encoded matrix that includes a plurality of encoded data blocks;

creating an initial set of encoded data slices from the encoded matrix, wherein an encoded data slice of the set of encoded data slices includes a set of encoded data blocks of the plurality of encoded data blocks;

identifying a first encoded data block of a first initial encoded data slice of the initial set of encoded data slices;

identifying a second encoded data block of a second initial encoded data slice of the initial set of encoded data slices;

appending the second encoded data block to the first initial encoded data slice to produce the first encoded data slice; and

appending the first encoded data block to the second initial encoded data slice to produce the second encoded data slice.

5. The method of claim 1 further comprises:

the first encoded data block processing order including prioritizing processing of other encoded data blocks of the first encoded data slice over the at least one redundant encoded data block;

the second encoded data block processing order including prioritizing processing of other encoded data blocks of the second encoded data slice over the at least one redundant encoded data block;

the first encoded data block processing order further including determining whether the second DST execution unit is likely to process the at least one redundant encoded data block before the first DST execution unit and, when the second DST execution unit is unlikely to process the at least one redundant encoded data block before the first DST execution unit, assuming, by the first DST execution unit responsibility for performing the first partial task on the at least one redundant encoded data block; and

the second encoded data block processing order further including determining whether the first DST execution unit is likely to process the at least one redundant encoded data block before the second DST execution unit and, when the first DST execution unit is unlikely to process the at least one redundant encoded data block before the second DST execution unit, assuming, by the second DST execution unit responsibility for performing the second partial task on the at least one redundant encoded data block.

6. A method for execution by a distributed storage and task (DST) execution unit, the method comprises:

receiving an assigned partial task and an encoded data block processing order regarding processing an encoded data slice, wherein a data segment of data is dispersed storage error encoded in accordance with a data block storage redundancy policy to produce a set of encoded data slices, wherein a first encoded data slice of the set of encoded data slices includes a first set of encoded data blocks, a second encoded data slice of the set of encoded data slices includes a second set of encoded data blocks, and at least one redundant encoded data block is included in both of the first and second sets of encoded data blocks;

commencing execution of the assigned partial task on the first set of encoded data blocks in accordance with the encoded data block processing order;

executing the assigned partial task on the at least one redundant encoded data block when latency of processing the first set of encoded data blocks is favorable to another DST execution unit latency of processing the second set of encoded data blocks; and

skipping execution of the assigned partial task on the at least one redundant encoded data block when the latency of processing the first set of encoded data blocks is unfavorable to the other DST execution unit latency of processing the second set of encoded data blocks.

7. The method of claim 6, wherein the data block storage redundancy policy comprises at least one of:

an indication of a number of encoded data blocks to include in the at least one redundant encoded data block;

an indication of which DST execution units of a set of DST executions units are to have overlapping redundant encoded data blocks; and

an indication as to whether a DST execution unit of the set of DST execution units is to have the overlapping redundant encoded data blocks with multiple DST execution units of the set of DST execution units.

8. The method of claim 6, wherein the latency of processing the first set of encoded data blocks and the second set of encoded data blocks comprises at least one of:

processing queues for first and second DST execution units regarding outstanding partial tasks for execution, wherein the first DST execution unit receives the first set of encoded data blocks and the second DST execution unit receives the second set of encoded data blocks;

historical processing times for each of the first and second DST execution units regarding processing various types of partial tasks;

network connection capabilities of each of the first and second DST execution units;

processing resources of each of the first and second DST execution units; and

predicted task execution response time for each of the first and second DST execution units.

9. The method of claim 6, wherein the dispersed storage error encoding the data segment comprises:

arranging the data segment into a data matrix of data blocks;

encoding the data matrix with an encoding matrix to produce an encoded matrix that includes a plurality of encoded data blocks;

creating an initial set of encoded data slices from the encoded matrix, wherein one of the set of encoded data slices includes a set of encoded data blocks of the plurality of encoded data blocks;

identifying a first encoded data block of a first initial encoded data slice of the initial set of encoded data slices;

identifying a second encoded data block of a second initial encoded data slice of the initial set of encoded data slices;

appending the second encoded data block to the first initial encoded data slice to produce the first encoded data slice; and

appending the first encoded data block to the second initial encoded data slice to produce the second encoded data slice.

10. The method of claim 6 further comprises:

the encoded data block processing order including prioritizing processing of other encoded data blocks of the first encoded data slice over the at least one redundant encoded data block; and

the encoded data block processing order further including determining whether another DST execution unit is likely to process the at least one redundant encoded data block before the DST execution unit and, when the other DST execution unit is unlikely to process the at least one redundant encoded data block before the DST execution unit, assuming, by the DST execution unit responsibility for performing the partial task on the at least one redundant encoded data block.

11. A dispersed storage (DS) module of a computing device to manage distributed computing of a task, the DS module comprises:

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

determine a data block storage redundancy policy among a set of distributed storage and task (DST) execution units based on processing latency information of the set of DST execution units;

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

dispersed storage error encode, in accordance with the data block storage redundancy policy, a data segment of data to produce a set of encoded data slices, wherein a first encoded data slice of the set of encoded data slices includes a first set of encoded data blocks, a second encoded data slice of the set of encoded data slices includes a second set of encoded data blocks, and at least one redundant encoded data block is included in both of the first and second sets of encoded data blocks; and

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

assign a set of partial tasks to the set of DST execution units regarding the set of encoded data slices;

assign a first partial task of the set of partial tasks and a first encoded data block processing order to a first DST execution unit of the set of DST execution units regarding processing the first set of encoded data blocks of the first encoded data slice; and

assign a second partial task of the set of partial tasks and a second encoded data block processing order to a second DST execution unit of the set of DST execution units regarding processing the second set of encoded data blocks of the second encoded data slice, wherein the first encoded data block processing order causes the first DST execution unit to execute the first partial task on the at least one redundant encoded data block when processing latency of the second DST execution unit is unfavorable to processing latency of the first DST execution unit and wherein the second encoded data block processing order causes the second DST execution unit to execute the second partial task on the at least one redundant encoded data block when the processing latency of the first DST execution unit is unfavorable to the processing latency of the second DST execution unit.

12. The DS module of claim 11, wherein the data block storage redundancy policy comprises at least one of:

an indication of a number of encoded data blocks to include in the at least one redundant encoded data block;

an indication of which DST execution units of the set of DST executions units are to have overlapping redundant encoded data blocks; and

an indication as to whether a DST execution unit of the set of DST execution units is to have the overlapping redundant encoded data blocks with multiple DST execution units of the set of DST execution units.

13. The DS module of claim 11, wherein the processing latency information of the set of DST execution units comprises at least one of:

queues for each of the set of DST execution units regarding outstanding partial tasks for execution;

historical processing times for each of the set of DST execution units regarding processing various types of partial tasks;

network connection capabilities of each of the set of DST execution units;

processing resources of each of the set of DST execution units; and

predicted task execution response time for each of the set of DST execution units.

14. The DS module of claim 11, wherein the second module functions to dispersed storage error encode the data segment by:

arranging the data segment into a data matrix of data blocks;

encoding the data matrix with an encoding matrix to produce an encoded matrix that includes a plurality of encoded data blocks;

creating an initial set of encoded data slices from the encoded matrix, wherein an encoded data slice of the set of encoded data slices includes a set of encoded data blocks of the plurality of data blocks;

identifying a first encoded data block of a first initial encoded data slice of the initial set of encoded data slices;

identifying a second encoded data block of a second initial encoded data slice of the initial set of encoded data slices;

appending the second encoded data block to the first initial encoded data slice to produce the first encoded data slice; and

appending the first encoded data block to the second initial encoded data slice to produce the second encoded data slice.

15. The DS module of claim 11 further comprises:

the first encoded data block processing order including prioritizing processing of other encoded data blocks of the first encoded data slice over the at least one redundant encoded data block;

the second data encoded block processing order including prioritizing processing of other encoded data blocks of the second encoded data slice over the at least one redundant encoded data block;

the first encoded data block processing order further including determining whether the second DST execution unit is likely to process the at least one redundant encoded data block before the first DST execution unit and, when the second DST execution unit is unlikely to process the at least one redundant encoded data block before the first DST execution unit, assuming, by the first DST execution unit responsibility for performing the first partial task on the at least one redundant encoded data block; and

the second encoded data block processing order further including determining whether the first DST execution unit is likely to process the at least one redundant encoded data block before the second DST execution unit and, when the first DST execution unit is unlikely to process the at least one redundant encoded data block before the second DST execution unit, assuming, by the second DST execution unit responsibility for performing the second partial task on the at least one redundant encoded data block.

16. A dispersed storage (DS) module of a distributed storage and task (DST) execution unit, the DS module comprises:

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

receive an assigned partial task and an encoded data block processing order regarding processing an encoded data slice, wherein a data segment of data is dispersed storage error encoded in accordance with a data block storage redundancy policy to produce a set of encoded data slices, wherein a first encoded data slice of the set of encoded data slices includes a first set of encoded data blocks, a second encoded data slice of the set of encoded data slices includes a second set of encoded data blocks, and at least one redundant encoded data block is included in both of the first and second sets of encoded data blocks; and

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

commence execution of the assigned partial task on the first set of encoded data blocks in accordance with the encoded data block processing order;

execute the partial task on the at least one redundant encoded data block when latency of processing the first set of encoded data blocks is favorable to another DST execution unit latency of processing the second set of encoded data blocks;

skip execution of the partial task on the at least one redundant encoded data block when the latency of processing the first set of encoded data blocks is unfavorable to the other DST execution unit latency of processing the second set of encoded data blocks.

17. The DS module of claim 16, wherein the data block storage redundancy policy comprises at least one of:

an indication of a number of encoded data blocks to include in the at least one redundant encoded data block;

an indication of which DST execution units of a set of DST executions units are to have overlapping redundant encoded data blocks; and

an indication as to whether a DST execution unit of the set of DST execution units is to have the overlapping redundant encoded data blocks with multiple DST execution units of the set of DST execution units.

18. The DS module of claim 16, wherein the latency of processing the first set of encoded data blocks and of the second set of encoded data blocks comprises at least one of:

processing queues for first and second DST execution units regarding outstanding partial tasks for execution, wherein the first DST execution unit receives the first set of encoded data blocks and the second DST execution unit receives the second set of encoded data blocks;

historical processing times for each of the first and second DST execution units regarding processing various types of partial tasks;

network connection capabilities of each of the first and second DST execution units;

processing resources of each of the first and second DST execution units; and

predicted task execution response time for each of the first and second DST execution units.

19. The DS module of claim 16, wherein the dispersed storage error encoding the data segment comprises:

arranging the data segment into a data matrix of data blocks;

encoding the data matrix with an encoding matrix to produce an encoded matrix that includes a plurality of encoded data blocks;

creating an initial set of encoded data slices from the encoded matrix, wherein one of the set of encoded data slices includes a set of encoded data blocks of the plurality of encoded data blocks;

identifying a first encoded data block of a first initial encoded data slice of the initial set of encoded data slices;

identifying a second encoded data block of a second initial encoded data slice of the initial set of encoded data slices;

appending the second encoded data block to the first initial encoded data slice to produce the first encoded data slice; and

appending the first encoded data block to the second initial encoded data slice to produce the second encoded data slice.

20. The DS module of claim 16 further comprises:

the encoded data block processing order including prioritizing, by the second module, processing of other encoded data blocks of the first encoded data slice over the at least one redundant encoded data block; and

the encoded data block processing order further including determining, by the second module, whether another DST execution unit is likely to process the at least one redundant encoded data block before the DST execution unit and, when the other DST execution unit is unlikely to process the at least one redundant encoded data block before the DST execution unit, assuming, by the DST execution unit responsibility for performing the partial task on the at least one redundant encoded data block.