System and method for real-time deduplication utilizing an electronic storage medium

• US 8,281,066 B1
• Filed: 04/05/2010
• Issued: 10/02/2012
• Est. Priority Date: 04/30/2009
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Trimmer, Don, Miller, Steven C.
• Primary Examiner(s): SCHNEE, HAL W
• Application Number:
  US12/754,162
• Time in Patent Office: 911 Days
• Field of Search: 711/103, 711/154, 711/161, 711/E12.008, 711/E12.01, 711/E12.103
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• 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/0689 Disk arrays, e.g. RAID, JBOD

Abstract

The present invention provides a system and method for eliminating duplicate data (de-duplication) in substantially real time using an electronic storage medium.

Claims

1. A method comprising:

chunking a data set, received at a storage system, into at least one block;

generating a signature of one of the at least one blocks;

determining if the generated signature is stored in a signature database in an electronic storage medium of the storage system;

in response to determining that the generated signature is stored in the signature database, replacing the block associated with the generated signature with a pointer to a previously stored block associated with the signature stored in the signature database;

setting one of a lowest and a highest clear bit in a bit field associated with a counter in a block reference counter file stored in the electronic storage medium to indicate that an additional reference to the block has been made; and

setting one of a lowest and a highest clear bit in the bit field to indicate that a reference to the block has been deleted, whereby deduplication of the data set occurs in real time.

2. The method of claim 1 further comprising:

determining if additional blocks are to be processed; and

in response to determining that additional blocks are to be processed looping back to generating the signature.

3. The method of claim 1 wherein generating a signature of one of the at least one blocks comprises performing a hash function on the block.

4. The method of claim 1 wherein chunking the data set into at least one block comprises generating one or more fixed size blocks.

5. The method of claim 1 wherein the electronic storage medium comprises non-volatile random access memory.

6. The method of claim 1 wherein chunking, generating, determining, replacing, and incrementing are performed as the data set is entering the storage system in substantially real time.

7. The method of claim 1 wherein the storage system is a virtual tape library system.

8. The method of claim 1 wherein the electronic storage medium comprises flash memory.

9. The method of claim 1 wherein, in response to determining that a last free bit of the bit field was set, performing a repack operation thereby obviating a need to rewrite a region of the electronic storage medium in response after each update to the bit field.

10. The method of claim 9 wherein the repack operation comprises:

reading all entries within the region of the electronic storage medium;

updating a counter for each of the read entries;

clearing the bit field for each of the read entries; and

writing each of the read entries to the region of the electronic storage medium.

11. A system for real time deduplication of a data stream comprising:

a network;

a storage system coupled to the network; and

a virtual tape library coupled to the network and configured to receive the data stream transmitted over the network from the storage system in accordance with a backup operation, the virtual tape library further configured to generate a signature for each block of the data stream and to determine whether the generated signature is stored in a signature database within an electronic storage medium of the virtual tape library;

wherein the signature database comprises a plurality of entries each of which is associated with one signature, each entry comprising a counter field and a bit field wherein the counter field is utilized to store a count of a number of references to a block associated with the signature associated with the entry and wherein one of a lowest and a highest clear bit of the bit field is set to record an increase to the number of references since a last repack operation and one of a lowest and a highest clear bit is set to record a decrease to the number of references since the last repack operation.

12. The system of claim 11 wherein the virtual tape library is further configured, in response to determining that the generated signature is stored in the signature database, to replace the block in the data stream with a pointer to a previously stored block having the same signature.

13. A method comprising:

in response to adding a reference to a previously stored block setting one of a lowest and a highest clear bit in a bit field of an entry associated with a signature for the previously stored block and in response to removing a reference to the previously stored blocksetting one of a lowest and a highest clear bit in the bit field of the entry associated with the signature for the previously stored block, the entry stored in a signature database in an electronic storage medium of the storage system;

determining whether a last clear bit in the bit field is set; and

in response to determining that the last clear bit in the bit field is set, performing a repack operation.

14. The method of claim 13 wherein the repack operation comprises:

reading all entries within a region of the electronic storage medium;

updating a counter for each of the read entries;

clearing a bit field for each of the read entries; and

writing each of the read entries within the region to the electronic storage medium.

15. A computer program product for real time data deduplication of a data set comprising:

computer code, configured for execution on a storage system, that chunks the data set into at least one block;

computer code, configured for execution on a storage system, that generates a signature of one of the at least one blocks;

computer code, configured for execution on a storage system, that determines if the generated signature is stored in a signature database in an electronic storage medium of the storage system;

computer code, configured for execution on a storage system, that, in response to determining that the generated signature is stored in the signature database, replaces the block associated with the generated signature with a pointer to a previously stored block associated with the signature stored in the signature database;

computer code that sets one of a lowest and a highest clear bit in a bit field associated with a counter in a block reference counter file to indicate that an additional reference to the block has been made;

computer code that sets one of a lowest and a highest clear bit in the bit field to indicate that a reference to the block has been deleted; and

a non-transitory computer readable medium that stores the computer codes.

16. The computer program product of claim 15 wherein the data set comprises a tape backup data stream.

17. The computer program product of claim 15 further comprising computer code, configured for execution on a storage system, that performs a repack operation.