# US 2017/0255624 A1 · Two-stage front end for extent map database

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

- Number: US 2017/0255624 A1
- Document ID: US20170255624A1
- Status: Published application
- Kind: A1
- Application number: 15/601,388
- Filed: 2017-05-22
- Published: 2017-09-07
- Earliest claimed: 2014-12-03
- Assignees: NetApp, Inc.
- Applicants: NetApp, Inc.
- Inventors: Alok Sharma; Satbir Singh; Sudhanshu Gupta
- Web page: https://patentgrep.com/patent/US20170255624A1

## CPC

- G06F 16/2255: {Hash tables}
- G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)}
- 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 16/217: {Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409)}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0641: {De-duplication techniques}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Multiple key-value stores may be employed to smooth out random updates (based on the extent ID) to the EMAP database. The updates to the EMAP database occur in a two-stage manner: (i) using an append-only log store for the first stage and (ii) using an on-disk hash store for the second stage. The append-only log store is used to convert the random updates to sequential write operations on the EMAP database. Once full, the contents of the log store are sorted and moved to the on-disk hash store, which holds the updates for a transient period of time to enable batching of the updates. Once sufficient batching of the extent map entries are accumulated, those entries are sorted and moved to the EMAP database. Thereafter, the EMAP database can be scanned to find extent map entries having identical checksum bits to perform data deduplication.

## Claims

### Claim 1

A method comprising:
appending extent identifiers in a log until the log is full, wherein the extent identifiers identify extents of a storage system;
based on a determination that the log is full, sorting the extent identifiers and moving the extent identifiers as sorted into a hash store;
accumulating extent identifiers moved from the log in the hash store for a time period;
based on expiration of the time period,
sorting the extent identifiers accumulated in the hash store; and
after sorting, moving the extent identifiers accumulated in the hash store into a mapping structure, wherein the mapping structure maps extent identifiers to storage location identifiers of corresponding extents.

### Claim 2 (depends on 1)

The method of claim 1 further comprising prioritizing deduplication of extents in the storage system based on the mapping structure.

### Claim 3 (depends on 1)

The method of claim 1, wherein an extent identifier comprises a checksum generated from an extent and a counter, wherein the counter distinguishes matching checksums.

### Claim 4 (depends on 1)

The method of claim 1, wherein the log comprises a key-value store and the hash store comprises a key-value store, wherein the extent identifiers are the keys and storage location identifiers are the values.

### Claim 5 (depends on 1)

The method of claim 1, wherein the storage location identifiers are physical volume block numbers.

### Claim 6 (depends on 1)

The method of claim 1,
wherein appending extent identifiers in the log comprises appending extent entries into the log, wherein an extent entry comprises the extent identifier and a corresponding one of the storage location identifiers,
wherein accumulating extent identifiers from the log in the hash store comprises accumulating the extent entries from the log,
wherein sorting extent identifiers comprises sorting extent entries.

### Claim 7 (depends on 6)

The method of claim 6, wherein moving the extent identifier from the hash store to the mapping structure comprises:
for each of the extent entries from the hash store,
determining whether a node of the mapping structure already includes an extent entry with the checksum of the extent identifier of the extent entry from the hash store;
based on a determination that a node of the mapping structure already includes an extent entry with the checksum, inserting the extent entry from the hash store into the node and updating a score for the node based on a number of the extent entries in the node with the same checksum; and
based on a determination that a node of the mapping structure does not include an extent entry with the checksum, inserting the extent entry from the hash store into a node.

### Claim 8 (depends on 7)

The method of claim 7, wherein moving the extent identifiers to the mapping structure further comprises marking a dirty bit for a node based on a determination that the node already has an extent entry with a checksum matching the checksum of an extent entry being inserted into the node.

### Claim 9 (depends on 1)

The method of claim 1 further comprising searching the log or the hash store with a partial cuckoo hash of an extent based on a write operation to the storage system and performing deduplication based on finding a match.

### Claim 10

A non-transitory computer-readable medium comprising program code for smoothing random updates to an extent map database, the program comprising instructions to:
append extent identifiers in a first structure until the first structure is full, wherein the extent identifiers identify extents of a storage system;
based on a determination that the first structure is full, sort the extent identifiers and move the extent identifiers as sorted into a second structure;
accumulate extent identifiers moved from the log in the hash store for a time period;
based on expiration of the time period,
sort the extent identifiers accumulated in the second structure; and
update the extent map database with the extent identifiers from the second structure.

### Claim 11 (depends on 10)

The non-transitory computer-readable medium of claim 10, wherein the program code further comprises instructions to prioritize deduplication of extents in the storage system based on the extent map database.

### Claim 12 (depends on 10)

The non-transitory computer-readable medium of claim 10, wherein an extent identifier comprises a checksum generated from an extent and a counter, wherein the counter distinguishes matching checksums.

### Claim 13 (depends on 10)

The non-transitory computer-readable medium of claim 10, wherein the first structure comprises a key-value store and the structure comprises a key-value store, wherein the extent identifiers are the keys and storage location identifiers are the values.

### Claim 14 (depends on 10)

The non-transitory computer-readable medium of claim 10, wherein the storage location identifiers are physical volume block numbers.

### Claim 15 (depends on 10)

The non-transitory computer-readable medium of claim 10,
wherein the instructions to append extent identifiers in the first structure comprise instructions to append extent entries into the first structure, wherein an extent entry comprises the extent identifier and a corresponding storage location identifier,
wherein the instructions to accumulate extent identifiers from the first structure in the second structure comprise instructions to accumulate the extent entries from the first structure,
wherein the instructions to sort extent identifiers comprise instructions to sort the extent entries.

### Claim 16 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the instructions to update the extent map database comprise instructions to:
for each of the extent entries from the second structure,
determine whether a node of the extent map database already includes an extent entry with the checksum of the extent identifier of the extent entry from the second structure;
based on a determination that a node of the extent map database already includes an extent entry with the checksum, insert the extent entry from the second structure into the node and update a score for the node based on a number of the extent entries in the node with the same checksum; and
based on a determination that a node of the extent map database does not include an extent entry with the checksum, inserting the extent entry from the hash store into a node.

### Claim 17 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein the instructions to update the extent map database further comprise instructions to mark a dirty bit for a node based on a determination that the node already has an extent entry with a checksum matching the checksum of an extent entry being inserted into the node.

### Claim 18 (depends on 10)

The non-transitory computer-readable medium of claim 10, wherein the program code further comprises instructions to search the first structure or the second structure with a partial cuckoo hash of an extent based on a write operation to the storage system and to perform deduplication based on finding a match.

### Claim 19

An apparatus comprising:
a processor;
a computer-readable medium comprising instructions executable by the processor to cause the apparatus to,
append extent identifiers in a first structure until the first structure is full, wherein the extent identifiers identify extents of a storage system;
based on a determination that the first structure is full, sort the extent identifiers and move the extent identifiers as sorted into a second structure;
accumulate extent identifiers moved from the log in the hash store for a time period;
based on expiration of the time period,
sort the extent identifiers accumulated in the second structure; and
update the extent map database with the extent identifiers from the second structure.

### Claim 20 (depends on 19)

The apparatus of claim 19, wherein the computer-readable medium further comprises instructions executable by the processor to cause the apparatus to search the first structure or the second structure with a partial cuckoo hash of an extent based on a write operation to the storage system and to perform deduplication based on finding a match.
