Spatial Sampling for Efficient Cache Utility Curve Estimation and Cache Allocation

摘要

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.

主权项

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.