Skip to content

Latest commit

 

History

History
139 lines (104 loc) · 4.56 KB

arc-a-self-tuning-low-overhead-replacement-cache.md

File metadata and controls

139 lines (104 loc) · 4.56 KB

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

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)

Course notes by Prof. Andrea Arpaci-Dusseau

  • 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.

Links