Memory cache entry management with pinned cache entries

Patent metadata

Field	Value
Publication number	US-11599462-B1
Application number	US-202117518467-A
Country	US
Kind code	B1
Filing date	Nov 3, 2021
Priority date	Nov 3, 2021
Publication date	Mar 7, 2023
Grant date	Mar 7, 2023

Abstract

Methods and systems for memory cache entry replacement with pinned cache entries. Data structures are maintained for tracking a state of entries of a memory cache. A first data structure includes identifiers for pinned entries of a memory cache. A second data structure includes identifiers for unpinned entries of the memory cache that have been accessed once. A third data structure includes identifiers for unpinned entries of the memory cache that have been accessed more than once. A request to pin an entry is received. A determination is made that an identifier associated with the entry to pin is included in the second data structure or the third data structure. The identifier associated with the pinned entry is added to the first data structure. A detection is made at a time period that one or more entries of the memory cache are to be removed from the memory cache in accordance with an eviction protocol. Identifiers of one or more unpinned entries with state data that satisfies an eviction criterion associated with the eviction protocol are selected from the second data structure and/or the third data structure. The one or more unpinned entries are removed from the memory cache while the pinned entry with corresponding state data is maintained in the memory cache.

First claim

What is claimed is:

1. A method comprising:
maintaining a plurality of data structures configured to track a state of entries of a memory cache, wherein a first data structure of the plurality of data structures comprises identifiers for pinned entries of a memory cache, a second data structure of the plurality of data structures comprises identifiers for unpinned entries of the memory cache that have been accessed once, and a third data structure of the plurality of data structures comprises identifiers for unpinned entries of the memory cache that have been accessed more than once;
receiving a request to pin an entry;
determining that an identifier associated with the entry to pin is included in the second data structure or the third data structure;
adding the identifier associated with the pinned entry to the first data structure;
detecting, at a time period, that one or more entries of the memory cache are to be removed from the memory cache in accordance with an eviction protocol;
selecting, from at least one of the second data structure or the third data structure, one or more identifiers of one or more unpinned entries with state data that satisfies an eviction criterion associated with the eviction protocol, wherein the state data of the one or more unpinned entries corresponds to state data of the pinned entry; and
removing the one or more unpinned entries from the memory cache while maintaining the pinned entry in the memory cache.

2. The method of claim 1 , wherein the first data structure is configured to store identifiers for pinned entries that have been accessed once, and wherein the identifier associated with the pinned entry is added to the first data structure responsive to determining that the identifier associated with the entry is included in the second data structure.

3. The method of claim 2 , wherein the plurality of data structures further comprises a fourth data structure comprising identifiers for pinned entries of the memory cache that have been accessed more than once, and wherein the method further comprises:
responsive to determining that the pinned entry added to the first data structure has been accessed more than once, moving the identifier associated with the pinned entry from the first data structure to the fourth data structure.

4. The method of claim 1 , wherein the first data structure is configured to store identifiers for pinned entries that have been accessed more than once, and wherein the identifier associated with the pinned entry is added to the first data structure responsive to determining that the identifier associated with the entry is included in the third data structure.

5. The method of claim 1 , further comprising:
receiving a request to unpin the entry;
identifying a slot in the second data structure or the third data structure to add the identifier associated with the entry; and
moving the identifier associated with the entry from the first data structure to the identified slot of the second data structure or the third data structure.

6. The method of claim 5 , further comprising:
determining that the state data of the entry satisfies the eviction criterion; and
removing the entry from the memory cache.

7. The method of claim 1 , wherein the state data of the one or more unpinned entries and the state data of the pinned entry correspond to an amount of time that has passed since the corresponding entry has been referenced.

8. The method of claim 7 , wherein the state data satisfies the eviction criterion in response to the amount of time that has passed since the corresponding entry has been accessed exceeding a threshold amount of time.

9. The method of claim 1 , wherein the eviction protocol corresponds to at least one of a least recently accessed eviction protocol or a least frequently accessed eviction protocol.

10. A system comprising:
a memory device; and
a processing device coupled to the memory device, the processing device to perform operations comprising:
maintaining a plurality of data structures configured to track a state of entries of a memory cache, wherein a first data structure of the plurality of data structures comprises identifiers for pinned entries of a memory cache, a second data structure of the plurality of data structures comprises identifiers for unpinned entries of the memory cache that have been accessed once, and a third data structure of the plurality of data structures comprises identifiers for unpinned entries of the memory cache that have been accessed more than once;
receiving a request to pin an entry;
determining that an identifier associated with the entry to pin is included in the second data structure or the third data structure;
adding the identifier associated with the pinned entry to the first data structure;
detecting, at a time period, that one or more entries of the memory cache are to be removed from the memory cache in accordance with an eviction protocol;
selecting, of at least one of the second data structure or the third data structure, one or more identifiers of one or more unpinned entries with state data that satisfies an eviction criterion associated with the eviction protocol, wherein the state data of the one or more unpinned entries corresponds to state data of the pinned entry; and
removing the one or more unpinned entries from the memory cache while maintaining the pinned entry in the memory cache.

11. The system of claim 10 , wherein the first data structure is configured to store identifiers for pinned entries that have been accessed once, and wherein the identifier associated with the pinned entry is added to the first data structure responsive to determining that the identifier associated with the entry is included in the second data structure.

12. The system of claim 11 , wherein the plurality of data structures further comprises a fourth data structure comprising identifiers for pinned entries of the memory cache that have been accessed more than once, and wherein the operations further comprise:
responsive to determining that the pinned entry added to the first data structure has been accessed more than once, moving the identifier associated with the pinned entry from the first data structure to the fourth data structure.

13. The system of claim 10 , wherein the first data structure is configured to store identifiers for pinned entries that have been accessed more than once, and wherein the identifier associated with the pinned entry is added to the first data structure responsive to determining that the identifier associated with the entry is included in the third data structure.

14. The system of claim 10 , wherein the operations further comprise:
receiving a request to unpin the entry;
identifying a slot in the second data structure or the third data structure to add the identifier associated with the entry; and
moving the identifier associated with the entry from the first data structure to the identified slot of the second data structure or the third data structure.

15. The system of claim 14 , wherein the operations further comprise:
determining that the state data of the entry satisfies the eviction criterion; and
removing the entry from the memory cache.

16. A non-transitory computer readable storage medium comprising instructions for a server that, when executed by a processing device, cause the processing device to perform operations comprising:
maintaining a plurality of data structures configured to track a state of entries of a memory cache, wherein a first data structure of the plurality of data structures comprises identifiers

Assignees

• Google Llc

Inventors

• Hawkins Amalia

Classifications

• 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

• G06F2212/60

  Details of cache memory · CPC title

• G06F12/126 Primary

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