Apparatus, system, and method for managing eviction of data

Patent metadata

Field	Value
Publication number	US-9678874-B2
Application number	US-201514794483-A
Country	US
Kind code	B2
Filing date	Jul 8, 2015
Priority date	Jan 31, 2011
Publication date	Jun 13, 2017
Grant date	Jun 13, 2017

Abstract

An apparatus, system, and method are disclosed for managing eviction of data. A cache write module stores data on a non-volatile storage device sequentially using a log-based storage structure having a head region and a tail region. A direct cache module caches data on the non-volatile storage device using the log-based storage structure. The data is associated with storage operations between a host and a backing store storage device. An eviction module evicts data of at least one region in succession from the log-based storage structure starting with the tail region and progressing toward the head region.

First claim

What is claimed is:

1. A method comprising:
caching data of a backing store within respective regions of a non-volatile storage medium;
selecting a region of the non-volatile storage medium for a grooming operation based on determined grooming costs for the respective regions, wherein determining the grooming cost for a particular region is based on an amount of data within the particular region to relocate on the non-volatile storage medium in a grooming operation on the particular region; and
grooming the selected region, wherein grooming the selected region comprises evicting data cached on the selected region.

2. The method of claim 1 , wherein the grooming cost for the particular region is based on an order of the particular region in a log-based structure on the non-volatile storage medium.

3. The method of claim 2 , further comprising designating a tail region of the log-based structure, the tail region corresponding to an oldest region appended to the log-based structure.

4. The method of claim 1 , further comprising selecting the region for the grooming operation in response to a storage capacity recovery event.

5. The method of claim 4 , wherein the storage capacity recovery event comprises a number of regions in an available storage pool satisfying a threshold.

6. The method of claim 4 , wherein the storage capacity recovery event comprises one or more of an amount of available storage capacity for the non-volatile storage medium falling below a threshold, a predefined period of time elapsing since a previous storage capacity recovery event, an eviction request from a cache client, and the non-volatile storage medium satisfying an error condition.

7. The method of claim 1 , wherein the grooming cost of the particular region is based on an access frequency to cached data of the backing store cached on the particular region.

8. The method of claim 1 , wherein the grooming operation on the selected region further comprises selectively copying valid, clean data from the selected region to retain the valid, clean data on the non-volatile storage medium in response to the valid, clean data satisfying a data use metric.

9. The method of claim 1 , wherein the grooming operation on the selected region further comprises destaging dirty write data from the selected region to the backing store.

10. The method of claim 1 , wherein the grooming operation further comprises copying dirty write data from the selected region to a different region of the non-volatile storage medium.

11. The method of claim 1 , wherein the grooming cost of the particular region is based on an amount of dirty cache data stored within the particular region.

12. The method of claim 1 , wherein caching the data of the backing store within the respective regions of the non-volatile storage medium further comprises caching the data according to a write through cache policy.

13. An apparatus comprising:
a cache write module configured to cache data on respective regions of a non-volatile storage device;
a grooming module configured to determine grooming costs of the respective regions based on an amount of data cached on the respective regions that must be retained on the non-volatile storage device, wherein the grooming module is further configured to select a region for a grooming operation based on the determined grooming costs of the respective region; and
an eviction module configured to evict data cached on the selected region in the grooming operation on the selected region.

14. The apparatus of claim 13 , further comprising a frequent data module that selectively copies valid, clean data from the selected region to an append point in the log structure in response to the valid, clean data satisfying a data use metric.

15. The apparatus of claim 13 , further comprising a destage module configured to one of, destage dirty write data from the selected region to the backing store prior to evicting the data cached on the selected region; and copy dirty write data from the selected region to another region of the non-volatile storage device in the grooming operation on the selected region.

16. The apparatus of claim 13 , wherein the log structure comprises a tail region, the tail region comprising an oldest written region of the log structure, wherein the grooming cost of the particular region is based on an order of the particular region relative to the tail region within the log structure.

17. The apparatus of claim 13 , wherein the grooming cost of the particular region is based on an error rate of the particular region.

18. A system for managing eviction of data, the system comprising:
a processor;
a storage controller for a non-volatile storage device, the non-volatile storage device configured to communicate with the processor over one or more communications buses, the storage controller configured to store data within sequentially ordered regions of a storage structure on the non-volatile storage device, wherein the sequential order of the regions corresponds to a time the respective regions were added to the storage structure;
a cache controller configured to communicate with the storage controller, the cache controller configured to cache data in the sequentially ordered storage structure by use of the storage controller; and
a data expiration module of the cache controller configured to expire, through the storage controller, data cached on selected regions of the storage structure, wherein the data expiration module selects the regions based on the time the respective regions were added to the storage structure.

19. The system of claim 18 , further comprising a host computer system, the host computer system comprising the processor, wherein the storage controller and the cache controller each comprise a device driver executing on the processor of the host computer system.

20. The system of claim 18 , wherein the data expiration module expires data cached on the non-volatile storage device in a first-in-first-out order that corresponds to the order in which the data was cached in the sequential writing storage structure on the non-volatile storage device.

Assignees

• Sandisk Technologies Llc

Inventors

• Nellans David
• Atkisson David
• Peterson Jim
• Garff Jeremy
• Zappe Michael

Classifications

• G06F12/0804 Primary

  with main memory updating (G06F12/0806 takes precedence) · CPC title

• G06F3/0614

  Improving the reliability of storage systems · CPC title

• G06F3/0655

  Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices · CPC title

• G06F3/065

  Replication mechanisms · CPC title

• G06F3/0679

  Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP] · CPC title