Apparatus, system, and method for managing eviction of data

• US 9,092,337 B2
• Filed: 01/31/2012
• Issued: 07/28/2015
• Est. Priority Date: 01/31/2011
• Status: Expired due to Fees

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Intelligent Intellectual Property Holdings LLC
• Inventors: Nellans, David, Atkisson, David, Peterson, Jim, Garff, Jeremy, Zappe, Mike
• Primary Examiner(s): SONG, HUA JASMINE
• Application Number:
  US13/362,973
• Publication Number:
  US 20120198174A1
• Time in Patent Office: 1,274 Days
• Field of Search: 711/118, 711/133, 711/135, 711/E12.009, 711/E12.022
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 2206/1014 One time programmable [OTP] memory, e.g. PROM, WORM
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

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.

Claims

1. A method for managing eviction of data, the method comprising:

storing data on non-volatile storage medium sequentially using a log-based storage structure having a head region and a tail region, wherein the storing comprises caching the data on the non-volatile storage medium using the log-based storage structure, the data associated with storage operations between a host and a backing store storage device; and

evicting 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 based on an order that regions of the log-based storage structure were added to the log-based storage structure.

2. The method of claim 1, further comprising evicting regions from the log-based storage structure in a first-in-first-out order based on an order that regions of the log-based storage structure are added to the log-based storage structure.

3. The method of claim 1, further comprising designating a neighboring region to a present tail region of the log-based storage structure as tail region of the log-based storage structure in response to successfully evicting data from the present tail region.

4. The method of claim 1, further comprising evicting the data of the at least one region 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, further comprising clearing data from a present tail region of the log-based storage structure during a garbage collection operation and designating a neighboring region to the present tail region of the log-based storage structure as tail region of the log-based storage structure in response to the present tail region comprising exclusively invalid data.

8. The method of claim 1, further comprising selectively copying valid, clean data out of the at least one region to retain the valid, clean data in response to the valid, clean data satisfying a data use metric.

9. The method of claim 1, further comprising destaging dirty write data from the at least one storage region to the backing store prior to evicting data of the at least one region.

10. The method of claim 1, further comprising copying dirty write data from the at least one region forward on the log-based storage structure in response to evicting data of the at least one region.

11. The method of claim 1, further comprising evicting a plurality of regions in order, the order defined by regions in the log-based storage structure moving from the tail of the log towards the head of the log.

12. The method of claim 1, wherein the non-volatile storage medium caches data according to a write through cache policy.

13. An apparatus, comprising:

a cache module configured to cache data on a non-volatile storage device sequentially using a log-based storage structure having a head region and a tail region, the data associated with storage operations between a host and a backing store storage device; and

an eviction module configured to evict at least one region of data sequentially from the log-based storage structure starting with the tail region and progressing toward the head region based on an order that regions of the log-based storage structure were added to the log-based storage structure.

14. The apparatus of claim 13, further comprising a frequent data module that selectively copies valid, clean data from the at least one region to an append point in the log-based storage 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 do one of (a) destage dirty write data from the at least one storage region to the backing store prior to evicting data of the at least one region;

and (b) copy dirty write data from the at least one region forward on the log-based storage structure in response to evicting data of the at least one region.

16. The apparatus of claim 13, wherein the at least one region comprises the tail of the log-based storage structure, the tail comprising an oldest written region of the log-based storage structure such that the eviction module evicts data in a first-in-first-out order.

17. The apparatus of claim 13, wherein the eviction module evicts a plurality of regions in order, the order defined by regions in the log-based storage structure moving from the tail of the log towards the head of the log in a first-in-first-out order.

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 on the non-volatile storage device sequentially using a sequential writing storage structure having a head portion and a tail portion;

a cache controller configured to communicate with the storage controller, the cache controller configured to cache data on the non-volatile storage device through the storage controller using the sequential writing storage structure, the data associated with storage operations between the processor and a backing store storage device; and

a data expiration module of the cache controller, the eviction module configured to expire, through the storage controller, data of at least one portion in succession from the sequential writing storage structure starting with the tail portion and progressing toward the head portion based on an order that regions of the log-based storage structure were added to the log-based 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 evicts portions from the sequential writing storage structure in a first-in-first-out order based on an order that portions of the sequential writing storage structure are added to the sequential writing storage structure.

21. A method for managing eviction of data, the method comprising:

caching data on non-volatile storage medium sequentially using a log-based storage structure having a head part and a tail part, the data associated with storage operations between a host device and a backing store storage device; and

trimming data of at least one region in order from the log-based storage structure starting with the tail part and progressing toward the head part based on an order that regions of the log-based storage structure are added to the log-based storage structure.

22. A system for clearing data, 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 on the non-volatile storage device sequentially using a sequential storage structure having a head part and a tail part; and

a cache controller configured to communicate with the storage controller, the cache controller configured to place data on the non-volatile storage device through the storage controller using the sequential storage structure, the data associated with storage operations between the processor and a backing store storage device, the cache controller further configured to clear data from the storage structure through the storage controller starting with the tail part and progressing toward the head part based on an order that regions of the log-based storage structure were added to the log-based storage structure.