Dynamic cache balancing

Abstract

Embodiments serve to balance overall performance of a finite-sized caching system having a first cache of a first cache size and a second cache of a second cache size. A tail portion and a head portion of each of the caches are defined wherein incoming data elements are initially stored in a respective head portion and wherein evicted data elements are evicted from a respective tail portion. Performance metrics are defined wherein a performance metric includes a predicted miss cost that would be incurred when replacing an evicted data elements. A quantitative function is defined to include cache performance metrics and a cache reallocation amount. The cache performance metrics are evaluated periodically to determine a then-current cache reallocation amount. The caches can be balanced by increasing the first cache size by the cache reallocation amount and decreasing the second cache size by the cache reallocation amount.

What is claimed is: 
     
         1 . A method comprising:
 identifying a first tail portion of a first cache partition and a second tail portion of a second cache partition, wherein the first cache partition corresponds to a first cache size and the second cache partition corresponds to a second cache size, wherein evicted data elements are evicted from a respective tail portion;   generating a first normalized cache performance metric derived from the first tail portion of the first cache partition, wherein the first normalized cache performance metric represents a first incremental value of adding more data elements to the first cache partition;   generating a second normalized cache performance metric derived from the second tail portion of the second cache partition, wherein the second normalized cache performance metric represents a second incremental value of adding more data elements to the first cache partition; and   adjusting the first cache size of the first cache partition and the second cache size of the second cache partition according to a cache reallocation amount, wherein the cache reallocation amount is derived by comparing the first normalized cache performance metric and the second normalized cache performance metric.   
     
     
         2 . The method of  claim 1 , further comprising receiving one or more data element attributes corresponding to one or more data elements that are stored in at least one of the cache partitions. 
     
     
         3 . The method of  claim 1 , wherein the cache reallocation amount is responsive to a change to one or more cache attributes. 
     
     
         4 . The method of  claim 3 , wherein the cache attributes comprise at least one of, a identifier, a cache size, or a total number of cache queries. 
     
     
         5 . The method of  claim 1 , wherein the first cache partition comprises a first portion of the data elements characterized by a first data element type and a second cache from the caches comprises a second portion of the data elements characterized by a second data element type. 
     
     
         6 . The method of  claim 5 , wherein the first portion of the data elements comprises extent data and the second portion of the data elements comprises metadata. 
     
     
         7 . The method of  claim 2 , wherein the data element attributes comprise at least one of, a identifier, a data element identifier, a data element type, a miss cost, or a timestamp. 
     
     
         8 . The method of  claim 1 , wherein the normalized cache performance metric is derived at least in part from one or more cache tail attributes characterizing a cache tail corresponding to a respective one of the caches. 
     
     
         9 . The method of  claim 8 , wherein the cache tail is defined based at least in part on at least one of, a number of cache data elements, or a number of cache data element hits. 
     
     
         10 . The method of  claim 1 , wherein generating the first or second normalized cache performance metric is based at least in part on a set of cache sizing rules. 
     
     
         11 . A computer readable medium, embodied in a non-transitory computer readable medium, the non-transitory computer readable medium having stored thereon a sequence of instructions which, when stored in memory and executed by one or more processors causes the one or more processors to perform a set of acts the acts comprising:
 identifying a first tail portion of a first cache partition and a second tail portion of a second cache partition, wherein the first cache partition corresponds to a first cache size and the second cache partition corresponds to a second cache size, wherein evicted data elements are evicted from a respective tail portion;
 generating a first normalized cache performance metric derived from the first tail portion of the first cache partition, wherein the first normalized cache performance metric represents a first incremental value of adding more data elements to the first cache partition; 
 generating a second normalized cache performance metric derived from the second tail portion of the second cache partition, wherein the second normalized cache performance metric represents a second incremental value of adding more data elements to the first cache partition; and 
 adjusting the first cache size of the first cache partition and the second cache size of the second cache partition according to a cache reallocation amount, wherein the cache reallocation amount is derived by comparing the first normalized cache performance metric and the second normalized cache performance metric. 
   
     
     
         12 . The computer readable medium of  claim 11 , wherein determining the cache reallocation amount is responsive to a change to one or more cache attributes. 
     
     
         13 . The computer readable medium of  claim 12 , wherein the cache attributes comprise at least one of, a identifier, a cache size, or a total number of cache queries. 
     
     
         14 . The computer readable medium of  claim 11 , wherein the first cache partition comprises a first portion of the data elements characterized by a first data element type and a second cache from the caches comprises a second portion of the data elements characterized by a second data element type. 
     
     
         15 . The computer readable medium of  claim 14 , wherein the first portion of the data elements comprises extent data and the second portion of the data elements comprises metadata. 
     
     
         16 . The computer readable medium of  claim 11 , further comprising receiving one or more data element attributes corresponding to one or more data elements that are stored in at least one of the cache partitions. 
     
     
         17 . The computer readable medium of  claim 11 , wherein the normalized cache performance metric is derived at least in part from one or more cache tail attributes characterizing a cache tail corresponding to a respective one of the caches. 
     
     
         18 . The computer readable medium of  claim 17 , wherein the cache tail attributes comprise at least one of, a identifier, a tail size, or a number of hits on data elements in the cache tail. 
     
     
         19 . A system comprising:
 a storage medium having stored thereon a sequence of instructions; and   one or more processors that execute the instructions to cause the one or more processors to perform a set of acts, the acts comprising,   
       identifying a first tail portion of a first cache partition and a second tail portion of a second cache partition, wherein the first cache partition corresponds to a first cache size and the second cache partition corresponds to a second cache size, wherein evicted data elements are evicted from a respective tail portion;
 generating a first normalized cache performance metric derived from the first tail portion of the first cache partition, wherein the first normalized cache performance metric represents a first incremental value of adding more data elements to the first cache partition; 
 generating a second normalized cache performance metric derived from the second tail portion of the second cache partition, wherein the second normalized cache performance metric represents a second incremental value of adding more data elements to the first cache partition; and 
 adjusting the first cache size of the first cache partition and the second cache size of the second cache partition according to a cache reallocation amount, wherein the cache reallocation amount is derived by comparing the first normalized cache performance metric and the second normalized cache performance metric. 
 
     
     
         20 . The system of  claim 19 , wherein determining the cache reallocation amount is responsive to a change to one or more cache attributes.