Methods for cache insertion using ghost lists

Patent metadata

Field	Value
Publication number	US-12461856-B2
Application number	US-202418641529-A
Country	US
Kind code	B2
Filing date	Apr 22, 2024
Priority date	Feb 9, 2022
Publication date	Nov 4, 2025
Grant date	Nov 4, 2025

Abstract

A reverse cache for inserting data into 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.

First claim

What is claimed is:

1 . A computing system comprising:
a processor; and a reverse cache configured to promote entries to a main cache based on recency and/or frequency, the reverse cache comprising:
a recency portion; and
a frequency portion,
wherein the recency portion and the frequency portion each store entries that are each a first representation of a corresponding data, wherein the recency portion stores entries for data that has been accessed a single time and wherein the frequency portion stores entries for data that has been accessed multiple times, wherein a size of each first representation is smaller than a size of the corresponding data.

2 . The computing system of claim 1 , wherein the recency portion comprises a recent list and a ghost recent list and the frequency portion comprises a frequent list and a ghost frequent list, wherein sizes of the recent list, the ghost recent list, the frequent list, and the ghost frequent list can vary during operation of the reverse cache, wherein entries in the recent list and the frequent list include the first representations and entries in the ghost recent list and the ghost frequent list include second representations of data that corresponds to the entries in the ghost recent list and the ghost frequent list.

3 . The computing system of claim 2 , wherein the reverse cache has a fixed size.

4 . The computing entry of claim 2 , wherein each first representation is a fingerprint and each second representation is an index value.

5 . The computing system of claim 1 , wherein the reverse cache is implemented in a portion of the main cache.

6 . The computing system of claim 1 , wherein the recency portion includes a recent list and a ghost recent list, wherein entries in the recent list and the ghost recent list have been accessed a single time.

7 . The computing system of claim 6 , wherein a new entry for data accessed for a first time is entered into the recent list, wherein other entries in the recent list are shifted towards the ghost recent list, wherein an oldest entry in the recent list is moved from the recent list to the ghost recent list if necessary, wherein an oldest entry in the ghost recent list is evicted from the reverse cache if necessary to accommodate the new entry accessed for the first time.

8 . The computing system of claim 7 , wherein the frequency portion comprises a frequent list and a ghost frequent list, wherein, when accessing the data associated with the new entry a second time, the new entry is moved to the ghost frequent list, wherein accessing the new entry additional times causes the new entry to be moved within the frequency portion based on contents of the frequent list and the ghost frequent list.

9 . The computing system of claim 8 , wherein a candidate entry from the frequency portion is promoted to the main cache based on operation of the reverse cache.

10 . The computing system of claim 8 , wherein a particular entry from the frequency portion is promoted to the main cache when data corresponding to the particular entry is accessed a threshold number of times.

11 . The computing entry of claim 1 , further comprising, when the reverse cache is full and new entry is received, evicting an entry from the reverse cache or promoting an entry from the reverse cache to the main cache.

12 . A computing system comprising:
a processor; and a reverse cache configured to promote entries to a main cache based on recency and/or frequency, the reverse cache comprising:
a recency portion that includes a recent list and a ghost recent list; and
a frequency portion that includes a frequent list and a ghost frequent list,
wherein the recent list and the frequent list each store entries that are each a first representation of a corresponding data and the ghost recent list and the ghost frequent list each store entries that are each a second representation of a corresponding data, wherein a size of the second representation is smaller than a size of the first representation.

13 . The computing entry of claim 12 , wherein each first representation is a fingerprint and each second representation is an index value.

14 . The computing system of claim 12 , wherein the reverse cache has a fixed size and is implemented in a portion of the main cache.

15 . The computing system of claim 12 , wherein a new entry for data accessed for a first time is entered into the recency portion, wherein other entries in the recency portion moved to accommodate the new entry, wherein an oldest entry in the recency portion is evicted from the reverse cache if necessary to accommodate the new entry accessed for the first time.

16 . The computing system of claim 15 , wherein, when accessing the data associated with the new entry a second time, the new entry is moved to the frequency portion, wherein accessing the new entry additional times causes the new entry to be moved within the frequency portion.

17 . The computing system of claim 16 , wherein a candidate entry from the frequency portion is promoted to the main cache based on operation of the reverse cache.

18 . The computing system of claim 16 , wherein a particular entry from the frequency portion is promoted to the main cache when data corresponding to the particular entry is accessed a threshold number of times.

19 . The computing system of claim 12 , wherein entries are promoted to the main cache using a combination of when data associated with the entries was accessed and a frequency or number of times data associated with entries was accessed.

Assignees

• Dell Products Lp

Inventors

• Desai Keyur B

Classifications

• G06F2212/60

  Details of cache memory · CPC title

• G06F2212/502

  using adaptive policy · CPC title

• G06F2212/1016

  Performance improvement · CPC title

• G06F12/127

  using additional replacement algorithms · CPC title

• G06F12/122

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