Encoding data in a dispersed storage network

• US 9,081,675 B2
• Filed: 06/11/2014
• Issued: 07/14/2015
• Est. Priority Date: 07/31/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US14/302,377
• Publication Number:
  US 20140298134A1
• Time in Patent Office: 398 Days
• Field of Search: 711/103, 711/5, 711/170, 711/173, 711/E12.059, 711/114, 714/6.2, 714/6.22, 714/6.24
• US Class Current: 1/1
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; 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], H04L67/1097
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1016 Error in accessing a memory location, i.e. addressing error
• 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 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 12/14 Protection against unauthorised use of memory or access to memory
• 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: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/4401 Bootstrapping security arrangements therefor G06F21/57

Abstract

A method begins where a processing module segments data into data segments. On a data segment by data segment basis, the method continues with the processing module performing a decode threshold level of dispersed storage error encoding on a data segment to produce a set of decode threshold level encoded data slices and caching the set of decode threshold level encoded data slices. On a set by set basis, the method continues with the processing module performing a redundancy level of dispersed storage error encoding on the set of decode threshold level encoded data slices to produce a set of redundancy error coded data slices. The method continues with the processing module outputting at least one of at least some of a plurality of sets of decode threshold level encoded data slices and at least a corresponding some of a plurality of sets of redundancy error coded data slices.

Claims

1. A computing device comprises:

an interface;

memory; and

a processing module operably coupled to the interface and the memory, wherein the processing module is operable to;

segment data into a plurality of data segments;

on a data segment by data segment basis;

perform a decode threshold level of dispersed storage error encoding on a data segment of the plurality of data segments to produce a set of decode threshold level encoded data slices;

cache the set of decode threshold level encoded data slices, wherein, for the plurality of data segments, a plurality of sets of decode threshold level encoded data slices are created;

on set by set basis, perform a redundancy level of dispersed storage error encoding based on one of the plurality of sets of decode threshold level encoded data slices to produce a set of redundancy error coded data slices, wherein a plurality of sets of redundancy error coded data slices are created based on the plurality of sets of decode threshold level encoded data slices; and

output at least one of;

at least some of the plurality of sets of decode threshold level encoded data slices; and

at least a corresponding some of the plurality of sets of redundancy error coded data slices.

2. The computing device of claim 1, wherein the processing module further functions to perform the decode threshold level of dispersed storage error encoding by:

arranging data blocks of the data segment into a data matrix; and

performing an encoding function on the data matrix to produce the set of decode threshold level encoded data slices.

3. The computing device of claim 2, wherein the encoding function comprises one or more of:

matrix multiplication with a unity matrix portion of an encoding matrix; and

a mathematical function performed on the data matrix to generate a decode threshold number of encoded data slices, wherein the decode threshold number is a minimum number of encoded data slices required to reconstruct the data segment.

4. The computing device of claim 1, wherein the processing module further functions to perform the redundancy level of dispersed storage error encoding by:

obtaining a data matrix that includes data blocks of the data segment; and

performing a redundancy encoding function on the data matrix to produce the set of redundancy error coded data slices.

5. The computing device of claim 4, wherein the redundancy encoding function comprises one or more of:

matrix multiplication with a redundancy matrix portion of an encoding matrix; and

a mathematical function performed on the data matrix to generate a redundancy number of error coded data slices, wherein the redundancy number of error coded data slices and the set of decode threshold level encoded data slices provide a complete set of encoded data slices for the data segment, wherein a decode threshold number of encoded data slices of the complete set of encoded data slices are required to reconstruct the data segment.

6. The computing device of claim 1, wherein the processing module further functions to output by:

decoding the at least some of the plurality of sets of decode threshold level encoded data slices to produce at least some of the plurality of data segments; and

outputting the at least some of the plurality of data segments to a video graphics processing module.

7. The computing device of claim 1, wherein the processing module further functions to output by:

correlating the at least some of the plurality of sets of decode threshold level encoded data slices with the at least a corresponding some of the plurality of sets of redundancy error coded data slices to produce at least some of a plurality of complete sets of encoded data slices; and

outputting the at least some of a plurality of complete sets of encoded data slices to a set of memory devices for storage therein.

8. The computing device of claim 1, wherein the processing module further functions to:

perform the decode threshold level of dispersed storage error encoding on the data segment and perform the redundancy level of dispersed storage error encoding asynchronously.

9. The computing device of claim 1, wherein the processing module further functions to:

cache the set of decode threshold level encoded data slices in a decode threshold level section of the memory; and

cache the set of redundancy error coded data slices in a redundancy section of the memory.

10. A method for execution by a computing core of a computing device, the method comprises:

segmenting data into a plurality of data segments;

on a data segment by data segment basis;

performing a decode threshold level of dispersed storage error encoding on a data segment of the plurality of data segments to produce a set of decode threshold level encoded data slices;

caching the set of decode threshold level encoded data slices, wherein, for the plurality of data segments, a plurality of sets of decode threshold level encoded data slices are created;

on set by set basis, performing a redundancy level of dispersed storage error encoding based on one of the plurality of sets of decode threshold level encoded data slices to produce a set of redundancy error coded data slices, wherein a plurality of sets of redundancy error coded data slices are created based on the plurality of sets of decode threshold level encoded data slices; and

outputting at least one of;

at least some of the plurality of sets of decode threshold level encoded data slices; and

at least a corresponding some of the plurality of sets of redundancy error coded data slices.

11. The method of claim 10, wherein the performing the decode threshold level of dispersed storage error encoding comprises:

arranging data blocks of the data segment into a data matrix; and

performing an encoding function on the data matrix to produce the set of decode threshold level encoded data slices.

12. The method of claim 11, wherein the encoding function comprises one or more of:

