Multi-Chance Scalable ARC (Adaptive Replacement Cache)

ZFS uses an Adaptive Replacement Cache, ARC, algorithm to manage the data and metadata page cache buffers. The cache is partitioned into most recently used and most frequently used buckets. For each partition it uses ghost caches to derive even better cache hit patterns. This way the algorithm provides a very good short term and long term value differentiation and is scan resistant.

However, the ARC has a serious scaling issues, especially on increasingly more dense multi-processor systems. The fundamental scaling problem is caused due the inherent LRU algorithm used in movement, insertion, and, eviction.

Multi-Chance Scalable ARC implements the lockless ARC. The buffer addresses are stored in page arrays using the atomic instructions. The insertion and removal just become a swap operation in the page array. Thus, it avoids global lock usage in extremely hot path and minimizes “too-many” movements within or across the lists.

Learning Objectives

Objectives of a good page cache
ZFS ARC page cache
Scaling issues in the ARC
Lockless ARC
Implementation details of the lockless ARC algorithm