SYSTEM AND METHOD FOR DATA DEDUPLICATION FOR DISK STORAGE SUBSYSTEMS

• US 20120016845A1
• Filed: 07/14/2011
• Published: 01/19/2012
• Est. Priority Date: 07/16/2010
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: TwinStrata, Inc. (Dell Technologies Inc.)
• Inventors: BATES, JOHN W.
• Granted Patent: US 9,678,688 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets

Abstract

A method for data deduplication includes the following steps. First, segmenting an original data set into a plurality of data segments. Next, transforming the data in each data segment into a transformed data representation that has a band-type structure for each data segment. The band-type structure includes a plurality of bands. Next, selecting a first set of bands, grouping them together and storing them with the original data set. The first set of bands includes non-identical transformed data for each data segment. Next, selecting a second set of bands and grouping them together. The second set of bands includes identical transformed data for each data segment. Next, applying a hash function onto the transformed data of the second set of bands and thereby generating transformed data segments indexed by hash function indices. Finally, storing the hash function indices and the transformed data representation of one representative data segment in a deduplication database.

Claims

1. A method for data deduplication comprising:

segmenting an original data set into a plurality of data segments;

transforming the data in each data segment into a transformed data representation that comprises a band-type structure for each data segment, wherein said band-type structure comprises a plurality of bands;

selecting a first set of bands, grouping them together and storing them with the original data set, wherein said first set of bands comprises non-identical transformed data for each data segment;

selecting a second set of bands and grouping them together, wherein said second set of bands comprises identical transformed data for each data segment;

applying a hash function onto the transformed data of the second set of bands and thereby generating transformed data segments indexed by hash function indices;

storing the hash function indices and the transformed data representation of one representative data segment in a deduplication database.

2. The method of claim 1 further comprising storing the hash function indices with the original data set.

3. The method of claim 1, wherein each data segment is transformed into a transform data representation via a Haar transform.

4. The method of claim 3, wherein said Haar transform comprises one of a basic integer Haar transform or a packet transform.

5. The method of claim 1, wherein each data segment is transformed into a transform data representation via a wavelet transform.

6. The method of claim 5, wherein said wavelet transform comprise one of Haar transform, a Daubechies 5/3 transform or algorithmic variations thereof.

7. The method of claim 1 wherein said original data set comprises one of text, image, audio, financial data, or application binaries.

8. A method for data deduplication comprising:

segmenting an original data set into a plurality of data segments;

transforming the data in each data segment into a transformed data representation;

removing one or more data from the transformed data representations of each data segment, wherein said removed data comprise non-identical data, and thereby resulting with identical remaining transformed data representations for each data segment;

applying a hash function onto the remaining identical transformed data representations and thereby generating transformed data representations indexed by hash function indices;

for each of the transformed data segments with the identical transformed data representations, storing the hash function indices and the transformed data representation of one representative data segment in a deduplication database.

9. The method of claim 8, further comprising storing the one or more removed data from the transformed data representations for each data segment in a database with the original set of data.

10. The method of claim 9 further comprising storing the hash function indices in the database with the original set of data.

11. The method of claim 8, wherein said identical remaining transformed data representations for each data segment comprise structurally identical data representations for each data segment.

12. A system for data deduplication comprising:

a deduplication engine comprising means for segmenting an original data set into a plurality of data segments, means for transforming the data in each data segment into a transformed data representation, means for removing one or more data from the transformed data representations of each data segment, wherein said removed data comprise non-identical data and thereby resulting with identical remaining transformed data representations for each data segment, means for applying a hash function onto the remaining identical transformed data representations and thereby generating transformed data representations indexed by hash function indices, and means for storing the hash function indices and the transformed data representation of one representative data segment in a deduplication database, for each of the transformed data segments with the identical transformed data representations.

13. The system of claim 12, wherein said deduplication engine further comprises means for storing the one or more removed data from the transformed data representations for each data segment in a database with the original set of data and means for storing the hash function indices in the database with the original set of data.

14. The system of claim 12, wherein said original data set comprises one of text, image, audio, financial data, or application binaries.

15. A system for data deduplication comprising:

a deduplication engine comprising means for segmenting an original data set into a plurality of data segments, means for transforming the data in each data segment into a transformed data representation that comprises a band-type data structure, wherein said band-type structure comprises a plurality of bands, means for selecting a first set of bands, grouping them together and storing them with the original data set, wherein said first set of bands comprise non-identical transformed data for each data segment, means for selecting a second set of bands and grouping them together, wherein said second set of bands comprise identical transformed data for each data segment, means for applying a hash function onto the transformed data of the second set of bands and thereby generating transformed data segments indexed by hash function indices, and means for storing the hash function indices and the transformed data representation of one representative data segment in a deduplication database.

16. The system of claim 15, wherein said means for storing the hash function indices comprise one or more virtual storage appliances provided by a cloud storage system.

17. The system of claim 15, further comprising a cache and a local storage device and wherein said deduplication engine is located behind said cache and said local storage device.

18. The system of claim 15 further comprising one or more computing host systems and wherein said computing systems connect to said deduplication engine via an Internet Small Computer System Interface (iSCSI).

19. The system of claim 15 further comprising a bi-directional network connection between said deduplication engine and a cloud storage appliance.

20. The system of claim 15 further comprising a cloud layout module and a cloud provider application programming interface (API).