# US 11,113,206 B2 · Cache data location system

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

- Number: US 11,113,206 B2
- Document ID: US11113206B2
- Status: Granted
- Kind: B2
- Application number: 16/396,555
- Filed: 2019-04-26
- Published: 2020-10-29
- Granted: 2021-09-07
- Earliest claimed: 2019-04-26
- Assignees: Hewlett Packard Enterprise Development LP
- Applicants: Hewlett Packard Enterprise Development LP
- Inventors: Matti A. Vanninen; Sudhanshu Goswami; Christopher J. Corsi
- Web page: https://patentgrep.com/patent/US11113206B2

## CPC

- G06F 12/1018: involving hashing techniques, e.g. inverted page tables
- G06F 2212/608: Details relating to cache mapping
- G06F 2212/657: Virtual address space management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system may include a persistent storage device, a low latency cache device, a volatile memory; and a processor. The processor is to store a data structure in the volatile memory that is usable to directly translate a block logical address for targeted data to a candidate physical location on the cache device, store a multilevel translation index in the volatile memory for translating the block logical address for the targeted data to an expected physical location of the targeted data on the cache device and attempt accessing the targeted data at the candidate physical location retrieved from the direct cache address translation data structure. In response to the targeted data not being at the candidate physical address, access the targeted data at the expected physical location retrieved from the multilevel translation index.

## Claims

### Claim 1

A method comprising:
storing a direct cache address translation data structure in a volatile memory that directly translates a block logical address for targeted data to a candidate physical location on a cache device;
storing a multilevel translation index in the volatile memory that is usable to translate the block logical address for the targeted data to an expected physical location on the cache device;
determining if the targeted data resides at the candidate physical location retrieved from the direct cache address translation data structure; and
in response to the targeted data not residing at the candidate physical location:
accessing the targeted data at the expected physical location retrieved from the multilevel translation index; and
caching the retrieved expected physical location in the direct cache address translation structure, including modifying the direct cache address translation data structure to:
disassociate the candidate physical address from the block logical address for the targeted data; and
associate retrieved expected physical location to the block logical address for the targeted data.

### Claim 2 (depends on 1)

The method of claim 1, wherein the direct cache address translation data structure comprises a hash table, the method further comprising:
determining a key based upon the block logical address;
identifying a location of the candidate physical location in the hash table based on the key; and
retrieving the candidate physical location from the identified location.

### Claim 3 (depends on 1)

The method of claim 1, wherein;
the direct cache address translation data structure stores a first identifier for the targeted data;
a second identifier is stored at the candidate physical location; and
the method further comprises comparing the first identifier to the second identifier to determine whether the data at the candidate physical location is the targeted data.

### Claim 4 (depends on 1)

The method of claim 1, wherein in response to the block logical address for the targeted data not being associated with any candidate physical location in the direct cache address translation data structure:
determining the expected physical location for the targeted data using the multilevel translation index; and
modifying the direct cache address translation data structure to associate the determined expected physical address with the block logical address for the targeted data.

### Claim 5

A system comprising:
a persistent storage device;
a low latency cache device;
a volatile memory; and
a processor to execute instructions stored on a machine-readable storage medium to:
store a direct cache address translation data structure in the volatile memory that is usable to directly translate a block logical address for targeted data to a candidate physical location in the cache device, wherein the direct cache address translation data structure comprises a hash table;
store a multilevel translation index in the volatile memory for translating the block logical address for the targeted data to an expected physical location of the targeted data in the cache device;
apply a hash function to the block logical address to produce a hash value;
retrieve the candidate physical location from the hash table based on the hash value;
determine whether the targeted data resides at the candidate physical location retrieved from the direct cache address translation data structure;
in response to the targeted data residing at the candidate physical location, access the targeted data at the candidate physical location; and
in response to the targeted data not residing at the candidate physical address, access the targeted data at the expected physical location retrieved from the multilevel translation index.

### Claim 6 (depends on 5)

The storage system of claim 5, wherein the low latency cache device comprises a second persistent storage device.

### Claim 7 (depends on 6)

The storage system of claim 6, wherein the second persistent storage device comprises a storage class memory (SCM).

