Caching algorithms for multiple caches

Patent metadata

Field	Value
Publication number	US-10691613-B1
Application number	US-201715418290-A
Country	US
Kind code	B1
Filing date	Jan 27, 2017
Priority date	Sep 27, 2016
Publication date	Jun 23, 2020
Grant date	Jun 23, 2020

Abstract

One embodiment is related to a method for implementing a cache hierarchy, comprising: implementing a plurality of cache layers in the cache hierarchy; and determining a cache algorithm for each cache layer of the plurality of cache layers.

First claim

What is claimed is:

1. A method for implementing a cache hierarchy, comprising:
implementing three or more cache layers in the cache hierarchy, wherein at least one of the three or more cache layers is implemented with either non-volatile memory express (NVMe) or solid state drive (SSD);
determining a cache algorithm for each cache layer of the three or more cache layers, wherein Container-aware LRU (CLRU) or Pannier cache algorithm is utilized at any of the three or more cache layers that is implemented with either NVMe or SSD to reduce erasures, wherein each remaining layer of the three or more cache layers is implemented with one of: dynamic random access memory (DRAM), non-volatile dual in-line memory module (NVDIMM), NVMe, or SSD, wherein the cache algorithm for each remaining cache layer is one of: Least Recently Used (LRU), Adaptive Replacement Cache (ARC), CLRU, or Pannier, wherein a first data entry is promoted from a first cache layer of the three or more cache layers to a second cache layer of the three or more cache layers, wherein the second cache layer is two or more layers above the first cache layer in the cache hierarchy, and wherein the second cache layer has a shorter access latency than the first cache layer; and
maintaining an index in the cache hierarchy recording a hit count associated with each data entry that has ever resided in the cache hierarchy, wherein a third bit count associated with a third data entry is kept updated after the third data entry is evicted from the cache hierarchy, and in response to the updated third hit count being above a cache hit count threshold associated with at least one of the cache layers, the third data entry is re-inserted into the cache hierarchy at a particular cache layer based at least in part on the updated third hit count.

2. The method of claim 1 , wherein the promotion of the first data entry is based on a first cache hit count associated with the first data entry and a cache hit count threshold associated with the second cache layer.

3. The method of claim 1 , wherein each cache layer is associated with its respective access latency and cache hit count threshold.

4. The method of claim 3 , wherein from a highest cache layer to a lowest cache layer in the cache hierarchy, the respective access latency associated with each layer increases monotonically, and the respective cache hit count threshold associated with each layer decreases monotonically.

5. The method of claim 2 , wherein the first cache hit count associated with the first data entry is stored in the index that resides in the second cache layer.

6. The method of claim 5 , wherein the index comprises a second cache hit count associated with a second data entry, the second data entry not being stored in the cache hierarchy.

7. The method of claim 2 , wherein the first cache hit count associated with the first data entry is stored in the index that resides in a third cache layer, wherein the third cache layer has a shorter access latency than the second cache layer.

8. The method of claim 1 , wherein a data entry is evicted from the second cache layer of the three or more cache layers to the first cache layer of the three or more cache layers, wherein the first cache layer has a longer access latency than the second cache layer.

9. The method of claim 8 , wherein a cache hit count associated with the data entry is above a cache hit count threshold associated with the first cache layer.

10. The method of claim 1 , wherein a data entry is evicted from the cache hierarchy in response to determining that a cache hit count associated with the data entry is not above a cache hit count threshold associated with a lowest cache layer in the cache hierarchy.

11. A data processing system, comprising:
three or more cache layers in a cache hierarchy, wherein at least one of the three or more cache layers is implemented with either non-volatile memory express (NVMe) or solid state drive (SSD);
a processor; and
a memory coupled to the processor storing instructions which, when executed by the processor, cause the processor to perform caching operations, the operations including:
determining a cache algorithm for each cache layer of the three or more cache layers, wherein Container-aware LRU (CLRU) or Pannier cache algorithm is utilized at any of the three or more cache layers that is implemented with either NVMe or SSD to reduce erasures, wherein each remaining layer of the three or more cache layers is implemented with one of: dynamic random access memory (DRAM), non-volatile dual in-line memory module (NVDIMM), NVMe, or SSD, wherein the cache algorithm for each remaining cache layer is one of: Least Recently Used (LRU), Adaptive Replacement Cache (ARC), CLRU, or Pannier, wherein a first data entry is promoted from a first cache layer of the three or more cache layers to a second cache layer of the three or more cache layers, wherein the second cache layer is two or more layers above the first cache layer in the cache hierarchy, and wherein the second cache layer has a shorter access latency than the first cache layer; and
maintaining an index in the cache hierarchy recording a hit count associated with each data entry that has ever resided in the cache hierarchy, wherein a third bit count associated with a third data entry is kept updated after the third data entry is evicted from the cache hierarchy, and in response to the updated third hit count being above a cache hit count threshold associated with at least one of the cache layers, the third data entry is re-inserted into the cache hierarchy at a particular cache layer based at least in part on the updated third hit count.

12. A non-transitory machine-readable medium having instructions stored therein which, when executed by a processor, cause the processor to perform caching operations, the operations comprising:
implementing three or more cache layers in a cache hierarchy, wherein at least one of the three or more cache layers is implemented with either non-volatile memory express (NVMe) or solid state drive (SSD);
determining a cache algorithm for each cache layer of the three or more cache layers, wherein Container-aware LRU (CLRU) or Pannier cache algorithm is utilized at any of the three or more cache layers that is implemented with either NVMe or SSD to reduce erasures, wherein each remaining layer of the three or more cache layers is implemented with one of: dynamic random access memory (DRAM), non-volatile dual in-line memory module (NVDIMM), NVMe, or SSD, wherein the cache algorithm for each remaining cache layer is one of: Least Recently Used (LRU), Adaptive Replacement Cache (ARC), CLRU, or Pannier, wherein a first data entry is promoted from a first cache layer of the three or more cache layers to a second cache layer of the three or more cache layers, wherein the second cache layer is two or more layers above the first cache layer in the cache hierarchy, and wherein the second cache layer has a shorter access latency than the first cache layer; and
maintaining an index in the cache hierarchy recording a hit count associated with each data entry that has ever resided in the cache hierarchy, wherein a third bit count associated with a third data entry is kept updated after the third data entry is evicted from the cache hierarchy, and in response to the updated third hit count being above a cache hit count threshold associated with at least one of the cache layers, the third data entry is re-inserted into the cache hierarchy at a particular cache layer based at least in part on the updated third hit count.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Tong Hao
• Shilane Philip

Classifications

• G06F2212/283

  Plural cache memories · CPC title

• G06F2212/225

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

• G06F12/128

  adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel · CPC title

• G06F12/123

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

• G06F12/0888

  using selective caching, e.g. bypass · CPC title