Smart weighted container data cache eviction
View Patent ↗Smart weighted container data cache eviction preserves write evict units (WEUs) containing the most frequently and recently accessed blocks to maintain low latency data cache. Prior to performing cache eviction, the WEUs are weighted based on the page statistics maintained for each WEU. Page statistics include page hit/frequency and recency statistics associated with each WEU and data cache eviction is performed at the WEU level of granularity. Therefore, an entire WEU can be evicted based on page hit/frequency and recency statistics associated with the WEU.
1. A computer-implemented method for managing a data cache in a cache memory device, the method comprising:
storing data in a data cache in a cache memory device, the data cache including a plurality of data structures in which a plurality of blocks of data is stored over time;
establishing counters, for each block of data stored in each data structure, to track a frequency of access for that block in a first time period, and a recency of access for that block in a second time period, wherein the first time period is longer than the second time period;
weighting each data structure based on the frequency of access and the frequency of access, including computing an average of a first hit count in the first time period and a second hit count in the second time period for the plurality of blocks of data stored in the data structure, and sorting the plurality of data structures based on the computed averages;
selecting, from the plurality of sorted data structures, one or more blocks of data with a lowest computed average;
generating a first list of data structures sorted by the recency of access of any of the one or more selected blocks of data stored in the data structures;
generating a second list of data structures sorted by the frequency of access of any of the one or more selected blocks of data stored in the data structure; and
evicting, from the data cache, a first data structure and a second data structure, the first data structure being in the first list of data structures and having a least recency of access of any of the one or more selected blocks of data, and the second data structure being in the second list of data structures and having a least frequency of access of any of the one or more selected blocks of data.
2. The computer-implemented method of claim 1 , wherein:
the data structures are write evict units (WEUs) in the cache memory device that each have a size determined based on an erase unit size of the cache memory device; and
data stored in the cache memory device is erased on a per-erase unit basis according to a specification of the cache memory device.
3. The computer-implemented method of claim 1 , wherein:
the one or more blocks of data are any one of a page and a segment capable of being identified in a map associating each block of data to the data structure in which it is stored; and
the counters established for each block of data contain cache hit counts for determining the frequency of access and the recency of access.
4. The computer-implemented method of claim 1 , wherein the first time period and the second time period are both periods of time based on a number of hours over a 24-hour period of time.
5. The method of claim 1 , wherein each of the first list of data structure and the second list of data structure is sorted using a quick sort algorithm.
6. The method of claim 1 , further comprising:
determining whether a predetermine eviction target has been met;
in response to determining that the predetermined eviction target has not been met, iteratively repeating the operations to evict one or more additional data structures from the data cache until the predetermined target is met.
7. The method of claim 6 , wherein the eviction target is determined to be a fixed percentage of reserved space in the data cache.
8. A storage system for caching data using a cache memory device, comprising:
a cache memory device having a data cache in which to store a plurality of blocks of data over time, the data cache including a plurality of data structures each capable of containing some of the plurality of blocks of data; and
a cache manager executed by a processor to:
establish counters for each block of data stored in each data structure to track a frequency of access for that block in a first time period, and a recency of access for that block in a second time period, wherein the first time period is longer than the second time period,
weight each data structure based on the frequency of access and the frequency of access, including computing an average of a first hit count in the first time period and a second hit count in the second time period for the blocks of data stored in the data structure, and sorting the plurality of data structures based on the computed averages,
select, from the plurality of sorted data structures, one or more blocks of data with a lowest computed average,
generate a first list of data structures sorted by the recency of access of any of the one or more selected blocks of data stored in the data structures,
generate a second list of data structures sorted by the frequency of access of any of the one or more selected blocks of data stored in the data structure, and
evict, from the data cache, a first data structure and a second data structure, the first data structure being in the first list of data structures and having a least recency of access of any of the one or more selected blocks of data, and the second data structure being in the second list of data structures and having a least frequency of access of any of the one or more selected blocks of data.
9. The storage system of claim 8 , wherein:
the data structures are write evict units (WEUs) in the cache memory device that each have a size determined based on an erase unit size of the cache memory device; and
data stored in the cache memory device is erased on a per-erase unit basis according to a specification of the cache memory device.
10. The storage system of claim 8 , wherein:
the one or more blocks of data are any one of a page and a segment capable of being identified in a map associating each block of data to the data structure in which it is stored; and
the counters established for each block of data contain cache hit counts for determining the frequency of access and the recency of access.
11. The storage system of claim 8 , wherein the first time period and the second time period are both periods of time based on a number of hours over a 24-hour period of time.
12. The storage system of claim 8 , wherein the cache manager executed by a processor is further to:
determine whether a predetermine eviction target has been met;
in response to determining that the predetermined eviction target has not been met, iteratively repeat the operations to evict one or more additional data structures from the data cache until the predetermined target is met.
13. The storage system of claim 8 , wherein the eviction target is determined to be a fixed percentage of reserved space in the data cache.
14. The storage system of claim 8 , wherein each of the first list of data structure and the second list of data structure is sorted using a quick sort algorithm.
15. A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations for managing a data cache in a cache memory device, the operations comprising:
storing data in a data cache in a cache memory device, the data cache including a plurality of data structures in which a plurality of blocks of data is stored over time;
establishing counters, for each block of data stored in each data structure, to track a frequency of access for that block in a first time period, and a recency of access for that block in a second time period, wherein the first time period is longer than the second time period;
weighting each data structure based on the frequency of access and the frequency of access, including computing an average: of a first hit count in the first time period and a second hit count in the second time period for the plurality of blocks of data stored in the data structure, and sorting the plurality of data structures based on the computed averages;
selecting, from the plurality of sorted data structures, one or more blocks of data with a lowest computed average;
generating a first list of data structures sorted by the recency of access of any of the one or more selected blocks of data stored in the data structures;
generating a second list of data structures sorted by the frequency of access of any of the one or more selected blocks of data stored in the data structure; and
evicting, from the data cache, a first data structure and a second data structure, the first data structure being in the first list of data structures and having a least recency of access of any of the one or more selected blocks of data, and the second data structure being in the second list of data structures and having a least frequency of access of any of the one or more selected blocks of data.
16. The non-transitory computer-readable storage medium of claim 15 , wherein:
the data structures are write evict units (WEUs) in the cache memory device that each have a size determined based on an erase unit size of the cache memory device; and
data stored in the cache memory device is erased on a per-erase unit basis according to a specification of the cache memory device.
17. The non-transitory computer-readable storage medium of claim 15 , wherein:
the one or more blocks of data are any one of a page and a segment capable of being identified in a map associating each block of data to the data structure in which it is stored; and
the counters established for each block of data contain cache hit counts for determining the frequency of access and the frequency of access.
18. The non-transitory computer-readable storage medium of claim 15 , wherein the first time period and the second time period are both periods of time based on a number of hours over a 24-hour period of time.
19. The non-transitory computer-readable storage medium of claim 15 , wherein the operations further comprise:
determining whether a predetermine eviction target has been met;
in response to determining that the predetermined eviction target has not been met, iteratively repeating the operations to evict one or more additional data structures from the data cache until the predetermined target is met.
20. The non-transitory computer-readable storage medium of claim 15 , wherein the eviction target is determined to be a fixed percentage of reserved space in the data cache.