Concatenating data objects for storage in a dispersed storage network

• US 9,529,834 B2
• Filed: 01/05/2015
• Issued: 12/27/2016
• 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:
  US14/589,391
• Publication Number:
  US 20150242272A1
• Time in Patent Office: 722 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/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 begins by a processing module of a dispersed storage network (DSN) concatenating a plurality of independent data objects into a concatenated data object and performing a dispersed storage error encoding function on the concatenated data object to produce a set of data-based encoded data slices and a set of redundancy-based encoded data slices. The method continues with the processing module outputting the set of data-based encoded data slices to a first set of storage units for storage and outputting the set of redundancy-based encoded data slices to a second set of storage units for storage.

Claims

1. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the method comprises:

concatenating a plurality of independent data objects into a concatenated data object, wherein the concatenating is based on a parameter of a dispersed storage error encoding function that indicates a number of data-based encoded data slices resulting from performing the dispersed storage error encoding function;

performing the dispersed storage error encoding function on the concatenated data object to produce a set of data-based encoded data slices and a set of redundancy-based encoded data slices, wherein one or more independent data objects of the plurality of independent data objects is recoverable from a corresponding data-based encoded data slice of the set of data-based encoded data slices or from a decode threshold number of encoded data slices, wherein the decode threshold number of encoded data slices includes one or more data-based encoded data slices of the set of data-based encoded data slices and one or more redundancy-based encoded data slices of the set of redundancy-based encoded data slices;

outputting the set of data-based encoded data slices to a first set of storage units for storage therein; and

outputting the set of redundancy-based encoded data slices to a second set of storage units for storage therein.

2. The method of claim 1, wherein the concatenating the plurality of independent data objects comprises:

identifying data objects having a common trait; and

establishing the plurality of independent data objects from the data objects having the common trait.

3. The method of claim 1, wherein the concatenating the plurality of independent data objects comprises:

mapping the plurality of independent data objects into “

k”

rows to produce the concatenated data object, wherein the “

k”

rows corresponds to the number of data-based encoded data slices resulting from performing the dispersed storage error encoding function and wherein the one or more independent data objects is mapped to a single row of the “

k”

rows.

4. The method of claim 3 further comprises:

padding the single row of the “

k”

rows when a combined size of the one or more independent data objects is less than a row size.

5. The method of claim 1, wherein the concatenating the plurality of independent data objects comprises:

mapping the plurality of the independent data objects into “

k”

rows to produce the concatenated data object, wherein the “

k”

rows corresponds to a number of data-based encoded data slices resulting from performing the dispersed storage error encoding function and wherein an independent data object of the plurality of independent data objects is mapped to more than one row of the “

k”

rows.

6. The method of claim 1, wherein the performing the dispersed storage error encoding function comprises:

converting the concatenated data object into a data matrix;

generating a coded matrix based on the data matrix and an encoding matrix;

generating the set of data-based encoded data slices from a first portion of the coded matrix that corresponds to a first portion of the encoding matrix; and

generating the set of redundancy-based encoded data slices from a second portion of the coded matrix that corresponds to a second portion of the encoding matrix.

7. The method of claim 1 further comprises:

receiving a message to concatenate the plurality of independent data objects, wherein the message is one of a user input message to group data objects having a common trait and a system message based on dispersed storage network conditions.

8. A non-transitory computer readable storage medium comprises:

at least one memory section that stores operational instructions that, when executed by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), causes the one or more computing devices to;

concatenate a plurality of independent data objects into a concatenated data object, wherein the concatenating is based on a parameter of a dispersed storage error encoding function that indicates a number of data-based encoded data slices resulting from performing the dispersed storage error encoding function;

perform the dispersed storage error encoding function on the concatenated data object to produce a set of data-based encoded data slices and a set of redundancy-based encoded data slices, wherein one or more independent data objects of the plurality of independent data objects is recoverable from a corresponding data-based encoded data slice of the set of data-based encoded data slices or from a decode threshold number of encoded data slices, wherein the decode threshold number of encoded data slices includes one or more data-based encoded data slices of the set of data-based encoded data slices and one or more redundancy-based encoded data slices of the set of redundancy-based encoded data slices;

output the set of data-based encoded data slices to a first set of storage units for storage therein; and

output the set of redundancy-based encoded data slices to a second set of storage units for storage therein.

9. The non-transitory computer readable storage medium of claim 8, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to concatenate the plurality of independent data objects by:

