DICTIONARY FOR DATA DEDUPLICATION

• US 20110066628A1
• Filed: 08/17/2010
• Published: 03/17/2011
• Est. Priority Date: 09/11/2009
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Ocarina Networks, Inc. (Dell Technologies Inc.)
• Inventors: Jayaraman, Vinod
• Granted Patent: US 8,200,641 B2
• Time in Patent Office: Days
• US Class Current: 707/758
• 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

Abstract

Mechanisms are provided for efficiently improving a dictionary used for data deduplication. Dictionaries are used to hold hash key and location pairs for deduplicated data. Strong hash keys prevent collisions but weak hash keys are more computation and storage efficient. Mechanisms are provided to use both a weak hash key and a strong hash key. Weak hash keys and corresponding location pairs are stored in an improved dictionary while strong hash keys are maintained with the deduplicated data itself. The need for having uniqueness from a strong hash function is balanced with the deduplication dictionary space savings from a weak hash function.

Claims

1. A method, comprising:

identifying a segment in a file for deduplication;

generating a strong a strong hash value and a weak hash value for the segment;

comparing the weak hash value to a plurality of weak hash values maintained in a deduplication dictionary;

reading metadata from a segment entry corresponding to the weak hash value;

comparing the strong hash value to a stored strong hash value maintained in the segment entry.

2. The method of claim 1, wherein if the strong hash value generated matches the strong hash value maintained in the segment entry, the reference count of the segment is incremented.

3. The method of claim 2, wherein if there are matches for the weak hash value and the strong hash value, the location of the segment entry is returned.

4. The method of claim 3, wherein the location of the segment entry is a suitcase location.

5. The method of claim 3, wherein the weak hash function is maintained using fewer bits than the strong hash function.

6. The method of claim 1, wherein if the strong hash value generated does not match the strong hash value maintained in the segment entry, the segment and the strong hash value generated is added to a suitcase.

7. The method of claim 6, wherein metadata for the segment is also added to the suitcase.

8. The method of claim 7, wherein the strong hash value generated is included in the metadata for the segment.

9. The method of claim 7, wherein metadata includes a last access time.

10. The method of claim 7, wherein metadata includes ownership and group association information.

11. A system, comprising:

an interface configured to receive a segment in a file for deduplication;

a processor configured to generate a strong a strong hash value and a weak hash value for the segment and compare the weak hash value to a plurality of weak hash values maintained in a deduplication dictionary;

wherein metadata from a segment entry corresponding to the weak hash value is read and the strong hash value is compared to a stored strong hash value maintained in the segment entry.

12. The system of claim 11, wherein if the strong hash value generated matches the strong hash value maintained in the segment entry, the reference count of the segment is incremented.

13. The system of claim 12, wherein if there are matches for the weak hash value and the strong hash value, the location of the segment entry is returned.

14. The system of claim 13, wherein the location of the segment entry is a suitcase location.

15. The system of claim 13, wherein the weak hash function is maintained using fewer bits than the strong hash function.

16. The system of claim 11, wherein if the strong hash value generated does not match the strong hash value maintained in the segment entry, the segment and the strong hash value generated is added to a suitcase.

17. The system of claim 16, wherein metadata for the segment is also added to the suitcase.

18. The system of claim 17, wherein the strong hash value generated is included in the metadata for the segment.

19. The system of claim 17, wherein metadata includes a last access time.

20. A computer readable storage medium having computer code embodied therein, the computer readable storage medium, comprising:

computer code for identifying a segment in a file for deduplication;

computer code for generating a strong a strong hash value and a weak hash value for the segment;

computer code for comparing the weak hash value to a plurality of weak hash values maintained in a deduplication dictionary;

computer code for reading metadata from a segment entry corresponding to the weak hash value;

computer code for comparing the strong hash value to a stored strong hash value maintained in the segment entry.