Ghost list cache eviction

Patent metadata

Field	Value
Publication number	US-11669449-B1
Application number	US-202117457000-A
Country	US
Kind code	B1
Filing date	Nov 30, 2021
Priority date	Nov 30, 2021
Publication date	Jun 6, 2023
Grant date	Jun 6, 2023

Abstract

One example method includes a cache eviction operation. Entries in a cache are maintained in an entry list that includes a recent list, a recent ghost list, a frequent list, and a frequent ghost list. When an eviction operation is initiated or triggered, timestamps of last access for the entries in the entry list are adjusted by corresponding adjustment values. Candidate entries for eviction are identified based on the adjusted timestamps of last access. At least some of the candidates are evicted from the cache.

First claim

What is claimed is:

1. A method, comprising:
initiating a cache eviction operation for a cache, wherein entries associated with the cache are identified in an entry list that includes a recent list, a recent ghost list, a frequent list, and a frequent ghost list;
generating an adjusted characteristic for each entry in the entry list;
identifying candidate entries for eviction from the cache based at least on the adjusted characteristics of the entries compared to a time threshold; and
evicting at least one of the identified candidate entries from the cache based on the comparisons.

2. The method of claim 1 , wherein the characteristic is a timestamp of last access, further comprising adjusting the timestamp of last access of each entry by an adjustment value to generate an adjusted timestamp for each entry, wherein the adjusted characteristics comprise the adjusted timestamps.

3. The method of claim 2 , wherein the adjustment value for different entries is different.

4. The method of claim 2 , wherein the adjustment values for entries in the recent list are different from adjustment values in the recent ghost list and wherein adjustment values for entries in the frequent list are different from adjustment values in the frequent ghost list.

5. The method of claim 4 , wherein the adjustment values for entries in the frequent list are larger than the adjustment values for entries in the recent list.

6. The method of claim 4 , wherein the adjustment values for entries near a top of the recent list are greater than the adjustment values for entries further from the top of the recent list and wherein the adjustment values for entries near a top of the frequent list are greater than the adjustment values for entries further from the top of the frequent list.

7. The method of claim 4 , wherein the adjustments values for entries in the recent list decrease by a constant value moving from a top of the recent list to a bottom of the recent list, wherein the adjustment values for entries in the recent ghost list decrease by a second constant value, wherein the adjustments values for entries in the frequent list decrease by a third constant value moving from a top of the frequent list to a bottom of the frequent list, and wherein adjustment values for entries in the frequent ghost list decrease by a fourth constant value.

8. The method of claim 1 , wherein the first, second, third, and fourth constant values can be the all the same, partially the same, or all different.

9. The method of claim 1 , further comprising operating the cache, wherein the cache includes an entry list having a recent list and a frequent list, by:
adding new entries to a top of the recent list;
moving entries in the recent list that are accessed a second time to a top of the frequent list; and
moving entries in the frequent list that are accessed another time to the top of the frequent list.

10. The method of claim 1 , further comprising storing, for each entry, a recency value and a frequency value.

11. A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
initiating a cache eviction operation for a cache, wherein entries associated with the cache are identified in an entry list that includes a recent list, a recent ghost list, a frequent list, and a frequent ghost list;
generating an adjusted characteristic for each entry in the entry list;
identifying candidate entries for eviction from the cache based at least on the adjusted characteristics of the entries compared to a time threshold; and
evicting at least one of the identified candidate entries from the cache.

12. The non-transitory storage medium of claim 11 , wherein the characteristic is a timestamp of last access, further comprising adjusting the timestamp of last access of each entry by an adjustment value to generate an adjusted timestamp for each entry, wherein the adjusted characteristics comprise the adjusted timestamps.

13. The non-transitory storage medium of claim 12 , wherein the adjustment value for different entries is different.

14. The non-transitory storage medium of claim 12 , wherein the adjustment values for entries in the recent list are different from adjustment values in the recent ghost list and wherein adjustment values for entries in the frequent list are different from adjustment values in the frequent ghost list.

15. The non-transitory storage medium of claim 14 , wherein the adjustment values for entries in the frequent list are larger than the adjustment values for entries in the recent list.

16. The non-transitory storage medium of claim 14 , wherein the adjustment values for entries near a top of the recent list are greater than the adjustment values for entries further from the top of the recent list and wherein the adjustment values for entries near a top of the frequent list are greater than the adjustment values for entries further from the top of the frequent list.

17. The non-transitory storage medium of claim 14 , wherein the adjustments values for entries in the recent list decrease by a constant value moving from a top of the recent list to a bottom of the recent list, wherein the adjustment values for entries in the recent ghost list decrease by a second constant value, wherein the adjustments values for entries in the frequent list decrease by a third constant value moving from a top of the frequent list to a bottom of the frequent list, and wherein adjustment values for entries in the frequent ghost list decrease by a fourth constant value.

18. The non-transitory storage medium of claim 11 , wherein the first, second, third, and fourth constant values can be the all the same, partially the same, or all different.

19. The non-transitory storage medium of claim 11 , further comprising operating the cache, wherein the cache includes an entry list having a recent list and a frequent list, by:
adding new entries to a top of the recent list;
moving entries in the recent list that are accessed a second time to a top of the frequent list; and
moving entries in the frequent list that are accessed another time to the top of the frequent list.

20. The non-transitory storage medium of claim 11 , further comprising storing, for each entry, a recency value and a frequency value.

Assignees

• Dell Products Lp

Inventors

• Desai Keyur B
• Zhang Xiaobing

Classifications

• G06F2212/60

  Details of cache memory · CPC title

• G06F12/0802 Primary

  Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches · CPC title

• G06F12/123 Primary

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

• G06F12/126

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

• G06F2212/1016

  Performance improvement · CPC title