Method to decrease computation for cache eviction using deferred calculations
View Patent ↗A data processing system and methods for performing cache eviction are disclosed. An exemplary method includes maintaining a metadata set for each cache unit of a cache device, wherein the cache device comprises a plurality of cache units, each cache unit having a plurality of segments, calculating a score for each metadata set, and arranging the metadata sets in a list in ascending order from lowest score to highest score. The exemplary method further includes in response to determining that a cache eviction is to be performed, selecting a cache unit corresponding to the metadata set in the list having the lowest score, without recalculating a score for any of the metadata set, and evicting the selected cache unit. The metadata nay include, for example, segment count metadata, validity metadata, last access time (LAT) metadata, and hotness metadata.
1. A computer-implemented method for performing cache eviction, the method comprising:
maintaining a metadata set for each cache unit of a cache device comprising a plurality of cache units, each cache unit having a plurality of segments, the metadata set for each cache unit including a segment count metadata, a validity metadata, and a last access time (LAT) metadata, wherein the segment count metadata indicates a total number of segments in a cache unit corresponding to the metadata set, wherein the validity metadata indicates which segments in the cache unit corresponding to the metadata set are valid, and wherein the LAT metadata indicates when the cache unit corresponding to the metadata set was last accessed;
calculating a score for each of the metadata sets based at least in part on the segment count metadata, the validity metadata, and the LAT metadata;
arranging the metadata sets in a list in ascending order from lowest score to highest score;
in response to determining that a cache eviction is to be performed, selecting a cache unit corresponding to the metadata set in the list having the lowest score, without recalculating a score for any of the metadata sets in the list; and
evicting the selected cache unit.
2. The method of claim 1 , further comprising:
in response to determining a first cache unit has been created in the cache device, determining a score for cache unit metadata of the first cache unit;
determining a first location in the list to insert the cache unit metadata of the first cache unit such that the metadata sets in the list remain in ascending order from lowest score to highest score, wherein the first location is determined without having to recalculate a score for each cache unit metadata in the list; and
inserting the cache unit metadata of the first cache unit at the determined first location.
3. The method of claim 2 , further comprising:
in response to determining a second cache unit has been created in the cache device, determining a score for cache unit metadata of the second cache unit;
determining a second location in the list to reposition the cache unit metadata of the second cache unit such that the metadata sets in the list remain in ascending order from lowest score to highest score, wherein the second location is determined without having to recalculate a score for each cache unit metadata in the list; and
repositioning the cache unit metadata of the second cache unit at the determined second location.
4. The method of claim 3 , wherein determining the second location in the list comprises using a binary search.
5. The method of claim 1 , further comprising:
in response to evicting the selected cache unit, locating a cache unit metadata corresponding to the evicted cache unit in the list; and
removing the cache unit metadata corresponding to the evicted cache unit from the list.
6. The method of claim 1 , wherein:
the metadata set for each cache unit of the cache device further includes a hotness metadata, wherein the hotness metadata contains a value which increases each time the cache unit corresponding to the metadata set is accessed, and decreases each time the cache unit corresponding to the metadata set is not accessed for a predetermined time period; and
calculating the score for each metadata set is further based on the hotness metadata.
7. A non-transitory computer-readable storage medium having computer code stored therein, which when executed by a processor, causes the processor to perform operations, the operations comprising:
maintaining a metadata set for each cache unit of a cache device comprising a plurality of cache units, each cache unit having a plurality of segments, the metadata set for each cache unit including a segment count metadata, a validity metadata, and a last access time (LAT) metadata, wherein the segment count metadata indicates a total number of segments in a cache unit corresponding to the metadata set, wherein the validity metadata indicates which segments in the cache unit corresponding to the metadata set are valid, and wherein the LAT metadata indicates when the cache unit corresponding to the metadata set was last accessed;
calculating a score for each of the metadata sets based at least in part on the segment count metadata, the validity metadata, and the LAT metadata;
arranging the metadata sets in a list in ascending order from lowest score to highest score;
in response to determining that a cache eviction is to be performed, selecting a cache unit corresponding to the metadata set in the list having the lowest score, without recalculating a score for any of the metadata sets in the list; and
evicting the selected cache unit.
8. The non-transitory computer-readable storage medium of claim 7 , wherein the operations further comprise:
in response to determining a first cache unit has been created in the cache device, determining a score for cache unit metadata of the first cache unit;
determining a first location in the list to insert the cache unit metadata of the first cache unit such that the metadata sets in the list remain in ascending order from lowest score to highest score, wherein the first location is determined without having to recalculate a score for each cache unit metadata in the list; and
inserting the cache unit metadata of the first cache unit at the determined first location.
9. The non-transitory computer-readable storage medium of claim 7 , wherein the operations further comprise:
in response to determining a second cache unit has been created in the cache device, determining a score for cache unit metadata of the second cache unit;
determining a second location in the list to reposition the cache unit metadata of the second cache unit such that the metadata sets in the list remain in ascending order from lowest score to highest score, wherein the second location is determined without having to recalculate a score for each cache unit metadata in the list; and
repositioning the cache unit metadata of the second cache unit at the determined second location.
10. The non-transitory computer-readable storage medium of claim 9 , wherein determining the second location in the list comprises using a binary search.
11. The non-transitory computer-readable storage medium of claim 7 , wherein the operations further comprise:
in response to evicting the selected cache unit, locating a cache unit metadata corresponding to the evicted cache unit in the list; and
removing the cache unit metadata corresponding to the evicted cache unit from the list.
12. The non-transitory computer-readable storage medium of claim 7 , wherein:
the metadata set for each cache unit of the cache device further includes a hotness metadata, wherein the hotness metadata contains a value which increases each time the cache unit corresponding to the metadata set is accessed, and decreases each time the cache unit corresponding to the metadata set is not accessed for a predetermined time period; and
calculating the score for each metadata set is further based on the hotness metadata.
13. A data processing system, comprising:
a cache device;
a set of one or more processors; and
a non-transitory machine-readable storage medium storing instructions, which when executed by the set of one or more processors, causes the set of one or more processors to
maintain a metadata set for each cache unit of the cache device, the cache device comprising a plurality of cache units, each cache unit having a plurality of segments, the metadata set for each cache unit including a segment count metadata, a validity metadata, and a last access time (LAT) metadata, wherein the segment count metadata indicates a total number of segments in a cache unit corresponding to the metadata set, wherein the validity metadata indicates which segments in the cache unit corresponding to the metadata set are valid, and wherein the LAT metadata indicates when the cache unit corresponding to the metadata set was last accessed;
calculate a score for each of the metadata sets based at least in part on the segment count metadata, the validity metadata, and the LAT metadata;
arrange the metadata sets in a list in ascending order from lowest score to highest score;
in response to determining that a cache eviction is to be performed, select a cache unit corresponding to the metadata set in the list having the lowest score, without recalculating a score for any of the metadata sets in the list; and
evict the selected cache unit.
14. The data processing system of claim 13 , wherein the set of one or more processors is further to:
in response to determining a first cache unit has been created in the cache device, determine a score for cache unit metadata of the first cache unit;
determine a first location in the list to insert the cache unit metadata of the first cache unit such that the metadata sets in the list remain in ascending order from lowest score to highest score, wherein the first location is determined without having to recalculate a score for each cache unit metadata in the list; and
insert the cache unit metadata of the first cache unit at the determined first location.
15. The data processing system of claim 13 , wherein the set of one or more processors is further to:
in response to determining a second cache unit has been created in the cache device, determine a score for cache unit metadata of the second cache unit;
determine a second location in the list to reposition the cache unit metadata of the second cache unit such that the metadata sets in the list remain in ascending order from lowest score to highest score, wherein the second location is determined without having to recalculate a score for each cache unit metadata in the list; and
reposition the cache unit metadata of the second cache unit at the determined second location.
16. The data processing system of claim 15 , wherein determining the second location in the list is performed using a binary search.
17. The data processing system of claim 13 , wherein the set of one or more processors is further to:
in response to evicting the selected cache unit, locate a cache unit metadata corresponding to the evicted cache unit in the list; and
remove the cache unit metadata corresponding to the evicted cache unit from the list.
18. The data processing system of claim 13 , wherein:
the metadata set for each cache unit of the cache device further includes a hotness metadata, wherein the hotness metadata contains a value which increases each time the cache unit corresponding to the metadata set is accessed, and decreases each time the cache unit corresponding to the metadata set is not accessed for a predetermined time period; and
calculating the score for each metadata set is further based on the hotness metadata.