DATA STORAGE SYSTEM AND METHOD BY SHREDDING AND DESHREDDING

• US 20110173161A1
• Filed: 03/18/2011
• Published: 07/14/2011
• 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 8,805,792 B2
• Time in Patent Office: Days
• US Class Current: 707/687
• 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-3. -3. (canceled)

4. A system for use with data, the system comprising a storage unit, at least one processor coupled to the storage unit, and a memory comprising instructions executable by the at least one processor, when executed by the at least one processor, the instructions performing a shredding process and a deshredding process,

the shredding process comprising:

(a) a plurality of data operations performable on the data in a shred order to produce a plurality of shreds, the plurality of data operations comprising at least one transformation operation, and at least one redundancy operation;

(b) a tag generation process configured to generate a plurality of tags for the plurality of shreds, one or more tags being associated with each of the plurality of shreds, the tag generation process generating at least one tag after each data operation is performed on the data in accordance with the shred order, the at least one tag comprising information identifying the data operation performed, the shred order being determinable from the one or more tags associated with each of the plurality of shreds; and

(c) a storage operation configured to store the plurality of shreds and the plurality of tags in the storage unit,

the deshredding process comprising;

(a) a retrieval process configured to retrieve a portion of the plurality of shreds and the one or more tags associated with each of the portion of the plurality of shreds from the storage unit;

(b) a plurality of inverse data operations comprising for each of plurality of data operations of the shredding process, an operation that is an inverse of the data operation; and

(c) a tag reading process, for each of a portion of the plurality of shreds, the tag reading process being configured to;

read the one or more tags associated with the shred,

identify the plurality of data operations performed to produced the shred,

identify ones of the plurality of inverse data operations that are inverses of the plurality of data operations performed to produced the shred, and

execute each of the ones of plurality of inverse data operations identified as being inverses of the plurality of data operations performed to produced the shred in accordance with a deshred order to recover the data from the portion of the plurality of shreds, the deshred order being an inverse of the shred order.

5. The system of claim 4, wherein the plurality of data operations of the shredding process further comprises an allocation operation configured to allocate the data into portions, and

the plurality of inverse data operations of the deshredding process further comprises a deallocation operation that is an inverse of the allocation operation.

6. The system of claim 4, wherein the tag generation process is further configured to insert the one or more tags associated with each of the plurality of shreds into the shred.

7. The system of claim 4, wherein the tag generation process is further configured to add the at least one tag to the data after the at least one tag is generated so that any subsequent data operations performed on the data are also performed on the at least one tag.

8. The system of claim 7, wherein for at least one of the portion of the plurality of shreds, until all of the one or more tags associated with the shred have been read by the tag reading process, the tag reading process:

reads a next tag of the one or more tags associated with the shred,

reads the information identifying a next data operation contained in the next tag,

identifies a next inverse data operation of the plurality of inverse data operations that is an inverse of the next of data operation,

executes the next inverse data operation, and

after executing the next inverse data operation, identifies a different tag of the one or more tags associated with the shred as the next tag.

9. The system of claim 4, wherein the instructions are further configured to perform the shredding process more than once on the data before performing the deshredding process.

10. The system of claim 9, wherein the instructions are further configured to repeat the deshredding process multiple times to recover the data.

11. The system of claim 4, wherein the at least one transformation of the plurality of data operations of the shredding process comprises a compression transformation, and the plurality of inverse data operations of the deshredding process comprise a decompression transformation that is an inverse of the compression transformation.

12. The system of claim 4, wherein the at least one transformation of the plurality of data operations of the shredding process comprises an encryption transformation and, the plurality of inverse data operations of the deshredding process comprise a decryption operation that is an inverse of the encryption transformation.

13. The system of claim 4, wherein the plurality of data operations of the shredding process further comprise at least one signature transformation configured to generate a signature describing the data or a portion thereof, and the plurality of inverse data operations of the deshredding process further comprises an operation that decodes the signature and uses the signature to verify the data or a portion thereof.

14. The system of claim 4, wherein the storage unit comprises multiple available output units,

the plurality of data operations of the shredding process further comprise a partition operation configured to partition the plurality of shreds for storage on the multiple available output units, and

the plurality of inverse data operations of the deshredding process further comprises a repartition operation that is an inverse of the partition operation.

15. The system of claim 4, wherein the at least one redundancy operation of the plurality of data operations of the shredding process performs non-systematic encoding or systematic encoding.

16. A method comprising:

performing data operations on initial data to obtain a plurality of shreds, the data operations comprising a transformation operation and a redundancy operation;

