# US 2017/0286307 A1 · Optimized Read Cache For Persistent Cache On Solid State Devices

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

- Number: US 2017/0286307 A1
- Document ID: US20170286307A1
- Status: Published application
- Kind: A1
- Application number: 15/085,485
- Filed: 2016-03-30
- Published: 2017-10-05
- Earliest claimed: 2016-03-30
- Assignees: Infinio Systems, Inc.
- Applicants: Infinio Systems, Inc.
- Inventors: David W. Harvey; Scott H. Davis; Martin Charles Martin; Vishal Misra; Hooman Vassef
- Web page: https://patentgrep.com/patent/US20170286307A1

## CPC

- G06F 12/0866: for peripheral storage systems, e.g. disk cache
- G06F 11/14: Error detection or correction of the data by redundancy in operations (error detection or correction of the data by redundancy in hardware G06F11/16)
- G06F 11/1441: {Resetting or repowering}
- G06F 11/1446: Point-in-time backing up or restoration of persistent data
- G06F 11/1471: involving logging of persistent data for recovery
- G06F 12/1018: involving hashing techniques, e.g. inverted page tables
- G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing
- G06F 2212/1004: Compatibility, e.g. with legacy hardware
- G06F 2212/1021: Hit rate improvement
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/214: Solid state disk
- G06F 2212/222: Non-volatile memory
- G06F 2212/281: Single cache
- G06F 2212/461: Sector or disk block
- G06F 2212/466: Metadata, control data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems and methods for a content addressable cache that is optimized for SSD use are disclosed. In some embodiments, the cache utilizes an identifier array where identification information is stored for each entry in the cache. However, the size of the bit field used for the identification information is not sufficient to uniquely identify the data stored at the associated entry in the cache. A smaller bit field increases the likelihood of a “false positive”, where the identification information indicates a cache hit when the actual data does not match the digest. A larger bit field decreases the probability of a “false positive”, at the expense of increased metadata memory space. Thus, the architecture allows for a compromise between metadata memory size and processing cycles.

## Claims

### Claim 1

A method of minimizing metadata for a content addressable cache, the content addressable cache comprising a plurality of entries, each entry containing a block of data, the content addressable cache also containing identification information associated with each entry in the content addressable cache wherein the identification information is created based on a hash of the block of data at the entry, comprising:
determining a digest based on a system address;
comparing a portion of the digest to the identification information associated with an entry, wherein the identification information is insufficient to uniquely identify the contents of the block of data at the entry;
calculating a hash for the block of data contained in the entry, only if the portion of the digest matches the identification information associated with the entry;
comparing the hash to the digest;
returning the block of data in the entry as a cache hit if the hash matches the digest; and
indicating a cache miss if the hash does not match the digest.

### Claim 2 (depends on 1)

The method of claim 1, wherein, in the event of a cache miss, the portion of the digest is compared to identification information of a second entry and the calculating, comparing, returning and indicating steps are repeated for the second entry only if the portion of the digest matches the identification information associated with the second entry.

### Claim 3 (depends on 1)

The method of claim 1, wherein the content addressable cache is configured as an N-way associative cache, having a plurality of sets, wherein each set comprises N entries.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
using the digest to determine a set associated with the system address;
wherein the comparing of the portion of the digest to identification information is only performed if the entry belongs to the set associated with the system address.

### Claim 5 (depends on 4)

The method of claim 4, wherein the set is selected based on a subset of bits that comprise the digest.

### Claim 6 (depends on 1)

The method of claim 1, wherein the identification information comprises a subset of bits that comprise the hash of the block of data.

### Claim 7

A method of recreating metadata for an N-way associative content addressable cache stored in non-volatile memory, wherein the cache comprises a plurality of sets, each with N entries, comprising:
determining a digest based on a system address;
using the digest to determine a set associated with the system address;
checking if a verified indicator, located in the volatile memory, associated with the set, is set;
and, if the verified indicator is not set:
calculating a hash for each block of data contained in the N entries in the set;
updating identification information for each of the N entries based on the calculated hash; and
setting the verified indicator once identification information for all N entries in the set has been updated.

### Claim 8 (depends on 7)

