STORING A DATA STREAM IN A SET OF STORAGE DEVICES

• US 20160156433A1
• Filed: 02/08/2016
• Published: 06/02/2016
• Est. Priority Date: 08/02/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Gladwin, S. Christopher, Markison, Timothy W., Dhuse, Greg, Shirley, Thomas Franklin Jr., Leggette, Wesley, Resch, Jason K., Grube, Gary W.
• Granted Patent: US 9,819,447 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/2053 where persistent mass storage functionality or persistent mass storage control functionality is redundant error detection or correction in information storage based on relative movement between record carrier and transducer G11B20/18
• 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/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding
• CPC Class Codes: H04L 1/0076 Distributed coding, e.g. network coding, involving channel coding coding in both space and time H04L1/0618; cooperative diversity H04B7/022
• 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 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A method includes generating, by execution units, a plurality of sets of a decode threshold number of encoded data slices from data streams. A first execution unit produces a first encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices from a first data stream. The method further includes generating, by at least some of the execution units, a plurality of sets of partially encoded data slices from the plurality of a sets of a decode number of encoded data slices. When partially encoded data slices are processed, the processed partially encoded data slices represent redundancy encoded data slices. The decode threshold number of encoded data slices combined with the redundancy encoded data slices forms a full set of encoded data slices. The method further includes sending the partially encoded data slices to other execution units for storage therein.

Claims

1. A method comprises:

generating, by a plurality of execution units of a dispersed storage network (DSN), a plurality of sets of a decode threshold number of encoded data slices from a plurality of data streams, wherein a first execution unit of the plurality of execution units produces a first encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices from a first data stream of the plurality of data streams, and wherein, for a set of the plurality of sets of the decode threshold number of encoded data slices, the decode threshold number of encoded data slices is required to recover corresponding data segments of each of the plurality of data streams;

generating, by at least some of the plurality of execution units, a plurality of sets of partially encoded data slices from the plurality of a sets of a decode number of encoded data slices, wherein, when partially encoded data slices of a set of the plurality of sets of partially encoded data slices are processed, the processed partially encoded data slices represent redundancy encoded data slices, wherein the decode threshold number of encoded data slices of the set of the plurality of sets of the decode threshold number of encoded data slices combined with the redundancy encoded data slices forms a full set of encoded data slices for the corresponding data segment; and

sending, by the at least some of the plurality of execution units, the plurality of sets of partially encoded data slices to a set of execution units for storage therein.

2. The method of claim 1 further comprises:

determining, by the plurality of execution units, a common source name for the plurality of sets of the decode threshold number of encoded data slices;

generating, by the plurality of execution units, a plurality of sets of slice names for the plurality of sets of the decode threshold number of encoded data slices to include the common source name; and

generating, by the at least some of the plurality of execution units, another plurality of sets of slices names for the plurality of sets of partially encoded data slices to include the common source name.

3. The method of claim 2 further comprises:

updating a directory to associate data stream identifiers, the common source name, and ranges of slice names of the plurality of sets of slices names and the other plurality of slices names.

4. The method of claim 1 further comprises:

determining, by the plurality of execution units, a first common source name for a first portion of the plurality of sets of the decode threshold number of encoded data slices; and

determining, by the plurality of execution units, a second common source name for a second portion of the plurality of sets of the decode threshold number of encoded data slices.

5. The method of claim 1 further comprises:

receiving the plurality of data streams further by one of;

dividing a large data stream into the plurality of data streams; and

receiving the plurality of data streams from a plurality of related data sources.

6. The method of claim 1, wherein generating a partial encoded data slice of the plurality of sets of partial encoded data slices comprises:

obtaining, by an execution unit of the at least some of the plurality of execution units, an encoding matrix used in the generating of the plurality of sets of the decode threshold number of encoded data slices;

reducing, by the execution unit, the encoding matrix to a square matrix that includes rows corresponding to the decode threshold number of encoded data slices;

inverting, by the execution unit, the square matrix to produce an inverted matrix;

matrix multiplying, by the execution unit, the inverted matrix by a corresponding one of the decode threshold number of encoded data slices to produce a data vector; and

matrix multiplying, by the execution unit, the data vector with a row of the encoding matrix that corresponds to the corresponding one of the decode threshold number of encoded data slices to produce the partial encoded data slice.

7. The method of claim 1 further comprises:

dividing, by the first execution unit, the first data stream into a plurality of first data segments;

generating, by the first execution unit, a first data matrix to include a row of the plurality of first data segments;

matrix multiplying, by the first execution unit, the first data matrix with an encoding matrix to produce a first encoded matrix, wherein the first encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices corresponds to data block of the first encoded matrix; and

