Adaptive smart data cache eviction

Patent metadata

Field	Value
Publication number	US-10102150-B1
Application number	US-201715581788-A
Country	US
Kind code	B1
Filing date	Apr 28, 2017
Priority date	Apr 28, 2017
Publication date	Oct 16, 2018
Grant date	Oct 16, 2018

Abstract

An adaptive smart data cache eviction method takes file-based quotas into account during eviction of WEUs as opposed to a default eviction policy that treats all files the same. Adaptive smart data cache eviction is a granular and dynamic eviction of the least frequently and least recently accessed blocks contained in a WEU for those files that have exceeded file-based quotas established for them or that are determined to be candidates for eviction based on the number of blocks stored for them relative to other files and how frequently and recently those blocks were accessed.

First claim

What is claimed is:

1. A computer-implemented method for managing a data cache in a cache memory device, the method comprising:
storing data in a data cache in a cache memory device, the data cache composed of data structures in which one or more blocks of data is stored over time;
establishing a file information table for each file whose data is stored in the data cache, the file information table identifying a maximum quota established for each file and a used block counter;
tracking how many blocks of data are stored in the data cache for a file in the used block counter;
weighting each file being tracked in the file information table based on how many blocks of data is stored in the data cache; and
evicting from the data cache one or more blocks of data belonging to the weighted files with a higher number of blocks of data stored in the data cache.

2. The computer-implemented method of claim 1 , wherein:
the one or more blocks of data are any one of a page and a segment capable of being identified in a map associating each block of data to the data structure in which it is stored;
a counter established for each block of data contain cache hit counts for determining how frequently and how recently each block was accessed over time; and
wherein the one or more blocks of data evicted from the data cache belonging to the weighted files with the higher number of blocks of data are selected from the one or more blocks that are any one or more of least frequently and least recently accessed until an eviction target is met.

3. The computer-implemented method of claim 1 , wherein weighting each file being tracked in the file information table based on how many blocks of data is stored in the data cache includes how frequently and how recently the one or more blocks of data stored for each file were accessed, including:
computing for each file averages of how frequently and how recently the one or more blocks of data stored for the file were accessed over time; and
sorting the files based on a combination of how many blocks of data is stored in the data cache for each file and its computed averages.

4. The computer-implemented method of claim 1 , wherein the file information table further includes an activity flag indicating whether a file is active or inactive, the method further comprising:
tracking how frequently or recently a file was accessed in the recency flag based on how frequently or recently the one or more blocks of data stored for the file were accessed over time; and
weighting each file being tracked in the file information table based on whether the file was accessed any one or more of less frequently and less recently as compared to other weighted files over a same period of time.

5. The computer-implemented method of claim 4 , wherein evicting from the data cache the one or more blocks of data stored for a file over time includes:
selecting from the sorted files the one or more blocks of data least frequently accessed over time;
generating a first list of data structures sorted by how recently any of the selected blocks of data stored in the data structure were accessed over time;
generating a second list of data structures sorted by how frequently any of the selected blocks of data stored in the data structure were accessed over time;
evicting from the data cache data structures in the first list blocks of data stored for the file least recently accessed over time; and
evicting from the data cache data structures in the second list blocks of data stored for the file least frequently accessed over time.

6. The computer-implemented method of claim 4 , wherein how frequently each block was accessed over time is based on a long period of time and how recently each block was accessed over time is based on a short period of time as compared to the long period of time, the periods of time based on a number of hours over a 24-hour period of time.

7. The computer-implemented method of claim 1 , the method further comprising:
determining that a file has exceeded the maximum quota established for the file; and
evicting from the data cache any of the one or more blocks of data belonging to the file until the file no longer exceeds the maximum quota.

8. A storage system for managing a data cache in a cache memory device, comprising:
a cache memory device having a data cache in which to store data, the data cache composed of data structures in which one or more blocks of data is stored over time;
a cache manager executed by a processor in communication with the cache memory device to:
establish a file information table for each file whose data is stored in the data cache, the file information table identifying a maximum quota established for each file and a used block counter;
track in the used block counter of the file information table how many blocks of data are stored in the data cache for a file;
weight each file being tracked based on the respective maximum quota and used block counter; and
evict from the data cache one or more blocks of data belonging to the weighted files having a higher used block counter as compared to the weighted files having a lower used block counter.

9. The storage system of claim 8 , wherein the one or more blocks of data are any one of a page and a segment capable of being identified in a map associating each block of data to the data structure in which it is stored, and wherein the cache manager executed by the processor in communication with the cache memory device is further to:
establish a counter for each block of data containing cache hit counts for determining how frequently and how recently each block was accessed over time, including how frequently and how recently any one of a page and a segment in each block was accessed over time;
select from the one or more blocks of data belonging to the weighted files having the higher used block counter any one or more of the least frequently and least recently accessed blocks; and
evict from the data cache the selected blocks until an eviction target is met.

10. The storage system of claim 8 , wherein to weight each file being tracked based on the respective maximum quota and used block counter includes determining how frequently and how recently the one or more blocks of data stored for each file were accessed, wherein the cache manager executed by the processor in communication with the cache memory device is further to:
compute for each file averages of how frequently and how recently the one or more blocks of data stored for the file were accessed over time; and
sort the files based on a combination of how many blocks of data are stored in the data cache for each file and its computed averages.

11. The storage system of claim 8 , wherein the file information table further includes an activity flag indicating whether a file is active or inactive, wherein the cache manager executed by the processor in communication with the cache memory device is further to:
track in the recency flag how frequently or recently a file was accessed based on how frequently or recently the one or more blocks of data stored for the file were accessed over time; and
weight each file being tracked in the file information table based on whether the file was accessed any one or more of less frequently and less recently as compared to other weighted files over a same period of time.

12. The storage system of claim 11 , wherein to evict from the data cache the one or more blocks of data belonging to the weighted files having a higher used block counter as compared to the weighted files having a lower used block counter, the cache manager executed by the processor in communication

Assignees

• Emc Ip Holding Co Llc

Inventors

• Visvanathan Satish Kumar Kashi
• Ugale Rahul

Classifications

• G06F2212/401

  Compressed data · CPC title

• G06F2212/225

  Hybrid cache memory, e.g. having both volatile and non-volatile portions · CPC title

• G06F12/122 Primary

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

• G06F12/0897

  with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811) · CPC title

• G06F2212/463

  File · CPC title