Method, electronic device and computer program product for managing cache

Patent metadata

Field	Value
Publication number	US-2021286730-A1
Application number	US-202017079925-A
Country	US
Kind code	A1
Filing date	Oct 26, 2020
Priority date	Mar 12, 2020
Publication date	Sep 16, 2021
Grant date	—

Abstract

Techniques for cache management involve accessing, when a first data block to be accessed is missing in a first cache, the first data block from a storage device storing the first data block; selecting, when the first cache is full and based on a plurality of parameters associated with a plurality of eviction policies, an eviction policy for evicting a data block in the first cache from the plurality of eviction policies, the plurality of parameters indicating corresponding possibilities that the plurality of eviction policies are selected; evicting a second data block in the first cache to a second cache based on the selected eviction policy, the second cache being configured to record the data block evicted from the first cache; and caching the accessed first data block in the first cache. Such techniques can improve the cache hit rate, thereby improving the access performance of a system.

First claim

1 . A method for cache management, comprising:
accessing, according to a determination that a first data block to be accessed is missing in a first cache, the first data block from a storage device storing the first data block; selecting, according to a determination that the first cache is full and based on a plurality of parameters associated with a plurality of eviction policies, an eviction policy for evicting a data block in the first cache from the plurality of eviction policies, the plurality of parameters indicating corresponding possibilities that the plurality of eviction policies are selected; evicting a second data block in the first cache to a second cache based on the selected eviction policy, the second cache being configured to record the data block evicted from the first cache; and caching the accessed first data block in the first cache.

2 . The method of claim 1 , wherein accessing the first data block from the storage device storing the first data block comprises:
accessing, according to a determination that the first data block exists in the second cache, the first data block from the second cache; and accessing, according to a determination that the first data block is missing in the second cache, the first data block from the storage device storing the first data block.

3 . The method of claim 1 , further comprising:
deleting the first data block from the second cache according to a determination that the first data block exists in the second cache; and updating the plurality of parameters according to an eviction policy for evicting the first data block to the second cache.

4 . The method of claim 3 , wherein the second cache comprises a plurality of lists, each of the plurality of lists comprising data blocks evicted from the first cache based on a corresponding eviction policy in the plurality of eviction policies, and deleting the first data block from the second cache comprises:
determining, from the plurality of lists, a list in which the first data block is located; and deleting the first data block from the determined list.

5 . The method of claim 3 , wherein the plurality of eviction policies comprise a first eviction policy and a second eviction policy, and the plurality of parameters comprise a first parameter associated with the first eviction policy and a second parameter associated with the second eviction policy, and updating the plurality of parameters comprises:
updating the first parameter and the second parameter according to a determination that the first data block is evicted to the second cache based on the first eviction policy, to increase the possibility that the second eviction policy is selected; and updating the first parameter and the second parameter according to a determination that the first data block is evicted to the second cache based on the second eviction policy, to increase the possibility that the first eviction policy is selected.

6 . The method of claim 1 , wherein selecting the eviction policy from the plurality of eviction policies comprises:
determining a maximum parameter in the plurality of parameters; and selecting an eviction policy corresponding to the maximum parameter in the plurality of eviction policies as the eviction policy for evicting the second data block.

7 . The method of claim 1 , wherein the plurality of eviction policies comprise:
a first eviction policy based on the least recently used (LRU) algorithm; and a second eviction policy based on the least frequently used (LFU) algorithm.

8 . The method of claim 7 , wherein the second cache comprises a first list for caching data blocks evicted from the first cache based on the first eviction policy, and evicting the second data block from the first cache to the second cache comprises:
determining, according to a determination that the first eviction policy is selected, a least recently accessed data block from the first cache as the second data block; and evicting the second data block from the first cache to the first list.

9 . The method of claim 7 , wherein the second cache comprises a second list for caching data blocks evicted from the first cache based on the second eviction policy, and evicting the second data block from the first cache to the second cache comprises:
determining, according to a determination that the second eviction policy is selected, a least frequently accessed data block from the first cache as the second data block; and evicting the second data block from the first cache to the second list.

10 . The method of claim 1 , further comprising:
accessing the first data block from the first cache according to a determination that the first data block to be accessed exists in the first cache.

11 . The method of claim 1 , further comprising:
caching the first data block in the first cache according to a determination that the first data block is accessed from the storage device and the first cache is not full.

12 . An electronic device, comprising:
a processor; a memory coupled to the processor and storing instructions for execution by the processor, wherein when executed by the processor, the instructions cause the device to perform actions comprising:
accessing, according to a determination that a first data block to be accessed is missing in a first cache, the first data block from a storage device storing the first data block;
selecting, according to a determination that the first cache is full and based on a plurality of parameters associated with a plurality of eviction policies, an eviction policy for evicting a data block in the first cache from the plurality of eviction policies, the plurality of parameters indicating corresponding possibilities that the plurality of eviction policies are selected;
evicting a second data block in the first cache to a second cache based on the selected eviction policy, the second cache being configured to record the data block evicted from the first cache; and
caching the accessed first data block in the first cache.

13 . The device of claim 12 , wherein accessing the first data block from the storage device storing the first data block comprises:
accessing, according to a determination that the first data block exists in the second cache, the first data block from the second cache; and accessing, according to a determination that the first data block is missing in the second cache, the first data block from the storage device storing the first data block.

14 . The device of claim 12 , wherein the actions further comprise:
deleting the first data block from the second cache according to a determination that the first data block exists in the second cache; and updating the plurality of parameters according to an eviction policy for evicting the first data block to the second cache.

15 . The device of claim 14 , wherein the second cache comprises a plurality of lists, each of the plurality of lists comprising data blocks evicted from the first cache based on a corresponding eviction policy in the plurality of eviction policies, and deleting the first data block from the second cache comprises:
determining, from the plurality of lists, a list in which the first data block is located; and deleting the first data block from the determined list.

16 . The device of claim 14 , wherein the plurality of eviction policies comprise a first eviction policy and a second eviction policy, and the plurality of parameters comprise a first parameter associated with the first eviction policy and a second parameter associated with the second eviction policy,

Assignees

• Emc Ip Holding Co Llc

Inventors

• Lv Shuo
• Zhang Ming

Classifications

• G06F2212/1016

  Performance improvement · CPC title

• G06F12/122 Primary

  of the least frequently used [LFU] type, e.g. with individual count value · CPC title

• G06F2212/1021

  Hit rate improvement · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title