ARC: A Self-Tuning, Low Overhead Replacement Cache

One-line Summary

ARC is a new cache management policy.

Paper Structure Outline

  1. Introduction

    1. The Problem

    2. Our Contributions

    3. A Brief Outline of the Paper

  2. Prior Work: A Brief Review

    1. Offline Optimal

    2. Recency

    3. Frequency

    4. Recency and Frequency

    5. Temporal Distance Distribution

    6. Caching using Multiple Experts

    7. Ghost Caches

    8. Summary

  3. A Class of Replacement Policies

    1. Double Cache and a Replacement Policy

    2. A New Class of Policies

    3. LRU

  4. Adaptive Replacement Cache

    1. Fixed Replacement Cache

    2. The Policy

    3. Learning

    4. Scan-Resistant

    5. Extra History

  5. Experimental Results

    1. Traces

    2. OLTP

    3. Two Traces: P8 and P12

    4. ARC and 2Q

    5. ARC and MQ

    6. ARC and LRU

    7. ARC is Self-Tuning and Empirically Universal

    8. A Closer Examination of Adaptation in ARC

  6. Conclusions

Background & Motivation

The goals/metrics of this work are:

  • High hit rate

  • Low overhead

    • computational & space

    • locking overhead (high concurrency)

  • Scan resistant: A large file does not blow out the cache

  • No parameters to tune (self-tuning)

  • Online algorithm: Handles any workload; Changes dynamically

  • Balance between recency & frequency

  • Empirically universal: Performs as well as fixed replacement policies

Some assumptions are:

  • The replacement policy (selecting the page to page out) is investigated

  • No prefetching (assume all demand paging)

  • Only look at read policy (no write)

  • The cache receives a continuous stream of requests for pages

Existing Algorithms

Offline Optimal

  • Replaces the furthest page in the future

  • Upper bound on the achievable hit ratio by any online policy


  • Replaces the least recently used page

  • Not scan resistant

  • High concurrency (lock overhead)


  • Replaces the least frequently used page

  • High implementation complexity

  • Does not adapt to changes in access patterns (pages with previous high frequency counts may no longer be useful)

LRU-k (LRU-2 in paper, most common)

  • Track time of last 2 accesses of each page

  • Replaces the page with the least recent penultimate reference

  • Expensive algorithm (for maintaining a priority queue)

2Q (VLDB '94, used in PostgreSQL)

  • Keeps three working sets: Current working set, previous working set, and the long term working set.

  • Scan resistant

  • Easy to implement

  • Takes into account both recency and frequency

  • 2Q has some sizing parameters (K_in and K_out)

MQ (Multiple queues, USENIX '01)

  • Focused on a replacement algorithm for buffer caches (second level on the storage system, below the traditional OS buffer cache)

  • Put items in m LRU queues according to their frequency. Q_i contains pages that have been seen at least 2^i times but no more than 2^(i+1)-1 times recently

  • An expiration time is associated with every item

  • Maintains Q_out: Ghost cache, contains references instead of actual data

  • Not robust under a wider range of workloads

  • Higher overhead than LRU, ARC, 2Q (need to check time stamps of pages on every request)

Design and Implementation

ARC is:

  • Parameter-less

  • Self-tuning

  • Simple to implement

  • Scan resistant

  • Considers both recency and frequency

Two LRU lists are maintained: L1 contains pages accessed once recently (recency), partitioned into a top portion T1 and a bottom portion B1. Only T1 is in cache. L2 contains pages accessed at least twice recently (frequency), partitioned into a top portion T2 and a bottom portion B2. Only T2 is in cache. The middle line between the two lists can be shifted.

  • Hit in T1 or T2: MRU to T2

  • Miss in B1: MRU to T2, increase p, move T1

  • Miss in B2: MRU of T2, decrease p

  • Miss everywhere (not in B1/B2): MRU in T1, replace some LRU (complicated)

New Vocabulary

  • Demand paging: A disk page is copied into physical memory only if an attempt is made to access it and that page is not already in memory.

Last updated