Method and apparatus for dynamically adapting sizes of cache partitions in a partitioned cache

Patent metadata

Field	Value
Publication number	US-11138118-B2
Application number	US-202016740601-A
Country	US
Kind code	B2
Filing date	Jan 13, 2020
Priority date	Jan 13, 2020
Publication date	Oct 5, 2021
Grant date	Oct 5, 2021

Abstract

The sizes of cache partitions, in a partitioned cache, are dynamically adjusted by determining, for each request, how many cache misses will occur in connection with implementing the request against the cache partition. The cache partition associated with the current request is increased in size by the number of cache misses and one or more other cache partitions is decreased in size causing cache evictions to occur from the other cache partitions rather than from the current cache partition. The other cache partitions, that are to be decreased in size, may be determined by ranking the cache partitions according to frequency of use and selecting the least frequently used cache partition to be reduced in size.

First claim

What is claimed is:

1. A method of dynamically adjusting sizes of cache partitions of a partitioned cache, each cache partition being implemented in memory and having a respective plurality of slots to be used for caching purposes, comprising:
receiving a plurality of cache requests, each cache request being associated with a respective partition of the partitioned cache;
for each cache request:
determining a number of cache misses associated with the cache request on the respective cache partition;
increasing a size of the respective cache partition by a number of cache slots equal to the number of cache misses;
selecting a cache partition other than the respective cache partition; and
decreasing a size of the selected other cache partition by the number of cache slots equal to the number of cache misses; and
implementing the cache request on the respective cache partition after increasing the size of the respective cache partition;
wherein each time a cache request is received, the steps of determining the number of cache misses associated with the cache request and increasing the size of the respective cache partition by the number of cache slots equal to the number of cache misses occur before implementing the cache request against the respective cache partition, to prevent the cache misses associated with the cache request from resulting in evictions of data from the respective cache partition.

2. The method of claim 1 , wherein the step of decreasing the size of the selected other cache partition results in eviction of data from the selected other cache partition.

3. The method of claim 1 , wherein selecting the cache partition comprises ranking the cache partitions based on frequency of use, and selecting the least recently used cache partition in the partitioned cache as the selected other cache partition.

4. The method of claim 1 , further comprising setting an upper size limit on sizes of the cache partitions, and not performing the step of increasing the size of the respective cache partition if the step of increasing the size of the respective cache partition would cause the first size of the respective cache partition to exceed the upper size limit.

5. The method of claim 1 , further comprising setting a lower size limit on sizes of the cache partitions, and not performing the step of decreasing the size of the selected other cache partition if the step of decreasing the size of the selected other cache partition would cause the size of the selected other cache partition to drop below the lower size limit.

6. A storage system, comprising:
a plurality of storage resources;
a partitioned cache having multiple cache partitions, each cache partition being implemented in the storage resources and having a respective plurality of slots to be used for caching purposes; and
a cache management system, the cache management system containing control logic configured to:
receive a plurality of cache requests, each cache request being associated with a respective partition of the partitioned cache; and
for each cache request:
determine a number of cache misses associated with the first request on the respective cache partition;
increase a size of the respective cache partition by a number of cache slots equal to the number of cache misses;
select a cache partition other than the respective cache partition;
decrease a size of the selected other cache partition by the number of cache slots equal to the number of cache misses; and
implement the cache request on the respective cache partition after increasing the size of the respective cache partition;
wherein each time a cache request is received, the control logic is configured to determine the number of cache misses associated with the cache request and increase the size of the respective cache partition by the number of cache slots equal to the number of cache misses before implementing the cache request against the respective cache partition, to prevent the cache misses associated with the cache request from resulting in evictions of data from the respective cache partition.

7. The storage system of claim 6 , wherein the decrease of the size of the selected other cache partition results in eviction of data from the selected other cache partition.

8. The storage system of claim 6 , wherein the control logic configured to select the cache partition comprises control logic configured to rank the cache partitions based on frequency of use, and select the least recently used cache partition in the partitioned cache as the selected other cache partition.

9. The storage system of claim 6 , further comprising control logic configured to set an upper size limit on the size of the respective cache partition, and not increase the size of the respective cache partition if increasing the size of the respective cache partition would cause the size of the respective cache partition to exceed the upper size limit.

10. The storage system of claim 6 , further comprising control logic configured to set a lower size limit on the sizes of the cache partitions, and not decrease the size of the selected other cache partition if decreasing the size of the selected other cache partition would cause the size of the selected other cache partition to drop below the lower size limit.

11. A non-transitory tangible computer readable storage medium having stored thereon a computer program for dynamically adjusting sizes of cache partitions of a partitioned cache, each cache partition being implemented in memory and having a respective plurality of slots to be used for caching purposes, the computer program including a set of instructions which, when executed by a computer, cause the computer to perform a method comprising the steps of:
receiving a plurality of cache requests, each cache request being associated with a respective partition of the partitioned cache;
for each cache request:
determining a number of cache misses associated with the cache request on the respective cache partition;
increasing a size of the respective cache partition by a number of cache slots equal to the number of cache misses;
selecting a cache partition other than the respective cache partition;
decreasing a size of the selected other cache partition by the number of cache slots equal to the number of cache misses; and
implementing the cache request on the respective cache partition after increasing the size of the respective cache partition;
wherein each time a cache request is received, the steps of determining the number of cache misses associated with the first cache request and increasing the size of the respective cache partition by the number of cache slots equal to the number of cache misses occur before implementing the cache request against the respective cache partition, to prevent the cache misses associated with the cache request from resulting in evictions of data from the respective cache partition.

12. The non-transitory tangible computer readable storage medium of claim 11 :
wherein selecting the cache partition comprises ranking the cache partitions based on frequency of use, and selecting the least recently used cache partition in the partitioned cache as the selected other cache partition; and
wherein the step of decreasing the size of the selected other cache partition results in eviction of data from the selected other cache partition.

13. The non-transitory tangible computer readable storage medium of claim 11 , the method further comprising:
setting an upper size limit on sizes of the cache partitions, and not performing the step of increasing the size of the respective cache partition if the step of i

Assignees

• Emc Ip Holding Co Llc

Inventors

• Barbalho Hugo De Oliveira
• Dias Jonas Furtado
• Gottin Vinícius Michel

Classifications

• G06F12/0848 Primary

  Partitioned cache, e.g. separate instruction and operand caches · CPC title

• G06F2212/601

  Reconfiguration of cache memory · CPC title

• G06F12/0859

  with reload from main memory · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title