Data storage system and method by shredding and deshredding

• US 20030065656A1
• Filed: 09/03/2002
• Published: 04/03/2003
• Est. Priority Date: 08/31/2001
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Peerify Technology
• Inventors: Young, David W., de la Torre, Douglas R.
• Granted Patent: US 7,636,724 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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 deshredder for retrievel of data store by a shredder inculding an allocator configured to allocate the data into portions;

and a plurality of redundancy generators each configured to process at least one of the portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group, the deshredder comprising;

a plurality of inverse redundancy generators configured to receive at least one of the shred groups and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number; and

a deallocator configured to received the portions of data outputted by the plurality of inverse redundancy generators and to output the data.

2. A shredder for storage of data to be retrieved by a deshredder a deshredder including a plurality of inverse redundancy generators configured to receive at least one shred group storing a portion of the data and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than a first number;

and a deallocator configured to received the portions of data outputted by the plurality of inverse redundancy generators and to output the data, the shredder comprising;

an allocator configured to allocate the data into the portions; and

a plurality of redundancy generators each configured to process at least one of the portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as the first number of shreds in a shred group.

3. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

an allocator configured to allocate the data into portions; and

a plurality of redundancy generators each configured to process at least one of the portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

a deshredder including;

a plurality of inverse redundancy generators configured to receive at least one of the shred groups and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number; and

a deallocator configured to received the portions of data outputted by the plurality of inverse redundancy generators and to output the data.

4. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

an allocator configured to allocate the data into portions; and

a redundancy generator configured to process the portions of the data one at a time to generate for each portion processed a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

a deshredder including;

an inverse redundancy generator configured to receive the shred groups one at time and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number; and

a deallocator configured to received the portions of data outputted by the inverse redundancy generator and to output the data.

5. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

a transformer configured to compress the data; and

at least one redundancy generator configured to process portions of the compressed data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

a deshredder including;

at least one inverse redundancy generator configured to receive the shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number; and

a inverse transformer configured to received the portions outputted by the at least one inverse redundancy generator and to output the data as decompressed.

6. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

at least one redundancy generator configured to process portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

at least one transformer configured to compress the shred groups; and

a deshredder including;

at least one inverse transformer configured to receive the compressed shred groups and to output the shred groups as decompressed; and

at least one inverse redundancy generator configured to receive the decompressed shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number.

7. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

a transformer configured to compress the data in a first manner;

a tag generator configured to generate a tag describing the first manner of compression, and

at least one redundancy generator configured to process portions of the compressed data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

a deshredder including;

at least one inverse redundancy generator configured to receive the shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number;

a tag reader configured to determine that the first manner was used for compression based upon the tag; and

a inverse transformer configured to perform more than one type of decompression including the first manner of decompression, to receive the portions outputted by the at least one inverse redundancy generator and to output the data as decompressed through the first manner based upon input from the tag reader.

8. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

at least one redundancy generator configured to process portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group;

at least one transformer configured to compress the shred groups in a first manner; and

a tag generator configured to generate a tag describing the first manner of compression; and

a deshredder including;

a tag reader configured to determine that the first manner was used for compression based upon the tag;

at least one inverse transformer configured to perform more than one type of decompression including the first manner of decompression, to receive the compressed shred groups to output the data as decompressed through the first manner based upon input from the tag reader; and

at least one inverse redundancy generator configured to receive the decompressed shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number.

9. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

a transformer configured to encrypt the data; and

at least one redundancy generator configured to process portions of the encrypted data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

a deshredder including;

at least one inverse redundancy generator configured to receive the shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number; and

a inverse transformer to received the portions outputted by the at least one inverse redundancy generator and to output the data as decrypted.

10. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

at least one redundancy generator configured to process portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

at least one transformer configured to encrypt the shred groups; and

a deshredder including;

at least one inverse transformer configured to receive the encrypted shred groups and to output the shred groups as decrypted and

at least one inverse redundancy generator configured to receive the decrypted shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number.

11. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

a transformer configured to encrypt the data in a first manner;

a tag generator configured to generate a tag describing the first manner of encryption, and

at least one redundancy generator configured to process portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

a deshredder including;

at least one inverse redundancy generator configured to receive the shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number;

a tag reader configured to determine that the first manner was used for encryption based upon the tag; and

a inverse transformer configured to perform more than one type of decryption including the first manner of decryption, to receive the portions outputted by the at least one inverse redundancy generator and to output the data as decrypted through the first manner based upon input from the tag reader.

12. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

at least one redundancy generator configured to process portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group;

at least one transformer configured to encrypt the shred groups in a first manner; and

a tag generator configured to generate a tag describing the first manner of encryption; and

a deshredder including;

