Jeremy Hylton : weblog : 2003-11-30

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.