Methods to efficiently implement coarse granularity cache eviction

Patent metadata

Field	Value
Publication number	US-9892044-B1
Application number	US-201514609889-A
Country	US
Kind code	B1
Filing date	Jan 30, 2015
Priority date	Jan 30, 2015
Publication date	Feb 13, 2018
Grant date	Feb 13, 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 at a sub-cache unit granularity, wherein the cache device comprises a plurality of cache units, each cache unit having a plurality of segments, wherein the cache device is accessible by a cache client at a segment granularity. The exemplary method further includes in response to determining that a cache eviction is to be performed, selecting a predetermined number of cache units from the plurality of cache units, determining a score for each of the selected cache units based on the respective metadata set maintained at the sub-cache unit granularity, and evicting one or more of the selected predetermined number of cache units based on their scores. The metadata may include, for example, last access time (LAT) metadata, an access count, and hotness metadata, and metadata may be maintained at a segment or a segment group granularity.

First claim

What is claimed is:

1. A computer-implemented method, the method comprising:
maintaining a metadata set for each cache unit of a cache device at a segment granularity, wherein the cache device comprises a plurality of cache units, each cache unit having a plurality of segments, wherein the cache device is accessible by a cache client at the segment granularity;
in response to determining that a cache eviction is to be performed:
selecting a predetermined number of cache units from the plurality of cache units, and
determining a score for each of the selected predetermined number of cache units based on the respective metadata set maintained at the segment granularity, a deletion hint (DH) ratio, and a probability that deprecated segments in the cache unit revert back to being non-deprecated, wherein the DH ratio is indicative of a ratio of a number of segments in the cache unit with DH being active to the total number of segments in the cache unit, wherein the number of segments in the cache unit with DH being active is included in the metadata set; and

evicting one or more of the selected predetermined number of cache units based on their respective scores.

2. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device at the sub-cache unit granularity comprises:
maintaining last access time (LAT) metadata, wherein the LAT metadata indicates when a segment or segment group was last accessed; and
maintaining priority metadata, wherein the priority metadata indicates priority of a segment or segment group.

3. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device at the sub-cache unit granularity comprises:
maintaining access count metadata, wherein the access count metadata indicates how many times a segment or segment group has been accessed.

4. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device at the sub-cache unit granularity comprises:
maintaining hotness metadata, wherein the hotness metadata contains a value which increases each time a segment or segment group is accessed, and decreases each time a segment or segment group is not accessed for a predetermined time period.

5. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device at the sub-cache unit granularity comprises maintaining the metadata set at a segment granularity.

6. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device at the sub-cache unit granularity comprises maintaining the metadata set at a segment group granularity.

7. The method of claim 1 , wherein for each cache unit, the score for each sub-cache unit of the cache unit is determined based further on a last access time indicative of a time when the sub-cache unit was last accessed, and a current time.

8. The method of claim 1 , wherein determining the score for each of the selected predetermined number of cache units comprises:
determining each score based on a plurality of metadata, wherein each metadata is assigned a different weight.

9. A non-transitory computer-readable storage medium having computer code stored therein, which when executed by a processor, causes the processor to perform operations comprising:
maintaining a metadata set for each cache unit of a cache device at a segment granularity, wherein the cache device comprises a plurality of cache units, each cache unit having a plurality of segments, wherein the cache device is accessible by a cache client at the segment granularity;
in response to determining that a cache eviction is to be performed:
selecting a predetermined number of cache units from the plurality of cache units, and
determining a score for each of the selected predetermined number of cache units based on the respective metadata set maintained at the segment granularity, a deletion hint (DH) ratio, and a probability that deprecated segments in the cache unit revert back to being non-deprecated, wherein the DH ratio is indicative of a ratio of a number of segments in the cache unit with DH being active to the total number of segments in the cache unit, wherein the number of segments in the cache unit with DH being active is included in the metadata set; and

evicting one or more of the selected predetermined number of cache units based on their respective scores.

10. The non-transitory computer-readable storage medium of claim 9 , wherein maintaining the metadata set for each cache unit of the cache device at the sub-cache unit granularity comprises:
maintaining last access time (LAT) metadata, wherein the LAT metadata indicates when a segment or segment group was last accessed; and
maintaining priority metadata, wherein the priority metadata indicates priority of a segment or segment group.

11. The non-transitory computer-readable storage medium of claim 9 , wherein maintaining the metadata set for each cache unit of the cache device at the sub-cache unit granularity comprises:
maintaining access count metadata, wherein the access count metadata indicates how many times a segment or segment group has been accessed.

12. The non-transitory computer-readable storage medium of claim 9 , wherein maintaining the metadata set for each cache unit of the cache device at the sub-cache unit granularity comprises:
maintaining hotness metadata, wherein the hotness metadata contains a value which increases each time a segment or segment group is accessed, and decreases each time a segment or segment group is not accessed for a predetermined time period.

13. The non-transitory computer-readable storage medium of claim 9 , wherein maintaining the metadata set for each cache unit of the cache device at the sub-cache unit granularity comprises maintaining the metadata set at a segment granularity.

14. The non-transitory computer-readable storage medium of claim 9 , wherein maintaining the metadata set for each cache unit of the cache device at the sub-cache unit granularity comprises maintaining the metadata set at a segment group granularity.

15. The non-transitory computer-readable storage medium of claim 9 , wherein for each cache unit, the score for each sub-cache unit of the cache unit is determined based further on a last access time indicative of a time when the sub-cache unit was last accessed, and a current time.

16. The non-transitory computer-readable storage medium of claim 9 , wherein determining the score for each of the selected predetermined number of cache units comprises:
determining each score based on a plurality of metadata, wherein each metadata is assigned a different weight.

17. A data processing system, comprising:
a cache device comprising a plurality of cache units, each cache unit having a plurality of segments;
a set of one or more processors; and
a non-transitory machine-readable storage medium storing instructions, which when executed, causes the set of one or more processors to:
maintain a metadata set for each cache unit of the cache device at a segment granularity, wherein the cache device is accessible by a cache client at the segment granularity;
in response to determining that a cache eviction is to be performed:
select a predetermined number of cache units from the plurality of cache units, and
determine a score for each of the selected predetermined number of cache units based on the respective metadata set maintained at the segment granularity, a deletion hint (DH) ratio, and a probability that deprecated segments in the cache unit revert ba

Assignees

• Emc Ip Holding Co Llc

Inventors

• Wallace Grant
• Douglis Frederick
• Li Cheng
• Shilane Philip

Classifications

• G06F2212/62

  Details of cache specific to multiprocessor cache arrangements · CPC title

• G06F12/126

  with special data handling, e.g. priority of data or instructions, handling errors or pinning · CPC title

• G06F12/121

  using replacement algorithms · CPC title

• G06F12/0833 Primary

  in combination with broadcast means (e.g. for invalidation or updating) · CPC title

• G06F2212/466

  Metadata, control data · CPC title