a tag reader configured to determine that the first manner was used for encryption based upon the tag;

a least one inverse transformer configured to perform more than one type of decryption including the first manner of decryption, to receive the portions outputted by the at least one inverse redundancy generator and to output the data as decrypted through the first manner based upon input from the tag reader; and

at least one inverse redundancy generator configured to receive the shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number.

13. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

at least one redundancy generator configured to process portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

at least one transformer configured to generate a signature describing at least one of the portions; and

a deshredder including;

at least one inverse redundancy generator configured to receive the shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number; and

a least one inverse transformer configured to use the signature to verify at least one of the portions.

14. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

at least one redundancy generator configured to process portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

at least one transformer configured to partition the shred groups according to available storage units; and

a deshredder including;

at least one inverse redundancy generator configured to receive the shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number; and

a least one inverse transformer configured to repartition the shred groups before being received the inverse redundancy generator.

15. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

at least one redundancy generator configured to process portions of the data to generate in a first manner for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

a tag generator configured to generate a tag describing the first manner of redundancy generation; and

a deshredder including;

a tag reader configured to determine that the first manner was used for redundancy generation based upon the tag; and

at least one inverse redundancy generator configured to perform one than one manner of inverse redundancy generation, to receive the shred groups for each of the portions, and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number according to the first manner of inverse redundancy generation based upon input from the tag reader.

16. A shredding and deshredding system for storage and retrieval of data comprising:

a plurality of shredders having inputs and outputs, a first of the plurality configured to receive the data and to output to more than one of the plurality, each of the plurality including;

at least one redundancy generator configured to process portions of the data to generate in a first manner for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

a deshredder including;

at least one inverse redundancy generator configured to perform one than one manner of inverse redundancy generation, to receive the shred groups for each of the portions, and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number according to the first manner of inverse redundancy generation based upon input from the tag reader.

17. A shredding and deshredding system for storage and retrieval of data comprising:

a plurality of shredders, each having an input and at least one output, a first of the plurality configured to receive the data and to output to more than one of the plurality, each of the plurality including;

at least one redundancy generator configured to process portions of the data to generate in a first manner for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

a tag generator configured to generate a tag describing a relationship that the shedder input and the at least one output have with respect to directly coupled one or more other of the plurality of shredder; and

a deshredder including;

a tag reader configured to determine what the relationship that the input and the at least one output have with respect to directly coupled one or more of the other plurality of shredders; and

at least one inverse redundancy generator configured to perform inverse redundancy generation, to receive the shred groups for each of the portions, and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number according to the relationship that the input and the at least one output have with respect to directly coupled one or more of the other plurality of shredders.

18. A shredding and deshredding system for storage and retrieval of data comprising:

a shredder including;

at least one redundancy generator configured to process portions of the data to generate with a version of non-systematic encoding for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

a deshredder including;

at least one inverse redundancy generator configured to receive the shred groups for each of the portions, and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number according to the version of the non-systematic encoding.

19. A method of shredding and deshredding for storage and retrieval of data, the method comprising:

allocating the data into portions; and

generating for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

receiving the shred groups to output the portions stored in the shred groups from a second number of shreds of each of the received shred groups, the second number being smaller than the first number; and

deallocating the portions of data to output the data.

20. The method of claim 19, further comprising generating a signature describing at least one of the portions;

and using the signature to verify at least one of the portions.

21. The method of claim 19, further comprising:

partitioning the shred groups according to available storage units; and

repartitioning the shred groups before inverse redundancy generation.

22. The method of claim 19, further comprising describing the manner of redundancy generation;

and determining that the manner was used for redundancy generation based upon the description.

23. The method of claim 19 wherein the redundant part was generated with a version of non-systematic encoding

24. A method of shredding and deshredding for storage and retrieval of data, the method comprising:

compressing the data;

processing portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

receiving the shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number; and

decompressing the portions to output the data as decompressed.

25. The method of claim 24, wherein compressing is done in a first manner and further comprising generating a tag describing the first manner of compression, determining that the first manner was used for compression, and decompressing the portions through the first manner based upon the determining.

26. A method of shredding and deshredding for storage and retrieval of data, the method comprising:

encrypting the data;

processing portions of the data to generate for each portion a redundant part of the portion, each portion and redundant part to be stored as a first number of shreds in a shred group; and

receiving the shred groups for each of the portions and to output the portion stored in the shred group from a second number of shreds of the received shred group, the second number being smaller than the first number; and

decrypting the portions to output the data as decrypted.

27. The method of claim 26, wherein encrypting is done in a first manner and further comprising generating a tag describing the first manner of encrypting, determining that the first manner was used for encrypting, and decrypting the portions through the first manner based upon the determining.