Apparatus, system, and method for managing eviction of data

• US 8,966,184 B2
• Filed: 01/31/2012
• Issued: 02/24/2015
• Est. Priority Date: 01/31/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Intelligent Intellectual Property Holdings LLC
• Inventors: Atkisson, David
• Primary Examiner(s): SONG, HUA JASMINE
• Application Number:
  US13/362,959
• Publication Number:
  US 20120198175A1
• Time in Patent Office: 1,120 Days
• Field of Search: 711/103, 711/118, 711/133, 711/135, 711/E12.022
• US Class Current: 711/133
• 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, comprising:

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

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 for grooming the data from the selected region to the other region.

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, comprising:

a grooming cost module configured to determine 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 another region;

a grooming candidate set module configured to add 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 configured to select 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 configured to recovers storage capacity of the low cost region when the data is groomed from the selected region.

17. The apparatus of claim 16, further comprising a grooming clock module configured to select 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 configured to determine 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. A system, comprising:

a processor;

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

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

a grooming cost module for communication with the storage controller, the grooming cost module for examining a grooming cost for a selected region of a solid state storage media 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 another region;

a grooming candidate module that designates the selected region as a grooming candidate in response to the grooming cost satisfying a grooming cost threshold;

and

a groomer module for communication with the storage controller, the groomer module for recovering storage capacity based on the grooming cost when the data is groomed from the selected region.

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

21. An apparatus, comprising:

a storage recovery cost module configured to determine a storage recovery cost for a selected region of a nonvolatile solid-state cache, the storage recovery cost comprising a cost of evicting the selected region of the nonvolatile solid-state cache relative to another region;

a storage recovery candidate set module configured to add the selected region to a storage recovery candidate set in response to the storage recovery cost satisfying a storage recovery cost threshold by being lower than at least one region of the storage recovery candidate set;

a low cost module configured to select a low cost region within the storage recovery candidate set, the low cost region comprising a lowest storage recovery cost of members of the storage recovery candidate set; and

a storage recovery module configured to recover storage capacity of the low cost region when the data is evicted from the selected region to the other region.

22. A method, comprising:

analyzing a garbage collection cost for a selected region of a solid state storage media of a nonvolatile solid-state cache, the garbage collection cost comprising a cost of evicting data from the selected region of the nonvolatile solid-state cache relative to a cost of evicting data from another region;

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

selecting a low cost region within the grooming candidate set for garbage collection when the data is moved from the selected region to the other region.