matrix multiplication with a unity matrix portion of an encoding matrix; and

a mathematical function performed on the data matrix to generate a decode threshold number of encoded data slices, wherein the decode threshold number is a minimum number of encoded data slices required to reconstruct the data segment.

13. The method of claim 10, wherein the performing the redundancy level of dispersed storage error encoding comprises:

obtaining a data matrix that includes data blocks of the data segment; and

performing a redundancy encoding function on the data matrix to produce the set of redundancy error coded data slices.

14. The method of claim 13, wherein the redundancy encoding function comprises one or more of:

matrix multiplication with a redundancy matrix portion of an encoding matrix; and

a mathematical function performed on the data matrix to generate a redundancy number of error coded data slices, wherein the redundancy number of error coded data slices and the set of decode threshold level encoded data slices provide a complete set of encoded data slices for the data segment, wherein a decode threshold number of encoded data slices of the complete set of encoded data slices are required to reconstruct the data segment.

15. The method of claim 10, wherein the outputting comprises:

decoding the at least some of the plurality of sets of decode threshold level encoded data slices to produce at least some of the plurality of data segments; and

outputting the at least some of the plurality of data segments to a video graphics processing module.

16. The method of claim 10, wherein the outputting comprises:

correlating the at least some of the plurality of sets of decode threshold level encoded data slices with the at least a corresponding some of the plurality of sets of redundancy error coded data slices to produce at least some of a plurality of complete sets of encoded data slices; and

outputting the at least some of a plurality of complete sets of encoded data slices to a set of memory devices for storage therein.

17. The method of claim 10 further comprises:

the performing of the decode threshold level of dispersed storage error encoding on the data segment being asynchronous with the performing of the redundancy level of dispersed storage error encoding.

18. The method of claim 10 further comprises:

caching the set of decode threshold level encoded data slices in a decode threshold level section of main memory of the computing device; and

caching the set of redundancy error coded data slices in a redundancy section of main memory of the computing device.

19. A non-transitory computer readable storage medium having accessible therefrom a set of instructions interpretable by a processing module, the set of instructions being configured to cause the processing module to carry out operations for:

segmenting data into a plurality of data segments;

on a data segment by data segment basis;

performing a decode threshold level of dispersed storage error encoding on a data segment of the plurality of data segments to produce a set of decode threshold level encoded data slices;

caching the set of decode threshold level encoded data slices, wherein, for the plurality of data segments, a plurality of sets of decode threshold level encoded data slices are created;

on set by set basis, performing a redundancy level of dispersed storage error encoding based on one of the plurality of sets of decode threshold level encoded data slices to produce a set of redundancy error coded data slices, wherein a plurality of sets of redundancy error coded data slices are created based on the plurality of sets of decode threshold level encoded data slices; and

outputting at least one of;

at least some of the plurality of sets of decode threshold level encoded data slices; and

at least a corresponding some of the plurality of sets of redundancy error coded data slices.

20. The non-transitory computer readable storage medium of claim 19, wherein the set of instructions further causes the processing module to carry out operations for the performing the decode threshold level of dispersed storage error encoding by:

arranging data blocks of the data segment into a data matrix; and

performing an encoding function on the data matrix to produce the set of decode threshold level encoded data slices.

21. The non-transitory computer readable storage medium of claim 20, wherein the encoding function comprises one or more of:

matrix multiplication with a unity matrix portion of an encoding matrix; and

a mathematical function performed on the data matrix to generate a decode threshold number of encoded data slices, wherein the decode threshold number is a minimum number of encoded data slices required to reconstruct the data segment.

22. The non-transitory computer readable storage medium of claim 19, wherein the set of instructions further causes the processing module to carry out operations for the performing the redundancy level of dispersed storage error encoding by:

obtaining a data matrix that includes data blocks of the data segment; and

performing a redundancy encoding function on the data matrix to produce the set of redundancy error coded data slices.

23. The non-transitory computer readable storage medium of claim 22, wherein the redundancy encoding function comprises one or more of:

matrix multiplication with a redundancy matrix portion of an encoding matrix; and

a mathematical function performed on the data matrix to generate a redundancy number of error coded data slices, wherein the redundancy number of error coded data slices and the set of decode threshold level encoded data slices provide a complete set of encoded data slices for the data segment, wherein a decode threshold number of encoded data slices of the complete set of encoded data slices are required to reconstruct the data segment.

24. The non-transitory computer readable storage medium of claim 19, wherein the set of instructions further causes the processing module to carry out operations for the outputting by:

decoding the at least some of the plurality of sets of decode threshold level encoded data slices to produce at least some of the plurality of data segments; and

outputting the at least some of the plurality of data segments to a video graphics processing module.

25. The non-transitory computer readable storage medium of claim 19, wherein the set of instructions further causes the processing module to carry out operations for the outputting by:

correlating the at least some of the plurality of sets of decode threshold level encoded data slices with the at least a corresponding some of the plurality of sets of redundancy error coded data slices to produce at least some of a plurality of complete sets of encoded data slices; and

outputting the at least some of a plurality of complete sets of encoded data slices to a set of memory devices for storage therein.

26. The non-transitory computer readable storage medium of claim 19, wherein the set of instructions further being configured to cause the processing module to carry out operations for:

the performing of the decode threshold level of dispersed storage error encoding on the data segment being asynchronous with the performing of the redundancy level of dispersed storage error encoding.

27. The non-transitory computer readable storage medium of claim 19, wherein the set of instructions further being configured to cause the processing module to carry out operations for:

caching the set of decode threshold level encoded data slices in a decode threshold level section of main memory of a computing device; and

caching the set of redundancy error coded data slices in a redundancy section of main memory of the computing device.