Adaptive Replacement Cache (ARC) is a cache management algorithm with better performance^[1] than LRU (Least Recently Used) developed^[2] at the IBM Almaden Research Center. Look up cache in Wiktionary, the free dictionary. ... Cache algorithms are optimizing instructions â€“ algorithms â€“ that a computer program can follow to manage a cache of information stored on the computer. ... This page is a candidate for speedy deletion, because: A page of links If you disagree with its speedy deletion, please explain why on its talk page or at Wikipedia:Speedy deletions. ...

Summary

Basic LRU maintains an ordered list (the cache directory) of resource entries in the cache, with the sort order based on the time of most recent access. New entries are added at the top of the list, after the bottom entry has been evicted. Cache hits move to the top, pushing all other entries down.

ARC improves the basic LRU strategy by maintaining an equal sized phantom history of recently evicted cache entries, and using phantom hits to adapt to recent change in resource usage. The combined cache directory is organised in four LRU lists, one each for:

1. single cache hits
2. double cache hits
3. single phantom hits, cache misses corresponding to an entry in recent history
4. double phantom hits

Cache hits result in an entry moving from the single hit list to the double hit list, unless it's already there. To make room, a phantom hit will shrink the single phantom list, unless the total of double hits and double phantom hits exceeds the cache size.

The size of either hit list is variable, and can grow up to the full cache size.

Cache hits grow the double hit list at the expense of the single hit list.

The whole algorithm can be visualised in a single line:

 . . . [1 hit,evicted [1 hit, in cache <-|-> 2 hits, in cache] 2 hits, evicted] . . . 

Deployment

ARC is currently deployed in IBM's DS6000/DS8000 storage controllers.

Sun's scalable file system ZFS uses a variant^[3] of ARC as an alternative to the traditional Solaris filesystem page cache in virtual memory. The Sun is the star at the centre of the Solar System. ... ZFS, is a free, open-source file system produced by Sun Microsystems for its Solaris Operating System. ... Look up Solaris in Wiktionary, the free dictionary. ...

References

1. ^ One Up on LRU, Usenix :login; August 2003
2. ^ Megiddo and Modha, [ARC home page], with pointers to several articles
3. ^ comments in Solaris ZFS arc.c source file explains differences with original work[[1]]

See Also

• [Linux Memory Management Wiki]
• Bourbonnais, B. [ZFS Dynamics]