# US 2021/0064581 A1 · Small in-memory cache to speed up chunk store operation for deduplication

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

- Number: US 2021/0064581 A1
- Document ID: US20210064581A1
- Status: Published application
- Kind: A1
- Application number: 16/552,976
- Filed: 2019-08-27
- Published: 2021-03-04
- Earliest claimed: 2019-08-27
- Assignees: VMware, Inc.
- Applicants: VMware, Inc.
- Inventors: Wenguang WANG; Junlong GAO; Marcos K. AGUILERA; Richard P. SPILLANE; Christos KARAMANOLIS; Maxime AUSTRUY
- Web page: https://patentgrep.com/patent/US20210064581A1

## CPC

- G06F 16/1752: {based on file chunks}
- G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)}
- G06F 16/172: Caching, prefetching or hoarding of files
- G06F 9/45558: {Hypervisor-specific management and integration aspects}
- G06F 2009/45579: {I/O management, e.g. providing access to device drivers or storage}
- G06F 2009/45583: {Memory management, e.g. access or allocation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present disclosure provides techniques for deduplicating files. The techniques include creating a cache or subset of a large data structure. The large data structure organizes information by random hash values. The random hash values result in a random organization of information within the data structure, with the information spanning a large number of storage blocks within a storage system. The cache, however, is within memory and is small relative to the data structure. The cache is created so as to contain information that is likely to be needed during deduplication of a file. Having needed information within memory rather than in storage results in faster read and write operations to that information, improving the performance of a computing system.

## Claims

### Claim 1

A method of deduplicating a file, the file comprising a first chunk, the method comprising:
determining if a hash of a content of the first chunk is in a cache of a chunk hash data structure, wherein the chunk hash data structure comprises a first plurality of key-value mappings between a first plurality of keys and first plurality of values, the first plurality of keys each being a hash of a content of a corresponding chunk, and the first plurality of values each being a chunk ID of the corresponding chunk; and
if the hash is not in the cache:
determining a chunk ID of the first chunk;
determining a plurality of chunk IDs that are subsequent and contiguous to the chunk ID;
for each chunk ID of the plurality of chunk IDs, obtaining a set of information corresponding to the chunk ID of the plurality of chunk IDs based on a chunk ID data structure, wherein the chunk ID data structure comprises a second plurality of key-value mappings between a second plurality of keys and a second plurality of values, the second plurality of keys being the chunk IDs of the chunk hash data structure, and the second plurality of values each being a corresponding set of information about the corresponding chunk, wherein each set of information comprises the hash of the content of the corresponding chunk;
generating first plurality of key-value mappings for each of the plurality of chunk IDs using the obtained sets of information; and
storing the generated first plurality of key-value mappings as entries in the cache.

### Claim 2 (depends on 1)

The method of claim 1, wherein the determining the chunk ID of the first chunk is performed by accessing the chunk hash data structure.

### Claim 3 (depends on 1)

The method of claim 1, wherein at least a portion of the sets of information of the chunk ID data structure are stored in order of corresponding chunk IDs in a storage block of a storage, wherein the storage block is cached in a second cache, and wherein obtaining the sets of information corresponding to the chunk IDs of the plurality of chunk IDs comprises obtaining the portion of the sets of information from the second cache.

### Claim 4 (depends on 1)

The method of claim 1, further comprising, if the hash is not in the cache:
determining if the hash is in the chunk hash data structure; and
if the hash is in the chunk hash data structure:
determining a first set of information of a second chunk by mapping the chunk ID to the first set of information using the chunk ID data structure, the first set of information including a pointer to content of the second chunk; and
modifying a pointer in a first file corresponding to the first chunk to point to the content of the second chunk.

### Claim 5 (depends on 1)

The method of claim 1, further comprising, if the hash is in the cache:
determining, from the cache, the chunk ID of the first chunk;
reading, from the chunk ID data structure, a first set of information of a second chunk by mapping the chunk ID to the first set of information using the chunk ID data structure, the first set of information including a pointer to content of the second chunk; and
modifying a pointer in a first file corresponding to the first chunk to point to the content of the second chunk.

### Claim 6 (depends on 1)

The method of claim 1, wherein each set of information comprises the corresponding hash of the corresponding chunk, and at least one of: (a) a pointer to the content of the corresponding chunk, or (b) a reference count of the corresponding chunk.

### Claim 7 (depends on 1)

The method of claim 1, wherein the chunk hash data structure is stored in storage with entries in order of the first plurality of keys.

### Claim 8

A non-transitory computer readable medium comprising instructions to be executed in a processor of a computer system, the instructions when executed in the processor cause the computer system to carry out a method of deduplicating a file, the file comprising a first chunk, the method comprising:
determining if a hash of a content of the first chunk is in a cache of a chunk hash data structure, wherein the chunk hash data structure comprises a first plurality of key-value mappings between a first plurality of keys and first plurality of values, the first plurality of keys each being a hash of a content of a corresponding chunk, and the first plurality of values each being a chunk ID of the corresponding chunk; and
if the hash is not in the cache:
determining a chunk ID of the first chunk;
determining a plurality of chunk IDs that are subsequent and contiguous to the chunk ID;
for each chunk ID of the plurality of chunk IDs, obtaining a set of information corresponding to the chunk ID of the plurality of chunk IDs based on a chunk ID data structure, wherein the chunk ID data structure comprises a second plurality of key-value mappings between a second plurality of keys and a second plurality of values, the second plurality of keys being the chunk IDs of the chunk hash data structure, and the second plurality of values each being a corresponding set of information about the corresponding chunk, wherein each set of information comprises the hash of the content of the corresponding chunk;
generating first plurality of key-value mappings for each of the plurality of chunk IDs using the obtained sets of information; and
storing the generated first plurality of key-value mappings as entries in the cache.

### Claim 9 (depends on 8)

The non-transitory computer readable medium of claim 8, wherein the determining the chunk ID of the first chunk is performed by accessing the chunk hash data structure.

### Claim 10 (depends on 8)

The non-transitory computer readable medium of claim 8, wherein at least a portion of the sets of information of the chunk ID data structure are stored in order of corresponding chunk IDs in a storage block of a storage, wherein the storage block is cached in a second cache, and wherein obtaining the sets of information corresponding to the chunk IDs of the plurality of chunk IDs comprises obtaining the portion of the sets of information from the second cache.

### Claim 11 (depends on 8)

The non-transitory computer readable medium of claim 8, the method further comprising, if the hash is not in the cache:
determining if the hash is in the chunk hash data structure; and
if the hash is in the chunk hash data structure:
determining a first set of information of a second chunk by mapping the chunk ID to the first set of information using the chunk ID data structure, the first set of information including a pointer to content of the second chunk; and
modifying a pointer in a first file corresponding to the first chunk to point to the content of the second chunk.

### Claim 12 (depends on 8)

The non-transitory computer readable medium of claim 8, the method further comprising, if the hash is in the cache:
determining, from the cache, the chunk ID of the first chunk;
reading, from the chunk ID data structure, a first set of information of a second chunk by mapping the chunk ID to the first set of information using the chunk ID data structure, the first set of information including a pointer to content of the second chunk; and
modifying a pointer in a first file corresponding to the first chunk to point to the content of the second chunk.

### Claim 13 (depends on 8)

The non-transitory computer readable medium of claim 8, wherein each set of information comprises the corresponding hash of the corresponding chunk, and at least one of: (a) a pointer to the content of the corresponding chunk, or (b) a reference count of the corresponding chunk.

### Claim 14 (depends on 8)

The non-transitory computer readable medium of claim 8, wherein the chunk hash data structure is stored in storage with entries in order of the first plurality of keys.

### Claim 15

A computer system comprising:
a file;
a chunk hash data structure;
a chunk ID data structure; and
at least one processor, wherein the at least one processor is programmed to carry out a method of deduplicating the file, the file comprising a first chunk, the method comprising:
determining if a hash of a content of the first chunk is in a cache of the chunk hash data structure, wherein the chunk hash data structure comprises a first plurality of key-value mappings between a first plurality of keys and first plurality of values, the first plurality of keys each being a hash of a content of a corresponding chunk, and the first plurality of values each being a chunk ID of the corresponding chunk; and
if the hash is not in the cache:
determining a chunk ID of the first chunk;
determining a plurality of chunk IDs that are subsequent and contiguous to the chunk ID;
for each chunk ID of the plurality of chunk IDs, obtaining a set of information corresponding to the chunk ID of the plurality of chunk IDs based on the chunk ID data structure, wherein the chunk ID data structure comprises a second plurality of key-value mappings between a second plurality of keys and a second plurality of values, the second plurality of keys being the chunk IDs of the chunk hash data structure, and the second plurality of values each being a corresponding set of information about the corresponding chunk, wherein each set of information comprises the hash of the content of the corresponding chunk;
generating first plurality of key-value mappings for each of the plurality of chunk IDs using the obtained sets of information; and
storing the generated first plurality of key-value mappings as entries in the cache.

### Claim 16 (depends on 15)

The computer system of claim 15, wherein the determining the chunk ID of the first chunk is performed by accessing the chunk hash data structure.

### Claim 17 (depends on 15)

The computer system of claim 15, wherein at least a portion of the sets of information of the chunk ID data structure are stored in order of corresponding chunk IDs in a storage block of a storage, wherein the storage block is cached in a second cache, and wherein obtaining the sets of information corresponding to the chunk IDs of the plurality of chunk IDs comprises obtaining the portion of the sets of information from the second cache.

### Claim 18 (depends on 15)

The computer system of claim 15, the method further comprising, if the hash is not in the cache:
determining if the hash is in the chunk hash data structure; and
if the hash is in the chunk hash data structure:
determining a first set of information of a second chunk by mapping the chunk ID to the first set of information using the chunk ID data structure, the first set of information including a pointer to content of the second chunk; and
modifying a pointer in a first file corresponding to the first chunk to point to the content of the second chunk.

### Claim 19 (depends on 15)

The computer system of claim 15, the method further comprising, if the hash is in the cache:
determining, from the cache, the chunk ID of the first chunk;
reading, from the chunk ID data structure, a first set of information of a second chunk by mapping the chunk ID to the first set of information using the chunk ID data structure, the first set of information including a pointer to content of the second chunk; and
modifying a pointer in a first file corresponding to the first chunk to point to the content of the second chunk.

### Claim 20 (depends on 15)

The computer system of claim 15, wherein each set of information comprises the corresponding hash of the corresponding chunk, and at least one of: (a) a pointer to the content of the corresponding chunk, or (b) a reference count of the corresponding chunk.
