# US 8,543,555 B2 · Dictionary for data deduplication

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,543,555 B2
- Document ID: US8543555B2
- Status: Granted
- Kind: B2
- Application number: 13/436,388
- Filed: 2012-03-30
- Published: 2012-07-26
- Granted: 2013-09-24
- Earliest claimed: 2009-09-11
- Assignees: Dell Products L.P.
- Applicants: Vinod Jayaraman
- Inventors: Vinod Jayaraman
- Web page: https://patentgrep.com/patent/US8543555B2

## CPC

- 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)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 3)

The method of claim 3, wherein the second hash value generated is included in the metadata for the segment.

### Claim 5 (depends on 1)

The method of claim 1, wherein the first hash value is compared to a plurality of weak hash values maintained in the deduplication dictionary.

### Claim 6 (depends on 5)

The method of claim 5, wherein metadata from the segment entry corresponding to the weak hash value is accessed.

### Claim 7 (depends on 1)

The method of claim 1, wherein deduplicated data corresponding to the segment entry is maintained in a suitcase location.

### Claim 8 (depends on 1)

The method of claim 1, wherein the first hash value is maintained using fewer bits than the second hash value.

### Claim 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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 9)

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.

### Claim 12 (depends on 11)

The system of claim 11, wherein the second hash value generated is included in the metadata for the segment.

### Claim 13 (depends on 9)

The system of claim 9, wherein the first hash value is compared to a plurality of weak hash values maintained in the deduplication dictionary.

### Claim 14 (depends on 13)

The system of claim 13, wherein metadata from the segment entry corresponding to the weak hash value is accessed.

### Claim 15 (depends on 9)

The system of claim 9, wherein deduplicated data corresponding to the segment entry is maintained in a suitcase location.

### Claim 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.