Redundant Task Execution in a Distributed Storage and Task Network

• US 20130232184A1
• Filed: 01/29/2013
• Published: 09/05/2013
• Est. Priority Date: 03/02/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W.
• Granted Patent: US 9,195,684 B2
• Time in Patent Office: Days
• US Class Current: 709/201
• 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 data block storage redundancy 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 at least one redundant encoded data block in common with a second encoded data slice of the set of encoded data slices;

assigning a first partial task and a first encoded block processing order to a first DST execution unit of the set of DST execution units 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 of the set of DST execution units regarding processing the second encoded data slice, wherein the first encoded 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 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 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 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 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 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 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 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 the encoded data slice includes at least one redundant encoded data block in common with another encoded data slice of the set of encoded data slices;

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

executing the assigned partial task on the at least one redundant encoded data block when latency of processing the other encoded data slice is unfavorable to latency of processing the encoded data slice; and

skipping execution of the assigned partial task on the at least one redundant encoded data block when the latency of processing the other encoded data slice is favorable to the latency of processing the encoded data slice.

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 encoded data slice and of the other encoded data slice 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 encoded data slice and the second DST execution unit receives the other encoded data slice;

historical processing times for each of the first and second 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 encoded data slice; and

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

10. The method of claim 6 further comprises:

the encoded 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 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 data block storage redundancy 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, 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 at least one redundant encoded data block in common with a second encoded data slice of the set of encoded data slices; and

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

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

assign a second partial task and a second encoded block processing order to a second DST execution unit of the set of DST execution units regarding processing the second encoded data slice, wherein the first encoded 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 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 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 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 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 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 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 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 the encoded data slice includes at least one redundant encoded data block in common with another encoded data slice of the set of encoded data slices; and

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

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

execute the partial task on the at least one redundant encoded data block when latency of processing the other encoded data slice is unfavorable to latency of processing the encoded data slice; and

skip execution of the partial task on the at least one redundant encoded data block when the latency of processing the other encoded data slice is favorable to the latency of processing the encoded data slice.

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 encoded data slice and of the other encoded data slice 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 encoded data slice and the second DST execution unit receives the other encoded data slice;

historical processing times for each of the first and second 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 encoded data slice; and

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

20. The DS module of claim 16 further comprises:

the encoded 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 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.