Method for optimized cache insertion

Patent metadata

Field	Value
Publication number	US-12105626-B2
Application number	US-202217650407-A
Country	US
Kind code	B2
Filing date	Feb 9, 2022
Priority date	Feb 9, 2022
Publication date	Oct 1, 2024
Grant date	Oct 1, 2024

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, which are representations of 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 method, comprising:
identifying a request for a data;
determining whether an identifier for the requested data is present in a reverse cache, wherein the reverse cache stores a set of identifiers corresponding to a set of data, the reverse cache does not store the set of data, and a main cache is configured to store the set of data;
adding the identifier for the requested data to the reverse cache as an entry in the reverse cache when the identifier is not present in the reverse cache, wherein the entry is adjusted in the reverse cache when the identifier is present in the reverse cache; and
promoting a candidate entry from the reverse cache to the main cache.

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

3. The method of claim 2 , wherein the recent list includes entries that have been accessed a single time and the frequent list includes entries that have been accessed more than once.

4. The method of claim 1 , wherein the reverse cache comprises a recent list and a frequent list, further comprising, when the entry is present in the reverse cache, adjusting a position of the entry in the frequent list when the entry is in the frequent list.

5. The method of claim 1 , wherein the candidate entry has been accessed more than once and is in a frequent list.

6. The method of claim 5 , further comprising inserting data corresponding to the candidate entry into the main cache.

7. The method of claim 6 , further comprising evicting an old entry from the reverse cache without adding data corresponding to the old entry to the main cache.

8. The method of claim 7 , wherein the old entry is an oldest entry in a recent list and has only been accessed once.

9. The method of claim 1 , further comprising setting a threshold value of access times, wherein the candidate entry is promoted when a number of accesses of the candidate entry satisfies the threshold value or when promotion is needed to add the entry to the reverse cache.

10. The method of claim 1 , wherein the reverse cache is smaller than the main cache.

11. A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
identifying a request for a data;
determining whether an identifier for the requested data is present in a reverse cache, wherein the reverse cache stores a set of identifiers corresponding to a set of data, the reverse cache does not store the set of data, and a main cache is configured to store the set of data;
adding the identifier for the requested data to the reverse cache as an entry in the reverse cache when the identifier is not present in the reverse cache, wherein the entry is adjusted in the reverse cache when the identifier is present in the reverse cache; and
promoting a candidate entry from the reverse cache to the main cache.

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

13. The non-transitory storage medium of claim 12 , wherein the recent list includes entries that have been accessed a single time and the frequent list includes entries that have been accessed more than once.

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

15. The non-transitory storage medium of claim 11 , wherein the candidate entry has been accessed more than once and is in a frequent list.

16. The non-transitory storage medium of claim 15 , further comprising inserting data corresponding to the candidate entry into the main cache.

17. The non-transitory storage medium of claim 16 , further comprising evicting an old entry from the reverse cache without adding data corresponding to the old entry to the main cache.

18. The non-transitory storage medium of claim 17 , wherein the old entry is an oldest entry in a recent list and has only been accessed once.

19. The non-transitory storage medium of claim 11 , further comprising setting a threshold value of access times, wherein the candidate entry is promoted when a number of accesses of the candidate entry satisfies the threshold value or when promotion is needed to add the entry to the reverse cache.

20. The non-transitory storage medium of claim 11 , wherein the reverse cache is smaller than the main cache.

Assignees

• Dell Products Lp

Inventors

• Desai Keyur B

Classifications

• G06F2212/60

  Details of cache memory · CPC title

• G06F2212/1016

  Performance improvement · CPC title

• G06F2212/502

  using adaptive policy · CPC title

• G06F12/0848

  Partitioned cache, e.g. separate instruction and operand caches · CPC title

• G06F12/127

  using additional replacement algorithms · CPC title