DETECTION OF AVOIDABLE CACHE THRASHING FOR OLTP AND DW WORKLOADS

• US 20180129612A1
• Filed: 08/25/2017
• Published: 05/10/2018
• Est. Priority Date: 11/04/2016
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: LEWIS, JUSTIN MATTHEW, TAO, ZUOYU, SHI, JIA, UMAMAGESWARAN, KOTHANDA
• Granted Patent: US 10,331,573 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/1021 Hit rate improvement
• CPC Class Codes: G06F 2212/466 Metadata, control data

Abstract

Techniques are provided to adjust the behavior of a cache based on a count of cache misses for items recently evicted. In an embodiment, a computer responds to evicting a particular item (PI) from a cache by storing a metadata entry for the PI into memory. In response to a cache miss for the PI, the computer detects whether or not the metadata entry for the PI resides in memory. When the metadata entry for the PI is detected in memory, the computer increments a victim hit counter (VHC) that may be used to calculate how much avoidable thrashing is the cache experiencing, which is how much thrashing would be reduced if the cache were expanded. Either immediately or arbitrarily later, the computer adjusts a policy of the cache based on the VHC'"'"'s value. For example, the computer may adjust the capacity of the cache based on the VHC.

Claims

1. A method comprising:

storing in memory, in response to evicting a particular item from a cache, a metadata entry for the particular item;

detecting, in response to a cache miss for the particular item, whether or not the metadata entry for the particular item resides in memory;

incrementing, when the metadata entry for the particular item is detected in memory, a victim hit counter;

adjusting, based on the victim hit counter, a policy of the cache.

2. The method of claim 1 wherein:

the memory comprises a first-in first-out (FIFO) of metadata for a plurality of items, wherein the FIFO comprises a head and a tail;

storing the metadata entry for the particular item in memory comprises;

removing a metadata entry for another item from the head of the FIFO;

appending the metadata entry for the particular item to the tail of the FIFO.

3. The method of claim 1 further comprising:

storing, after evicting the particular item, the particular item into the cache;

removing the metadata entry for the particular item from the memory.

4. The method of claim 1 wherein:

the method further comprises incrementing, during a hit in the cache, a cache hit counter;

the adjusting is further based on the cache hit counter.

5. The method of claim 4 wherein the adjusting is further based on at least one of:

a ratio of the victim hit counter to the cache hit counter, or a ratio of a victim hit rate to a cache hit rate.

6. The method of claim 5 wherein:

adjusting the policy of the cache comprises at least one of;

increasing, when the ratio exceeds a first threshold, a size of the cache;

decreasing, when a second threshold exceeds the ratio, the size of the cache.

7. The method of claim 5 wherein:

the policy of the cache includes distinguishing first-class items from second-class items;

adjusting the policy of the cache comprises at least one of;

decreasing, when the ratio exceeds a first threshold, how much of the cache is reserved for first-class items;

increasing, when a second threshold exceeds the ratio, how much of the cache is reserved for first-class items.

8. The method of claim 4 wherein only items of a particular subset of classes are counted during at least one of:

said incrementing the victim hit counter, or said incrementing the cache hit counter.

9. The method of claim 1 wherein the policy of the cache includes distinguishing first-class items from second-class items.

10. The method of claim 9 wherein adjusting the policy of the cache comprises adjusting how much of the cache is reserved for first-class items.

11. The method of claim 1 wherein adjusting the policy of the cache comprises adjusting a size of the cache.

12. The method of claim 1 wherein said adjusting a policy of the cache is further based on an input/output (I/O) latency metric of a backing store of the cache.

13. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:

storing in memory, in response to evicting a particular item from a cache, a metadata entry for the particular item;

detecting, in response to a cache miss for the particular item, whether or not the metadata entry for the particular item resides in memory;

incrementing, when the metadata entry for the particular item is detected in memory, a victim hit counter;

adjusting, based on the victim hit counter, a policy of the cache.

14. The one or more non-transitory computer-readable media of claim 13 wherein:

the memory comprises a first-in first-out (FIFO) of metadata for a plurality of items, wherein the FIFO comprises a head and a tail;

storing the metadata entry for the particular item in memory comprises;

removing a metadata entry for another item from the head of the FIFO;

appending the metadata entry for the particular item to the tail of the FIFO.

15. The one or more non-transitory computer-readable media of claim 13 wherein the instructions, when executed by one or more processors, further cause:

storing, after evicting the particular item, the particular item into the cache;

removing the metadata entry for the particular item from the memory.

16. The one or more non-transitory computer-readable media of claim 13 wherein:

the instructions, when executed by one or more processors, further cause incrementing, during a hit in the cache, a cache hit counter;

the adjusting is further based on the cache hit counter.

17. The one or more non-transitory computer-readable media of claim 16 wherein the adjusting is further based on at least one of:

a ratio of the victim hit counter to the cache hit counter, or a ratio of a victim hit rate to a cache hit rate.

18. The one or more non-transitory computer-readable media of claim 16 wherein only items of a particular subset of classes are counted during at least one of:

said incrementing the victim hit counter, or said incrementing the cache hit counter.

19. The one or more non-transitory computer-readable media of claim 13 wherein adjusting the policy of the cache comprises adjusting a size of the cache.

20. The one or more non-transitory computer-readable media of claim 13 wherein said adjusting a policy of the cache is further based on an input/output (I/O) latency metric of a backing store of the cache.