Data storage system and method by shredding and deshredding

• US 7,636,724 B2
• Filed: 09/03/2002
• Issued: 12/22/2009
• Est. Priority Date: 08/31/2001
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Peerify Technology
• Inventors: de la Torre, Douglas R., Young, David W.
• Primary Examiner(s): Alam, Shahid A
• Assistant Examiner(s): Colan, Giovanna
• Application Number:
  US10/234,636
• Publication Number:
  US 20030065656A1
• Time in Patent Office: 2,667 Days
• Field of Search: 709/219, 714/752, 395/250, 713/168, 707/101, 707/3, 710/56, 710/52, 710/26, 711/105
• 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/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 system for use with data, the system comprising:

a storage location;

at least one processor coupled to the storage location;

a memory comprising instructions executable by the at least one processor, the instructions when executed by the at least one processor implementing a customizable shredder including an allocator, a first plurality of transformers, a tag generator, and a plurality of redundancy generators,

the allocator being configured to perform an allocation operation allocating the data into a selected number of portions, the selected number being greater than one, and

the first plurality of transformers applying at least one transformation to the data,

the plurality of redundancy generators applying a redundancy operation to the data to add redundancy to the data, the memory further comprising instructions executable by the at least one processor, the instructions when executed by the at least one processor storing the data in the storage location as a plurality of shreds, each shred storing a portion of the data,

the tag generator being configured to generate a tag for each of the plurality of shreds, the tag comprising information identifying the allocation operation, the at least one transformation, and the redundancy operation applied to the portion of the data stored in the shred and a shred order in which the allocation operation, the at least one transformation, and the redundancy operation were applied to the portion of the data stored in the shred;

the memory further comprising instructions executable by the at least one processor, the instructions when executed by the at least one processor implementing a deshredder including a tag reader, a plurality of inverse redundancy generators, a first plurality of inverse transformers, and a deallocator,

for each of at least a portion the plurality of shreds, the tag reader being configured to read the tag for the shred, identify the allocation operation, the at least one transformation, and the redundancy operation applied to the portion of the data stored in the shred and identify the shred order in which the allocation operation, the at least one transformation, and the redundancy operation were applied to the portion of the data stored in the shred, the memory further comprising instructions that when executed by the at least one processor identifies an inverse allocation operation inverse to the allocation operation applied to the portion of the data stored in the shred, at least one inverse transformation inverse to the at least one transformation applied to the portion of the data stored in the shred, an inverse redundancy operation inverse to the redundancy operation applied to the portion of the data stored in the shred, and to execute the inverse allocation operation, the at least one inverse transformation, and the inverse redundancy operation in a deshred order inverse to the shred order,

the plurality of inverse redundancy generators applying the inverse redundancy operation to a portion of the plurality of shreds and outputting the portions of the data stored in each shred without the redundancy, the portion of the plurality of shreds being fewer than all of the plurality of shreds, the outputted portions of the data stored in the portion of the plurality of shreds comprising the data,

the first plurality of inverse transformers applying the at least one inverse transformation to the portions of the data stored in the portion of the plurality of shreds; and

the deallocator being configured to apply the inverse allocation operation to the portions of the data stored in the portion of the plurality of shreds.

2. The system of claim 1 wherein the at least one transformation comprises a compression transformation, and

the at least one inverse transformation comprises a decompression transformation.

3. The system of claim 1 wherein the shredder includes a second plurality of transformers each configured to apply a compression operation that compresses the plurality of shreds before they are stored in the storage location, the tag comprising information identifying the compression operation and indicating where in the shred order the compression operation was performed;

the memory further comprises instructions that when executed by the at least one processor identifies a decompression operation inverse to the compression operation applied to the plurality of shreds, and

the deshredder includes a second plurality of inverse transformers each configure to perform the decompression operation to decompress the compressed plurality of shreds in accordance with the deshred order.

4. The system of claim 1 wherein the at least one transformation comprises an encryption transformation and, the at least one inverse transformation comprises a decryption operation.

5. The system of claim 1 wherein the shredder includes:

a second plurality of transformers each configured to apply an encryption operation to the plurality of shreds before they are stored in the storage location, the tag comprising information identifying the encryption operation and indicating where in the shred order the encryption operation was performed,

