Systems and methods for cache endurance

• US 9,767,032 B2
• Filed: 12/05/2013
• Issued: 09/19/2017
• 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, Plasson, Ned D., Yang, Jingpei, Wood, Robert, Sundararaman, Swaminathan, Gillis, Gregory N.
• Primary Examiner(s): DOAN, DUC T
• Application Number:
  US14/098,281
• Publication Number:
  US 20140095775A1
• Time in Patent Office: 1,384 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

A cache and/or storage module may be configured to reduce write amplification in a cache storage. Cache layer write amplification (CLWA) may occur due to an over-permissive admission policy. The cache module may be configured to reduce CLWA by configuring admission policies to avoid unnecessary writes. Admission policies may be predicated on access and/or sequentiality metrics. Flash layer write amplification (FLWA) may arise due to the write-once properties of the storage medium. FLWA may be reduced by delegating cache eviction functionality to the underlying storage layer. The cache and storage layers may be configured to communicate coordination information, which may be leveraged to improve the performance of cache and/or storage operations.

Claims

1. An apparatus, comprising:

a cache layer that caches data associated with a backing store in a cache corresponding to a non-volatile solid-state storage device and maintains cache metrics for respective logical identifiers of the backing store in response to monitoring storage requests directed to the respective logical identifiers of the backing store, the cache metrics including cache metrics for cached logical identifiers and non-cached logical identifiers, the cached logical identifiers comprising logical identifiers of the backing store that are admitted into the cache, the non-cached logical identifiers comprising logical identifiers of the backing store that are not admitted into the cache,

wherein the cache layer services storage requests directed to cached logical identifiers by use of the cache, and wherein servicing a storage request directed to a particular logical identifier of the backing store, the particular logical identifier comprising a non-cached logical identifier, comprises;

determining whether to admit the particular logical identifier into the cache by comparing a cache metric for the particular address to an admission threshold, the admission threshold to control admission of non-cached logical identifier of the backing store into the cache,

admitting the particular logical identifier into the cache in response to the cache metric satisfying the admission threshold, such that the particular logical identifier comprises a cached logical identifier of the backing store to be serviced by use of the cache, and

rejecting admission of the particular logical identifier in response to the cache metric failing to satisfy the admission threshold, such that the particular logical identifier remains a non-cached logical identifier to be serviced by use of the backing store; and

a cache coordinator that modifies the admission threshold in response to a coordination message pertaining to the non-volatile solid-state storage device by one of;

increasing the admission threshold and decreasing the admission threshold, wherein the cache layer uses the modified admission threshold to control admission of non-cached logical identifiers of the backing store in response to the coordination message.

2. The apparatus of claim 1, wherein data admitted into the cache are stored within storage divisions of a log maintained on the non-volatile solid-state storage device, the apparatus further comprising:

a garbage collector configured to recover storage divisions of the log maintained on the non-volatile solid-state storage device, wherein the garbage collector is configured to recover a selected storage division of the log by,

identifying valid cache data stored on the selected storage division of the log, wherein the identified valid cache data is associated with the backing store and is referenced by the cache layer,

accessing coordination information maintained by the cache layer to select first valid cache data, of the identified valid cache data, to retain on the non-volatile solid-state storage device, and to select second valid cache data, of the identified valid cache data, to remove from the non-volatile solid-state storage device during recovery of the selected storage division of the log,

writing the first valid cache data to another storage division of the log, and

erasing the selected storage division of the log, such that the second valid cache data is removed from the non-volatile solid-state storage device.

3. The apparatus of claim 2, wherein the garbage collector is configured to issue a query to the cache layer to determine whether to evict data of the identified valid cache data from the non-volatile solid-state storage device.

4. The apparatus of claim 1, wherein the coordination message indicates one or more of a wear rate of the non-volatile solid-state storage device and a wear level of the non-volatile solid-state storage device, and

wherein the cache coordinator modifies the admission threshold to restrict admission of non-cached logical identifiers into the cache based on one or more of the wear rate of the non-volatile solid-state storage device and the wear level of the non-volatile solid-state storage device.

