Cache replacement policy for data with strong temporal locality

• US 9,779,029 B2
• Filed: 11/06/2012
• Issued: 10/03/2017
• Est. Priority Date: 11/06/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Frachtenberg, Eitan, Xu, Yuehai
• Primary Examiner(s): Farrokh, Hashem
• Assistant Examiner(s): Warren, Tracy A
• Application Number:
  US13/670,147
• Publication Number:
  US 20140129779A1
• Time in Patent Office: 1,792 Days
• Field of Search: 711133-136
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 2212/283 Plural cache memories

Abstract

Various cache replacement policies are described whose goals are to identify items for eviction from the cache that are not accessed often and to identify items stored in the cache that are regularly accessed that should be maintained longer in the cache. In particular, the cache replacement policies are useful for workloads that have a strong temporal locality, that is, items that are accessed very frequently for a period of time and then quickly decay in terms of further accesses. In one embodiment, a variation on the traditional least recently used caching algorithm uses a reuse period or reuse distance for an accessed item to determine whether the item should be promoted in the cache queue. In one embodiment, a variation on the traditional two queue caching algorithm evicts items from the cache from both an active queue and an inactive queue.

Claims

1. A method, comprising:

receiving a request for an item stored in a cache queue;

promoting the item to a specified position within the cache queue in an event the item satisfies at least one criterion of multiple criteria, wherein the multiple criteria include a reuse period of the item and a reuse distance of the item, wherein the reuse period is an elapsed time between two consecutive accesses of the item, and wherein the reuse distance is a number of different items accessed between the two consecutive accesses of the item, wherein promoting the item to the specified position includes promoting the item to a head of the cache queue; and

otherwise maintaining a location of the item in the cache queue in an event the item does not satisfy any of the reuse period and the reuse distance.

2. The method of claim 1, wherein the multiple criteria further include a second criterion, wherein the second criterion is that the item is within a threshold of a head of the cache queue.

3. The method of claim 1, wherein promoting the item to the specified position includes promoting the item by a fixed number of positions upward in the cache queue.

4. The method of claim 1, wherein the multiple criteria further include a second criterion, wherein the second criterion is that the item is outside a threshold of a head of the cache queue.

5. The method of claim 1, wherein the item is promoted upward a number of positions that is substantially inversely proportional to a latest reuse period for the item.

6. The method of claim 1, further comprising fitting reuse periods or reuse distances of the item to a function, and based on the function, determining an estimate when a next access will occur, and promoting the item in the cache queue based on the estimate.

7. The method of claim 1, further comprising:

identifying temporal access patterns of a plurality of items;

adjusting the multiple criteria based on the identified temporal access patterns.

8. The method of claim 1, further comprising:

tracking a hit rate of multiple requested items;

applying a search and optimization algorithm to adjust the multiple criteria to increase the hit rate.

9. The method of claim 1, further comprising:

maintaining a cost function based on miss penalty information, wherein a promotion of the requested item within the cache queue of the requested item is based on miss penalty information for the item.

10. The method of claim 1, further comprising:

identifying whether an existing item in the cache queue has spatial locality with a family of one or more other items,

wherein in an event the existing item is to be evicted from a tail of the cache queue, and the existing item has spatial locality with the family of one or more other items near a head of the cache queue, the existing item is promoted within the cache queue, and

wherein in an event the existing item is promoted within the cache queue, the family of one or more other items with which the requested item has spatial locality are also promoted within the cache queue.

11. A method, comprising:

maintaining an active queue and an inactive queue in a cache, the active queue having a first plurality of items, the inactive queue having a second plurality of items;

receiving a request for an item;

placing the requested item within the inactive queue of the cache in an event requested item is not already stored in the active queue or the inactive queue of the cache;

moving the requested item to a head of the active queue in an event the requested item is already stored in the inactive queue;

promoting the requested item to a specified position within the active queue of the cache in an event the requested item is already stored in the active queue; and

