SYSTEM AND METHOD FOR DATA DEDUPLICATION

• US 20100250896A1
• Filed: 03/30/2009
• Published: 09/30/2010
• Est. Priority Date: 03/30/2009
• Status: Active Grant

• Current Assignee: Exar Corporation (Maxlinear Incorporated)
• Original Assignee: Hifn, Inc. (Maxlinear Incorporated)
• Inventors: Matze, John Edward Gerard
• Granted Patent: US 8,205,065 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• 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/0674 Disk device

Abstract

A system for deduplicating data comprises a card operable to receive at least one data block and a processor on the card that generates a hash for each data block. The system further comprises a first module that determines a processing status for the hash and a second module that discards duplicate hashes and their data blocks and writes unique hashes and their data blocks to a computer readable medium. In one embodiment, the processor also compresses each data block using a compression algorithm.

Claims

1. A method for deduplication comprising:

receiving a block of data;

generating a hash value for the block of data;

determining if the hash value is unique;

discarding the hash value and the block of data if the hash value is not unique; and

writing the block of data to a disk if the hash value is unique.

2. The method of claim 1 wherein if the hash value is unique the data block is compressed before it is written to the disk.

3. A system for deduplicating data comprising:

a card operable to receive at least one data block;

a processor on the card that generates a hash for each data block;

a first module that determines a processing status for the hash;

a second module that discards duplicate hashes and their data blocks and writes unique hashes and their data blocks to a computer readable medium.

4. The system of claim 3 further comprising:

wherein the processor also compresses each data block using a compression algorithm.

5. A system for deduplicating data comprising:

a computer that includes a computer readable medium and general processor operating thereon;

a card, coupled to the computer, that includes a processor for performing hashing operations and hardware-assisted compression;

a virtual block device that is an interface with applications and that is operable to set a block size for deduplication;

a deduplication block manager that passes blocks to the processor and receives a hash for each block and a compressed block from the processor;

a truncated hash array that includes an index for each possible truncated hash value and a corresponding entry initially set to a default value wherein when a new hash is processed, the corresponding entry is modified to include a pointer to the new hash and block;

wherein the card

receives blocks from the deduplication block manager,

creates a hash value for each block of data using a hashing algorithm, and

compresses each block of data using a compression algorithm; and

wherein the deduplication block manager

receives the hash values and the compressed blocks from the card, and

creates a truncated hash corresponding to each hash value.

6. The system of claim 5 further comprising:

wherein the deduplication block manager looks up each truncated hash in the truncated hash array; and

wherein if the corresponding entry to the truncated hash is the default value then the virtual block device writes the compressed block to a computer readable medium and adds a pointer to the compressed block and hash value to the truncated hash array.

7. The system of claim 5 further comprising:

wherein the deduplication block manager looks up each truncated hash in the truncated hash array; and

wherein if the corresponding entry to the truncated hash includes a pointer to a processed hash value and compressed block then the deduplication block manager retrieves the processed hash value and checks whether the hash value corresponding to the truncated hash matches the processed hash value.

8. The system of claim 7 wherein if the hash value matches the processed hash value then the compressed block is discarded.

9. The system of claim 7 wherein if the hash value does not match the processed hash value then the deduplication block manager determines if there is are pointers to additional processed hash values and the additional processed hash values are compared with the hash value.

10. The system of claim 9 wherein if the hash value does not match any processed hash values then the virtual block device writes the compressed block to a computer readable medium and adds a pointer to the compressed block and hash value to the truncated hash array.