Selecting one of multiple cache eviction algorithms to use to evict a track from the cache using a machine learning module

Patent metadata

Field	Value
Publication number	US-10983922-B2
Application number	US-201815984180-A
Country	US
Kind code	B2
Filing date	May 18, 2018
Priority date	May 18, 2018
Publication date	Apr 20, 2021
Grant date	Apr 20, 2021

Abstract

Provided are a computer program product, system, and method for using a machine learning module to select one of multiple cache eviction algorithms to use to evict a track from the cache. A first cache eviction algorithm determines tracks to evict from the cache. A second cache eviction algorithm determines tracks to evict from the cache, wherein the first and second cache eviction algorithms use different eviction schemes. At least one machine learning module is executed to produce output indicating one of the first cache eviction algorithm and the second cache eviction algorithm to use to select a track to evict from the cache. A track is evicted that is selected by one of the first and second cache eviction algorithms indicated in the output from the at least one machine learning module.

First claim

What is claimed is:

1. A computer program product for demoting tracks from cache to a storage, the computer program product comprising a computer readable storage medium having computer readable program code embodied therein that when executed performs operations, the operations comprising:
providing a first cache eviction algorithm to determine tracks to evict from the cache;
providing a second cache eviction algorithm to determine tracks to evict from the cache, wherein the first and second cache eviction algorithms use different eviction schemes;
executing a first machine learning module that outputs a first confidence level indicating a likelihood that the first cache eviction algorithm optimizes a read hit rate to the cache;
executing a second machine learning module that outputs a second confidence level indicating a likelihood that the second cache eviction algorithm optimizes the read hit rate to the cache;
evicting a first evict track, determined by the first cache eviction algorithm, from the cache in response to the first confidence level exceeding the second confidence level; and
evicting a second evict track, determined by the second cache eviction algorithm, from the cache in response to the second confidence level exceeding the first confidence level.

2. The computer program product of claim 1 , wherein the operations further comprise:
providing a least recently used (LRU) list of tracks in the cache, wherein the first cache eviction algorithm comprises an LRU algorithm that selects a track to evict that is at an LRU end of the LRU list.

3. The computer program product of claim 2 , wherein the operations further comprise:
providing a frequency counter for each of the tracks in the LRU list indicating a number of times a track in the cache has been accessed while on the LRU list, wherein the second cache eviction algorithm comprises a Least Frequently Used (LFU) algorithm that selects a track to evict that has a lowest frequency counter of the frequency counters for the tracks in the cache.

4. The computer program product of claim 1 , wherein the operations further comprise:
executing the first cache eviction algorithm to determine the first evict track to evict from the cache;
executing the second cache eviction algorithm to determine the second evict track to evict from the cache; and
wherein the first machine learning module receives as input the first evict track and cache statistics to output the first confidence level and wherein the second machine learning module receives as input the second evict track and cache statistics to output the second confidence level.

5. A computer program product for demoting tracks from cache to a storage, the computer program product comprising a computer readable storage medium having computer readable program code embodied therein that when executed performs operations, the operations comprising:
executing a first cache eviction algorithm to determine a first evict track to evict from the cache;
executing a second cache eviction algorithm to determine a second evict track to evict from the cache, wherein the first and second cache eviction algorithms use different eviction schemes;
executing at least one machine learning module that receives as input the first evict track, the second evict track and cache statistics and produces output used to select one of the first and the second cache eviction algorithms to use to select a track to evict from the cache;
evicting the first evict track from the cache in response to the output from the at least one machine learning module indicating to use the first cache eviction algorithm; and
evicting the second evict track from the cache in response to the output from the at least one machine learning module indicating to use the second cache eviction algorithm.

6. The computer program product of claim 5 , wherein the cache statistics comprises at least one of a size of the cache, a cache miss-to-hit ratio, first access frequency of the first evict track for the first machine learning module and second access frequency of the second evict track for the second machine learning module, a first location of the first evict track in a least recently used (LRU) list for the first machine learning module and a second location of the second evict track in the LRU list for the second machine learning module.

7. The computer program product of claim 5 , wherein the output from the at least one machine learning module comprises:
a first confidence level indicating a likelihood that the first cache eviction algorithm optimizes a read hit rate to the cache;
a second confidence level indicating a likelihood that the second cache eviction algorithm optimizes the read hit rate to the cache;
wherein the output indicates to use the first cache eviction algorithm in response to the first confidence level exceeding the second confidence level; and
wherein the output indicates to use the second cache eviction algorithm in response to the second confidence level exceeding the first confidence level.

8. The computer program product of claim 7 , wherein the at least one machine learning module comprises a first machine learning module that receives as input the first evict track and outputs the first confidence level and a second machine learning module that receives as input the second evict track and outputs the second confidence level.

9. The computer program product of claim 8 , wherein the operations further comprise:
maintaining an active cache list of the tracks in the cache;
maintaining an inactive cache list of tracks evicted from the cache;
removing indication of a track from the active cache list when the track is evicted from the cache; and
adding indication of the track evicted from the cache to the inactive cache list.

10. The computer program product of claim 9 , wherein the active and inactive cache lists comprise least recently used (LRU) lists of tracks in the cache, wherein the first cache eviction algorithm comprises an LRU algorithm that selects a track to evict that is at an LRU end of the LRU list.

11. The computer program product of claim 9 , wherein the operations further comprise:
providing a frequency counter for each of the tracks in the active and inactive cache lists indicating a number of times the track in the cache has been accessed while on the active cache list before being moved to the inactive cache list, wherein the second cache eviction algorithm comprises a Least Frequently Used (LFU) algorithm that selects a track to evict that has a lowest frequency counter of the frequency counters for the tracks in the cache.

12. A system for demoting tracks from cache to a storage, comprising:
a processor; and
a computer readable storage medium having computer readable program code embodied therein that when executed performs operations, the operations comprising:
providing a first cache eviction algorithm to determine tracks to evict from the cache;
providing a second cache eviction algorithm to determine tracks to evict from the cache, wherein the first and second cache eviction algorithms use different eviction schemes;
executing a first machine learning module that outputs a first confidence level indicating a likelihood that the first cache eviction algorithm optimizes a read hit rate to the cache;
evicting a first evict track, determined by the first cache eviction algorithm, from the cache in response to the first confidence level exceeding a second confidence level; and
evicting a second evict track, determined by the second cache eviction algorithm, from the cache in response to the second confidence level exceeding the first confidence l

Assignees

• IBM

Inventors

• Gupta Lokesh M
• Borlick Matthew G
• Anderson Kyler A
• Ash Kevin J

Classifications

• G06N3/045

  Combinations of networks · CPC title

• G06N3/08

  Learning methods · CPC title

• G06N3/09

  Supervised learning · CPC title

• G06N3/0499

  Feedforward networks · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title