Systems and methods for cache and storage device coordination

• US 10,102,117 B2
• Filed: 02/22/2013
• Issued: 10/16/2018
• Est. Priority Date: 01/12/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Talagala, Nisha, Sundararaman, Swaminathan
• Primary Examiner(s): Bragdon, Reginald G
• Assistant Examiner(s): Wang, Edward
• Application Number:
  US13/774,881
• Publication Number:
  US 20130185488A1
• Time in Patent Office: 2,062 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0862 with prefetch
• 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 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/502 using adaptive policy
• CPC Class Codes: G06F 2212/6024 History based prefetching
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

A cache module leverages storage metadata to cache data of a backing store on a non-volatile storage device. The cache module maintains access metadata pertaining to access characteristics of logical identifiers in the logical address space, including access characteristics of un-cached logical identifiers (e.g., logical identifiers associated with data that is not stored on the non-volatile storage device). The access metadata may be separate and/or distinct from the storage metadata. The cache module determines whether to admit data into the cache and/or evict data from the cache using the access metadata. A storage module may provide eviction candidates to the cache module. The cache module may select candidates for eviction. The storage module may leverage the eviction candidates to improve the performance of storage recovery and/or grooming operations.

Claims

1. An apparatus, comprising:

a storage controller of a non-volatile storage device configured to cache data of a backing store on the non-volatile storage device; and

a cache manager configured to maintain a window comprising an ordered sequence of data accesses received during respective time intervals, and to use the window to determine sequentiality metrics pertaining to logical identifiers of the backing store, including a particular logical identifier that corresponds to data cached on the non-volatile storage device, wherein the sequentiality metric of the particular logical identifier is based on one or more storage requests in the window corresponding to the particular logical identifier, including;

a first storage request received subsequent to caching the data of the particular logical identifier, and

a second storage request pertaining to data cached prior to caching the data of the particular logical identifier on the non-volatile storage device,

the sequentiality metric indicating whether the data was cached in a sequential data access,

wherein the cache manager is configured to determine whether to evict the data of the particular logical identifier from the non-volatile storage device based on the sequentiality metric.

2. The apparatus of claim 1, wherein the storage controller is configured to identify cached data on a section of the non-volatile storage device in response to selecting the section for recovery, and wherein the cache manager is configured to determine whether to evict the identified cached data by use of sequentiality metrics of logical identifiers corresponding to the identified cached data.

3. The apparatus of claim 1, wherein the cache manager is further configured to indicate to the storage controller that the cached data corresponding to the particular logical identifier can be evicted from the non-volatile storage device in a storage recovery operation of the storage controller, wherein the cache manager provides access to the cached data of the particular logical identifier subsequent to the indication and until the cached data corresponding to the particular logical identifier is erased from the non-volatile storage device.

4. The apparatus of claim 3, wherein the cache manager is configured to indicate to the storage controller that data of a logical identifier does not need to be retained on the non-volatile storage device in response to the sequentiality metric of the particular logical identifier satisfying an eviction threshold.

5. The apparatus of claim 4, wherein the storage controller is configured to retain an association between the logical identifier and a physical storage location and to provide access to data stored at the physical storage location after receiving the indication.

6. The apparatus of claim 3, wherein the storage module is configured to invalidate an association between the particular logical identifier and a physical storage location in response to erasing the cached data of the particular logical identifier from the non-volatile storage device subsequent to the indication from the cache manager that the cached data of the particular logical identifier can be evicted from the cache.

7. The apparatus of claim 3, wherein the cache manager is configured to indicate that the cached data of the logical identifier can be evicted from the non-volatile storage device by sending a TRIM message to the storage controller, and wherein the storage controller is configured to notify the cache manager of erasure of the cached data of the particular logical identifier from the non-volatile storage device.

8. The apparatus of claim 1, wherein the cache manager is further configured to maintain access metrics pertaining to the logical identifiers, wherein the access metrics comprise an access data structure comprising a plurality of entries, each entry indicating access characteristics of one or more logical identifiers, and wherein, in response to an access metric of an entry satisfying an eviction threshold, the cache manager is configured to indicate to the storage controller that data of the one or more logical identifiers of the entry can be erased from the non-volatile storage device.