the memory further comprises instructions that when executed by the at least one processor identifies a decryption operation inverse to the encryption operation applied to the plurality of shreds, and

the deshredder includes a second plurality of inverse transformers each configured to perform the decryption operation to decrypt the encrypted plurality of shreds in accordance with the deshred order.

6. The system of claim 1 wherein the at least one transformation includes at least one signature transformation configured to generate a signature describing the data or a portion thereof, and the at least one the first plurality of inverse transformations uses the signature to verify the data or a portion thereof.

7. The system of claim 1 wherein the storage location comprises multiple available output units,

the shredder further includes a second plurality of transformers configured to partition the plurality of shreds according to the multiple available output units, the tag comprising information indicating the partition occurred and indicating where in the shred order the partition occurred,

the memory further comprises instructions that when executed by the at least one processor identifies a repartition operation inverse to the partition applied to the plurality of shreds, and

the deshredder includes a second plurality of inverse transformers configured to perform the repartition operation on the plurality of shreds in accordance with the deshred order.

8. The system of claim 1 wherein the redundancy operation comprises a version of non-systematic encoding.

15. The system of claim 1 wherein the shredder includes a second transformer configured to apply a signature operation to the plurality of shreds to generate a signature describing the plurality of shreds before they are stored in the storage location, the tag comprising information identifying the signature operation and indicating where in the shred order the signature operation was performed;

the memory further comprises instructions that when executed by the at least one processor identifies an inverse signature operation inverse to the signature operation applied to the plurality of shreds, and

the deshredder includes an inverse signature transformer configure to use the signature describing the plurality of shreds to perform the inverse signature operation to verify the plurality of shreds in accordance with the deshred order.

9. A method comprising:

performing an allocation operation on initial data to allocate the initial data into allocated portions;

selecting a first transformation operation for each allocated portion;

applying the first transformation operation to the allocated portions;

for each allocated portion, performing a redundancy operation on the transformed portions to generate a first number of shreds, the first number of shreds being greater than the number of transformed portions of the allocated portion;

for each allocated portion, generating a tag for each shred, the tag comprising information identifying the allocation operation, the first transformation operation, and the redundancy operation applied previously to the initial data to generate the shred and indicating a shred order in which the allocation operation, the first transformation operation, and the redundancy operation were applied;

reading the tag for at least a portion of the shreds to determine a deshred order that is the inverse of the shred order;

for each allocated portion, in accordance with the deshred order, performing an operation inverse to the redundancy operation on a second number of shreds to output the transformed portions, the second number of shreds being smaller than the first number of shreds;

for each allocated portion, in accordance with the deshred order, performing a transformation inverse to the first transformation operation on the transformed portions to generate the allocated portion; and

in accordance with the deshred order, performing an operation inverse to the allocation operation on the allocated portions of the initial data to output the initial data.

10. The method of claim 9 wherein the first transformation operation compresses each of allocated portions of the initial data, and

the transformation inverse to the first transformation decompresses the transformed portions to generate each of allocated portions of the initial data.

11. The method of claim 9 wherein the first transformation operation comprises an encryption transformation configured to encrypt the allocated portions of the initial data and the transformation inverse to the first transformation operation comprises a decryption transformation configured to decrypt the transformed portions.

12. The method of claim 9, wherein the first transformation operation comprises a signature transformation configured to generate a signature describing at least one of the allocated portions of the initial data, and the transformation inverse to the first transformation operation comprises using the signature to verify at least one of the allocated portions of the initial data.

13. The method of claim 9, further comprising:

dividing the plurality of shreds according to a number of available storage units; and

aggregating the plurality of shreds before performing the operation inverse to the redundancy operation.

14. The method of claim 9 wherein the redundancy operation performed on the transformed portions comprises a version of non-systematic encoding.

16. The method of claim 9, further comprising:

after generating the tag for each shred and before reading the tag for the portion of the shreds to determine the deshred order, discarding a portion of the shreds.

17. The method of claim 9, further comprising:

dividing the plurality of shreds according to a number of available storage units or modalities based on performance of the available storage units; and

aggregating the plurality of shreds before performing the operation inverse to the redundancy operation.

18. The method of claim 9, further comprising:

dividing the plurality of shreds according to available storage units or modalities based on a set of data storage requirements; and