### Claim 8 (depends on 5)

The storage system of claim 5, wherein the instructions to retrieve the candidate physical location from the hash table based on the hash value comprise instructions to:
utilize a first portion of the hash value as a first key for the hash table to identify a particular page of a plurality of pages; and
utilize the hash value as a second key for the hash table to identify a location of the candidate physical location on the particular page.

### Claim 9 (depends on 8)

The storage system of claim 8, wherein each of the plurality of pages is protected by a spin lock.

### Claim 10 (depends on 5)

The storage system of claim 5, wherein the hash table is N-way set associative, wherein N is no greater than 6.

### Claim 11 (depends on 5)

The storage system of claim 5, wherein the hash table is set associative, wherein each set fits in two processor cache lines.

### Claim 12 (depends on 5)

The storage system of claim 5, wherein the hash table is set associative and wherein each key has a location within its corresponding set based upon an eviction temperature for the key.

### Claim 13 (depends on 5)

The storage system of claim 5, wherein:
the direct cache address translation data structure stores a first identifier for the targeted data;
a second identifier is stored at the candidate physical location; and
the instructions are executable to compare the first identifier to the second identifier to determine whether the data stored at the candidate physical location is the targeted data.

### Claim 14 (depends on 13)

The storage system of claim 13, wherein the instructions are executable to, in response to the first identifier being different than the second identifier:
disassociate the candidate physical location from the block logical address for the targeted data in the direct cache address translation data structure;
determine the expected physical location for the targeted data using the multilevel translation index; and
associate the determined expected physical location to the block logical address for the targeted data.

### Claim 15 (depends on 5)

The storage system of claim 5, wherein the instructions are executable to, in response to the block logical address for the targeted data not being associated with any candidate physical address:
determine the expected physical location for the targeted data using the multilevel translation index; and
modify the direct cache address translation data structure to associate the determined expected physical location with the block logical address for the targeted data.

### Claim 16 (depends on 5)

The storage system of claim 5, wherein the multilevel translation index comprises:
a first level to translate the block logical address for the targeted data to an identifier for the targeted data; and
a second level to translate the identifier to the expected physical location of the targeted data.

### Claim 17 (depends on 5)

The storage system of claim 5, wherein:
the multilevel translation index comprises:
a first index table to translate the block logical address to a first internal identifier; and
a second index table to translate the first internal identifier to the expected physical location on the cache device;
the instructions are executable to associate the first internal identifier with another physical location in response to data at the physical location being moved to the another physical location.

### Claim 18

A non-transitory computer-readable medium comprising instructions executable by processor to:
store, in volatile memory, a direct cache address translation data structure that is usable to directly translate a block logical address for targeted data to a candidate physical location in a cache device;
store, in the volatile memory, a multilevel translation index usable to translate the block logical address for the targeted data to an expected physical location of the targeted data in the cache device, wherein the multilevel translation index comprises:
a first index table to translate the block logical address to a first internal identifier; and
a second index table to translate the first internal identifier to the expected physical location in the cache device;
determine whether the targeted data resides at the candidate physical location determined via the direct cache address translation data structure;
in response to the targeted data residing at the candidate physical location, access the targeted data at the candidate physical location;
in response to the targeted data not residing at the candidate physical location, access the targeted data at the expected physical location determined via the multilevel translation index; and
associate the first internal identifier with another physical location in response to data at the expected physical location being moved to the another physical location.

### Claim 19 (depends on 18)

The non-transitory computer-readable medium of claim 18, wherein:
the direct cache address translation data structure comprises a hash table; and
the instructions are executable to:
apply a hash function to the block logical address to produce a hash value; and
retrieve the candidate physical location from the hash table based on the hash value.

### Claim 20 (depends on 18)

The non-transitory computer-readable medium of claim 18, wherein the instructions are executable to:
in response to the targeted data not residing at the candidate physical location:
cache the retrieved expected physical location in the direct cache address translation structure, including modifying the direct cache address translation data structure to:
disassociate the candidate physical address from the block logical address for the targeted data; and
associate retrieved expected physical location to the block logical address for the targeted data.