IP Library Granted Patent US 10,768,833
Granted Patent B2
US 10,768,833 · App. 15/819,198 · Granted Sep 8, 2020

Object dispersal load balancing

Inventors: Gary W. Grube (Barrington Hills, IL); Greg R. Dhuse (Chicago, IL); Wesley B. Leggette (Chicago, IL); Jason K. Resch (Chicago, IL); Andrew D. Baptist (Mt. Pleasant, WI); Ilya Volvovski (Chicago, IL)
Assignee: PURE STORAGE, INC.
G06F3/0631G06F3/064G06F3/0604G06F3/067G06F3/0619G06F3/0635G06F3/0659G06F11/1076H04L67/1097
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 10,768,833
App. No.
15/819,198
Granted
Sep 8, 2020
Kind
B2
Abstract

A method includes dividing dispersed storage error encoding of a data object into a plurality of operations based on at least one of the data object and available computing devices for executing the dispersed storage error encoding. The method further includes allocating the plurality of operations to the available computing devices, where a first encoding operation of the plurality of encoding operations is allocated to a first computing device of the available computing devices. The method further includes coordinating execution of the plurality of operations by the available computing devices to dispersed storage error encode the data object into a plurality of sets of encoded data slices and a corresponding plurality of sets of slice names, and write the plurality of sets of encoded data slices based on the corresponding plurality of sets of slice names to a set of storage units.

Claims (65)

1. A method comprises:

dividing, by a coordinating computing device of a dispersed storage network (DSN), dispersed storage error encoding of a data object into a plurality of operations based on at least one of the data object and available computing devices for executing the dispersed storage error encoding, wherein an operation of the plurality of operations includes at least a portion of: a segmenting operation, an encoding matrix operation, an addressing operation, and a writing operation, wherein the encoding matrix operation includes a unity matrix operation and a redundancy operation;

allocating, by the coordinating computing device, the plurality of operations to the available computing devices, wherein at least one of the plurality of operations is allocated to a first computing device of the available computing devices; and

coordinating, by the coordinating computing device, execution of the plurality of operations by the available computing devices to dispersed storage error encode the data object into a plurality of sets of encoded data slices and a corresponding plurality of sets of slice names, and write the plurality of sets of encoded data slices based on the corresponding plurality of sets of slice names to a set of storage units of the DSN.

2. The method of claim 1 further comprises:

dividing, by the coordinating computing device, the dispersed storage error encoding of the data object into the segmenting operation, the encoding matrix operation, the addressing operation, and the writing operation;

allocating, by the coordinating computing device, the segmenting operation to the first computing device, the encoding matrix operation to a second computing device of the available computing devices, the addressing operation to a third computing device of the available computing devices, and the writing operation to a fourth computing device of the available computing devices;

coordinating, by the coordinating computing device, execution of the segmenting operation by the first computing device to segment the data object into a set of data segments;

coordinating, by the coordinating computing device, execution of the encoding matrix operation by the second computing device to apply an encoding matrix to each data segment of the set of data segments to produce the plurality of sets of encoded data slices;

coordinating, by the coordinating computing device, execution of the addressing operation by the third computing device to produce the corresponding plurality of sets of slice names for the plurality of sets of encoded data slices; and

coordinating, by the coordinating computing device, execution of the writing operation by the fourth computing device to write the plurality of sets of encoded data slices based on the corresponding plurality of sets of slice names to the set of storage units of the DSN.

3. The method of claim 1 further comprises:

dividing, by the coordinating computing device, the dispersed storage error encoding of the data object into a segmenting and unity matrix operation, the redundancy operation, and an addressing and writing operation;

allocating, by the coordinating computing device, the segmenting and unity matrix operation to the first computing device, the redundancy operation to a second computing device of the available computing devices, and the addressing and writing operation to a third computing device of the available computing devices;

coordinating, by the coordinating computing device, execution of the segmenting and unity matrix operation by the first computing device to segment the data object into a set of data segments and apply a unity matrix to each data segment of the set of data segments to create a first plurality of sets of encoded data slices of the plurality of sets of encoded data slices;

coordinating, by the coordinating computing device, execution of the redundancy operation by the second computing device to apply the redundancy operation on each data segment of the set of data segments to produce a remaining plurality of sets of encoded data slices of the plurality of sets of encoded data slices; and

coordinating, by the coordinating computing device, execution of the addressing and writing operation by the third computing device to produce the corresponding plurality of sets of slice names for the plurality of sets of encoded data slices and to write the plurality of sets of encoded data slices based on the corresponding plurality of sets of slice names to the set of storage units of the DSN.

4. The method of claim 1 further comprises:

dividing, by the coordinating computing device, the dispersed storage error encoding of the data object into a first operation including the segmenting operation, the unity matrix operation, a first portion of the addressing operation, and a first portion of the writing operation, and a second operation including the redundancy operation, a second portion of the addressing operation, and a second portion of the writing operation;

