CACHE REPLACEMENT POLICY FOR DATA WITH STRONG TEMPORAL LOCALITY

• US 20140129779A1
• Filed: 11/06/2012
• Published: 05/08/2014
• 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
• Granted Patent: US 9,779,029 B2
• Time in Patent Office: Days
• US Class Current: 711/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 within the cache queue if the item satisfies a criterion;

otherwise maintaining a location of the item in the cache queue.

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

3. The method of claim 1, wherein the item is promoted to a head of the queue or promoted a fixed number of positions upward in the queue.

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

5. The method of claim 1, wherein the criterion is based on a reuse period or a reuse distance of the item, wherein the reuse period is an elapsed time between two consecutive accesses of the item, and further wherein the reuse distance is a number of different items accessed between two consecutive accesses of the item.

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

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

8. The method of claim 1, further comprising:

identifying temporal access patterns of a plurality of items;

adjusting the criterion based on the identified temporal access patterns.

9. The method of claim 1, further comprising:

tracking a hit rate of a plurality of requested items;

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

10. 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.

11. 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 if the existing item is to be evicted from a tail of the cache queue, and the item has spatial locality with the one or more other items near a head of the cache queue, the item is promoted within the cache queue, and

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

12. A method comprising:

maintaining an active queue and an inactive queue in a cache;

receiving a request for an item;

placing the requested item within the inactive queue if the requested item is not already stored in the cache;

inserting the requested item in the active queue if the requested item is already stored in the cache;

maintaining a ratio of a size of the active queue to the inactive queue within certain limits by evicting an existing item from the cache, wherein the existing item is selected from the least recently accessed item of a tail of the active queue and a tail of the inactive queue.

13. The method of claim 12, further comprising:

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

wherein if 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 if the recycle bit for the tail item is set, the tail item is evicted.

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

15. The method of claim 12, further comprising:

maintaining a reuse period or a reuse distance of each item in the cache,

wherein the reuse period is an elapsed time between two consecutive accesses of the item, and the reuse distance is a number of different items accessed between two consecutive accesses of the item, and

further wherein the reuse period or the reuse distance is used to determine a position within the active queue to which the requested item that is already stored in the cache should be promoted.

16. The method of claim 12, 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.

17. The method of claim 12, further comprising:

dynamically adjusting the ratio of the size of the active queue to the inactive queue to increase a hit rate.

18. The method of claim 12, further comprising:

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

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

if the requested item is promoted within the active queue or the inactive queue, promoting the one or more other items with which the requested item has spatial locality.

19. A machine readable medium storing instructions which when executed by a machine, cause the machine to:

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

if the requested item satisfies a criterion, promote the requested item to a head of the cache queue;

maintain a recycle bit for each item in the cache queue, wherein the recycle bit is initially unset;

if a tail item of the cache queue is to be evicted and the recycle bit for the tail item is unset, probabilistically determine whether to set the recycle bit;

promote the tail item within the cache queue if the recycle bit was probabilistically set, and

evict the tail item from the cache queue if the recycle bit for the tail item was set or was not probabilistically set.

20. The machine readable medium of claim 19, wherein the criterion is that the requested item is within a threshold of the head of the cache queue.