Cache allocation system and method using a sampled cache utility curve in constant space

摘要

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 sampled subset, 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 sampling rate is adaptively changed so as to hold the number of location identifiers needed to be stored to compute the cache utility curves to within a set maximum limit.

主权项

1. A method for evaluating interaction between a cache in a computer system and at least one entity, where each entity submits location identifiers corresponding to data storage locations in a storage system, the method comprising, for each of at least one of the entities,
sampling, at a sampling rate, the location identifiers submitted by the at least one entity; computing a hash threshold value for each of the submitted location identifiers; determining, for at least one cache size allocation option of a simulated cache, a cache utility value as a function of the frequency with which the simulated cache includes cache entries corresponding to the sampled location identifiers whose hash threshold values satisfy at least one simulated cache sampling criterion; maintaining a data structure having entries corresponding to the sampled location identifiers whose hash threshold values satisfy the sampling criterion; adaptively changing the sampling rate so as to maintain a bound on the number of location identifiers that are sampled such that the number of entries stored in the data structure is no greater than a maximum number; and compiling the cache utility values for determination of respective cache utility for the respective entities.