Also as “ARC: A Self-Tuning, Low Overhead Replacement Cache” by the same authors. In Proceedings of 2nd USENIX Conference on File and Storage Technologies (FAST), pp.115–130, San Francisco CA, Mar 31–Apr 2 2003.

This is the paper that proposed Adaptive Replacement Cache (ARC) as a caching algorithm.

ARC implements with two LRU (lease recently used) queues $$L_1$$ and $$L_2$$. Where $$L_1$$ is storing objects that seen only once and $$L_2$$ is storing objects that referenced at least twice. Supposedly, the union of these two LRU queues, which each holds at most $$c$$ items, can provide a better cache than a single LRU queue because it solves the temporal locality problem. But then the total amount of memory is $$2c$$.

ARC therefore assumes $$L_1=T_1+B_1$$ and $$L_2=T_2+B_2$$ which the union of $$L_1$$ and $$L_2$$ is called the directory (with size limit of $$2c$$ and $$L_1$$ is no bigger than $$c$$) and the union of $$T_1$$ and $$T_2$$ is the cache (with size limit of $$c$$). Only the items in cache is stored in memory. Directory indexes the ID of the objects only. The maximum size of the caches $$T_1$$ and $$T_2$$ are $$p$$ and $$c-p$$ respectively, where $$p$$ is adaptive.

When an object is referenced, it is put into the cache, using the following algorithm:

• If cache hit in $$T_1+T_2$$: Move the item to MRU position of $$T_2$$
• If directory hit in $$B_1$$, then p is too small. So load the object into MRU position of $$T_2$$ and set $$p=\min(c, p+\max(\lvert B_2\rvert/\lvert B_1\rvert),1))$$
• If directory hit in $$B_2$$, then p is too big. So load the object into MRU position of $$T_2$$ and set $$p=\min(c, p-\max(\lvert B_1\rvert/\lvert B_2\rvert),1))$$
• If directory miss, do not adjust p but replace items in the directory/cache as follows
• If $$\lvert L_1\rvert=c$$, delete the LRU of $$L_1$$ (which is also the LRU of $$B_1$$)
• If $$\lvert L_1\rvert<c$$, delete the LRU of $$L_2$$ (which is also the LRU of $$B_2$$)
• Then load the item into the MRU position of $$T_1$$

In the above algorithm, we will move an item from $$T$$ to $$B$$ if necessary so that the size constraint imposed by the parameter $$p$$ is honoured.

## Bibliographic data

@article{
title = "Outperforming LRU with an Adaptive Replacement Cache Algorithm",
author = "Nimrod Megiddo and Dharmendra S. Modha",
affiliation = "IBM Almaden Research Center",
journal = "IEEE Computer Magazine",
pages = "58--65",
month = "April",
year = "2004",
}