aggregating the plurality of shreds before performing the operation inverse to the redundancy operation.

19. The method of claim 9, wherein for each shred, the tag further comprises information identifying one of the allocated portions for which the shred was generated, and the method further comprises:

for each shred, reading the information identifying the one of the allocated portions to identify the allocated portion for the shred; and

for each allocated portion, identifying the second number of shreds based on the reading of the tags of the shreds.

20. The method of claim 19, further comprising:

after generating the tag for each shred for each allocated portion, distributing the plurality of shreds for each allocated portion in a plurality of storage locations.

21. A method for use with a block of data, the method comprising:

selecting at least one transformation operation, an allocation operation, a redundancy operation, and a shred order in which to apply the at least one transformation operation, the allocation operation, and the redundancy operation to the block of data, the allocation operation being configured to divide data into a plurality of sub-blocks;

applying the at least one transformation operation, the allocation operation, and the redundancy operation to the block of data in accordance with the shred order to obtain a plurality of shreds;

generating a tag for each shred identifying the at least one transformation operation, the allocation operation, the redundancy operation applied to the block of data to obtain the shred, and the shred order;

storing the plurality of shreds in at least one storage location;

identifying a portion of plurality of shreds sufficient to recover the block of data, the portion being fewer than all of the shreds in the plurality of shreds;

for each shred in the portion, reading the tag to determine an inverse operation for each of the at least one transformation operation, the allocation operation, and the redundancy operation applied to the block of data to obtain the shred, and to determine a deshred order inverse to the shred order for the shred; and

for each shred in the portion, applying the inverse operation for the at least one transformation operation, the inverse allocation operation, and the inverse redundancy operation to the shred in accordance with the deshred order to obtain the block of data.

22. The method of claim 21, further comprising:

before applying the inverse allocation operation organizing the portion of the plurality of shreds into groups corresponding to the sub-blocks into which the allocation operation divided the block of data.

23. A computer-readable medium comprising instructions executable by a processor and when executed instructing the processor to:

obtain a block of data;

select at least one transformation operation, an allocation operation, a redundancy operation, and a shred order in which to the apply the at least one transformation operation, the allocation operation, and the redundancy operation to the block of data, the allocation operation being configured to divide data into a plurality of sub-blocks;

apply the at least one transformation operation, the allocation operation, and the redundancy operation to the block of data in accordance with the shred order to obtain a plurality of shreds;

generate a tag for each shred identifying the at least one transformation operation, the allocation operation, the redundancy operation applied to the block of data to obtain the shred, and the shred order;

store the plurality of shreds in at least one storage location;

identify a portion of plurality of shreds sufficient to recover the block of data, the portion being fewer than all of the shreds in the plurality of shreds;

for each shred in the portion, read the tag to determine an inverse operation for each of the at least one transformation operation, the allocation operation, and the redundancy operation applied to the block of data to obtain the shred, and to determine a deshred order inverse to the shred order for the shred; and

for each shred in the portion, apply the inverse operation for the at least one transformation operation, the inverse allocation operation, and the inverse redundancy operation to the shred in accordance with the deshred order to obtain the block of data.

24. A system for use with data, the system comprising:

a storage location;

a plurality of processors coupled to the storage location;

a memory comprising instructions executable by the processors, the instructions when executed by one or more of the plurality of processors implementing a customizable shredder including an allocator, a first plurality of transformers, a tag generator, and a plurality of redundancy generators,

the allocator being configured to perform an allocation operation allocating the data into a selected number of portions, the selected number being greater than one, and

the first plurality of transformers being executable by the plurality of processors in parallel and during execution applying at least one transformation to the data,

the plurality of redundancy generators being executable by the plurality of processors in parallel and during execution applying a redundancy operation to the data to add at least one redundant part of the data to the data, the memory further comprising instructions executable by the processors, the instructions when executed by one or more of the plurality of processors storing the data including the at least one redundant part in the storage location as a plurality of shreds, each shred storing a portion of the data,

the tag generator being configured to generate a tag for each of the plurality of shreds, the tag comprising information identifying the allocation operation, the at least one transformation, and the redundancy operation applied to the portion of the data stored in the shred and a shred order in which the allocation operation, the at least one transformation, and the redundancy operation were applied to the portion of the data stored in the shred,