generating at least one tag for each shred, the at least one tag comprising information identifying the data operations performed on the initial data, and indicating a shred order in which the data operations were performed;

storing the plurality of shreds on at least one storage unit;

selecting a portion of the plurality of shreds;

for at least one of the selection portion of the plurality of shreds, reading the at least one tag generated for the shred to identify an operation inverse to each of the data operations; and

performing the operations inverse to each of the data operations on the selected portion of the plurality of shreds in accordance with a deshred order to thereby recover the initial data, the deshred order being an inverse of the shred order.

17. The method of claim 16, wherein the selected portion of the plurality of shreds includes fewer than all of the plurality of shreds.

18. The method of claim 17, further comprising:

discarding ones of the plurality of shreds other than those in the selected portion of the plurality of shreds.

19. The method of claim 16, wherein performing the data operations on the initial data to obtain the plurality of shreds further comprises performing a first one of the data operations on the initial data to produce second data;

generating the at least one tag for each shred further comprises generating a first tag identifying the first one of the data operations performed on the initial data to produce the second data;

after the first tag is generated, performing the data operations on the initial data to obtain the plurality of shreds further comprises performing a second one of the data operations on the second data and the first tag; and

generating the at least one tag for each shred further comprises generating a second tag identifying the second one of the data operations, together the first tag and the second tag indicating the shred order in which the data operations were performed.

20. The method of claim 16, wherein performing the data operations on the initial data to obtain the plurality of shreds further comprises performing the transformation operation on the initial data to produce transformed data;

generating the at least one tag for each shred further comprises generating a first tag identifying the transformation operation;

after the first tag is generated, performing the data operations on the initial data to obtain the plurality of shreds further comprises performing the redundancy operation on the transformed data and the first tag to obtain the plurality of shreds; and

generating the at least one tag for each shred further comprises generating a second tag for each of the plurality of shreds identifying the redundancy operation, together the first tag and each of the second tags indicating the shred order in which the transformation operation and the redundancy operation were performed.

21. The method of claim 16, wherein the transformation operation compresses or encrypts the initial data.

22. The method of claim 16, wherein the redundancy operation performs systematic or non-systematic encoding.

23. A method comprising:

performing each of a series of data operations to produce resulting data for each of the series of data operations, the plurality of data operations comprising a first data operation performed on initial data, and a last data operation performed after the first data operation, the resulting data of the last data operation being a plurality of shreds, the series of data operations comprising at least a transformation operation and a redundancy operation;

after each of the series of data operations is performed, generating at least one tag and adding the at least one tag to the resulting data obtained from the performance of the data operation such that successive ones in the series of data operations, if any, are performed on both the at least one tag and the resulting data obtained from the performance of the data operation, the at least one tag comprising information identifying the data operation;

storing the plurality of shreds and the at least one tag generated after the last data operation is performed on at least one storage unit;

selecting a portion of the plurality of shreds stored on the at least one storage unit;

reading the at least one tag generated after the last data operation was performed, and identifying an operation inverse to the last data operation;

performing the operation inverse to the last data operation on the selected portion of the plurality of shreds to obtain the resulting data of the data operation performed before the last data operation and the at least one tag generated after that data operation was performed, the data operation performed before the last data operation being a previous data operation, the at least one tag generated after the previous data operation being at least one previously generated tag, and the resulting data of the previous data operation being previous resulting data; and

until an operation inverse to the first data operation has been performed;

reading the at least one previously generated tag;

identifying an operation inverse to the previous data operation;

performing the operation inverse to the previous data operation on the previous resulting data, if the previous data operation is the first data operation, performing the operation inverse to the previous data operation on the previous resulting data yielding the initial data,

otherwise, if the previous data operation is not the first data operation, the data operation performed before the previous data operation being redefined as the previous data operation, the at least one tag generated after the redefined previous data operation being redefined as the at least one previously generated tag, and the resulting data of the redefined previous data operation being redefined as the previous resulting data.

24. The method of claim 23, wherein the redundancy operation performs systematic or non-systematic encoding.

25. A computer-readable medium comprising instructions executable by at least one processor and when executed by the at least one processor instruct the at least one processor to:

perform data operations on initial data to obtain a plurality of shreds, the data operations comprising a transformation operation and a redundancy operation;

generate at least one tag for each shred, the at least one tag comprising information identifying the data operations performed on the initial data, and indicating a shred order in which the data operations were performed;

store the plurality of shreds on at least one storage unit;

select a portion of the plurality of shreds;