The method of claim 7, wherein the identification information is insufficient to uniquely identify the block of data in the N entries.

### Claim 9 (depends on 7)

The method of claim 7, wherein the identification information uniquely identifies the block of data in the entry.

### Claim 10 (depends on 7)

The method of claim 7, further comprising returning one of the blocks of data in the set as a cache hit if the calculated hash of that entry matches the digest.

### Claim 11

A method of recreating metadata for a content addressable cache stored in non-volatile memory, wherein metadata for each entry in the cache is also stored in non-volatile memory, comprising:
copying the metadata from non-volatile memory to volatile memory to create an array, comprising identification information for each entry in the cache, wherein some of the metadata may be out of date;
determining a digest based on a system address;
comparing the digest to the identification information for a first entry in the content addressable cache; and
if the digest matches the identification information:
checking if a verified indicator associated with the first entry is set;
returning the block of data contained in the first entry if the verified indicator is set; and
if the verified indicator is not set:
calculating the hash for the block of data contained in the first entry;
calculating identification information based on the hash;
comparing the calculated identification information to the identification information stored in the array; and
setting the verified indicator for the first entry and returning the data at the first entry if the calculated identification information matches the identification information stored in the array.

### Claim 12 (depends on 11)

The method of claim 11, further comprising: if the calculated identification information does not match the identification information stored in the array:
updating the identification information stored in the array for the first entry with the calculated identification information if the calculated identification information does not match the identification information stored in the array;
setting the verified indicator for the first entry; and
returning a cache miss.

### Claim 13 (depends on 11)

The method of claim 11, further comprising comparing the digest to the identification information for a second entry in the content addressable cache if the digest does not match the identification information of the first entry.

### Claim 14

A method of minimizing metadata for a content addressable cache, wherein the content addressable cache is configured as an N-way associative cache, having a plurality of sets, wherein each set comprises N entries and each entry contains a block of data, the content addressable cache also containing identification information associated with each entry in the content addressable cache wherein the identification information is created based on the hash of the block of data at the entry, comprising:
determining a digest based on a system address;
using the digest to determine a set associated with the system address;
calculating a hash for the block of data contained in an entry, only if the entry belongs to the set associated with the system address;
comparing the hash to the digest;
returning the block of data in the entry as a cache hit if the hash matches the digest; and
indicating a cache miss if the hash does not match the digest.

### Claim 15 (depends on 14)

The method of claim 14, wherein the set is selected based on a subset of bits that comprise the digest.

### Claim 16 (depends on 14)

The method of claim 14, wherein, in the event of a cache miss, the digest is compared to the hash of a second entry and the calculating, comparing, returning and indicating steps are repeated for the second entry only if the second entry belongs to the set associated with the system address.

### Claim 17

A method of updating metadata stored in a non-volatile memory, wherein the metadata is associated with a cache, comprising:
maintaining a copy of the metadata in a volatile memory;
maintaining a log in the volatile memory which stores the changes made to the metadata in the volatile memory;
updating the copy of the metadata in the volatile memory whenever a change to the cache is made;
updating the log wherever the copy of metadata in the volatile memory is changed;
periodically writing a portion of the copy of metadata in the volatile memory to a corresponding location in the non-volatile memory; and
periodically writing the log to a change log stored in the non-volatile memory.

### Claim 18 (depends on 17)

The method of claim 17, wherein a frequency at which the copy of metadata is written to the non-volatile memory is based on the number of changes made to the copy of metadata stored in the volatile memory.

### Claim 19 (depends on 17)

The method of claim 17, wherein the log is written to the change log whenever the size of the log reaches a predetermined size.

### Claim 20 (depends on 17)

The method of claim 17, wherein an indication of whether a block of metadata in the volatile memory has been changed is maintained, and the portion of the metadata is only written to non-volatile memory if the metadata has been changed.

### Claim 21 (depends on 17)

A method of recreating metadata for a content addressable cache stored in non-volatile memory, wherein the recreated metadata is stored in a volatile memory, comprising:
copying metadata stored in non-volatile memory to the volatile memory; and
applying the change log of claim 17 to update the metadata in the volatile memory.