# ARC Policy for Cache Replacement

**Sunday, November 30, 2003**

Taj Khattra passed along a reference to a new
cache replacement algorithm from IBM that was presented at the
FAST conference this spring. The algorithm is conceptually simple,
has low overhead, and the paper shows good results for a wide variety
of workloads. I'll run it through our simulator on Monday.

The basic idea is to keep two LRU lists, one of pages seen once
recently and one of pages seen twice recently. The cache keeps about
twice as many objects in the lists as it can hold in memory. It keeps
a variable number of objects from each list in memory, varying that
number to track the current workload.

I looked at the greedy dual-size paper, but
it's not obvious that it is a good fit. The implementation requires a
priority queue, so replacement is O(log k), where k is the size of the
cache. The algorithm considers both the size of an object and the
cost to fetch it, where we assume a uniform cost.

Irani has a more theoretical paper on caching
with multi-size pages. It's fairly dense, but has a couple of
important ideas early on. First, I haven't thought about what the
cost model should be. We've been using hit rate, but we might
consider bit rate -- the number of bits that don't have to be fetched
rather than the number of objects. Second, computing an optimal
replacement policy for bit rate cost with multi-size objects is NP hard
(according to Fiat); it's unknown whether the hit rate model is in P.

### References

Pei Cao and Sandy Irani.
Cost-Aware WWW Proxy Caching Algorithms
In Proceedings of the Usenix Symposium on Internet Technologies and
Systems (USITS), 1997.

Sandy Irani.
Page Replacement with Multi-Size Pages and Applications to Web Caching.
Algorithmica, vol. 33, no.3, July 2002, pp. 384-409. A preliminary
version appeared in Proceedings of the 29th Symposium on the Theory of
Computing, 1997.

Nimrod Megiddo and Dharmendra S. Modha.
ARC: A Self-Tuning, Low Overhead Replacement Cache
(PDF).
In Proceedings of the USENIX Conference on File and Storage
Technologies (FAST 03), 2003.