storing, by the first execution unit, the first encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices.

8. The method of claim 7 further comprises:

dividing, by a second execution unit of the plurality of execution units, a second data stream of the plurality of data streams into a plurality of second data segments;

generating, by the second execution unit, a second data matrix to include a row of the plurality of second data segments;

matrix multiplying, by the second execution unit, the second data matrix with the encoding matrix to produce a second encoded matrix, wherein second encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices corresponds to data block of the second encoded matrix; and

storing, by the second execution unit, the second encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices.

9. A dispersed storage system comprises:

a first module that, when operable in execution units of a plurality of execution units, causes the plurality of execution units to;

generate a plurality of sets of a decode threshold number of encoded data slices from a plurality of data streams, wherein a first execution unit of the plurality of execution units produces a first encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices from a first data stream of the plurality of data streams, and wherein, for a set of the plurality of sets of the decode threshold number of encoded data slices, the decode threshold number of encoded data slices is required to recover corresponding data segments of each of the plurality of data streams;

a second module that, when operable in at least some of the plurality of execution units, causes the at least some of the plurality of execution units to;

generate a plurality of sets of partially encoded data slices from the plurality of a sets of a decode number of encoded data slices, wherein, when partially encoded data slices of a set of the plurality of sets of partially encoded data slices are processed, the processed partially encoded data slices represent redundancy encoded data slices, wherein the decode threshold number of encoded data slices of the set of the plurality of sets of the decode threshold number of encoded data slices combined with the redundancy encoded data slices forms a full set of encoded data slices for the corresponding data segment; and

a third module that, when operable in the at least some of the plurality of execution units, causes the at least some of the plurality of execution units to;

send the plurality of sets of partially encoded data slices to a set of execution units for storage therein.

10. The dispersed storage system of claim 9 further comprises:

a fourth module that, when operable in the plurality of execution units, causes the plurality of execution units to;

determine a common source name for the plurality of sets of the decode threshold number of encoded data slices;

generate a plurality of sets of slice names for the plurality of sets of the decode threshold number of encoded data slices to include the common source name; and

generate another plurality of sets of slices names for the plurality of sets of partially encoded data slices to include the common source name.

11. The dispersed storage system of claim 10, wherein the fourth module that, when operable in the plurality of execution units, further causes the plurality of execution units to:

update a directory to associate data stream identifiers, the common source name, and ranges of slice names of the plurality of sets of slices names and the other plurality of slices names.

12. The dispersed storage system of claim 9 further comprises:

a fourth module that, when operable in the plurality of execution units, causes the plurality of execution units to;

determine a first common source name for a first portion of the plurality of sets of the decode threshold number of encoded data slices; and

determine a second common source name for a second portion of the plurality of sets of the decode threshold number of encoded data slices.

13. The dispersed storage system of claim 9 further comprises:

a fourth module that, when operable in the plurality of execution units, causes the plurality of execution units to;

receive the plurality of data streams further by one of;

dividing a large data stream into the plurality of data streams; and

receiving the plurality of data streams from a plurality of related data sources.

14. The dispersed storage system of claim 9, wherein the third module that, when operable in an execution unit of the at least some of the plurality of execution units, further causes the execution unit to generate the partial encoded data slice of the plurality of sets of partial encoded data slices by:

obtaining an encoding matrix used in the generating of the plurality of sets of the decode threshold number of encoded data slices;

reducing the encoding matrix to a square matrix that includes rows corresponding to the decode threshold number of encoded data slices;

inverting the square matrix to produce an inverted matrix;

matrix multiplying the inverted matrix by a corresponding one of the decode threshold number of encoded data slices to produce a data vector; and

matrix multiplying the data vector with a row of the encoding matrix that corresponds to the corresponding one of the decode threshold number of encoded data slices to produce the partial encoded data slice.

15. The dispersed storage system of claim 10, wherein the first module that, when operable in the first execution unit, further causes the first execution unit to:

divide the first data stream into a plurality of first data segments;

generate a first data matrix to include a row of the plurality of first data segments;

matrix multiply the first data matrix with an encoding matrix to produce a first encoded matrix, wherein the first encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices corresponds to data block of the first encoded matrix; and

store the first encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices.

16. The dispersed storage system of claim 15, wherein the first module that, when operable in a second execution unit of the plurality of execution units, further causes the second execution unit to:

divide a second data stream of the plurality of data streams into a plurality of second data segments;

generate a second data matrix to include a row of the plurality of second data segments;

matrix multiply the second data matrix with the encoding matrix to produce a second encoded matrix, wherein second encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices corresponds to data block of the second encoded matrix; and

store the second encoded data slice for each set of the plurality of sets of the decode threshold number of encoded data slices.