Using dispersed computation to change dispersal characteristics

• US 10,268,554 B2
• Filed: 11/28/2017
• Issued: 04/23/2019
• Est. Priority Date: 02/05/2013
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Leggette, Wesley B., Baptist, Andrew D., Dhuse, Greg R., Resch, Jason K., Grube, Gary W., Gladwin, S. Christopher
• Primary Examiner(s): Moser, Bruce M
• Application Number:
  US15/823,811
• Publication Number:
  US 20180081769A1
• Time in Patent Office: 511 Days
• 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/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 16/16 File or folder operations, e.g. details of user interfaces specifically adapted to file systems
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/235 Update request formulation
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06Q 30/04 Billing or invoicing
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• 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 determining an encoding modification for a set of encoded data slices. The method continues by determining a plurality of tasks for executing the encoding modification. The method continues by dividing a first task of the plurality of tasks into one or more partial tasks based on the first task and assigning a first partial task of the one or more partial tasks to a first storage unit. The method continues by dividing a second task of the plurality of tasks into a plurality of partial tasks based on the second task and assigning the plurality of partial tasks to a set of storage units. The method continues by executing, by the first storage unit and at least some storage units of the set of storage units, the first partial task and the plurality of partial tasks, respectively, to produce a modified set of encoded data slices.

Claims

1. A method comprises:

determining, by a computing device, an encoding modification for a set of encoded data slices, wherein a data segment of data is dispersed storage error encoded into the set of encoded data slices based on dispersed storage error encoding parameters;

determining, by the computing device, a plurality of tasks for executing the encoding modification, wherein the encoding modification includes altering one or more parameters of the dispersed storage error encoding parameters;

dividing, by the computing device, a first task of the plurality of tasks into one or more partial tasks based on the first task;

assigning, by the computing device, a first partial task of the one or more partial tasks to a first storage unit;

dividing, by the computing device, a second task of the plurality of tasks into a plurality of partial tasks based on the second task;

assigning, by the computing device, the plurality of partial tasks to a set of storage units; and

executing, by the first storage unit and at least some storage units of the set of storage units, the first partial task and the plurality of partial tasks, respectively, to produce a modified set of encoded data slices.

2. The method of claim 1, wherein the encoding modification comprises one or more of:

deleting one or more encoded data slices;

adding one or more encoded data slices;

re-encoding the data segment using a new decode threshold;

changing coefficients of an encoding matrix; and

changing an encoding function.

3. The method of claim 1, wherein determination factors for the determining the encoding modification comprises:

comparing a measured reliability to a reliability threshold;

modifying a storage location;

responding to new hardware; and

changing a storage tier.

4. The method of claim 1, wherein when the encoding modification is to add an encoded data slice:

determining, by the computing device, the first task is obtaining a data matrix;

determining, by the computing device;

a first intermediate task is creating a new row of an encoding matrix;

a second intermediate task is performing a matrix multiplication of the new row by the data matrix to produce the encoded data slice; and

a third intermediate task is storing the encoded data slice; and

determining, by the computing device, the second task is updating slice names for the set of encoded data slices.

5. The method of claim 1, wherein when the encoding modification is to delete an encoded data slice:

determining, by the computing device, the first task is identifying the encoded data slice;

determining, by the computing device;

a first intermediate task is sending a delete command to a storage unit of the set of storage units that is storing the identified encoded data slice; and

determining, by the computing device, the second task is updating slice names for set of encoded data slices.

6. The method of claim 1, wherein when the encoding modification is to change an encoding matrix:

determining, by the computing device, the first task is obtaining a data matrix;

determining, by the computing device;

a first intermediate task is creating a new encoding matrix;

a second intermediate task is performing a matrix multiplication of the new encoding matrix by the data matrix to produce a coded matrix;

a third intermediate task is transforming the coded matrix to produce the modified set of encoded data slices; and

a fourth intermediate task is storing the modified set of encoded data slices; and

determining, by the computing device, the second task is updating slice names for the modified set of encoded data slices.

7. The method of claim 6 further comprises:

determining, by the computing device, the first intermediate task includes a plurality of partial first intermediate tasks, wherein the plurality of partial first intermediate tasks include a first partial first intermediate task of obtaining a first row of the new encoding matrix; and

determining, by the computing device, the second intermediate task includes a plurality of partial second intermediate tasks, wherein the plurality of partial second intermediate tasks include a first partial second intermediate task of multiplying the first row of the new encoding matrix with the data matrix to produce a first new encoded data slice of the modified set of encoded data slices.

