Systems, devices and methods using a solid state device as a caching medium with a cache replacement algorithm

Patent metadata

Field	Value
Publication number	US-10176103-B1
Application number	US-201615145883-A
Country	US
Kind code	B1
Filing date	May 4, 2016
Priority date	May 7, 2015
Publication date	Jan 8, 2019
Grant date	Jan 8, 2019

Abstract

An example method for performing cache replacement in a caching medium for a data storage system can include providing an SSD cache, providing an LRU data structure including buckets for managing the SSD cache, and providing cache headers for managing the cache lines. The method can include assigning two or more cache headers to a same bucket of the LRU data structure, and arranging the cache headers in a linked list based on access time. A cache header for an LRU cache line is a tail node of the linked list. The method can further include providing an LFU data structure including frequency buckets, assigning the tail node of the linked list of the same bucket of the LRU data structure to a frequency bucket based on access frequency, and selecting an LFU cache line for cache replacement using the LFU data structure.

First claim

What is claimed:

1. A computer-implemented method for performing cache replacement in a caching medium for a data storage system, comprising:
providing an SSD cache including a plurality of cache lines;
providing a least-recently used (LRU) data structure including a plurality of buckets for managing the SSD cache;
providing a plurality of cache headers for managing the cache lines, each cache header associating a cache line and a corresponding data block stored in the data storage system;
assigning two or more cache headers to a same bucket of the LRU data structure;
arranging the two or more cache headers assigned to the same bucket of the LRU data structure in a linked list based on a time of access, wherein a cache header for an LRU cache line is a tail node of the linked list of the same bucket of the LRU data structure;
providing a least-frequently used (LFU) data structure including a plurality of frequency buckets, each frequency bucket corresponding to a fixed frequency range;
assigning the tail node of the linked list of the same bucket of the LRU data structure to one of the frequency buckets of the LFU data structure based on a frequency of access; and
selecting an LFU cache line for cache replacement using the LFU data structure.

2. The computer-implemented method of claim 1 , wherein the frequency buckets of the LFU data structure are arranged from an LFU frequency bucket to a most-recently used (MFU) frequency bucket.

3. The computer-implemented method of claim 2 , wherein selecting an LFU cache line for cache replacement using the LFU data structure further comprises searching the frequency buckets of the LFU data structure beginning with the LFU frequency bucket to identify a frequency bucket containing the LFU cache line.

4. The computer-implemented method of claim 1 , further comprising:
assigning two or more tail nodes corresponding to different buckets of the LRU data structure to a same frequency bucket of the LFU data structure; and
arranging the two or more tail nodes assigned to the same frequency bucket of the LFU data structure in a linked list based on the frequency of access.

5. The computer-implemented method of claim 1 , further comprising:
removing a cache header for the LFU cache line from the linked list of the same frequency bucket of the LFU data structure; and
assigning a next LRU cache header to the linked list of the same frequency bucket of the LFU data structure.

6. The computer-implemented method of claim 4 , wherein the linked list of the same bucket of the LRU data structure and the linked list of the same frequency bucket of the LFU data structure are doubly-linked lists.

7. The computer-implemented method of claim 6 , wherein each of the two or more tail nodes participate in the doubly-linked list of the same frequency bucket of the LFU data structure.

8. The computer-implemented method of claim 7 , wherein each of the two or more tail nodes is a respective cache header comprising a previous pointer and a subsequent pointer, the previous pointer being reserved to point to a next LFU cache header in the doubly-linked list of the same frequency bucket of the LFU data structure, and the subsequent pointer being reserved to point to a next MFU cache header in the doubly-linked list of the same frequency bucket of the LFU data structure.

9. The computer-implemented method of claim 8 , wherein each of the two or more tail nodes is a respective cache header further comprising a frequency counter, and each of the two or more tail nodes is arranged in the doubly-linked list of the same frequency bucket of the LFU data structure based on a value of the frequency counter.

10. A non-transitory computer-readable recording medium having computer-executable instructions stored thereon for performing cache replacement in a caching medium for a data storage system that, when executed by a data storage system computer, cause the data storage system computer to:
provide an SSD cache including a plurality of cache lines;
provide a least-recently used (LRU) data structure including a plurality of buckets for managing the SSD cache;
provide a plurality of cache headers for managing the cache lines, each cache header associating a cache line and a corresponding data block stored in the data storage system;
assign two or more cache headers to a same bucket of the LRU data structure;
arrange the two or more cache headers assigned to the same bucket of the LRU data structure in a linked list based on a time of access, wherein a cache header for an LRU cache line is a tail node of the linked list of the same bucket of the LRU data structure;
provide a least-frequently used (LFU) data structure including a plurality of frequency buckets, each frequency bucket corresponding to a fixed frequency range;
assign the tail node of the linked list of the same bucket of the LRU data structure to one of the frequency buckets of the LFU data structure based on a frequency of access; and
select an LFU cache line for cache replacement using the LFU data structure.

11. The non-transitory computer-readable recording medium of claim 10 , wherein the frequency buckets of the LFU data structure are arranged from an LFU frequency bucket to a most-recently used (MFU) frequency bucket.

12. The non-transitory computer-readable recording medium of claim 11 , wherein selecting an LFU cache line for cache replacement using the LFU data structure further comprises searching the frequency buckets of the LFU data structure beginning with the LFU frequency bucket to identify a frequency bucket containing the LFU cache line.

13. The non-transitory computer-readable recording medium of claim 10 , having further computer-executable instructions stored thereon that, when executed by the data storage system computer, cause the data storage system computer to:
assign two or more tail nodes corresponding to different buckets of the LRU data structure to a same frequency bucket of the LFU data structure; and
arrange the two or more tail nodes assigned to the same frequency bucket of the LFU data structure in a linked list based on the frequency of access.

14. The non-transitory computer-readable recording medium of claim 10 , having further computer-executable instructions stored thereon that, when executed by the data storage system computer, cause the data storage system computer to:
remove a cache header for the LFU cache line from the linked list of the same frequency bucket of the LFU data structure; and
assign a next LRU cache header to the linked list of the same frequency bucket of the LFU data structure.

15. The non-transitory computer-readable recording medium of claim 13 , wherein the linked list of the same bucket of the LRU data structure and the linked list of the same frequency bucket of the LFU data structure are doubly-linked lists.

16. The non-transitory computer-readable recording medium of claim 15 , wherein each of the two or more tail nodes participate in the doubly-linked list of the same frequency bucket of the LFU data structure.

17. The non-transitory computer-readable recording medium of claim 16 , wherein each of the two or more tail nodes is a respective cache header comprising a previous pointer and a subsequent pointer, the previous pointer being reserved to point to a next LFU cache header in the doubly-linked list of the same frequency bucket of the LFU data structure, and the subsequent pointer being reserved to point to a next MFU cache header in the doubly-linked list of the same frequency bucket of the LFU data structure.

Assignees

• American Megatrends Inc

Inventors

• Chatterjee Paresh
• Subramanian Srikumar
• Ramasamy Senthilkumar
• Ganapathy Narayanaswami

Classifications

• G06F12/0868

  Data transfer between cache memory and other subsystems, e.g. storage devices or host systems · CPC title

• G06F2212/222

  Non-volatile memory · CPC title

• G06F12/127

  using additional replacement algorithms · CPC title

• G06F2212/224

  Disk storage · CPC title

• G06F12/122

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