for at least one of the selection portion of the plurality of shreds, read the at least one tag generated for the shred to identify an operation inverse to each of the data operations; and

perform the operations inverse to each of the data operations on the selected portion of the plurality of shreds in accordance with a deshred order to thereby recover the initial data, the deshred order being an inverse of the shred order.

26. The computer-readable medium of claim 25, wherein the redundancy operation performs systematic or non-systematic encoding.

27. A system for use with data, the system comprising at least one storage unit;

a plurality of processors coupled to the at least one storage unit; and

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 and a deshredder, the customizable shredder including at least one transformer, at least one redundancy generator, and a tag generator, the deshredder including a tag reader, at least one inverse redundancy generator, and at least one inverse transformer,

the at least one transformer of the customizable shredder being executable by the plurality of processors in parallel and during execution performing at least one transformation on the data,

the at least one redundancy generator of the customizable shredder being executable by the plurality of processors in parallel and during execution performing at least one redundancy operation on the data, after the at least one transformation and the at least one redundancy operation have been performed on the data in a shred order, the data comprising a plurality of shreds, the data being recoverable from a portion of the plurality of shreds by performing at least one inverse transformation and at least one inverse redundancy operation on the portion of the plurality of shreds in a deshred order, the deshred order being an inverse of the shred order,

the tag generator of the customizable shredder being configured to generate at least one tag for each of the plurality of shreds, the at least one tag comprising information identifying the at least one transformation, the at least one redundancy operation, and the shred order, the customizable shredder being configured to store the plurality of shreds in the at least one storage unit,

for at least one of the portion of the plurality of shreds, the tag reader of the deshredder being configured to (a) read the at least one tag generated for the shred, (b) identify the at least one transformation and the at least one redundancy operation performed on the data to produce the shred, and (c) identify the shred order in which the at least one transformation and the at least one redundancy operation were performed on the data to produce the shred, the deshredder being configured to identify the at least one inverse transformation and the at least one inverse redundancy operation, and instruct the at least one inverse transformer to perform the at least one inverse transformation and the at least one inverse redundancy generator to perform the at least one inverse redundancy operation on the portion of the plurality of shreds in the deshred order to recover the data,

the at least one inverse redundancy generator being executable by the plurality of processors in parallel and during execution, performing the at least one inverse redundancy operation, and

the at least one inverse transformer being executable by the plurality of processors in parallel and during execution, performing the at least one inverse transformation.

28. The system of claim 27, wherein the at least one redundancy operation comprises systematic or non-systematic encoding.

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

at least one storage unit;

a shredder in communication with the at least one storage unit 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 at least one transformer, a second portion of the first plurality of logic circuits being configured to implement at least one redundancy generator, a third portion of the first plurality of logic circuits being configured to implement a tag generator,

the at least one transformer applying at least one transformation to the data,

the at least one redundancy generator applying at least one redundancy operation to the data, after the at least one transformation and the at least one redundancy operation have been performed on the data in a shred order, the data comprising a plurality of shreds, the data being recoverable from a portion of the plurality of shreds by performing at least one inverse transformation and at least one inverse redundancy operation on the portion of the plurality of shreds in a deshred order, the deshred order being an inverse of the shred order

the tag generator being configured to generate at least one tag for each of the plurality of shreds, the at least one tag comprising information identifying the at least one transformation, the at least one redundancy operation, and the shred order, the shredder being configured to store the plurality of shreds in the at least one storage unit; and

a deshredder in communication with the at least one storage unit, the deshredder 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, a second portion of the second plurality of logic circuits being configured to implement at least one inverse redundancy generator, and a third portion of the second plurality of logic circuits being configured to implement at least one inverse transformer,

for at least one of the portion the plurality of shreds, the tag reader being configured to (a) read the at least one tag generated for the shred, (b) identify the at least one transformation and the at least one redundancy operation performed on the data to produce the shred, (c) identify the shred order in which the at least one transformation and the at least one redundancy operation were performed on the data to produce the shred, (d) identify the at least one inverse transformation and the at least one inverse redundancy operation, and (e) instruct the at least one inverse transformer to perform the at least one inverse transformation and the at least one inverse redundancy generator to perform the at least one inverse redundancy operation on the portion of the plurality of shreds in the deshred order to recover the data,

the at least one inverse redundancy generator performing the inverse redundancy operation in response to receiving the instruction from the tag reader,

the at least one inverse transformer performing the at least one inverse transformation in response to receiving the instruction from the tag reader.

30. The system of claim 29, wherein the at least one redundancy operation comprises systematic or non-systematic encoding.