Methods to select segments of an evicted cache unit for reinsertion into the cache

Patent metadata

Field	Value
Publication number	US-9892045-B1
Application number	US-201514609902-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 comprising a plurality of cache units, each cache unit having a plurality of segments. In response to determining that a cache eviction is to be performed, a cache unit is evicted based on its metadata set. The exemplary method includes selecting one or more segments of the evicted cache unit to copy to a second cache unit based on the metadata set of the evicted cache unit, copying the selected one or more segments to the second cache unit, and writing the second cache unit to a storage device. The metadata set may include deletion hints (DH) to indicate valid segments, last access time (LAT) or age based metadata, an access count, or a score for each segment based on the metadata set.

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, wherein the cache device comprises a plurality of cache units, each cache unit having a plurality of segments;
in response to determining that a cache eviction is to be performed, evicting a cache unit based on its metadata set;
selecting one or more segments of the evicted cache unit to copy to a second cache unit based on the metadata set of the evicted cache unit including determining a score for each segment of the evicted cache unit based at least in part on a probability that deprecated segments in the evicted cache unit revert back to being non-deprecated;
copying the selected one or more segments to the second cache unit; and
writing the second cache unit to a storage device.

2. The method of claim 1 , wherein:
maintaining the metadata set for each cache unit of the cache device comprises maintaining deletion hints (DH) metadata to indicate whether segments of a corresponding cache unit are valid; and
selecting one or more segments of the evicted cache unit to copy comprises selecting one or more segments that are valid.

3. The method of claim 1 , wherein:
maintaining the metadata set for each cache unit of the cache device comprises maintaining last access time (LAT) metadata to indicate when segments of a corresponding cache unit were most recently accessed; and
selecting one or more segments of the evicted cache unit to copy comprises selecting one or more segments that have an age that is less than a predetermined age threshold based on a most recent access time of the selected one or more segments and a current time.

4. The method of claim 1 , wherein:
maintaining the metadata set for each cache unit of the cache device comprises maintaining an access count metadata to indicate how many times segments of a corresponding cache unit have been accessed; and
selecting one or more segments of the evicted cache unit to copy comprises selecting one or more segments that have an access count that is greater than a predetermined access count threshold.

5. The method of claim 1 , wherein:
selecting one or more segments of the evicted cache unit to copy further comprises:
selecting one or more segments that have a score that has a predetermined mathematical relationship with a predetermined score threshold.

6. The method of claim 1 , wherein:
maintaining the metadata set for each cache unit of the cache device comprises maintaining last access time (LAT) metadata, wherein the LAT metadata contains two most recent access times for segments of a corresponding cache unit; and
selecting one or more segments of the evicted cache unit to copy comprises, for each segment of the evicted cache unit:
determining a difference of two most recent access times of the segment,
summing the difference with a most recent access time of the segment to determine a predicted next access time, and
selecting the segment if the predicted next access time falls within a specified threshold of time either before or after the current time.

7. The method of claim 1 , wherein:
maintaining the metadata set for each cache unit of the cache device comprises maintaining hotness metadata, wherein the hotness metadata contains a value which increases each time a segment corresponding to the metadata set is accessed, and decreases each time the segment corresponding to the metadata set is not accessed for a predetermined time period; and
selecting one or more segments of the evicted cache unit to copy comprises selecting one or more segments that have hotness greater than a predetermined hotness threshold.

8. 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, wherein the cache device comprises a plurality of cache units, each cache unit having a plurality of segments;
in response to determining that a cache eviction is to be performed, evicting a cache unit based on its metadata set;
selecting one or more segments of the evicted cache unit to copy to a second cache unit based on the metadata set of the evicted cache unit including determining a score for each segment of the evicted cache unit based at least in part on a probability that deprecated segments in the evicted cache unit revert back to being non-deprecated;
copying the selected one or more segments to the second cache unit; and
writing the second cache unit to a storage device.

9. The non-transitory computer-readable storage medium of claim 8 , wherein:
maintaining the metadata set for each cache unit of the cache device comprises maintaining deletion hints (DH) metadata to indicate whether segments of a corresponding cache unit are valid; and
selecting one or more segments of the evicted cache unit to copy comprises selecting one or more segments that are valid.

10. The non-transitory computer-readable storage medium of claim 8 , wherein:
maintaining the metadata set for each cache unit of the cache device comprises maintaining last access time (LAT) metadata to indicate when segments of a corresponding cache unit were most recently accessed; and
selecting one or more segments of the evicted cache unit to copy comprises selecting one or more segments that have an age that is less than a predetermined age threshold based on a most recent access time of the selected one or more segments and a current time.

11. The non-transitory computer-readable storage medium of claim 8 , wherein:
maintaining the metadata set for each cache unit of the cache device comprises maintaining an access count metadata to indicate how many times segments of a corresponding cache unit have been accessed; and
selecting one or more segments of the evicted cache unit to copy comprises selecting one or more segments that have an access count that is greater than a predetermined access count threshold.

12. The non-transitory computer-readable storage medium of claim 8 , wherein:
selecting one or more segments of the evicted cache unit to copy further comprises:
selecting one or more segments that have a score that has a predetermined mathematical relationship with a predetermined score threshold.

13. The non-transitory computer-readable storage medium of claim 8 , wherein:
maintaining the metadata set for each cache unit of the cache device comprises maintaining last access time (LAT) metadata, wherein the LAT metadata contains two most recent access times for segments of a corresponding cache unit; and
selecting one or more segments of the evicted cache unit to copy comprises, for each segment of the evicted cache unit:
determining a difference of two most recent access times of the segment,
summing the difference with a most recent access time of the segment to determine a predicted next access time, and
selecting the segment if the predicted next access time falls within a specified threshold of time either before or after the current time.

14. The non-transitory computer-readable storage medium of claim 8 , wherein:
maintaining the metadata set for each cache unit of the cache device comprises maintaining hotness metadata, wherein the hotness metadata contains a value which increases each time a segment corresponding to the metadata set is accessed, and decreases each time the segment corresponding to the metadata set is not accessed for a predetermined time period; and
selecting one or more segments of the evict

Assignees

• Emc Ip Holding Co Llc

Inventors

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

Classifications

• G06F12/122 Primary

  of the least frequently used [LFU] type, e.g. with individual count value · 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

• G06F12/123

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

• G06F2212/69

  Physics · mapped topic