Dictionary for data deduplication
AssigneeDell Products L.P.
InventorVinod Jayaraman
Life of this patent
Estimating the term…
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.
Claims16
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.
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.
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.
Dependencies are inferred from the claim text.