SYSTEM AND METHOD FOR ON-THE-FLY ELIMINATION OF REDUNDANT DATA

• US 20080294696A1
• Filed: 05/22/2007
• Published: 11/27/2008
• Est. Priority Date: 05/22/2007
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Frandzel, Yuval
• Granted Patent: US 8,315,984 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1752 based on file chunks
• 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

A system and method for “on-the-fly” de-duplication of data before storing the data in a storage system is provided. A data de-duplication module illustratively cooperates with protocol servers and a file system of a storage operating system executing on the storage system to implement the novel de-duplication technique. The de-duplication module illustratively generates a block store, an index file and a hash table on storage space provided by the storage system. The hash table is utilized for tracking fingerprints and locations of blocks within the block store. The index file is utilized for storing directory information identifying the contents of data containers stored on the storage system, while the block store is utilized to store raw data blocks that comprise the data containers.

Claims

1. A method for elimination of redundant data, the method comprising the steps of:

receiving a set of data;

partitioning the set of data into one or more blocks;

generating a fingerprint for each of the one or more blocks;

determining whether a previously stored block has a fingerprint one of the generated fingerprints;

in response to determining that a previously stored block has a matching fingerprint, identifying a location of the previously stored block in a block store and updating indexing information with the location information of the block; and

in response to determining that there is not a previously stored block having a matching fingerprint, storing the identified block in the block store and updating indexing information with a location of the stored block in the block store.

2. The method of claim 1 wherein the step of partitioning is performed based on a predetermined block size.

3. The method of claim 1 wherein the step of partitioning comprises the step of generating variable length blocks.

4. The method of claim 1 wherein the step of generating a fingerprint comprises the step of generating a Robin-Karp fingerprint.

5. The method of claim 1 wherein the step of determining further comprises the step of examining a hash table to identify whether a previously stored block having a fingerprint matching one of the generated fingerprints.

6. The method of claim 5 wherein the hash table comprises of a plurality of entries, each entry comprising a fingerprint field, a location field and a length field.

7. The method of claim 6 wherein the location field identifies an offset into the block store where an identified block is stored.

8. The method of claim 1 wherein the indexing information comprises an ordered list of location and lengths of blocks comprising a data container.

9. The method of claim 11 wherein each data container stored within it is associated.

10. The method of claim 1 further comprising the step of associating a data container entry with an index with each data container stored.

11. The method of claim 1 wherein the indexing information references a plurality of blocks in a single indexing entry in response to a plurality of blocks being contiguous in the block store.

12. A system for a limitation of redundant data, the system comprising:

a computer executing a data de-duplication module, the de-duplication module managing a block store, an index and a hash table; and

wherein the de-duplication module is configured to, in response to receiving a set of data, (i) partition the set of data into one or more blocks, (ii) generate a fingerprint for each of the one or more blocks and (iii) in response to determining that a block has not been previously stored within the block store, store the block within the block store.

13. The system of claim 12 wherein the de-duplication module is operatively interconnected with a file system.

14. The system of claim 13 wherein the file system provides storage space for the block store.

15. The system of claim 14 wherein the block store comprises a file in the file system.

16. The system of claim 12 wherein the de-duplication module is further configured to determine that the block has not been previously stored within the block store by examining the hash table.

17. The system of claim 16 wherein the hash table comprises information relating to a fingerprint of a block, a location of the block within the block store and a length of the block.

18. The system of claim 12 wherein the de-duplication module is further configured to update the index to associate the block with a data container.

19. The system of claim 18 wherein the index references a plurality of blocks in a single indexing entry in response to a plurality of blocks being contiguous in the block store.

20. The system of claim 12 wherein the set of data comprises write data directed to a data container stored on the computer.

21. A system for elimination of redundant data, the system comprising:

means for receiving a set of data;

means for partitioning the set of data into one or more blocks;

means for generating a fingerprint for each of the one or more blocks;

means for determining whether a previously stored block has a fingerprint matching one of the generated fingerprints;

in response to determining that a previously stored block has an identical fingerprint, identifying a location of the previously stored block in a block store and updating indexing information with the location information of the block; and

in response to determining that there is not a previously stored block having an identical fingerprint, means for storing the identified block in the block store and updating indexing information with a location of the stored block in the block store.

22. A computer readable medium for elimination of redundant data, the computer readable medium including instructions for performing the steps of:

receiving a set of data;

partitioning the set of data into one or more blocks;

generating a fingerprint for each of the one or more blocks;

determining whether a previously stored block has a fingerprint matching one of the generated fingerprints;

in response to determining that a previously stored block has an identical fingerprint, identifying a location of the previously stored block in a block store and updating indexing information with the location information of the block; and

in response to determining that there is not a previously stored block having an identical fingerprint, storing the identified block in the block store and updating indexing information with a location of the stored block in the block store.

23. The computer readable medium of claim 22 wherein the identified block is compressed prior to storing the identified block in the block store.