identifying data objects having a common trait; and

establishing the plurality of independent data objects from the data objects having the common trait.

10. The non-transitory computer readable storage medium of claim 8, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to concatenate the plurality of independent data objects by:

mapping the plurality of independent data objects into “

k”

rows to produce the concatenated data object, wherein the “

k”

rows corresponds to the number of data-based encoded data slices resulting from performing the dispersed storage error encoding function and wherein the one or more independent data objects is mapped to a single row of the “

k”

rows.

11. The non-transitory computer readable storage medium of claim 10 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

pad the single row of the “

k”

rows when a combined size of the one or more independent data objects is less than a row size.

12. The non-transitory computer readable storage medium of claim 8, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to concatenate the plurality of independent data objects by:

mapping the plurality of independent data objects into “

k”

rows to produce the concatenated data object, wherein the “

k”

rows corresponds to a number of data-based encoded data slices resulting from performing the dispersed storage error encoding function and wherein an independent data object of the plurality of independent data objects is mapped to more than one row of the “

k”

rows.

13. The non-transitory computer readable storage medium of claim 8, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to perform the dispersed storage error encoding function by:

converting the concatenated data object into a data matrix;

generating a coded matrix based on the data matrix and an encoding matrix;

generating the set of data-based encoded data slices from a first portion of the coded matrix that corresponds to a first portion of the encoding matrix; and

generating the set of redundancy-based encoded data slices from a second portion of the coded matrix that corresponds to a second portion of the encoding matrix.

14. The non-transitory computer readable storage medium of claim 8 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

receive a message to concatenate the plurality of independent data objects, wherein the message is one of a user input message to group data objects having a common trait and a system message based on dispersed storage network conditions.

15. A computing device of a group of computing devices 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;

concatenate a plurality of independent data objects into a concatenated data object, wherein the concatenating is based on a parameter of a dispersed storage error encoding function that indicates a number of data-based encoded data slices resulting from performing the dispersed storage error encoding function;

perform the dispersed storage error encoding function on the concatenated data object to produce a set of data-based encoded data slices and a set of redundancy-based encoded data slices, wherein one or more independent data objects of the plurality of independent data objects is recoverable from a corresponding data-based encoded data slice of the set of data-based encoded data slices or from a decode threshold number of encoded data slices, wherein the decode threshold number of encoded data slices includes one or more data-based encoded data slices of the set of data-based encoded data slices and one or more redundancy-based encoded data slices of the set of redundancy-based encoded data slices;

output, via the interface, the set of data-based encoded data slices to a first set of storage units for storage therein; and

output, via the interface, the set of redundancy-based encoded data slices to a second set of storage units for storage therein.

16. The computing device of claim 15, wherein the processing module functions to concatenate the plurality of independent data objects by:

identifying data objects having a common trait; and

establishing the plurality of independent data objects from the data objects having the common trait.

17. The computing device of claim 15, wherein the processing module functions to concatenate the plurality of independent data objects by:

mapping the plurality of independent data objects into “

k”

rows to produce the concatenated data object, wherein the “

k”

rows corresponds to the number of data-based encoded data slices resulting from performing the dispersed storage error encoding function and wherein the one or more independent data objects is mapped to a single row of the “

k”

rows.

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

pad the single row of the “

k”

rows when a combined size of the one or more independent data objects is less than a row size.

19. The computing device of claim 15, wherein the processing module functions to concatenate the plurality of independent data objects by:

mapping the plurality of independent data objects into “

k”

rows to produce the concatenated data object, wherein the “

k”

rows corresponds to a number of data-based encoded data slices resulting from performing the dispersed storage error encoding function and wherein an independent data object of the plurality of independent data objects is mapped to more than one row of the “

k”

rows.

20. The computing device of claim 15, wherein the processing module functions to perform the dispersed storage error encoding function by:

converting the concatenated data object into a data matrix;

generating a coded matrix based on the data matrix and an encoding matrix;

generating the set of data-based encoded data slices from a first portion of the coded matrix that corresponds to a first portion of the encoding matrix; and

generating the set of redundancy-based encoded data slices from a second portion of the coded matrix that corresponds to a second portion of the encoding matrix.

21. The computing device of claim 15, wherein the processing module further functions to:

receive a message to concatenate the plurality of independent data objects, wherein the message is one of a user input message to group data objects having a common trait and a system message based on dispersed storage network conditions.