5. The apparatus of claim 1, wherein the cache metrics comprise access counts for respective logical identifiers of the backing store, the access counts indicating a number of storage requests directed to the respective addresses during particular time windows, wherein the cache coordinator modifies the admission threshold to increase an access count threshold, and wherein the cache layer determines whether to admit a non-cached address into the cache based on whether access counts determined for the non-cached address satisfy the access count threshold.

6. The apparatus of claim 1, wherein the cache metrics determined for the respective addresses of the backing store comprise one or more of access metrics and non-sequentiality metrics, and wherein the admission threshold for the cache comprises one or more of an access metric threshold, a non-sequentiality threshold, and an adaptive threshold, the adaptive threshold corresponding to access and non-sequentiality metrics.

7. The apparatus of claim 1, wherein the cache coordinator modifies the admission threshold for the cache in accordance with a write amplification reduction policy, wherein the write amplification reduction policy is configured to reduce a rate at which non-cached addresses of the backing store are admitted into the cache.

8. The apparatus of claim 1, wherein the cache coordinator modifies the admission threshold for the cache in response to one or more of:

the coordination message indicating that the non-volatile solid-state storage device is subject to write amplification, a wear level of the non-volatile solid-state storage device indicated by the coordination message, a wear rate of the non-volatile solid-state storage device indicated by the coordination message, and availability of write capacity indicated by the coordination message, the write capacity corresponding to availability of initialized storage divisions of the non-volatile solid-state storage device.

9. The apparatus of claim 1, wherein the cache coordinator decreases the admission threshold, wherein the decrease to the admission threshold is configured to increase a rate at which non-cached addresses are admitted into the cache.

10. The apparatus of claim 1, wherein the cache metrics determined for the non-cached addresses of the backing store comprise access metrics and sequentiality metrics, the access metrics corresponding to a number of storage requests identified as being directed to the respective non-cached addresses during a particular time window, and the sequentiality metrics indicating a proximity of the respective non-cached addresses to addresses of other storage requests monitored during the particular time window, and wherein modifying the admission threshold comprises modifying one or more of:

an access metric threshold, a sequentiality metric threshold, and a combined access and sequentiality metric threshold to one or more of an access metric and a sequentiality metric.

11. A method, comprising:

maintaining input/output (I/O) request characteristics of identifiers corresponding to an address space of a backing store;

determining cache metrics for identifiers of the address space of the backing store by use of the determined I/O characteristics, the determined cache metrics including cache metrics for cached identifiers and non-cached identifiers, the cached identifiers comprising identifiers of the address space that are admitted into a cache corresponding to a solid-state storage medium, the non-cached identifiers comprising identifiers of the address space that are not admitted into the cache;

servicing I/O requests directed to identifiers of the address space of the backing store, wherein servicing an I/O request directed to an identifier of the address space comprises;

servicing the I/O request by use of the cache in response to the identifier comprising a cached identifier,

admitting the identifier into the cache in response to a cache metric determined for the identifier satisfying a cache admission threshold such that I/O requests directed to the identifier are serviced by use of the cache, the cache admission threshold configured to control the admission of data into the cache, and

retaining the identifier as a non-cached identifier in response to the cache metric determined for the identifier failing to satisfy the cache admission threshold such that I/O requests directed to the identifier are serviced by use of the backing store; and

adjusting the cache admission threshold based on coordination information pertaining to the solid-state storage medium, wherein adjusting the cache admission threshold comprises one of increasing the cache admission threshold and decreasing the cache admission threshold.

12. The method of claim 11, wherein the coordination information indicates one or more of a wear rate of the solid-state storage medium and a wear level of the solid-state storage medium, and wherein adjusting the cache admission threshold comprises one of:

increasing the cache admission threshold to reduce a cache admission rate to the coordination Information indicating one or more of a high wear rate and a high wear level, and

decreasing the cache admission threshold to increase the cache admission rate in response to the coordination information indicating one or more of a low wear rate for the solid-state storage medium and a low wear level for the solid-state storage medium.

13. The method of claim 11, wherein the coordination information indicates an amount of available write capacity, the amount of available write capacity corresponding to availability of initialized storage divisions of the solid-state storage medium, and wherein adjusting the cache admission threshold comprises one of:

increasing the cache admission threshold in response to the indicated amount of available write capacity satisfying a write capacity threshold, and

