ARC - Adaptive Replacement Cache for Storage Systems       

Machine Organization Accomplishment | 2003

IBM researchers: Nimrod Megiddo, Dharmendra S. Modha

Where the work was done: Almaden Research Center

What we accomplished: Adaptive Replacement Cache (ARC) produces improvements up to 2× in storage systems.

ARC and its cousin, Sequential Adaptive Replacement Cache (SARC) improve performance hit rate by up to 2× on mixed random-sequential workloads, without affecting sequential performance. This technology is embedded in many IBM disk storage systems.  ARC dynamically, adaptively, and continually balances between the recency and frequency components in an online and self-tuning fashion to adaptively and continually revise its assumptions about the workload. ARC works uniformly well across varied workloads and cache sizes without any need for workload specific a priori knowledge or tuning. The policy ARC is simple-to-implement and, like LRU, has constant complexity per request. (Nimrod Megiddo and Dharmendra S. Modha, pictured, l. and r.)

Related link: ARC: A Self-Tuning, Low Overhead Replacement Cache, USENIX Conference on File and Storage Technologies (FAST 03), San Francisco, CA, pp. 115-130, March 31-April 2, 2003.

  • Winner of 2014 USENIX/FAST Test-of-Time Award.
  • 1000+ citations.
  • Taught in universities throughout the world.
  • Winner of 2004 Pat Goldberg Memorial Award.

Image credit: Courtesy of Dharmendra Modha