Dictionary for data deduplication
View Patent ↗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.
1. A method comprising:
generating a first hash value for a segment, wherein the first hash value is a weak hash value;
accessing a deduplication dictionary using the first hash value, wherein the first hash value comprises fewer bits than the segment;
identifying a segment entry corresponding to the first hash value;
generating a second hash value for the segment, wherein the second hash value is a strong hash value; and
comparing the second hash value for the segment with a stored second hash value maintained in deduplicated data corresponding to the segment entry.
2. The method of claim 1 , wherein if the second hash does match the stored second hash value, a reference count associated with the segment entry is incremented.
3. The method of claim 1 , wherein if the second hash value generated does not match the stored second hash value, the segment and the second hash value generated is added to a suitcase.
4. The method of claim 3 , wherein the second hash value generated is included in the metadata for the segment.
5. The method of claim 1 , wherein the first hash value is compared to a plurality of weak hash values maintained in the deduplication dictionary.
6. The method of claim 5 , wherein metadata from the segment entry corresponding to the weak hash value is accessed.
7. The method of claim 1 , wherein deduplicated data corresponding to the segment entry is maintained in a suitcase location.
8. The method of claim 1 , wherein the first hash value is maintained using fewer bits than the second hash value.
9. A system comprising:
an interface operable to receive a segment;
a processor operable to generate a first hash value and a second hash value for the segment, the first hash value comprising fewer bits than the segment, wherein the first hash value is a weak hash value;
storage operable to maintain a deduplication dictionary, wherein the deduplication dictionary is access using the first hash value for the segment to identify a segment entry corresponding to the first hash value;
wherein the second hash value for the segment is compared to a stored second hash value maintained in deduplicated data corresponding to the segment entry, wherein the second hash value is a strong hash value.
10. The system of claim 9 , wherein if the second hash does match the stored second hash value, a reference count associated with the segment entry is incremented.
11. The system of claim 9 , wherein if the second hash value generated does not match the stored second hash value, the segment and the second hash value generated is added to a suitcase.
12. The system of claim 11 , wherein the second hash value generated is included in the metadata for the segment.
13. The system of claim 9 , wherein the first hash value is compared to a plurality of weak hash values maintained in the deduplication dictionary.
14. The system of claim 13 , wherein metadata from the segment entry corresponding to the weak hash value is accessed.
15. The system of claim 9 , wherein deduplicated data corresponding to the segment entry is maintained in a suitcase location.
16. A non-transitory computer readable medium comprising:
computer code for generating a first hash value for a segment, the first hash value comprising fewer bits than the segment, wherein the first hash value is a weak hash value;
computer code for accessing a deduplication dictionary using the first hash value for the segment;
computer code for identifying a segment entry corresponding to the first hash value for the segment;
computer code for generating a second hash value for the segment, wherein the second hash value is a strong hash value; and
computer code for comparing the second hash value for the segment with a stored second hash value maintained in deduplicated data corresponding to the segment entry.