ARC: A Self-Tuning, Low Overhead Replacement Cache

One-line Summary

ARC is a new cache management policy.

Paper Structure Outline

Introduction
1. The Problem
2. Our Contributions
3. A Brief Outline of the Paper
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
A Class of Replacement Policies
1. Double Cache and a Replacement Policy
2. A New Class of Policies
3. LRU
Adaptive Replacement Cache
1. Fixed Replacement Cache
2. The Policy
3. Learning
4. Scan-Resistant
5. Extra History
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
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

LRU

Replaces the least recently used page
Not scan resistant
High concurrency (lock overhead)

LFU

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.

Rui's Blog