Detection of avoidable cache thrashing for OLTP and DW workloads

• US 10,331,573 B2
• Filed: 08/25/2017
• Issued: 06/25/2019
• 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
• Primary Examiner(s): Yi, David
• Assistant Examiner(s): Goldschmidt, Craig S
• Application Number:
  US15/687,296
• Publication Number:
  US 20180129612A1
• Time in Patent Office: 669 Days
• Field of Search: None
• 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;

incrementing, when a second metadata entry for a second item is detected in memory, same said 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. The method of claim 2 wherein the FIFO contains more metadata entries than the cache contains items.

14. The method of claim 1 wherein said metadata entry contains at least one of:

a device identifier, a block identifier, or a reference to a second metadata entry.

15. 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;

incrementing, when a second metadata entry for a second item is detected in memory, same said victim hit counter;

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

16. The one or more non-transitory computer-readable media of claim 15 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.

17. The one or more non-transitory computer-readable media of claim 15 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.

18. The one or more non-transitory computer-readable media of claim 15 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.

19. The one or more non-transitory computer-readable media of claim 18 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.

20. The one or more non-transitory computer-readable media of claim 18 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.

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

22. The one or more non-transitory computer-readable media of claim 15 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.