Method of storing encoded data slices using a distributed agreement protocol

• US 10,223,201 B2
• Filed: 06/28/2016
• Issued: 03/05/2019
• Est. Priority Date: 06/30/2015
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Motwani, Manish, Resch, Jason K., Volvovski, Ilya
• Primary Examiner(s): Chou, Alan S
• Application Number:
  US15/194,946
• Publication Number:
  US 20170006104A1
• Time in Patent Office: 980 Days
• Field of Search: 709219
• 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/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2471 Distributed queries
• 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 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/33 Synchronisation based on error coding or decoding
• 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 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• 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]
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

Abstract

A method includes encoding a data object in accordance with dispersed storage error encoding parameters to produce sets of encoded data slices having sets of slice names. The dispersed storage error encoding parameters includes a pillar width number of encoded data slices. The data object is associated with a unique source name and each slice name includes a reference to the unique source name. The method further includes executing a distributed agreement protocol using the unique source name and coefficients regarding a plurality of storage units of the dispersed storage network (DSN) to produce a ranking of the plurality of storage units. The method further includes identifying the pillar width number of storage units of the plurality of storage units based on the ranking of the storage units. The method further includes sending the plurality of sets of encoded data slices to the pillar width number of storage units for storage therein.

Claims

1. A method for execution by a computing device of a dispersed storage network (DSN), the method comprises:

encoding a data object in accordance with dispersed storage error encoding parameters to produce a plurality of sets of encoded data slices having a plurality of sets of slice names, wherein the dispersed storage error encoding parameters includes a pillar width number of encoded data slices in a set of encoded data slices of the plurality of sets of encoded data slices, wherein the data object is associated with a unique source name, and wherein each slice name of the plurality of sets of slice names includes a reference to the unique source name;

executing a distributed agreement protocol using the unique source name and coefficients regarding a plurality of storage units of the DSN to produce a ranking of the plurality of storage units;

identifying the pillar width number of storage units of the plurality of storage units based on the ranking of the storage units, and when the plurality of storage units is less than two times the pillar width number, executing the distributed agreement protocol using the unique source name and the coefficients regarding the plurality of storage units of the DSN to produce the ranking of the plurality of storage units; and

when the plurality of storage units is at least two times the pillar width number of storage units, executing the distributed agreement protocol using a slice identifier and the coefficients regarding the plurality of storage units of the DSN to produce identified set of storage units of the plurality of storage units; and

sending the plurality of sets of encoded data slices to the pillar width number of storage units for storage therein.

2. The method of claim 1 further comprises:

executing the distributed agreement protocol to produce a plurality of scoring values for the plurality of storage units, wherein each scoring value of the plurality of scoring values is a unique value, wherein the ranking of the plurality of storage units is based on an ordering of the plurality of scoring values; and

selecting the pillar width number of storage units as the storage units associated with the first pillar width number of scoring values in the ranking of the plurality of storage units.

3. The method of claim 1, wherein the sending the plurality of sets of encoded data slices to the pillar width number of storage units for storage comprises:

sending a first group of encoded data slices to a first storage unit of the pillar width number of storage units, wherein the first group of encoded data slices includes a first encoded data slice of each set of at least some of the plurality of sets of encoded data slices; and

sending a second group of encoded data slices to a second storage unit of the pillar width number of storage units, wherein the second group of encoded data slices includes a second encoded data slice of each set of at least some of the plurality of sets of encoded data slices.

4. The method of claim 1 further comprises:

encoding a second data object in accordance with second dispersed storage error encoding parameters to produce a second plurality of sets of encoded data slices having a second plurality of sets of slice names, wherein the second dispersed storage error encoding parameters includes a second pillar width number of encoded data slices in a set of encoded data slices of the second plurality of sets of encoded data slices, wherein the second data object is associated with a second unique source name, and wherein each slice name of the second plurality of sets of slice names includes a reference to the second unique source name;

executing the distributed agreement protocol using the second unique source name and the coefficients regarding the plurality of storage units of the DSN to produce a second ranking of the plurality of storage units;

identifying the second pillar width number of storage units of the plurality of storage units based on the second ranking of the storage units; and

sending the second plurality of sets of encoded data slices to the second pillar width number of storage units for storage therein.

5. The method of claim 1 further comprises:

when a storage unit is added to the plurality of storage units to produce an updated plurality of storage units, updating the coefficients of the distributed agreement protocol in accordance with the updated plurality of storage units;

executing, by each storage unit of the updated plurality of storage units, the distributed agreement protocol based on the unique source name and the updated coefficients to produce an updated ranking of the updated plurality of storage units; and

transferring, by at least one storage unit of the pillar width number of storage units, at least one encoded data slice to the added storage unit based on the updated ranking of the updated plurality of storage units.

