Method to decrease computation for cache eviction using deferred calculations

Patent metadata

Field	Value
Publication number	US-9921963-B1
Application number	US-201514609928-A
Country	US
Kind code	B1
Filing date	Jan 30, 2015
Priority date	Jan 30, 2015
Publication date	Mar 20, 2018
Grant date	Mar 20, 2018

Abstract

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.

First claim

What is claimed is:

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 (LA

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Li Cheng
• Shilane Philip
• Wallace Grant

Classifications

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F2212/7207

  management of metadata or control data · CPC title

• G06F2212/62

  Details of cache specific to multiprocessor cache arrangements · CPC title

• G06F12/12

  Replacement control · CPC title

• G06F12/122

  of the least frequently used [LFU] type, e.g. with individual count value · CPC title