Efficient method for redundant storage of a set of encoded data slices

• US 10,061,648 B2
• Filed: 06/28/2016
• Issued: 08/28/2018
• Est. Priority Date: 06/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Ciborowski, Brian S., Jarczyk, Justin M.
• Primary Examiner(s): Britt, Cynthia
• Application Number:
  US15/195,252
• Publication Number:
  US 20170004195A1
• Time in Patent Office: 791 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/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 dispersed storage error encoding, by a device of the dispersed storage network (DSN), a data segment of a data object into a set of encoded data slices. The method further includes sending, by the device, a set of write fan out with redundancy sharing requests to a set of storage units of the DSN. The method further includes, in response to the set of write fan out with redundancy sharing requests, storing, by the set of storage units, a number of copies of a decode threshold number of encoded data slices of the set of encoded data slices. The method further includes storing, by the set of storage units, a single copy of a redundancy number of encoded data slices of the set of encoded data slices.

Claims

1. A method for write fan out with redundancy sharing in a dispersed storage network (DSN), the method comprises:

dispersed storage error encoding, by a device of the DSN, a data segment of a data object into a set of encoded data slices;

sending, by the device, a set of write fan out with redundancy sharing requests to a set of storage units of the DSN; and

in response to the set of write fan out with redundancy sharing requests;

storing, by the set of storage units, a number of copies of a decode threshold number of encoded data slices of the set of encoded data slices; and

storing, by the set of storage units, a single copy of a redundancy number of encoded data slices of the set of encoded data slices.

2. The method of claim 1 further comprises:

receiving, by a first storage unit of the set of storage units, a first write fan out with redundancy sharing request of the set of write fan out with redundancy sharing requests, wherein the first write fan out with redundancy sharing request is regarding a first encoded data slice of the decode threshold number of encoded data slices;

replicating, by the first storage unit, the first encoded data slice to produce one or more copies of the first encoded data slice; and

storing, by the first storage unit, the first encoded data slice and the one or more copies of the first encoded data slice in different memory devices of the first storage unit.

3. The method of claim 1 further comprises:

receiving, by a first storage unit of the set of storage units, a first write fan out with redundancy sharing request of the set of write fan out with redundancy sharing requests, wherein the first write fan out with redundancy sharing request is regarding a first encoded data slice of the decode threshold number of encoded data slices;

replicating, by the first storage unit, the first encoded data slice to produce one or more copies of the first encoded data slice;

storing, by the first storage unit, the first encoded data slice; and

sending, by the first storage unit, the one or more copies of the first encoded data slice to one or more other first storage units of the set of storage units for storage therein.

4. The method of claim 1 further comprises:

receiving, by a first redundancy storage unit of the set of storage units, a write fan out with redundancy sharing request of the set of write fan out with redundancy sharing requests, wherein the write fan out with redundancy sharing request is regarding a first encoded data slice of the redundancy number of encoded data slices;

storing, by the first redundancy storage unit, the first encoded data slices of the redundancy number of encoded data slices;

receiving, by a second redundancy storage unit of the set of storage units, a second write fan out with redundancy sharing request of the set of write fan out with redundancy sharing requests, wherein the second write fan out with redundancy sharing request is regarding a second encoded data slice of the redundancy number of encoded data slices; and

storing, by second first redundancy storage unit, the second encoded data slices of the redundancy number of encoded data slices.

5. The method of claim 1 further comprises:

receiving, by a first redundancy storage unit of the set of storage units, a write fan out with redundancy sharing request of the set of write fan out with redundancy sharing requests, wherein the write fan out with redundancy sharing request is regarding a first encoded data slice of the redundancy number of encoded data slices;

determining, by the first redundancy storage unit, whether to store the first encoded data slices of the redundancy number of encoded data slices or to send the first encoded data slices of the redundancy number of encoded data slices to another first redundancy storage unit of the set of storage units; and

when the first redundancy storage unit determines to send the first encoded data slices of the redundancy number of encoded data slices to the other first redundancy storage unit of the set of storage units, sending, by the first redundancy storage unit, the first encoded data slices of the redundancy number of encoded data slices to the other first redundancy storage unit of the set of storage units.

6. The method of claim 5 further comprises:

selecting, by the first redundancy storage unit, the other first redundancy storage unit from a plurality of first redundancy storage units of the set of storage units.

7. The method of claim 1 further comprises:

receiving, by storage units of the set of storage units, a plurality of read requests;

for a first read request of the plurality of read requests, determining, by the storage units, whether a first copy of the number of copies of the decode threshold number of encoded data slices is available;

when the first copy of the decode threshold number of encoded data slices is available, sending, by the storage unit, the first copy of the decode threshold number of encoded data slices to a requesting computing device;

