# US 2021/0334206 A1 · Optimized Inline Deduplication

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

- Number: US 2021/0334206 A1
- Document ID: US20210334206A1
- Status: Published application
- Kind: A1
- Application number: 17/360,791
- Filed: 2021-06-28
- Published: 2021-10-28
- Earliest claimed: 2011-08-11
- Assignees: Pure Storage, Inc.
- Applicants: Pure Storage, Inc.
- Inventors: JOHN COLGROVE; JOHN HAYES; ETHAN MILLER; FENG WANG
- Web page: https://patentgrep.com/patent/US20210334206A1

## CPC

- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/061: {Improving I/O performance}
- G06F 3/0638: {Organizing or formatting or addressing of data}
- G06F 3/0641: {De-duplication techniques}
- G06F 3/0665: {at area level, e.g. provisioning of virtual or logical volumes}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 12/0802: Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F 12/0888: using selective caching, e.g. bypass
- G06F 12/1009: using page tables, e.g. page table structures
- G06F 2212/50: Control mechanisms for virtual memory, cache or TLB
- G06F 2212/7201: Logical to physical mapping or translation of blocks or pages
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods, computer systems, and computer readable medium are described. In a particular embodiment, a storage controller is configured to receive, from a host computing device, a request to perform a bulk array task and in response to receiving the request, store an indication relating old keys of a mapping table to new keys, wherein both the old keys and the new keys correspond to the request. The storage controller is also configured to convey a response indicating completing of the request without prior access of user data and update the mapping table to replace the old keys with the new keys.

## Claims

### Claim 1

A method comprising:
receiving a request to write data to a storage system;
generating, based on the request, a hash value associated with the request to write data;
determining whether the generated hash value matches an entry in a deduplication data structure; and
responsive to determining that the generated hash value matches an entry in a deduplication data structure, discarding the data and updating the entry in the deduplication data structure.

### Claim 2 (depends on 1)

The method of claim 1 further comprising:
responsive to determining that the generated hash value does not match an entry in a deduplication data structure:
writing the data to the storage system; and
adding an entry to the deduplication data structure that includes the generated hash value.

### Claim 3 (depends on 1)

The method of claim 1 wherein updating the entry in the deduplication data structure includes moving the entry to a highest level in the deduplication data structure.

### Claim 4 (depends on 2)

The method of claim 2 wherein the added entry to the deduplication data structure is included in a highest level in the deduplication data structure.

### Claim 5 (depends on 1)

The method of claim 1 wherein determining whether the generated hash value matches an entry in a deduplication data structure includes searching only a cached portion of the deduplication data structure, wherein the deduplication data structure also includes a non-cached portion that is not searched.

### Claim 6 (depends on 5)

The method of claim 5 further comprising:
responsive to determining that the generated hash value does not match an entry in the cached portion of the deduplication data structure:
writing the data to the storage system; and
adding an entry to the cached portion of the deduplication data structure that includes the generated hash value.

### Claim 7 (depends on 1)

The method of claim 1 further comprising:
receiving a read request;
identifying a query value corresponding to a read request;
selecting, based on the query value, from a plurality of levels within a mapping table, the youngest level associated with the query value; and
searching the selected youngest level for an entry that maps the query value to a value corresponding to a location within the storage system.

### Claim 8

A computing system comprising:
a storage controller coupled to at least one storage device, wherein the storage controller is configured for:
receiving a request to write data to a storage system;
generating, based on the request, a hash value associated with the request to write data;
determining whether the generated hash value matches an entry in a deduplication data structure; and
responsive to determining that the generated hash value matches an entry in a deduplication data structure, discarding the data and updating the entry in the deduplication data structure.

### Claim 9 (depends on 8)

The computing system of claim 8 wherein the storage controller is further configured for:
responsive to determining that the generated hash value does not match an entry in a deduplication data structure:
writing the data to the storage system; and
adding an entry to the deduplication data structure that includes the generated hash value.

### Claim 10 (depends on 8)

The computer system of claim 8 wherein updating the entry in the deduplication data structure includes moving the entry to a highest level in the deduplication data structure.

### Claim 11 (depends on 9)

The computer system of claim 9 wherein the added entry to the deduplication data structure is included in a highest level in the deduplication data structure.

### Claim 12 (depends on 8)

The computer system of claim 8 wherein determining whether the generated hash value matches an entry in a deduplication data structure includes searching only a cached portion of the deduplication data structure, wherein the deduplication data structure also includes a non-cached portion that is not searched.

### Claim 13 (depends on 12)

The computer system of claim 12 wherein the storage controller is further configured for:
responsive to determining that the generated hash value does not match an entry in the cached portion of the deduplication data structure:
writing the data to the storage system; and
adding an entry to the cached portion of the deduplication data structure that includes the generated hash value.

### Claim 14 (depends on 8)

The computer system of claim 8 wherein the storage controller is further configured for:
receiving a read request;
identifying a query value corresponding to a read request;
selecting, based on the query value, from a plurality of levels within a mapping table, the youngest level associated with the query value; and
searching the selected youngest level for an entry that maps the query value to a value corresponding to a location within the storage system.

### Claim 15

A non-transitory computer readable storage medium storing program instruction executable by a processor for:
receiving a request to write data to a storage system;
generating, based on the request, a hash value associated with the request to write data;
determining whether the generated hash value matches an entry in a deduplication data structure; and
responsive to determining that the generated hash value matches an entry in a deduplication data structure, discarding the data and updating the entry in the deduplication data structure.

### Claim 16 (depends on 15)

The computer readable storage medium of claim 15 further comprising program instructions executable by a processor for:
responsive to determining that the generated hash value does not match an entry in a deduplication data structure:
writing the data to the storage system; and
adding an entry to the deduplication data structure that includes the generated hash value.

### Claim 17 (depends on 15)

The computer readable medium of claim 15 wherein updating the entry in the deduplication data structure includes moving the entry to a highest level in the deduplication data structure.

### Claim 18 (depends on 16)

The computer readable storage medium of claim 16 wherein the added entry to the deduplication data structure is included in a highest level in the deduplication data structure.

### Claim 19 (depends on 15)

The computer readable medium of claim 15 wherein determining whether the generated hash value matches an entry in a deduplication data structure includes searching only a cached portion of the deduplication data structure, wherein the deduplication data structure also includes a non-cached portion that is not searched.

### Claim 20 (depends on 19)

The computer readable medium of claim 19 further comprising program instructions executable by a processor for:
responsive to determining that the generated hash value does not match an entry in the cached portion of the deduplication data structure:
writing the data to the storage system; and
adding an entry to the cached portion of the deduplication data structure that includes the generated hash value.
