Spatial Sampling for Efficient Cache Utility Curve Estimation and Cache Allocation

Abstract

Cache utility curves are determined for different software entities depending on how frequently their storage access requests lead to cache hits or cache misses. Although possible, not all access requests need be tested, but rather only a subset, comprising fewer than all of the requests, determined by whether a hash value of each current storage location identifier (such as an address or block number) meets one or more sampling criteria. The subset may comprise as few as 20% or 10% or even less of the access requests.

We claim: 
     
         1 . A method for evaluating interaction between a cache in a computer system and at least one entity, where each entity submits a stream of location identifiers corresponding to data storage locations in a storage system, the method comprising:
 for each of at least one of the entities, determining, for each of a plurality of cache size allocation options of a simulated cache, a cache utility value as a function of the frequency with which the simulated cache includes cache entries corresponding to a selected sample of the entity's submitted identifiers;   sampling the stream of location identifiers by selecting a sub-set comprising fewer than all of the location identifiers in the stream and, for each selected location identifier in the stream, computing a respective hash value as a hash function of the selected location identifier;   selecting, as the selected samples of location identifiers, those location identifiers whose hash values satisfy a simulated cache selection condition; and   compiling the cache utility values for determination of respective cache utility for the respective entities.   
     
     
         2 . The method of  claim 1 , in which the simulated cache selection condition is that a function of the hash value falls within a numerical range. 
     
     
         3 . The method of  claim 2 , further comprising, by changing the numerical range, changing the percentage of storage location identifiers that are sampled. 
     
     
         4 . The method of  claim 2 , in which the function of the hash value is an inequality and the numerical range is a subset of a larger numerical range. 
     
     
         5 . The method of  claim 2 , further comprising choosing the selection condition to be that the hash value, in binary form, includes at least one predetermined bit pattern. 
     
     
         6 . The method of  claim 2 , further comprising:
 applying a bit mask to each hash value; and   choosing the function of the hash value to be a numerical value of the bits remaining after application of the bit mask.   
     
     
         7 . The method of  claim 2 , further comprising:
 choosing the numerical range to be a power n of 2;   selecting a sub-set of no more than n bits of each hash value; and   choosing the function of the hash value to be a numerical value of the selected sub-set of bits.   
     
     
         8 . The method of  claim 1 , further comprising:
 evaluating a reuse-distance distribution for the simulated cache entries and a rate of change of the reuse-distance distribution;   increasing the rate at which submitted identifiers are sampled when the rate of change is above a first threshold value and decreasing the rate at which the submitted identifiers are sampled when the rate of change is below a second threshold value.   
     
     
         9 . The method of  claim 1 , in which the cache utility value is a cache utility ratio, further comprising adjusting the cache utility ratio as a function of time since the storage location identifiers have been submitted by the currently selected entity. 
     
     
         10 . The method of  claim 1 , in which the cache utility value is a cache utility rate, further comprising:
 measuring the respective cache utility rate for the entities; and   allocating cache space among the selected ones of the entities also as a function of their respective cache utility rates.   
     
     
         11 . The method of  claim 10 , in which the cache utility rate indicates cache access results per system event. 
     
     
         12 . The method of  claim 11 , in which the system event is chosen from the group: instructions executed, either as an absolute number or per some unit time; elapsed time; translation lookaside buffer (TLB) misses; number of transactions processed; application-level and workload-specific operations such as database query count. 
     
     
         13 . The method of  claim 1 , in which the cache utility value is a cache miss ratio. 
     
     
         14 . The method of  claim 13 , further comprising providing the cache miss ratios for each entity in the form of a miss ratio curve (MRC). 
     
     
         15 . The method of  claim 1 , in which the cache utility ratio is a cache hit ratio. 
     
     
         16 . The method of  claim 1 , further comprising:
 simulating the cache as a least-recently used (LRU) data structure configured as a Mattson stack;   varying the cache size allocation options hypothetically by changing a reuse-distance cutoff value; and   determining whether the simulated cache includes cache entries corresponding to the sampled location identifiers by comparing a current reuse distance associated with each of the sampled location identifiers with the reuse-distance cutoff value.   
     
     
         17 . The method of  claim 16 , further comprising:
 evaluating a reuse-distance distribution for the cache entries and a rate of change of the reuse-distance distribution; and   increasing the rate at which the identifiers are sampled when the rate of change is above a first threshold value and decreasing the rate at which the identifiers are sampled when the rate of change is below a second threshold value.   
     
     
         18 . The method of  claim 1 , in which the cache utility value is a cache utility ratio, further comprising:
 receiving the storage location identifiers in a cache analysis system that is remote from the storage system and includes the simulated cache; and   determining the cache utility ratios in the cache analysis system.   
     
     
         19 . The method of  claim 1 , in which the cache utility value is a cache utility ratio, further comprising:
 in a primary system, partitioning a single actual cache into smaller per-entity caches, each of which operates independently; and   the relative sizes of the per-entity caches are allocated and adjusted according to their respective cache utility ratios.   
     
     
         20 . The method of  claim 1 , in which the cache in the computer system includes entries from multiple entities, further comprising individually replacing or evicting cache entries as a function of the cache utility values of the respective entities. 
     
     
         21 . The method of  claim 1 , in which the cache in the computer system is managed using a non-Least-Recently-Used replacement policy for entries from a plurality of the entities, further comprising:
 providing a simulated cache for each entity; and   compiling the cache utility values per simulated cache.   
     
     
         22 . The method of  claim 21 , in which the simulated caches function sequentially. 
     
     
         23 . The method of  claim 21 , in which the simulated caches are provided simultaneously and function in parallel. 
     
     
         24 . The method of  claim 1 , further comprising implementing the plurality of cache size allocation options by providing a corresponding plurality of simulated caches of different sizes, 
     
     
         25 . The method of  claim 1 , in which the sub-set comprises less than or equal to 20% of the location identifiers in the stream. 
     
     
         26 . The method of  claim 25 , in which the sub-set comprises less than or equal to 10% of the location identifiers in the stream. 
     
     
         27 . A system for evaluating interaction between a cache in a computer system and at least one entity, where each entity submits a stream of location identifiers corresponding to data storage locations in a storage system, comprising
 a processor and a cache analysis system including software modules provided, for each of at least one of the entities:   for determining, for each of a plurality of cache size allocation options of a simulated cache, a cache utility value as a function of the frequency with which the simulated cache includes cache entries corresponding to a selected sample of the entity's submitted identifiers;   for sampling the stream of location identifiers by selecting a sub-set of comprising fewer than all of the location identifiers in the stream, for each selected location identifier in the stream, computing a respective hash value as a hash function of the selected location identifier;   for selecting, as the selected samples of location identifiers, those location identifiers whose hash value satisfies a simulated cache selection condition; and   for compiling the cache utility values for determination of respective cache utility for the respective entities.   
     
     
         28 . The system of  claim 27 , in which the cache analysis system is further provided:
 for evaluating a reuse-distance distribution for the simulated cache entries and a rate of change of the reuse-distance distribution; and   for increasing the rate at which submitted identifiers are sampled when the rate of change is above a first threshold value and decreasing the rate at which the submitted identifiers are sampled when the rate of change is below a second threshold value.   
     
     
         29 . The system of  claim 27 , in which:
 the cache utility value is a cache utility ratio; and   the cache analysis system is further provided for adjusting the cache utility ratio as a function of time since the storage location identifiers have been submitted by the currently selected entity.   
     
     
         30 . The system of  claim 27 , in which:
 the cache utility value is a cache utility rate; and   the cache analysis system is further provided for measuring the respective cache utility rate for the entities and for allocating cache space among the selected ones of the entities also as a function of their respective cache utility rates.   
     
     
         31 . The system of  claim 30 , in which the cache utility rate indicates cache access results per system event. 
     
     
         32 . The system of  claim 30 , in which the system event is chosen from the group: instructions executed, either as an absolute number or per some unit time; elapsed time; translation lookaside buffer (TLB) misses; number of transactions processed; application-level and workload-specific operations such as database query count. 
     
     
         33 . The system of  claim 27 , in which the cache utility value is a cache miss ratio. 
     
     
         34 . The system of  claim 27 , in which the cache utility value is a point on a miss rate curve (MRC). 
     
     
         35 . The system of  claim 27 , in which the cache utility ratio is a cache hit ratio. 
     
     
         36 . The system of  claim 27 , in which:
 the simulated cache is configured as a least-recently used (LRU) data structure configured as a Mattson stack;   the cache analysis system is provided for varying the cache size allocation options hypothetically by changing a reuse-distance cutoff value; and for determining whether the simulated cache includes cache entries corresponding to the sampled location identifiers by comparing a current reuse distance associated with each of the sampled location identifiers with the reuse-distance cutoff value.   
     
     
         37 . The system of  claim 27 , in which the cache analysis system is configured within a system that is separate from the computer system that includes the storage system. 
     
     
         38 . The system of  claim 27 , in which the cache in the computer system is managed using a non-Least-Recently-Used replacement policy for entries from a plurality of the entities, further comprising: a simulated cache for each entity, said cache utility values being compiled per simulated cache. 
     
     
         39 . The system of  claim 38 , in which the simulated caches function sequentially. 
     
     
         40 . The system of  claim 38 , in which the simulated caches function simultaneously, in parallel. 
     
     
         41 . The system of  claim 38 , in which the simulated cache is a simulated cache component that comprises a plurality of simulated caches of different sizes implementing the plurality of cache size allocation options.