APPARATUS, SYSTEM, AND METHOD FOR MANAGING EVICTION OF DATA

• US 20120198175A1
• Filed: 01/31/2012
• Published: 08/02/2012
• Est. Priority Date: 01/31/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Atkisson, David
• Granted Patent: US 8,966,184 B2
• Time in Patent Office: Days
• US Class Current: 711/135
• 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 grooming cost module determines a grooming cost for a selected region of a nonvolatile solid-state cache. The grooming cost includes a cost of evicting the selected region of the nonvolatile solid-state cache relative to other regions. A grooming candidate set module adds the selected region to a grooming candidate set in response to the grooming cost satisfying a grooming cost threshold. A low cost module selects a low cost region within the grooming candidate set. A groomer module recovers storage capacity of the low cost region.

Claims

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

examining a grooming cost for a selected region of a nonvolatile solid-state cache, the grooming cost comprising a cost of evicting the selected region of the nonvolatile solid-state cache relative to other regions;

adding the selected region to a grooming candidate set in response to the grooming cost satisfying a grooming cost threshold; and

selecting a low cost region within the grooming candidate set.

2. The method of claim 1, further comprising recovering storage capacity of the low cost region.

3. The method of claim 2, further comprising retaining cached dirty write data from the low cost region in response to recovering the storage capacity of the low cost region.

4. The method of claim 2, wherein the grooming cost represents a cache efficiency cost of evicting data from the selected region and a storage efficiency cost of copying data forward from the selected region.

5. The method of claim 2, further comprising retaining cached data identified as frequently accessed data from the low cost region in response to recovering the storage capacity of the low cost region in a low pressure groom mode and evicting the cached data identified as frequently accessed data in response to recovering the storage capacity of the low cost region in a high pressure groom mode.

6. The method of claim 2, wherein recovering the storage capacity of the low cost region is in response to one or more of a storage capacity recovery event and a grooming pressure for the nonvolatile solid-state cache exceeding a predefined grooming pressure threshold.

7. The method of claim 1, further comprising selecting a next region of the nonvolatile solid-state cache as the selected region in response to the grooming cost of the selected region failing to satisfy the grooming cost threshold.

8. The method of claim 7, wherein regions of the nonvolatile solid-state cache are organized in a circular data structure and one or more successive next regions are selected in order around the circular data structure until a grooming cost for a next region satisfies the grooming cost threshold and the next region that satisfies the grooming cost threshold is added to the grooming candidate set.

9. The method of claim 1, wherein the grooming cost for the selected region is based at least partially on a frequency count for the selected region.

10. The method of claim 9, further comprising clearing the frequency count for the selected region in response to examining the grooming cost for the selected region such that a subsequent grooming cost for the selected region is based at least partially on a new frequency count for the selected region.

11. The method of claim 9, further comprising preserving a copy of the frequency count for the selected region in response to adding the selected region to the grooming candidate set, the frequency count identifying frequently accessed data from the low cost region.

12. The method of claim 9, wherein the frequency count comprises a number of blocks in the selected region accessed at least a predetermined number of times during a predefined time period.

13. The method of claim 1, wherein the grooming cost for the selected region accounts for an amount of cached dirty write data of the selected region.

14. The method of claim 1, wherein the selected region stores data for a plurality of cache units and the grooming cost accounts for one or more attributes of the plurality of cache units, the one or more attributes comprising one or more of a relative priority of the cache units, an allocated storage capacity for the cache units, and a quality-of-service for the cache units.

15. The method of claim 1, wherein the grooming cost of the selected region satisfies the grooming cost threshold by being lower than at least one region of the grooming candidate set.

16. An apparatus for managing eviction of data of a cache, the apparatus comprising:

a grooming cost module that determines a grooming cost for a selected region of a nonvolatile solid-state cache, the grooming cost comprising a cost of evicting the selected region of the nonvolatile solid-state cache relative to other regions;

a grooming candidate set module that adds the selected region to a grooming candidate set in response to the grooming cost satisfying a grooming cost threshold by being lower than at least one region of the grooming candidate set;

a low cost module that selects a low cost region within the grooming candidate set, the low cost region comprising a lowest grooming cost of members of the grooming candidate set; and

a groomer module that recovers storage capacity of the low cost region.

17. The apparatus of claim 16, further comprising a grooming clock module that selects the selected region and that selects a next region of the nonvolatile solid-state cache as the selected region in response to the grooming cost of the selected region failing to satisfy the grooming cost threshold.

18. The apparatus of claim 16, further comprising a frequency count module that determines a frequency count for the selected region, wherein the grooming cost module bases the grooming cost for the selected region at least partially on the frequency count.

19. The apparatus of claim 16, wherein the groomer module retains cached dirty write data from the low cost region, retains cached data identified as frequently accessed data from the low cost region in response to recovering the storage capacity of the low cost region in a low pressure groom mode, and evicts the cached data identified as frequently accessed data in response to recovering the storage capacity of the low cost region in a high pressure groom mode.

20. A system for managing eviction of data, the system comprising:

a processor;

a storage controller for a nonvolatile solid-state storage device, the nonvolatile solid-state storage device in communication with the processor over one or more communications buses;

a cache controller in communication with the storage controller, the cache controller comprising,

a grooming cost module in communication with the storage controller, the grooming cost module examining a grooming cost for a selected region of the nonvolatile solid-state storage device, the grooming cost comprising a cost of evicting the selected region of the nonvolatile solid-state storage device relative to other regions;

a grooming candidate set module that adds the selected region to a grooming candidate set in response to the grooming cost satisfying a grooming cost threshold;

a low cost module that selects a low cost region within the grooming candidate set; and

a groomer module in communication with the storage controller, the groomer module recovering storage capacity of the low cost region.

21. The system of claim 20, 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.