High performance cache eviction

Patent metadata

Field	Value
Publication number	US-12019542-B2
Application number	US-202217882802-A
Country	US
Kind code	B2
Filing date	Aug 8, 2022
Priority date	Aug 8, 2022
Publication date	Jun 25, 2024
Grant date	Jun 25, 2024

Abstract

Aspects of the disclosure are directed to high performance connection cache eviction for reliable transport protocols in data center networking. Connection priorities for connection entries are determined to store the connection entries in a cache based on their connection priority. During cache eviction, the connection entries with a lowest connection priority are evicted from the cache. Cache eviction can be achieved with low latency at a high rate.

First claim

The invention claimed is:

1. A method for evicting connection entries from a cache, the method comprising:
determining, with one or more processors, a connection priority for each of a plurality of connection entries based on a likelihood of receiving a transaction for each of the connection entries;
storing, with the one or more processors, each of the plurality of connection entries in at least one of a plurality of priority queues in the cache based on the determined connection priority for each connection entry; and
evicting, with the one or more processors, a connection entry of the plurality of connection entries from a priority queue of the plurality of priority queues when an occupancy of the cache is above an eviction threshold, the connection entry being evicted having a lowest determined connection priority.

2. The method of claim 1 , wherein the likelihood of receiving the transaction is based on a resource count and a recency of receiving a previous transaction.

3. The method of claim 2 , wherein the resource count comprises an amount of outstanding transactions.

4. The method of claim 2 , wherein determining the connection priority for each of the plurality of connection entries further comprises:
determining, with the one or more processors, an initial connection priority for a connection entry of the plurality of connection entries based on a resource count; and
reducing, with the one or more processors, the initial connection priority based on the recency of receiving a previous transaction to determine the connection priority for the connection entry.

5. The method of claim 1 , further comprising updating, with the one or more processors, the connection priority of at least one connection entry of the plurality of connection entries.

6. The method of claim 5 , wherein updating the connection priority of the at least one connection entry comprises moving the at least one connection entry from its existing slot in a respective priority queue to a tail of the same priority queue.

7. The method of claim 5 , wherein updating the connection priority of the connection entry comprises moving the connection entry from its existing slot in a respective priority queue to a tail of a different priority queue.

8. The method of claim 1 , further comprising pushing, with the one or more processors, a new connection entry to a tail of at least one of the plurality of priority queues based on a determined priority for the new connection entry.

9. The method of claim 1 , wherein storing the plurality of connection entries further comprises storing lower priority connection entries closer to a head of at least one of the plurality of priority queues and higher priority connection entries closer to a tail of at least one of the plurality of priority queues.

10. The method of claim 9 , wherein evicting the connection entry further comprises evicting a connection entry from a head of the priority queue.

11. A system comprising:
one or more processors; and
one or more storage devices coupled to the one or more processors and storing instructions that, when executed by the one or more processors, causes the one or more processors to perform operations for evicting connection entries from a cache, the operations comprising:
determining a connection priority for each of a plurality of connection entries based on a likelihood of receiving a transaction for each of the connection entries;
storing each of the plurality of connection entries in at least one of a plurality of priority queues in the cache based on the determined connection priority for each connection entry; and
evicting a connection entry of the plurality of connection entries from a priority queue of the plurality of priority queues when an occupancy of the cache is above an eviction threshold, the connection entry being evicted having a lowest determined connection priority.

12. The system of claim 11 , wherein the likelihood of receiving the transaction is based on a resource count and a recency of receiving a previous transaction, the resource count comprising an amount of outstanding transactions.

13. The system of claim 12 , wherein determining the connection priority for each of the plurality of connection entries further comprises:
determining an initial connection priority for a connection entry of the plurality of connection entries based on a resource count; and
reducing the initial connection priority based on the recency of receiving a previous transaction to determine the connection priority for the connection entry.

14. The system of claim 11 , wherein the operations further comprise updating the connection priority of at least one connection entry of the plurality of connection entries.

15. The system of claim 14 , wherein updating the connection priority of the at least one connection entry comprises moving the at least one connection entry from its existing slot in a respective priority queue to a tail of the same priority queue.

16. The system of claim 14 , wherein updating the connection priority of the connection entry comprises moving the connection entry from its existing slot in a respective priority queue to a tail of a different priority queue.

17. The system of claim 11 , wherein the operations further comprise pushing a new connection entry to a tail of at least one of the plurality of priority queues based on a determined priority for the new connection entry.

18. The system of claim 11 , wherein storing the plurality of connection entries further comprises storing lower priority connection entries closer to a head of at least one of the plurality of priority queues and higher priority connection entries closer to a tail of at least one of the plurality of priority queues.

19. The system of claim 18 , wherein evicting the connection entry further comprises evicting a connection entry from a head of the priority queue.

20. A non-transitory computer readable medium for storing instructions that, when executed by one or more processors, causes the one or more processors to perform operations for evicting connection entries from a cache, the operations comprising:
determining a connection priority for each of a plurality of connection entries based on a likelihood of receiving a transaction for each of the connection entries;
storing each of the plurality of connection entries in at least one of a plurality of priority queues in the cache based on the determined connection priority for each connection entry; and
evicting a connection entry of the plurality of connection entries from a priority queue of the plurality of priority queues when an occupancy of the cache is above an eviction threshold, the connection entry being evicted having a lowest determined connection priority.

Assignees

• Google Llc

Inventors

• Agarwal Abhishek
• Zheng Jiazhen
• Vaduvatha Srinivas
• Wang Weihuang
• Walsh Hugh Mcevoy
• Jiang Weiwei
• Venkatesan Ajay
• Chandra Prashant R

Classifications

• G06F2212/60

  Details of cache memory · CPC title

• G06F12/126

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

• H04L67/5682

  Policies or rules for updating, deleting or replacing the stored data · CPC title

• 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

• G06F12/123 Primary

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