Methods for cache insertion and cache eviction in a cache system that includes a reverse cache and a main cache

Patent metadata

Field	Value
Publication number	US-12105639-B2
Application number	US-202217663809-A
Country	US
Kind code	B2
Filing date	May 17, 2022
Priority date	May 17, 2022
Publication date	Oct 1, 2024
Grant date	Oct 1, 2024

Abstract

A cache system that includes a reverse cache and a main cache is disclosed. The reverse cache is configured to identify candidates for insertion into a main cache. The reverse cache stores entries such as fingerprints and index values, which are representations of or that identify data. When the entry has been accessed multiple times or is a candidate for promotion based on operation of the reverse cache, data corresponding to the entry is promoted to the main cache. The main cache is configured to evict entries using recency, frequency, and time-adjustments. The main cache and the reverse cache may be similarly configured with a recent list and a frequent list but operate differently.

First claim

What is claimed is:

1. A method, comprising:
operating a reverse cache that is configured to identify data to insert into a main cache, wherein operating the reverse cache includes:
determining whether an entry for a requested data is present in a reverse cache;
adding the entry for the requested data to the reverse cache when the entry is not present in the reverse cache, wherein the entry is adjusted in the reverse cache when the entry is present in the reverse cache;
promoting a candidate entry from the reverse cache to the main cache; and
evicting entries from the main cache based on metadata associated with each entry in the main cache, wherein the metadata includes a recency value, a frequency value, a timestamp, and an adjusted timestamp, wherein evicting entries from the main cache further comprises adjusting timestamps of each of the entries to generate adjusted timestamps for each of the entries.

2. The method of claim 1 , wherein the reverse cache comprises a frequent list and a frequency list, further comprising, when the entry is present in the reverse cache, moving the entry to the frequent list when the entry is in a recent list.

3. The method of claim 2 , wherein the candidate entry promoted to the main cache is in the frequent list.

4. The method of claim 3 , further comprising evicting an entry from the recent list of the reverse cache after a period of time and when the entry is not accessed a second time.

5. The method of claim 4 , further comprising promoting the entry to the main cache after the entry is moved to the frequent list and becomes the candidate entry for promotion to the main cache.

6. The method of claim 3 , further comprising moving the entry to from the recent list to the frequent list when the entry is in the recent list and is accessed a second time.

7. The method of claim 1 , wherein the main cache and the reverse cache each comprise lists, the lists including a recent list and a frequency list, wherein the lists of the reverse cache are operated differently from the lists of the main cache.

8. The method of claim 7 , wherein entries in the recent list are moved to the frequent list when accessed a second time for each of the reverse cache and the main cache.

9. The method of claim 1 , wherein the entry is the candidate entry.

10. A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
operating a reverse cache that is configured to identify data to insert into a main cache, wherein operating the reverse cache includes:
determining whether an entry for a requested data is present in a reverse cache;
adding the entry for the requested data to the reverse cache when the entry is not present in the reverse cache, wherein the entry is adjusted in the reverse cache when the entry is present in the reverse cache;
promoting a candidate entry from the reverse cache to the main cache; and
evicting entries from the main cache based on metadata associated with each entry in the main cache, wherein the metadata includes a recency value, a frequency value, a timestamp, and an adjusted timestamp, wherein evicting entries from the main cache further comprises adjusting timestamps of each of the entries to generate adjusted timestamps for each of the entries.

11. The non-transitory storage medium of claim 10 , wherein the reverse cache comprises a frequent list and a frequency list, further comprising, when the entry is present in the reverse cache, moving the entry to the frequent list when the entry is in a recent list.

12. The non-transitory storage medium of claim 11 , wherein the candidate entry promoted to the main cache is in the frequent list.

13. The non-transitory storage medium of claim 12 , further comprising evicting an entry from the recent list of the reverse cache after a period of time and when the entry is not accessed a second time.

14. The non-transitory storage medium of claim 13 , further comprising promoting the entry to the main cache after the entry is moved to the frequent list and becomes the candidate entry for promotion to the main cache.

15. The non-transitory storage medium of claim 12 , further comprising moving the entry to from the recent list to the frequent list when the entry is in the recent list and is accessed a second time.

16. The non-transitory storage medium of claim 10 , wherein the main cache and the reverse cache each comprise lists, the lists including a recent list and a frequency list, wherein the lists of the reverse cache are operated differently from the lists of the main cache.

17. The non-transitory storage medium of claim 16 , wherein entries in the recent list are moved to the frequent list when accessed a second time for each of the reverse cache and the main cache.

18. The non-transitory storage medium of claim 10 , wherein the entry is the candidate entry.

Assignees

• Dell Products Lp

Inventors

• Desai Keyur B

Classifications

• G06F12/123

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

• G06F12/0891

  using clearing, invalidating or resetting means · CPC title

• G06F2212/1016

  Performance improvement · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F12/0888

  using selective caching, e.g. bypass · CPC title