when the first copy of the decode threshold number of encoded data slices is not available;

identifying, by the storage units, one or more redundancy encoded data slices of the redundancy number of encoded data slices; and

sending, by the storage units, available encoded data slices of the first copy of the decode threshold number of encoded data slices and the one or more redundancy encoded data slices to the requesting computing device.

8. A computer readable memory comprises:

a first memory element that stores operational instructions that, when executed by a device of a dispersed storage network (DSN), causes the device to;

dispersed storage error encode a data segment of a data object into a set of encoded data slices; and

send a set of write fan out with redundancy sharing requests to a set of storage units of the DSN; and

second memory elements that store operational instructions that, when executed by the set of storage units, causes the set of storage units to;

in response to the set of write fan out with redundancy sharing requests;

store a number of copies of a decode threshold number of encoded data slices of the set of encoded data slices; and

store a single copy of a redundancy number of encoded data slices of the set of encoded data slices.

9. The computer readable memory of claim 8, wherein a second memory element of the second memory elements further stores operational instructions that, when executed by a first storage unit of the set of storage units, causes the first storage unit to:

receive a first write fan out with redundancy sharing request of the set of write fan out with redundancy sharing requests, wherein the first write fan out with redundancy sharing request is regarding a first encoded data slice of the decode threshold number of encoded data slices;

replicate the first encoded data slice to produce one or more copies of the first encoded data slice; and

store the first encoded data slice and the one or more copies of the first encoded data slice in different memory devices of the first storage unit.

10. The computer readable memory of claim 8, wherein a second memory element of the second memory elements further stores operational instructions that, when executed by a first storage unit of the set of storage units, causes the first storage unit to:

receive a first write fan out with redundancy sharing request of the set of write fan out with redundancy sharing requests, wherein the first write fan out with redundancy sharing request is regarding a first encoded data slice of the decode threshold number of encoded data slices;

replicate the first encoded data slice to produce one or more copies of the first encoded data slice;

store the first encoded data slice; and

send the one or more copies of the first encoded data slice to one or more other first storage units of the set of storage units for storage therein.

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

a second memory element of the second memory elements further stores operational instructions that, when executed by a first redundancy storage unit of the set of storage units, causes the first redundancy storage unit to;

receive a write fan out with redundancy sharing request of the set of write fan out with redundancy sharing requests, wherein the write fan out with redundancy sharing request is regarding a first encoded data slice of the redundancy number of encoded data slices; and

store the first encoded data slices of the redundancy number of encoded data slices; and

another second memory element of the second memory elements further stores operational instructions that, when executed by a second redundancy storage unit of the set of storage units, causes the second redundancy storage unit to;

receive a second write fan out with redundancy sharing request of the set of write fan out with redundancy sharing requests, wherein the second write fan out with redundancy sharing request is regarding a second encoded data slice of the redundancy number of encoded data slices; and

store the second encoded data slices of the redundancy number of encoded data slices.

12. The computer readable memory of claim 8, wherein a second memory element of the second memory elements further stores operational instructions that, when executed by a first redundancy storage unit of the set of storage units, causes the first redundancy storage unit to:

receive a write fan out with redundancy sharing request of the set of write fan out with redundancy sharing requests, wherein the write fan out with redundancy sharing request is regarding a first encoded data slice of the redundancy number of encoded data slices;

determine whether to store the first encoded data slices of the redundancy number of encoded data slices or to send the first encoded data slices of the redundancy number of encoded data slices to another first redundancy storage unit of the set of storage units; and

when the first redundancy storage unit determines to send the first encoded data slices of the redundancy number of encoded data slices to the other first redundancy storage unit of the set of storage units, send the first encoded data slices of the redundancy number of encoded data slices to the other first redundancy storage unit of the set of storage units.

13. The computer readable memory of claim 12, wherein a second memory element of the second memory elements further stores operational instructions that, when executed by the first redundancy storage unit, causes the first redundancy storage unit to:

select the other first redundancy storage unit from a plurality of first redundancy storage units of the set of storage units.

14. The computer readable memory of claim 8, wherein at least some of the second memory elements further store operational instructions that, when executed by storage units of the set of storage units, causes the storage units to:

receive a plurality of read requests;

for a first read request of the plurality of read requests, determine whether a first copy of the number of copies of the decode threshold number of encoded data slices is available;

when the first copy of the decode threshold number of encoded data slices is available, send the first copy of the decode threshold number of encoded data slices to a requesting computing device;

when the first copy of the decode threshold number of encoded data slices is not available;

identify one or more redundancy encoded data slices of the redundancy number of encoded data slices; and

send available encoded data slices of the first copy of the decode threshold number of encoded data slices and the one or more redundancy encoded data slices to the requesting computing device.