Data storage system and method by shredding and deshredding

• US 10,169,154 B2
• Filed: 12/01/2014
• Issued: 01/01/2019
• Est. Priority Date: 08/31/2001
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: de la Torre, Douglas R., Young, David W.
• Primary Examiner(s): Phillips, III, Albert M
• Application Number:
  US14/557,078
• Publication Number:
  US 20150088842A1
• Time in Patent Office: 1,492 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/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 11/141 for bus or memory accesses
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system and method for data storage by shredding and deshredding of the data allows for various combinations of processing of the data to provide various resultant storage of the data. Data storage and retrieval functions include various combinations of data redundancy generation, data compression and decompression, data encryption and decryption, and data integrity by signature generation and verification. Data shredding is performed by shredders and data deshredding is performed by deshredders that have some implementations that allocate processing internally in the shredder and deshredder either in parallel to multiple processors or sequentially to a single processor. Other implementations use multiple processing through multi-level shredders and deshredders. Redundancy generation includes implementations using non-systematic encoding, systematic encoding, or a hybrid combination. Shredder based tag generators and deshredder based tag readers are used in some implementations to allow the deshredders to adapt to various versions of the shredders.

Claims

1. A method for encoding data for storage in a plurality of storage units by use of at least one processor comprising:

dividing data into a set of separate pieces of data;

performing a redundancy function and a plurality of transformations on a separate piece of data of the set of separate pieces of data to generate a plurality of encoded data elements, wherein a threshold number of encoded data elements of the plurality of encoded data elements is needed to recover the separate piece of data, in which the threshold number of encoded data elements is less than all of the plurality of encoded data elements, wherein the plurality of transformations includes first transformations performed before performing the redundancy function and second transformations performed after performing the redundancy function;

generating metadata regarding the plurality of encoded data elements, wherein the metadata includes identification for each encoded data element and sequencing information regarding an order in which the redundancy function and the plurality of transformations were performed;

sending the plurality of encoded data elements to the plurality of storage units; and

sending the metadata to one of the storage units of the plurality of storage units or to another storage unit separately from sending the plurality of encoded data elements to the plurality of storage units.

2. The method of claim 1, further including identifying and selecting the plurality of storage units for sending the plurality of encoded data elements.

3. The method of claim 1, wherein when performing the redundancy function to generate the plurality of encoded data elements, systematic encoding is used.

4. The method of claim 1, wherein when performing the redundancy function to generate the plurality of encoded data elements, non-systematic encoding is used.

5. The method of claim 1, wherein when performing the redundancy function to generate the plurality of encoded data elements, a hybrid combination of systematic encoding and non-systematic encoding is used.

6. The method of claim 1, wherein the metadata includes information pertaining to relationships among different encoded data elements of the plurality of encoded data elements.

7. The method of claim 1, wherein the metadata includes information pertaining to identifiers of the functions performed in the generation of the plurality of encoded data elements.

8. The method of claim 7, wherein the identifiers of the functions performed identify one or more of an encryption function, a sequencing function, or parameters that have changed, in the generation of the plurality of encoded data elements.

9. The method of claim 1, wherein the metadata includes one or more information pertaining to:

data geometries;

data relationships;

data nesting;

structure;

coding structure;

data alignment;

size and length of data; and

data hash.

10. An apparatus for encoding data for storage in a plurality of storage units comprising:

an interface; and

at least one processor configured with the interface to;

divide data into a set of separate pieces of data;

execute a redundancy function and a plurality of transformations on a separate piece of data of the set of separate pieces of data to generate a plurality of encoded data elements, wherein a threshold number of encoded data elements of the plurality of encoded data elements is needed to recover the separate piece of data, in which the threshold number of encoded data elements is less than all of the plurality of encoded data elements, wherein the plurality of transformations includes first transformations performed before performing the redundancy function and second transformations performed after performing the redundancy function;

generate metadata regarding the plurality of encoded data elements, wherein the metadata includes identification for each encoded data element and sequencing information regarding an order in which the redundancy function and the plurality of transformations were performed;

send, via the interface, the plurality of encoded data elements to the plurality of storage units; and

send, via the interface, the metadata to one of the storage units of the plurality of storage units or to another storage separately from sending, via the interface, the plurality of encoded data elements to the plurality of storage units.

11. The apparatus of claim 10, wherein the at least one processor is to identify and select the plurality of storage units for sending the plurality of encoded data elements.

12. The apparatus of claim 10, wherein the at least one processor uses systematic encoding to generate the plurality of encoded data elements.

13. The apparatus of claim 10, wherein the at least one processor uses non-systematic encoding to generate the plurality of encoded data elements.

14. The apparatus of claim 10, wherein the at least one processor uses a hybrid combination of systematic encoding and non-systematic encoding to generate the plurality of encoded data elements.

15. The apparatus of claim 10, wherein the metadata includes information pertaining to relationships among different encoded data elements of the plurality of encoded data elements.

16. The apparatus of claim 10, wherein the metadata includes information pertaining to identifiers of the functions performed in the generating of the plurality of encoded data elements.

17. The apparatus of claim 16, wherein the identifiers of the functions performed identify one or more of an encryption function, a sequencing function, or parameters that have changed, in the generating of the plurality of encoded data elements.

18. The apparatus of claim 10, wherein the metadata includes one or more information pertaining to:

data geometries;

data relationships;

data nesting;

structure;

coding structure;

data alignment;

size and length of data; and

data hash.

19. A non-transitory computer-readable medium comprising instructions executable by a processor and when executed, instructing the processor to:

divide data into a set of separate pieces of data;

perform a redundancy function and a plurality of transformations on a separate piece of data of the set of separate pieces of data to generate a plurality of encoded data elements, wherein a threshold number of encoded data elements of the plurality of encoded data elements is needed to recover the separate piece of data, in which the threshold number of encoded data elements is less than all of the plurality of encoded data elements, wherein the plurality of transformations includes first transformations performed before performing the redundancy function and second transformations performed after performing the redundancy function;

generate metadata regarding the plurality of encoded data elements, wherein the metadata includes identification for each encoded data element and sequencing information regarding an order in which the redundancy function and the plurality of transformations were performed;

send the plurality of encoded data elements to a plurality of storage units; and

send the metadata to one of the storage units of the plurality of storage units or to another storage unit separately from sending the plurality of encoded data elements to the plurality of storage units.

20. The non-transitory computer-readable medium of claim 19, wherein the instructions instruct the processor to use systematic encoding, non-systematic encoding or a hybrid combination of systematic encoding and non-systematic encoding, to generate the plurality of encoded data elements.