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 and . Where is storing objects that seen only once and is storing objects that referenced at least twice. Supposedly, the union of these two LRU queues, which each holds at most 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 .

ARC therefore assumes and which the union of and is called the directory (with size limit of and is no bigger than ) and the union of and is the cache (with size limit of ). Only the items in cache is stored in memory. Directory indexes the ID of the objects only. The maximum size of the caches and are and respectively, where is adaptive.

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

  • If cache hit in : Move the item to MRU position of
  • If directory hit in , then p is too small. So load the object into MRU position of and set
  • If directory hit in , then p is too big. So load the object into MRU position of and set
  • If directory miss, do not adjust p but replace items in the directory/cache as follows
    • If , delete the LRU of (which is also the LRU of )
    • If , delete the LRU of (which is also the LRU of )
    • Then load the item into the MRU position of

In the above algorithm, we will move an item from to if necessary so that the size constraint imposed by the parameter 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",
}