Ghost list cache eviction

Patent metadata

Field	Value
Publication number	US-12386744-B2
Application number	US-202318327493-A
Country	US
Kind code	B2
Filing date	Jun 1, 2023
Priority date	Nov 30, 2021
Publication date	Aug 12, 2025
Grant date	Aug 12, 2025

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, each of the entries having a timestamp of last access;
generating an adjusted characteristic for each entry in the entry list, the adjusted characteristic is an adjusted timestamp of last access, the adjusted timestamp of last access of each entry being determined by adding an adjustment value to the timestamp of last access, wherein the adjustment value for different entries is different;
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 generating an adjusted characteristic includes giving entries that are most frequently used and/or most recently used a longer time to live in the cache.

3. The method of claim 1 , wherein the entry list comprises a recent list, a recent ghost list, a frequent list, and a frequent ghost list, 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.

4. The method of claim 3 , further comprising evicting an entry from the recent ghost list or the frequent ghost list.

5. The method of claim 4 , further comprising reordering entries in the frequent list and the frequent list based on number of times the entries are accessed.

6. 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.

7. The method of claim 3 , further comprising operating the cache, wherein the entry list includes 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.

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

9. The method of claim 8 , wherein the frequency value is not affected by the adjustment characteristic.

10. The method of claim 1 , wherein the adjustment characteristic prevents at least one of the entries from being a candidate for eviction based when evicting using time-based eviction operations.

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, each of the entries having a timestamp of last access;
generating an adjusted characteristic for each entry in the entry list, the adjusted characteristic is an adjusted timestamp of last access, the adjusted timestamp of last access of each entry being determined by adding an adjustment value to the timestamp of last access, wherein the adjustment value for different entries is different;
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.

12. The non-transitory storage medium of claim 11 , wherein generating an adjusted characteristic includes giving entries that are most frequently used and/or most recently used a longer time to live in the cache.

13. The non-transitory storage medium of claim 11 , wherein the entry list comprises a recent list, a recent ghost list, a frequent list, and a frequent ghost list, 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.

14. The non-transitory storage medium of claim 3 , further comprising evicting an entry from the recent ghost list or the frequent ghost list.

15. The non-transitory storage medium of claim 13 , further comprising reordering entries in the frequent list and the frequent list based on number of times the entries are accessed.

16. The non-transitory storage medium of claim 13 , 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.

17. The non-transitory storage medium of claim 14 , further comprising operating the cache, wherein the entry list includes 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.

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

19. The non-transitory storage medium of claim 18 , wherein the frequency value is not affected by the adjustment characteristic.

20. The non-transitory storage medium of claim 11 , wherein the adjustment characteristic prevents at least one of the entries from being a candidate for eviction based when evicting using time-based eviction operations.

Assignees

• Dell Products Lp

Inventors

• Desai Keyur B
• Zhang Xiaobing

Classifications

• G06F2212/60

  Details of cache memory · CPC title

• G06F12/122

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

• G06F2212/502

  using adaptive policy · CPC title

• G06F2212/1016

  Performance improvement · CPC title

• G06F12/126

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