6. The method of claim 1 further comprises:

selecting the dispersed storage error encoding parameters such that the pillar width number equals a number of storage units in the plurality of storage units.

7. A computer readable memory comprises:

a first memory element that stores operational instructions that, when executed by a computing device, causes the computing device to;

encode a data object in accordance with dispersed storage error encoding parameters to produce a plurality of sets of encoded data slices having a plurality of sets of slice names, wherein the dispersed storage error encoding parameters includes a pillar width number of encoded data slices in a set of encoded data slices of the plurality of sets of encoded data slices, wherein the data object is associated with a unique source name, and wherein each slice name of the plurality of sets of slice names includes a reference to the unique source name;

a second memory element that stores operational instructions that, when executed by the computing device, causes the computing device to;

execute a distributed agreement protocol using the unique source name and coefficients regarding a plurality of storage units of a dispersed storage network (DSN) to produce a ranking of the plurality of storage units; and

identify the pillar width number of storage units of the plurality of storage units based on the ranking of the storage units, and

when the plurality of storage units is less than two times the pillar width number, executing the distributed agreement protocol using the unique source name and the coefficients regarding the plurality of storage units of the DSN to produce the ranking of the plurality of storage units; and

when the plurality of storage units is at least two times the pillar width number of storage units, executing the distributed agreement protocol using a slice identifier and the coefficients regarding the plurality of storage units of the DSN to produce identified set of storage units of the plurality of storage units; and

a third memory element that stores operational instructions that, when executed by the computing device, causes the computing device to;

send the plurality of sets of encoded data slices to the pillar width number of storage units for storage therein.

8. The computer readable memory of claim 7, wherein the second memory element further stores operational instructions that, when executed by the computing device, causes the computing device to:

executing the distributed agreement protocol to produce a plurality of scoring values for the plurality of storage units, wherein each scoring value of the plurality of scoring values is a unique value, wherein the ranking of the plurality of storage units is based on an ordering of the plurality of scoring values; and

selecting the pillar width number of storage units as the storage units associated with the first pillar width number of scoring values in the ranking of the plurality of storage units.

9. The computer readable memory of claim 7, wherein the third memory element further stores operational instructions that, when executed by the computing device, causes the computing device to send the plurality of sets of encoded data slices to the pillar width number of storage units for storage by:

sending a first group of encoded data slices to a first storage unit of the pillar width number of storage units, wherein the first group of encoded data slices includes a first encoded data slice of each set of at least some of the plurality of sets of encoded data slices; and

sending a second group of encoded data slices to a second storage unit of the pillar width number of storage units, wherein the second group of encoded data slices includes a second encoded data slice of each set of at least some of the plurality of sets of encoded data slices.

10. The computer readable memory of claim 7 further comprises:

the first memory element further stores operational instructions that, when executed by the computing device, causes the computing device to;

encode a second data object in accordance with second dispersed storage error encoding parameters to produce a second plurality of sets of encoded data slices having a second plurality of sets of slice names, wherein the second dispersed storage error encoding parameters includes a second pillar width number of encoded data slices in a set of encoded data slices of the second plurality of sets of encoded data slices, wherein the second data object is associated with a second unique source name, and wherein each slice name of the second plurality of sets of slice names includes a reference to the second unique source name;

the second memory element further stores operational instructions that, when executed by the computing device, causes the computing device to;

execute the distributed agreement protocol using the second unique source name and the coefficients regarding the plurality of storage units of the DSN to produce a second ranking of the plurality of storage units; and

identify the second pillar width number of storage units of the plurality of storage units based on the second ranking of the storage units; and

the third memory element further stores operational instructions that, when executed by the computing device, causes the computing device to;

send the second plurality of sets of encoded data slices to the second pillar width number of storage units for storage therein.

11. The computer readable memory of claim 7 further comprises:

a fourth memory element that stores operational instructions that, when executed by the computing device, causes the computing device to;

when a storage unit is added to the plurality of storage units to produce an updated plurality of storage units, update the coefficients of the distributed agreement protocol in accordance with the updated plurality of storage units;

a fifth memory element that stores operational instructions that, when executed by a storage unit of the plurality of storage units, causes the storage unit to;

execute the distributed agreement protocol based on the unique source name and the updated coefficients to produce an updated ranking of the updated plurality of storage units; and

transfer at least one encoded data slice to the added storage unit based on the updated ranking of the updated plurality of storage units.

12. The computer readable memory of claim 7, wherein the first memory element further stores operational instructions that, when executed by the computing device, causes the computing device to:

selecting the dispersed storage error encoding parameters such that the pillar width number equals a number of storage units in the plurality of storage units.