evicting an existing item from the cache, wherein the existing item is selected for eviction from;

a tail of the active queue in an event a ratio of a length of the active queue to the inactive queue exceeds a specified range, the existing item evicted from the cache without further being stored in the inactive queue, and

a tail of the inactive queue in an event the ratio is below the specified range.

12. The method of claim 11, further comprising:

maintaining a recycle bit for each item in the cache, wherein the recycle bit is initially unset,

wherein in an event the tail item of the inactive queue is selected to be evicted and the recycle bit for the tail item is unset, the recycle bit is set and the item is promoted within the inactive queue, and

further wherein in an event the recycle bit for the tail item is set, the tail item is evicted.

13. The method of claim 11, further comprising setting a recycle bit of each item in the active queue.

14. The method of claim 11, further comprising:

maintaining a reuse period of each item in the cache;

wherein the reuse period is an elapsed time between two consecutive accesses of the item; and

wherein the reuse period is used to determine the position within the active queue to which the requested item that is already stored in the cache is promoted.

15. The method of claim 11, further comprising:

maintaining a cost function based on miss penalty information, wherein a promotion location of the requested item in the cache is based on miss penalty information for the item.

16. The method of claim 11, further comprising:

maintaining a reuse distance of each item in the cache;

wherein the reuse distance is a number of different items accessed between two consecutive accesses of the item; and

wherein the reuse distance is used to determine the position within the active queue to which the requested item that is already stored in the cache is promoted.

17. The method of claim 11, further comprising:

identifying whether the requested item has spatial locality with a family of one or more other items;

in an event the requested item is selected to be evicted from the cache, and the requested item has spatial locality with the family of one or more other items near a head of the active queue or of the inactive queue, recycling the requested item to stay in the cache; and

in an event the requested item is promoted within the active queue or the inactive queue, promoting the family of one or more other items with which the requested item has spatial locality.

18. A non-transitory computer readable storage medium storing instructions, comprising:

instructions for receiving a request for an item stored in a cache queue, the cache queue including an active queue and an inactive queue, the active queue having a first plurality of items, the inactive queue having a second plurality of items;

instructions for promoting the requested item to a head of the cache queue in an event the requested item satisfies a criterion and is in the active queue, the head of the cache queue being within the active queue of the cache queue, wherein the cache queue is configured to evict one of the first plurality of items from the active queue without further being stored in the inactive queue, wherein the cache queue is configured to evict a specified item from the active queue or the inactive queue based on a ratio of the length of the active queue to the inactive queue;

instructions for moving the requested item to the head of the active queue in an event the requested item is already stored in the inactive queue;

instructions for associating every item in the cache queue with a recycle bit, wherein the recycle bit associated with each item is initially unset at zero;

instructions for determining, in an event a tail item of the cache queue is to be evicted, whether the recycle bit for the tail item has been set; and

instructions for, in an event the recycle bit for the tail item has not been set;

setting the recycle bit for the tail item; and

promoting the tail item to a head of the inactive queue of the cache queue; and

instructions for evicting the tail item from the cache queue in an event the recycle bit for the tail item has been set.

19. The non-transitory computer readable storage medium of claim 18, wherein the criterion is that the requested item is within a threshold distance of the head of the cache queue, wherein a portion of the cache queue in the threshold distance is the active queue of the cache queue.

20. The non-transitory computer readable storage medium of claim 18, further comprising:

instructions for placing the requested item within the inactive queue of the cache queue in an event the requested item is not already stored in either the active queue or the inactive queue of the cache queue;

instructions for inserting the requested item in the active queue of the cache queue in an event the requested item is already stored in the cache queue; and

instructions for maintaining the ratio within the specified range by evicting an existing item from the cache queue, wherein the existing item is evicted from the active queue in an event the ratio exceeds the specified range and from the inactive queue in an event the ratio is below the specified range.