Systems and methods for profiling a non-volatile cache having a logical-to-physical translation layer

• US 9,251,052 B2
• Filed: 02/22/2013
• Issued: 02/02/2016
• Est. Priority Date: 01/12/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Intelligent Intellectual Property Holdings LLC
• Inventors: Talagala, Nisha, Sundararaman, Swaminathan, Mudrankit, Amar
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): Wang, Edward
• Application Number:
  US13/774,874
• Publication Number:
  US 20130185475A1
• Time in Patent Office: 1,075 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 2212/502 using adaptive policy

Abstract

A cache module leverages a logical address space and storage metadata of a storage module (e.g., virtual storage module) to cache data of a backing store. The cache module maintains access metadata to track access characteristics of logical identifiers in the logical address space, including accesses pertaining to data that is not currently in the cache. The access metadata may be separate from the storage metadata maintained by the storage module. The cache module may calculate a performance metric of the cache based on profiling metadata, which may include portions of the access metadata. The cache module may determine predictive performance metrics of different cache configurations. An optimal cache configuration may be identified based on the predictive performance metrics.

Claims

1. An apparatus, comprising:

a cache module configured to cache data of a backing store on a non-volatile storage device and to maintain access metadata pertaining to logical identifiers of data of the backing store, wherein the access metadata comprises access characteristics pertaining to logical identifiers of data of the backing store that is cached on the non-volatile storage device and logical identifiers of data of the backing store that is not cached on the non-volatile storage device; and

a performance analysis module configured to calculate a cache performance metric based on the access metadata;

wherein the cache module is further configured to selectively admit data of the backing store into the cache based on the access metadata, and to determine a sequentiality metric of a logical identifier selected for admission into the cache and to admit data of one or more logically adjacent logical identifiers into the cache in response to the sequentiality metric satisfying a threshold, wherein the sequentiality metric is based on logically proximate access requests within a predetermined window within a history of access requests, wherein the performance analysis module is configured to calculate an optimal window based on the access metadata, and

wherein the cache module and the performance analysis module comprise one or more of a circuit, a programmable circuit, and instructions stored on a non-transitory computer-readable storage medium.

2. The apparatus of claim 1, further comprising a metadata persistence module configured to store cache profiling metadata on a persistent storage medium, wherein the cache profiling metadata corresponds to at least a portion of the access metadata.

3. The apparatus of claim 1, wherein the access metadata comprises a history of access requests to logical identifiers of a logical address space corresponding to the backing store.

4. The apparatus of claim 1, wherein the access metadata comprises a history of write operations to cache data of the backing store on the non-volatile storage device.

5. The apparatus of claim 1, further comprising a storage module configured to allocate a portion of a physical storage capacity of the non-volatile storage device to the cache module, wherein the performance analysis module is configured to predict a cache performance metric corresponding to a different allocation of physical storage capacity to the cache module by use of the access metadata.

6. The apparatus of claim 1, further comprising a storage module configured to allocate a portion of a physical storage capacity of the non-volatile storage device to the cache module, wherein the performance analysis module is configured to determine an optimal allocation by use of the access metadata, and to provide the determined optimal allocation to the storage module.

7. The apparatus of claim 1, wherein the access metadata comprises a plurality of entries, wherein each entry is configured to indicate access characteristics of a respective plurality of logical identifiers, and wherein the access metadata is sparse such that entries are added to the access metadata in response to access requests directed to logical identifiers of the backing store.

8. The apparatus of claim 1, wherein the access metadata comprises a plurality of entries, wherein each entry is configured to indicate access characteristics of a respective plurality of logical identifiers according to a pre-determined mapping, and wherein the performance analysis module is further configured to calculate a predicted performance metric corresponding to access metadata comprising a different pre-determined mapping between logical identifiers and entries.

9. The apparatus of claim 8, wherein the performance analysis module is configured to calculate an optimal mapping ratio of logical identifiers to entries by use of the access metadata and to indicate the optimal mapping ratio to the cache module.

10. An apparatus, comprising:

a storage module configured to map logical identifiers corresponding to a backing store to storage locations of cache data of the backing store on a non-volatile storage device;

a cache module configured to generate access characteristics of the logical identifiers, including access characteristics of non-cached logical identifiers;

a metadata persistence module configured to store cache profiling metadata on a computer-readable storage medium, wherein the cache profiling metadata corresponds to the access characteristics;

a cache admission module configured to selectively admit data of the backing store into a cache on the non-volatile storage device based on the access metadata, and to determine a sequentiality metric of a logical identifier selected for admission into the cache and to admit data of one or more logically adjacent logical identifiers into the cache in response to the sequentiality metric satisfying a threshold, wherein the sequentiality metric is based on previous access requests within a threshold logical proximity to the logical identifier; and

a performance analysis module configured to calculate a cache performance metric by use of the persisted access metadata and to calculate a predicted cache performance metric corresponding to use of a different threshold logical proximity,

wherein the storage module, cache module, metadata persistence module, cache admission module, and performance analysis module comprise one or more of a circuit, a programmable circuit, and instructions stored on a non-transitory computer-readable storage medium.

11. The apparatus of claim 10, wherein the performance analysis module is configured to calculate an optimal logical proximity threshold using the persisted access metadata and to indicate the optimal proximity threshold to the cache admission module.

12. The apparatus of claim 10, wherein the sequentiality metric is based on logically proximate access requests within a predetermined window within a history of access requests, and wherein the apparatus further comprises a performance analysis module configured to calculate an optimal window based on the persisted cache profiling metadata.

13. The apparatus of claim 10, wherein the cache admission module is configured to select a logical identifier for admission into the cache in response to an access metric of the logical identifier satisfying an admission criteria, and wherein the performance analysis module is configured to generate predictive cache profiling metadata using the persisted cache profiling metadata and applying different access criteria for cache admission.

14. A computer program product comprising a non-transitory computer readable storage medium storing computer usable program code executable to perform operations, the operations comprising:

generating access data structures configured to indicate access characteristics of logical identifiers within a logical address space of a backing store;

admitting data of the backing store into a cache based on access metrics of the logical identifiers, wherein the access metrics of the logical identifiers are derived from one or more of the access data structures; and

calculating a predictive cache performance metric corresponding to a different cache configuration by use of one or more of the access data structures,

wherein calculating the predictive cache performance metric comprises;

replaying a history of access requests to logical identifiers within the logical address space, and

simulating selective admission into the cache based on the different cache configuration.

15. The computer program product of claim 14, wherein the different cache configuration comprises one or more of a different cache admission criteria, a different cache eviction criteria, and a different cache size.

16. The computer program product of claim 14, the operations further comprising modifying the admission criteria in response to the predictive cache performance metric.

17. The computer program product of claim 14, the operations further comprising determining an optimal cache configuration based on a plurality of predictive cache performance metrics derived from the access data structures.