Optimized Read Cache For Persistent Cache On Solid State Devices

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.

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.

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.

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.