allocating, by the coordinating computing device, the first operation to the first computing device and the second operation to a second computing device of the available computing devices;

coordinating, by the coordinating computing device, execution of the first operation by the first computing device to segment the data object into a set of data segments, apply the unity matrix operation to each data segment of the set of data segments to create a first plurality of sets of encoded data slices of the plurality of sets of encoded data slices, produce a corresponding first plurality of sets of slice names of the corresponding plurality of sets of slice names for the first plurality of sets of encoded data slices, and to write the first plurality of sets of encoded data slices based on the corresponding first plurality of sets of slice names to the set of storage units of the DSN; and

coordinating, by the coordinating computing device, execution of the second operation by the second computing device to apply the redundancy operation to each data segment of the set of data segments to create a remaining plurality of sets of encoded data slices of the plurality of sets of encoded data slices, to produce a corresponding remaining plurality of sets of slice names of the corresponding plurality of sets of slice names for the remaining plurality of sets of encoded data slices, and to write the remaining plurality of sets of encoded data slices based on the corresponding remaining second plurality of sets of slice names to the set of storage units of the DSN.

5. The method of claim 1 further comprises:

dividing, by the coordinating computing device, the encoding matrix operation of the dispersed storage error encoding of the data object into a unity matrix operation, a first redundancy operation, and a second redundancy operation;

allocating, by the coordinating computing device, the unity matrix operation to the first computing device, the first redundancy operation to a second computing device of the available computing devices, and the second redundancy operation to a third computing device of the available computing devices; and

coordinating, by the coordinating computing device, execution of the unity matrix operation by the first computing device, the first redundancy operation by the second computing device, and the second redundancy operation by the third computing device to dispersed storage error encode the data object into the plurality of sets of encoded data slices.

6. The method of claim 1 , wherein the coordinating computing device is a computing device of the available computing devices.

7. The method of claim 1 further comprises:

determining, by the coordinating computing device, the available computing devices by at least one of a default setting and a loading function.

8. The method of claim 1 , wherein the coordinating of the execution of the plurality of operations comprises at least one of:

sending, by the coordinating computing device, operation result destination instructions to the available computing devices, wherein an operation result destination instruction of the operation result destination instructions directs a computing device of the available computing devices to send a result of an executed operation of the plurality of operations to a particular location; and

sending, by the coordinating computing device, a dispersed error encoding division scheme to each computing device of the available computing devices, wherein the dispersed error encoding division scheme includes a list of each operation of the plurality of operations and a corresponding computing device of the available computing devices assigned to execute the operation.

9. A coordinating computing device of a dispersed storage network (DSN), the coordinating computing device comprises:

an interface;

memory; and

a processing module operably coupled to the memory and the interface, wherein the processing module is operable to:

divide dispersed storage error encoding of a data object into a plurality of operations, based on at least one of the data object and available computing devices for executing the dispersed storage error encoding, wherein an operation of the plurality of operations includes at least a portion of: a segmenting operation, an encoding matrix operation, an addressing operation, and a writing operation, wherein the encoding matrix operation includes a unity matrix operation and a redundancy operation; allocate the plurality of operations to the available computing devices, wherein at least one of the plurality of operations is allocated to a first computing device of the available computing devices; and coordinate execution of the plurality of operations by the available computing devices to dispersed storage error encode the data object into a plurality of sets of encoded data slices and a corresponding plurality of sets of slice names, and write the plurality of sets of encoded data slices based on the corresponding plurality of sets of slice names to a set of storage units of the DSN.

10. The coordinating computing device of claim 9 , wherein the processing module is further operable to:

divide the dispersed storage error encoding of the data object into the segmenting operation, the encoding matrix operation, the addressing operation, and the writing operation;

allocate the segmenting operation to the first computing device, the encoding matrix operation to a second computing device of the available computing devices, the addressing operation to a third computing device of the available computing devices, and the writing operation to a fourth computing device of the available computing devices;

coordinate execution of the segmenting operation by the first computing device to segment the data object into a set of data segments;

coordinate execution of the encoding matrix operation by the second computing device to apply an encoding matrix to each data segment of the set of data segments to produce the plurality of sets of encoded data slices;

coordinating execution of the addressing operation by the third computing device to produce the corresponding plurality of sets of slice names for the plurality of sets of encoded data slices; and

coordinate execution of the writing operation by the fourth computing device to write the plurality of sets of encoded data slices based on the corresponding plurality of sets of slice names to the set of storage units of the DSN.

11. The coordinating computing device of claim 9 , wherein the processing module is further operable to:

divide the dispersed storage error encoding of the data object into a segmenting and unity matrix operation, the redundancy operation, and an addressing and writing operation;

allocate the segmenting and unity matrix operation to the first computing device, the redundancy operation to a second computing device of the available computing devices, and the addressing and writing operation to a third computing device of the available computing devices;

coordinate execution of the segmenting and unity matrix operation by the first computing device to segment the data object into a set of data segments and apply a unity matrix to each data segment of the set of data segments to create a first plurality of sets of encoded data slices of the plurality of sets of encoded data slices;

