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",
}