decreasing the cache admission threshold in response to the indicated amount of available write capacity failing to satisfy the write capacity threshold.

14. The method of claim 11, further comprising receiving the coordination information from a storage controller, the storage controller configured to manage the solid-state storage medium.

15. The method of claim 11, wherein the coordination information indicates a wear level of the solid-state storage medium, and wherein adjusting the cache admission threshold comprises one of:

adjusting the cache admission threshold to restrict admission of data into the cache responsive to the indicated wear level failing to satisfy a wear level threshold, and

adjusting the cache admission threshold to increase admission of data into the cache responsive to the indicated wear level satisfying the wear level threshold.

16. The method of claim 11, further comprising:

determining an eviction policy for the cache based on the coordination information pertaining to the solid-state storage medium; and

evicting data from the cache in accordance with the determined eviction policy.

17. The method of claim 11, further comprising identifying data that can be removed from the cache during a storage recovery operation on a log segment on the solid-state storage medium.

18. A non-transitory computer-program product comprising program code configured for execution by a computing system, wherein the program code is configured to cause the computing system to perform operations, comprising:

monitoring I/O requests that pertain to logical addresses of a backing store;

maintaining cache metrics for respective logical addresses of the backing store in response to the monitoring the cache metrics comprising cache metrics for cached logical addresses and non-cached logical addresses, the cached logical addresses comprising logical addresses of the backing store that are admitted into a cache corresponding to a non-volatile storage device, the non-cached logical addresses comprising logical addresses of the backing store that are not admitted into the cache;

servicing an I/O request that pertains to a logical address of the backing store, wherein servicing the I/O request comprises;

determining whether the logical address comprises a cached logical address of the backing store that is admitted into the cache;

servicing the I/O request by use of the non-volatile storage device in response to the logical address comprising a cached logical address; and

in response to the logical address comprising a non-cached logical address;

comparing a cache metric for the logical address to a cache admission criterion, the cache admission controlling admission of non-cached logical addresses into the cache,

admitting the logical address into the cache in response to the cache metric satisfying the cache admission criterion, such that the logical address comprises a cached logical address to be serviced by use of the non-volatile storage device, and

preventing the logical address from being admitted into the cache in response to the cache metric failing to satisfy the cache admission criterion, such that the logical address remains a non-cached logical address to be serviced by use of the backing store; and

modifying the admission criterion used to control admission of non-cached logical addresses of the backing store into the cache based on coordination data corresponding to the non-volatile storage medium.

19. The computer-program product of claim 18, wherein maintaining the cache metrics comprises determining access metrics for the logical addresses of the backing store, the access metrics of the respective logical addresses indicating a number of accesses to the respective logical addresses during one or more time periods,

wherein the admission criterion comprises an access metric threshold,

wherein determining whether to admit the logical address into the cache comprises comparing the access metric determined for the logical address to the access metric threshold, such that the logical address is admitted into the cache in response to the access metric being greater than or equal to the access metric threshold, and is prevented from being admitted into the cache in response to the access metric being less than the access metric threshold, and

wherein modifying the admission criterion comprises one or more of increasing the access metric threshold and decreasing the access metric threshold.

20. The computer-program product of claim 18, wherein the coordination data indicates one or more of:

whether the non-volatile storage medium is subject to write amplification, whether the non-volatile storage medium is wear-limited, a wear rate of the non-volatile storage medium, a wear level of the non-volatile storage medium, and an available write capacity on the non-volatile storage medium.

21. The computer-program product of claim 18, wherein the logical identifier is admitted into the cache in response to determining that the cache metric of the logical identifier satisfies an admission threshold of the admission criterion, and wherein modifying the admission criterion comprises increasing the admission threshold in response to the coordination data indicating one or more of:

that the non-volatile storage medium is subject to write amplification and that the non-volatile storage medium is wear-limited.

22. The computer-program product of claim 18, the operations further comprising:

evicting data from the cache on the non-volatile storage medium in response to determining that an eviction metric associated with the data satisfies an eviction threshold for the cache; and

modifying the eviction threshold for the cache in response to the coordination information, wherein modifying the eviction threshold comprises one of increasing the eviction threshold and decreasing the eviction threshold.