Concatenating data objects for storage in a dispersed storage network

• US 9,798,619 B2
• Filed: 11/15/2016
• Issued: 10/24/2017
• Est. Priority Date: 02/26/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Resch, Jason K., Dhuse, Greg, Baptist, Andrew
• Primary Examiner(s): Rizk, Sam
• Application Number:
  US15/351,628
• Publication Number:
  US 20170060688A1
• Time in Patent Office: 343 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• 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/2906 using block codes H03M13/2957 takes precedence

Abstract

A method includes identifying an independent data object of a plurality of independent data objects for retrieval from dispersed storage network (DSN) memory. The method further includes determining a mapping of the plurality of independent data objects into a data matrix, wherein the mapping is in accordance with the dispersed storage error encoding function. The method further includes identifying, based on the mapping, an encoded data slice of the set of encoded data slices corresponding to the independent data object. The method further includes sending a retrieval request to a storage unit of the DSN memory regarding the encoded data slice. When the encoded data slice is received, the method further includes decoding the encoding data slice in accordance with the dispersed storage error encoding function and the mapping to reproduce the independent data object.

Claims

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

identifying an independent data object of a plurality of independent data objects for retrieval from DSN memory of the DSN, wherein the plurality of independent data objects is combined to produce a concatenated data object and wherein the concatenated data object is encoded in accordance with a dispersed storage error encoding function to produce a set of encoded data slices;

determining a mapping of the plurality of independent data objects into a data matrix, wherein the mapping is in accordance with the dispersed storage error encoding function;

identifying, based on the mapping, an encoded data slice of the set of encoded data slices corresponding to the independent data object;

sending a retrieval request to a storage unit of the DSN memory regarding the encoded data slice; and

when the encoded data slice is received, decoding the encoding data slice in accordance with the dispersed storage error encoding function and the mapping to reproduce the independent data object.

2. The method of claim 1 further comprises:

the data matrix including “

d”

number of rows and “

c”

number of columns of data blocks; and

the mapping of the plurality of independent data objects including a mapping of the plurality of independent data objects to the data blocks, wherein the independent data object is mapped to one or more of the data blocks.

3. The method of claim 2 further comprises:

the “

d”

number of rows corresponds to a decode threshold number of the dispersed storage error encoding function.

4. The method of claim 1, wherein the decoding the encoding data slice further comprises:

matrix multiplying the encoded data slice with a decoding matrix to produce a row of the data matrix; and

de-mapping the row of the data matrix to recover the independent data object.

5. The method of claim 1 further comprises:

when the encoded data slice is not received;

sending a decode threshold number of read requests regarding a decode threshold number of encoded data slices of the set of encoded data slices to storage units of the DSN memory, wherein the decode threshold number of encoded data slices does not include the encoded data slice;

when the decode threshold number of encoded data slices has been received, matrix multiplying the decode threshold number of encoded data slice with a decoding matrix to retrieve the data matrix; and

de-mapping the data matrix to recover the independent data object.

6. The method of claim 5 further comprises:

encoding the recovered independent data object in accordance with the dispersed storage error encoding function to produce a rebuilt encoded data slice regarding the independent data object; and

sending the rebuilt encoded data slice to the DSN memory for storage therein.

7. A computer readable memory comprises:

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

identify an independent data object of a plurality of independent data objects for retrieval from DSN memory of the DSN, wherein the plurality of independent data objects is combined to produce a concatenated data object and wherein the concatenated data object is encoded in accordance with a dispersed storage error encoding function to produce a set of encoded data slices;

determine a mapping of the plurality of independent data objects into a data matrix, wherein the mapping is in accordance with the dispersed storage error encoding function; and

identify, based on the mapping, an encoded data slice of the set of encoded data slices corresponding to the independent data object; and

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

send a retrieval request to a storage unit of the DSN memory regarding the encoded data slice; and

when the encoded data slice is received, decode the encoding data slice in accordance with the dispersed storage error encoding function and the mapping to reproduce the independent data object.

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

the data matrix including “

d”

number of rows and “

c”

number of columns of data blocks; and

the mapping of the plurality of independent data objects including a mapping of the plurality of independent data objects to the data blocks, wherein the independent data object is mapped to one or more of the data blocks.

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

the “

d”

number of rows corresponds to a decode threshold number of the dispersed storage error encoding function.

10. The computer readable memory of claim 7, wherein the second memory section further stores operational instructions that, when executed by the computing device, causes the computing device to decode the encoding data slice by:

matrix multiplying the encoded data slice with a decoding matrix to produce a row of the data matrix; and

de-mapping the row of the data matrix to recover the independent data object.

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

when the encoded data slice is not received;

send a decode threshold number of read requests regarding a decode threshold number of encoded data slices of the set of encoded data slices to storage units of the DSN memory, wherein the decode threshold number of encoded data slices does not include the encoded data slice;

when the decode threshold number of encoded data slices has been received, matrix multiply the decode threshold number of encoded data slice with a decoding matrix to retrieve the data matrix; and

de-mapping the data matrix to recover the independent data object.

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

encode the recovered independent data object in accordance with the dispersed storage error encoding function to produce a rebuilt encoded data slice regarding the independent data object; and

send the rebuilt encoded data slice to the DSN memory for storage therein.

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

an interface;

a local memory; and

a processing module operably coupled to the interface and the local memory, wherein the processing module functions to;

identify an independent data object of a plurality of independent data objects for retrieval from DSN memory of the DSN, wherein the plurality of independent data objects is combined to produce a concatenated data object and wherein the concatenated data object is encoded in accordance with a dispersed storage error encoding function to produce a set of encoded data slices;

determine a mapping of the plurality of independent data objects into a data matrix, wherein the mapping is in accordance with the dispersed storage error encoding function;

identifying, based on the mapping, an encoded data slice of the set of encoded data slices corresponding to the independent data object;

send, via the interface, a retrieval request to a storage unit of the DSN memory regarding the encoded data slice; and

when the encoded data slice is received, decode the encoding data slice in accordance with the dispersed storage error encoding function and the mapping to reproduce the independent data object.

14. The computing device of claim 13 further comprises:

the data matrix including “

d”

number of rows and “

c”

number of columns of data blocks; and

the mapping of the plurality of independent data objects including a mapping of the plurality of independent data objects to the data blocks, wherein the independent data object is mapped to one or more of the data blocks.

15. The computing device of claim 14 further comprises:

the “

d”

number of rows corresponds to a decode threshold number of the dispersed storage error encoding function.

16. The computing device of claim 13, wherein the processing module is further operable to decode the encoding data slice by:

matrix multiplying the encoded data slice with a decoding matrix to produce a row of the data matrix; and

de-mapping the row of the data matrix to recover the independent data object.

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

when the encoded data slice is not received;

send a decode threshold number of read requests regarding a decode threshold number of encoded data slices of the set of encoded data slices to storage units of the DSN memory, wherein the decode threshold number of encoded data slices does not include the encoded data slice;

when the decode threshold number of encoded data slices has been received, matrix multiply the decode threshold number of encoded data slice with a decoding matrix to retrieve the data matrix; and

de-mapping the data matrix to recover the independent data object.

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

encode the recovered independent data object in accordance with the dispersed storage error encoding function to produce a rebuilt encoded data slice regarding the independent data object; and

send, via the interface, the rebuilt encoded data slice to the DSN memory for storage therein.