On Efficient Replacement Policies for Cache Objects with Non-uniform Sizes and Costs

Replacement policies for cache management have been studied extensively. Most policies proposed in the literature tend to be ad hoc and typically exploit the retrieval cost or latency of the objects, object sizes, popularity of requests and temporal correlations between requests. A recent paper [1] studied the caching problem and developed an optimal replacement policy C∗₀ under the independent reference model (IRM), assuming nonuniform object retrieval costs. In this paper, we consider the more general setting where both object sizes and their retrieval costs are non-uniform. This setting arises in a number of applications such as web caching and view management in databases and in data warehouses. We consider static selection as a benchmark when evaluating the performance of replacement policies. Our first result is negative: no dynamic policy can achieve a better performance than the optimal static selection in terms of long run average metric. We also prove that a (dynamic) replacement policy attains this optimum iff the stochastic chain induced by it is irreducible. We show that previously studied optimal policies such as A₀ and C∗₀ are special cases of our optimal policy. This motivates the study of static selection. For the general case we are considering, static selection is NP-complete. Let K denote the maximum cache capacity and let K′ be the sum of sizes of all objects minus the cache capacity K. We propose a polynomial time algorithm that is both K-approximate w.r.t. the fractional optimum solution and H_K′ -approximate w.r.t. the integral optimum solution, where H_K′ is the K′-th Harmonic number. In addition, we develop a K-competitive dynamic policy and show that K is the best possible approximation ratio for both static algorithms and dynamic policies.