IP Library Granted Patent US 10,635,536
Granted Patent B2
US 10,635,536 · App. 15/467,832 · Granted Apr 28, 2020

Dynamic distributed agreement protocols in a dispersed storage network

Inventors: Andrew D. Baptist (Mt. Pleasant, WI); Wesley B. Leggette (Chicago, IL); Manish Motwani (Chicago, IL); Jason K. Resch (Chicago, IL); Ethan S. Wozniak (Park Ridge, IL)
Assignee: INTERNATIONAL BUSINESS MACHINES CORPORATION
G06F11/1076G06F3/061G06F3/064G06F3/0604G06F3/067G06F3/0619G06F3/0631G06F3/0635G06F3/0644G06F3/0647G06F3/0653G06F3/0659G06F11/1092G06F11/1662G06F11/3684G06F11/3688G06F11/3692H03M13/1515H03M13/616H04L67/1097G06F2201/805G06F2201/82H03M13/373
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,635,536
App. No.
15/467,832
Granted
Apr 28, 2020
Kind
B2
Abstract

A method for execution by a device of a dispersed storage network (DSN) to access a set of encoded data slices. The method begins by performing a first distributed agreement protocol (DAP) function using a slice identifier and a first set of coefficients to identify a set of storage units. The method continues by performing a second DAP function using the slice identifier and a second set of coefficients to identify pillar numbers for the set of storage units. The method continues by sending a set of data access requests to the set of storage units in accordance with the pillar numbers, wherein a data access request of the set of data access requests includes a slice name for a corresponding one of the set of encoded data slices and wherein the slice name includes one of the pillar numbers.

Claims (71)

1. A method for execution by a device of a dispersed storage network (DSN) to access a set of encoded data slices, the method comprises:

identifying a set of storage units of a plurality of sets of storage units of a storage pool by:

determining a first deterministic function from a plurality of deterministic functions based on a frequency of change of the plurality of sets of storage units; and

performing a first distributed agreement protocol (DAP) function using a slice identifier and a first set of coefficients to identify the set of storage units, wherein the first DAP function includes the first deterministic function;

identifying pillar numbers for the set of storage units by:

determining a second deterministic function from the plurality of deterministic functions based on a frequency of change of the set of storage units; and

performing a second DAP function using the slice identifier and a second set of coefficients to identify the pillar numbers, wherein the second DAP function includes the second deterministic function; and

sending a set of data access requests to the set of storage units in accordance with the pillar numbers, wherein a data access request of the set of data access requests includes a slice name for a corresponding one of the set of encoded data slices and wherein the slice name includes one of the pillar numbers.

2. The method of claim 1 , wherein the performing the first DAP function further comprises identifying the storage pool of a plurality of storage pools by:

performing a storage pool selection DAP function using the slice identifier and a storage pool set of coefficients to identify the storage pool, wherein the storage pool includes the plurality of sets of storage units.

3. The method of claim 1 , wherein the slice identifier comprises one or more of:

pillar number information;

data segment number information;

a vault identifier;

a data object identifier; and

revision information.

4. The method of claim 1 further comprises:

performing the first DAP function using a first DAP engine; and

performing the second DAP function using a second DAP engine.

5. The method of claim 1 further comprises:

performing the first DAP function using a DAP engine by providing the DAP engine with the slice identifier and the first set of coefficients; and

performing the second DAP function using the DAP engine by providing the DAP engine with the slice identifier and the second set of coefficients.

6. The method of claim 1 further comprises:

performing a first third DAP function using the slice identifier and a first third set of coefficients to identify a memory device of a plurality of memory devices of a first pillar number storage unit of the set of storage units;

performing a second third DAP function using the slice identifier and a second third set of coefficients to identify a memory device of a plurality of memory devices of a second pillar number storage unit of the set of storage units; and

performing a third third DAP function using the slice identifier and a third third set of coefficients to identify a memory device of a plurality of memory devices of a third pillar number storage unit of the set of storage units.