9. The apparatus of claim 1, wherein the cache manager is further configured to maintain access metrics pertaining to the logical identifiers, and to determine a threshold for cache eviction based on access metrics and sequentiality metrics of the logical identifiers.

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

determining sequentiality metrics of logical identifiers of a logical address space of a backing store, wherein the sequentiality metrics indicate whether data of the respective logical identifiers pertain to a sequential data access, wherein determining the sequentiality metric for a logical identifier comprises;

maintaining windows for respective storage requests, each window comprising an ordered sequence of storage requests received within a temporal threshold of a respective storage request,

determining sequentiality metrics for logical identifiers corresponding to the respective storage requests using the windows, wherein determining the sequentiality metric for a logical identifier corresponding to a particular storage request is based on a proximity of the logical identifier to logical identifiers corresponding to storage requests in a window comprising the particular storage request, including a first storage request pertaining to data previously cached on the non-volatile storage medium and a second storage request associated with data that is not cached on the non-volatile storage medium;

identifying a set of one or more logical identifiers associated with cache data of the backing store stored on a storage division of the non-volatile storage medium that has been selected for recovery; and

determining whether to evict one or more of the logical identifiers in the identified set from the non-volatile storage medium based on sequentiality metrics of the logical identifiers.

11. The non-transitory computer program product of claim 10, wherein determining the sequential metrics comprises monitoring storage requests directed to logical identifiers of the logical address space of the backing store.

12. The non-transitory computer program product of claim 10, the operations further comprising indicating that data of a logical identifier can be erased from the non-volatile storage medium in response to determining that a sequentiality metric of the logical identifier satisfies an eviction threshold.

13. The non-transitory computer program product of claim 12, the operations further comprising erasing data of the logical identifier from the non-volatile storage medium in a storage division recovery operation.

14. The non-transitory computer program product of claim 12, the operations further comprising evicting data corresponding to a logical identifier by invalidating an association between the logical identifier and a physical storage location of the non-volatile storage medium.

15. The non-transitory computer program product of claim 10, the operations further comprising:

identifying a logical identifier to retain on the non-volatile storage medium; and

relocating data of the identified logical identifier to another storage division of the non-volatile storage medium in a storage division recovery operation.

16. A system, comprising:

a storage device configured to map logical identifiers within a logical address space of a backing store to physical storage locations of a non-volatile storage device comprising data of the backing store;

a cache module configured to track access characteristics of the logical identifiers of the logical address space of the backing store, wherein the access characteristics correspond to storage requests pertaining to respective logical identifiers, including a window comprising storage requests received within a time threshold of the storage requests,

wherein the cache module is further configured to determine sequentiality metrics of the logical identifiers, the sequentiality metrics indicating whether data of the respective logical identifiers corresponds to a sequential data access, wherein the cache module determines a sequentiality metric for a particular logical identifier admitted into the cache in response to a storage request based on storage requests within the window corresponding to the storage request, the storage requests including a first storage request pertaining to a first logical identifier that is not mapped to a physical storage location of the non-volatile storage device and a second storage request pertaining to a second logical identifier cached on the non-volatile storage device; and

a cache eviction module configured to select data of the backing store for removal from the non-volatile storage device by use of the access characteristics and the sequentiality metrics.

17. The system of claim 16, further comprising a groomer module configured to select a storage division for a recovery operation, wherein the cache eviction module is configured to determine whether data associated with one or more of the logical identifiers of the backing store cached on the selected storage division can be removed from the non-volatile storage device in the recovery operation based on the access characteristics and the sequentiality metrics.

18. The system of claim 16, wherein the cache eviction module is configured to select data of the backing store for removal from the non-volatile storage device based on whether access characteristics and sequentiality metrics of the logical identifiers associated with the data satisfy an eviction threshold.

19. The system of claim 18, wherein the eviction threshold is based on access characteristics of one or more logical identifiers that are not mapped to physical storage locations of the non-volatile storage device.

20. The system of claim 16, wherein the cache module is configured to identify logical identifiers associated with data of the backing store that can be erased from the non-volatile storage device.