coordinate execution of the redundancy operation by the second computing device to apply the redundancy operation on each data segment of the set of data segments to produce a remaining plurality of sets of encoded data slices of the plurality of sets of encoded data slices; and

coordinate execution of the addressing and writing operation by the third computing device to produce the corresponding plurality of sets of slice names for the plurality of sets of encoded data slices and to write the plurality of sets of encoded data slices based on the corresponding plurality of sets of slice names to the set of storage units of the DSN.

12. The coordinating computing device of claim 9 , wherein the processing module is further operable to:

divide the dispersed storage error encoding of the data object into a first operation including the segmenting operation, the unity matrix operation, a first portion of the addressing operation, and a first portion of a writing operation, and a second operation including the redundancy operation, a second portion of the addressing operation, and a second portion of the writing operation;

allocate the first operation to the first computing device and the second operation to a second computing device of the available computing devices;

coordinate execution of the first operation by the first computing device to segment the data object into a set of data segments, apply the unity matrix operation to each data segment of the set of data segments to create a first plurality of sets of encoded data slices of the plurality of sets of encoded data slices, produce a corresponding first plurality of sets of slice names of the corresponding plurality of sets of slice names for the first plurality of sets of encoded data slices, and to write the first plurality of sets of encoded data slices based on the corresponding first plurality of sets of slice names to the set of storage units of the DSN; and

coordinate execution of the second operation by the second computing device to apply the redundancy operation to each data segment of the set of data segments to create a remaining plurality of sets of encoded data slices of the plurality of sets of encoded data slices, to produce a corresponding remaining plurality of sets of slice names of the corresponding plurality of sets of slice names for the remaining plurality of sets of encoded data slices, and to write the remaining plurality of sets of encoded data slices based on the corresponding remaining second plurality of sets of slice names to the set of storage units of the DSN.

13. The coordinating computing device of claim 9 , wherein the processing module is further operable to:

divide the encoding matrix operation of the dispersed storage error encoding of the data object into a unity matrix operation, a first redundancy operation, and a second redundancy operation;

allocate the unity matrix operation to the first computing device, the first redundancy operation to a second computing device of the available computing devices, and the second redundancy operation to a third computing device of the available computing devices; and

coordinate execution of the unity matrix operation by the first computing device, the first redundancy operation by the second computing device, and the second redundancy operation by the third computing device to dispersed storage error encode the data object into the plurality of sets of encoded data slices.

14. The coordinating computing device of claim 9 , wherein the coordinating computing device is a computing device of the available computing devices.

15. The coordinating computing device of claim 9 , wherein the processing module is further operable to:

determine the available computing devices by at least one of a default setting and a loading function.

16. The coordinating computing device of claim 9 , wherein the processing module is operable to coordinate the execution of the plurality of operations by at least one of:

sending operation result destination instructions to the available computing devices, wherein an operation result destination instruction of the operation result destination instructions directs a computing device of the available computing devices to send a result of an executed operation of the plurality of operations to a particular location; and

sending a dispersed error encoding division scheme to each computing device of the available computing device, wherein the dispersed error encoding division scheme includes a list of each operation of the plurality of operations and a corresponding computing device of the available computing devices assigned to execute the operation.

Assignments (5)
TERMINATION AND RELEASE OF SECURITY INTEREST IN PATENT RIGHTS Recorded Jun 11, 2025
From: BARCLAYS BANK PLC, AS ADMINISTRATIVE AGENT
To: PURE STORAGE, INC.
Reel/Frame 071558/0523 →
SECURITY INTEREST Recorded Aug 26, 2020
From: PURE STORAGE, INC.
To: BARCLAYS BANK PLC AS ADMINISTRATIVE AGENT
Reel/Frame 053867/0581 →
CORRECTIVE ASSIGNMENT TO CORRECT THE DELETE 15/174/279 AND 15/174/596 PROPERTY NUMBERS PREVIOUSLY RECORDED AT REEL: 49555 FRAME: 530. ASSIGNOR(S) HEREBY CONFIRMS THE ASSIGNMENT. Recorded Jan 7, 2020
From: INTERNATIONAL BUSINESS MACHINES CORPORATION
To: PURE STORAGE, INC.
Reel/Frame 051495/0831 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 21, 2019
From: INTERNATIONAL BUSINESS MACHINES CORPORATION
To: PURE STORAGE, INC.
Reel/Frame 049555/0530 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 21, 2017
From: GRUBE, GARY W.; DHUSE, GREG R.; LEGGETTE, WESLEY B.; RESCH, JASON K.; BAPTIST, ANDREW D.; VOLVOVSKI, ILYA
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 044190/0128 →
Continuity (4)
Continuation In Part 15238165 · Aug 16, 2016
Continuation In Part 13270528 · Oct 11, 2011
Provisional Application 61408980 · Nov 1, 2010
Related Publication 20180095688A1 · Apr 5, 2018