7. The method of claim 1 , wherein performing the first DAP function comprises:

performing a plurality of rating functions based on the slice identifier and the first set of coefficients to produce a plurality of ratings for the plurality of sets of storage units; and

selecting, in accordance with a ranking function, the set of storage units from the plurality of sets of storage units based on the plurality of ratings.

8. The method of claim 7 further comprises:

for a rating function of the plurality of rating functions:

performing the first deterministic function of the plurality of deterministic functions on the slice identifier and a first coefficient of the first set of coefficients to produce an interim result;

performing a normalizing function on the interim result to produce a normalized result; and

performing a scoring function on the normalized result based on a second coefficient of the first set of coefficients to produce a rating of the plurality of ratings.

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

an interface;

memory;

a processing module operably coupled to the memory and the interface, wherein the processing module is operable to access a set of encoded data slices by:

identifying a set of storage units of a plurality of sets of storage units of a storage pool by:

determining a first deterministic function from a plurality of deterministic functions based on a frequency of change of the plurality of sets of storage units; and

performing a first distributed agreement protocol (DAP) function using a slice identifier and a first set of coefficients to identify the set of storage units, wherein the first DAP function includes the first deterministic function;

identifying pillar numbers for the set of storage units by:

determining a second deterministic function from the plurality of deterministic functions based on a frequency of change of the set of storage units; and

performing a second DAP function using the slice identifier and a second set of coefficients to identify the pillar numbers, wherein the second DAP function includes the second deterministic function; and

sending, via the interface, a set of data access requests to the set of storage units in accordance with the pillar numbers, wherein a data access request of the set of data access requests includes a slice name for a corresponding one of the set of encoded data slices and wherein the slice name includes one of the pillar numbers.

10. The computing device of claim 9 , wherein the processing module is operable to perform the first DAP function further to identify the storage pool of a plurality of storage pools by:

performing a storage pool selection DAP function using the slice identifier and a storage pool set of coefficients to identify the storage pool, wherein the storage pool includes the plurality of sets of storage units.

11. The computing device of claim 9 , wherein the slice identifier comprises one or more of:

pillar number information;

data segment number information;

a vault identifier;

a data object identifier; and

revision information.

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

perform the first DAP function using a first DAP engine; and

perform the second DAP function using a second DAP engine.

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

perform the first DAP function using a DAP engine by providing the DAP engine with the slice identifier and the first set of coefficients; and

perform the second DAP function using the DAP engine by providing the DAP engine with the slice identifier and the second set of coefficients.

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

perform a first third DAP function using the slice identifier and a first third set of coefficients to identify a memory device of a plurality of memory devices of a first pillar number storage unit of the set of storage units;

perform a second third DAP function using the slice identifier and a second third set of coefficients to identify a memory device of a plurality of memory devices of a second pillar number storage unit of the set of storage units; and

perform a third third DAP function using the slice identifier and a third third set of coefficients to identify a memory device of a plurality of memory devices of a third pillar number storage unit of the set of storage units.

15. The computing device of claim 9 , wherein the processing module is operable to perform the first DAP function by:

performing a plurality of rating functions based on the slice identifier and the first set of coefficients to produce a plurality of ratings for the plurality of sets of storage units; and

selecting, in accordance with a ranking function, the set of storage units from the plurality of sets of storage units based on the plurality of ratings.

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

for a rating function of the plurality of rating functions:

perform the first deterministic function of the plurality of deterministic functions on the slice identifier and a first coefficient of the first set of coefficients to produce an interim result;

perform a normalizing function on the interim result to produce a normalized result; and

perform a scoring function on the normalized result based on a second coefficient of the first set of coefficients to produce a rating of the plurality of ratings.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 23, 2017
From: BAPTIST, ANDREW D.; LEGGETTE, WESLEY B.; MOTWANI, MANISH; RESCH, JASON K.; WOZNIAK, ETHAN S.
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 041711/0686 →