the memory further comprising instructions executable by the processors, the instructions when executed by one or more of the plurality of processors implementing a deshredder including a tag reader, a plurality of inverse redundancy generators, a first plurality of inverse transformers, and a deallocator,

for each of at least a portion the plurality of shreds, the tag reader configured to read the tag for the shred, identify the allocation operation, the at least one transformation, and the redundancy operation applied to the portion of the data stored in the shred and identify the shred order in which the allocation operation, the at least one transformation, and the redundancy operation were applied to the portion of the data stored in the shred, the memory further comprising instructions that when executed by one or more of the plurality of processors identifies an inverse allocation operation inverse to the allocation operation applied to the portion of the data stored in the shred, at least one inverse transformation inverse to the at least one transformation applied to the portion of the data stored in the shred, an inverse redundancy operation inverse to the redundancy operation applied to the portion of the data stored in the shred, and to execute the inverse allocation operation, the at least one inverse transformation, and the inverse redundancy operation in a deshred order inverse to the shred order,

the plurality of inverse redundancy generators being executable by the plurality of processors in parallel and during execution applying the inverse redundancy operation to a portion of the plurality of shreds and outputting the portions of the data stored in each shred without the at least one redundant part, the portion of the plurality of shreds being fewer than all of the plurality of shreds, the outputted portions of the data stored in the portion of the plurality of shreds comprising the data,

the first plurality of inverse transformers being executable by the plurality of processors in parallel and during execution applying the at least one inverse transformation to the portions of the data stored in the portion of the plurality of shreds, and

the deallocator being configured to apply the inverse allocation operation to the portions of the data stored in the portion of the plurality of shreds.

25. A system for use with data, the system comprising:

a storage location;

a shredder in communication with the storage location and comprising a first plurality of logic circuits interconnected by one or more buses, a first portion of the first plurality of logic circuits being configured to implement an allocator, a second portion of the first plurality of logic circuits being configured to implement a plurality of transformers, a third portion of the first plurality of logic circuits being configured to implement a plurality of redundancy generators and a tag generator,

the allocator performing an allocation operation allocating the data into a selected number of portions, the selected number being greater than one, and

the plurality of transformers applying at least one transformation to the data,

the plurality of redundancy generators applying a redundancy operation to the data to add redundancy to the data and storing the data in the storage location as a plurality of shreds, each shred storing a portion of the data,

the tag generator being configured to generate a tag for each of the plurality of shreds, the tag comprising information identifying the allocation operation, the at least one transformation, and the redundancy operation applied to the portion of the data stored in the shred and a shred order in which the allocation operation, the at least one transformation, and the redundancy operation were applied to the portion of the data stored in the shred; and

a deshredder in communication with the storage location and comprising a second plurality of logic circuits interconnected by one or more buses, a first portion of the second plurality of logic circuits being configured to implement a tag reader and a plurality of inverse redundancy generators, a second portion of the second plurality of logic circuits being configured to implement a first plurality of inverse transformers, and a third portion of the second plurality of logic circuits being configured to implement a deallocator,

for each of at least a portion the plurality of shreds, the tag reader being configured to read the tag generated for the shred, identify the allocation operation, the at least one transformation, and the redundancy operation applied to the portion of the data stored in the shred and identify the shred order in which the allocation operation, the at least one transformation, and the redundancy operation were applied to the portion of the data stored in the shred, the tag reader being further configured to identify an inverse allocation operation inverse to the allocation operation applied to the portion of the data stored in the shred, at least one inverse transformation inverse to the at least one transformation applied to the portion of the data stored in the shred, and an inverse redundancy operation inverse to the redundancy operation applied to the portion of the data stored in the shred,

the plurality of inverse redundancy generators applying the inverse redundancy operation to a portion of the plurality of shreds and outputting the portions of the data stored in each shred without the redundancy, the portion of the plurality of shreds being fewer than all of the plurality of shreds, the outputted portions of the data stored in the portion of the plurality of shreds comprising the data,

the first plurality of inverse transformers applying the at least one inverse transformation to the portions of the data stored in the portion of the plurality of shreds; and

the deallocator being configured to apply the inverse allocation operation to the portions of the data stored in the portion of the plurality of shreds.