8. The method of claim 7, wherein the plurality of partial first intermediate tasks includes a second partial first intermediate task of obtaining a second row of the new encoding matrix;

and

the plurality of partial second intermediate tasks includes a second partial second intermediate task of multiplying the second row of the new encoding matrix with the data matrix to produce a second new encoded data slice of the modified set of encoded data slices.

9. A non-transitory computer readable storage device comprises:

a first memory section for storing operational instructions that when executed by a computing device of a dispersed storage network (DSN), cause the computing device to;

determine an encoding modification for a set of encoded data slices, wherein a data segment of data is dispersed storage error encoded into the set of encoded data slices based on dispersed storage error encoding parameters;

a second memory section for storing operational instructions, that when executed by the computing device, cause the computing device to;

determine a plurality of tasks for executing the encoding modification, wherein the encoding modification includes altering one or more parameters of the dispersed storage error encoding parameters;

a third memory section for storing operational instructions, that when executed by the computing device, cause the computing device to;

divide a first task of the plurality of tasks into one or more partial tasks based on the first task;

assign a first partial task of the one or more partial tasks to a first storage unit;

divide a second task of the plurality of tasks into a plurality of partial tasks based on the second task;

assign the plurality of partial tasks to a set of storage units; and

a fourth memory section for storing operational instructions, that when executed by the first storage unit and at least some storage units of the set of storage units, cause the first storage unit and at least some storage units of the set of storage units to;

execute the first partial task and the plurality of partial tasks, respectively, to produce a modified set of encoded data slices.

10. The non-transitory computer readable storage device of claim 9, wherein the encoding modification comprises one or more of:

deleting one or more encoded data slices;

adding one or more encoded data slices;

re-encoding the data segment using a new decode threshold;

changing coefficients of an encoding matrix; and

changing an encoding function.

11. The non-transitory computer readable storage device of claim 9, wherein determination factors for the determining the encoding modification comprises:

comparing a measured reliability to a reliability threshold;

modifying a storage location;

responding to new hardware; and

changing a storage tier.

12. The non-transitory computer readable storage device of claim 9, wherein the second memory section stores further operational instructions that, when the encoding modification is to add an encoded data slice, cause the computing device to:

determine the first task is obtaining a data matrix;

determine;

a first intermediate task is creating a new row of an encoding matrix;

a second intermediate task is performing a matrix multiplication of the new row by the data matrix to produce the encoded data slice; and

a third intermediate task is storing the encoded data slice; and

determine the second task is updating slice names for the set of encoded data slices.

13. The non-transitory computer readable storage device of claim 9, wherein the second memory section stores further operational instructions that, when the encoding modification is to delete an encoded data slice, cause the computing device to:

determine the first task is identifying the encoded data slice;

determine a first intermediate task is sending a delete command to a storage unit of the set of storage units that is storing the identified encoded data slice; and

determine the second task is updating slice names for set of encoded data slices.

14. The non-transitory computer readable storage device of claim 9, wherein the second memory section stores further operational instructions that, when the encoding modification is to change an encoding matrix, cause the computing device to:

determine the first task is obtaining a data matrix;

determine;

a first intermediate task is creating a new encoding matrix;

a second intermediate task is performing a matrix multiplication of the new encoding matrix by the data matrix to produce a coded matrix;

a third intermediate task is transforming the coded matrix to produce the modified set of encoded data slices; and

a fourth intermediate task is storing the modified set of encoded data slices; and

determine the second task is updating slice names for the modified set of encoded data slices.

15. The non-transitory computer readable storage device of claim 14 further comprises:

a fifth memory section for storing operational instructions, that when executed by the computing device, cause the computing device to;

determine the first intermediate task includes a plurality of partial first intermediate tasks, wherein the plurality of partial first intermediate tasks include a first partial first intermediate task of obtaining a first row of the new encoding matrix; and

determine the second intermediate task includes a plurality of partial second intermediate tasks, wherein the plurality of partial second intermediate tasks include a first partial second intermediate task of multiplying the first row of the new encoding matrix with the data matrix to produce a first new encoded data slice of the modified set of encoded data slices.

16. The non-transitory computer readable storage device of claim 15, wherein the fifth memory section stores further operational instructions that when executed by the computing device, cause the computing device to:

determine the plurality of partial first intermediate tasks includes a second partial first intermediate task of obtaining a second row of the new encoding matrix; and

determine the plurality of partial second intermediate tasks includes a second partial second intermediate task of multiplying the second row of the new encoding matrix with the data matrix to produce a second new encoded data slice of the modified set of encoded data slices.