ARC: Adaptive Replacement Cache with Ghost Lists

The four-list structure

ARC maintains two real caches and two ghost caches:

| List | Contents | Size | |---|---|---| | T1 | Recently seen once (new pages) | p | | T2 | Seen at least twice (frequently used pages) | c - p | | B1 | Ghost: recently evicted from T1 (keys only, no data) | ≤ c | | B2 | Ghost: recently evicted from T2 (keys only, no data) | ≤ c |

c = cache capacity. p = adaptive parameter, the target size of T1. T1 + T2 together hold at most c pages. B1 and B2 hold keys only (no data), recording what was recently evicted.

Request handling logic

from collections import OrderedDict

class ARC:
    def __init__(self, cache_size):
        self.c = cache_size
        self.T1 = OrderedDict()   # recent: seen once
        self.B1 = OrderedDict()   # ghost of T1
        self.T2 = OrderedDict()   # frequent: seen 2+ times
        self.B2 = OrderedDict()   # ghost of T2
        self.p = 0                # target size of T1

    def request(self, key):
        # Case 1: Cache hit in T1 or T2
        if key in self.T1:
            del self.T1[key]
            self.T2[key] = True   # promote to frequent
            return True
        if key in self.T2:
            self.T2.move_to_end(key)
            return True

        # Case 2: Ghost hit in B1 — T1 was too small
        if key in self.B1:
            delta = len(self.B2) / max(1, len(self.B1))
            self.p = min(self.c, self.p + max(1, delta))
            self._replace(key)
            del self.B1[key]
            self.T2[key] = True
            return False

        # Case 3: Ghost hit in B2 — T2 was too small
        if key in self.B2:
            delta = len(self.B1) / max(1, len(self.B2))
            self.p = max(0, self.p - max(1, delta))
            self._replace(key)
            del self.B2[key]
            self.T2[key] = True
            return False

        # Case 4: Complete miss
        total = len(self.T1) + len(self.B1)
        if total >= self.c:
            if len(self.T1) < self.c:
                self.B1.popitem(last=False)  # evict from ghost
                self._replace(key)
            else:
                self.T1.popitem(last=False)  # evict from T1 directly
        elif len(self.T1) + len(self.T2) + len(self.B1) + len(self.B2) >= 2 * self.c:
            if self.B2:
                self.B2.popitem(last=False)
            self._replace(key)

        self.T1[key] = True   # new page enters T1
        return False

    def _replace(self, key):
        """Evict from T1 or T2 based on p."""
        if self.T1 and (len(self.T1) > self.p or (key in self.B2 and len(self.T1) == self.p)):
            # Evict from T1 → move to B1
            old_key, _ = self.T1.popitem(last=False)
            self.B1[old_key] = True
        else:
            # Evict from T2 → move to B2
            old_key, _ = self.T2.popitem(last=False)
            self.B2[old_key] = True

Adaptation examples

Starting with p = 0 (all space allocated to T2/frequent):

Workload shifts to new data access:

• Many B1 ghost hits occur (recently evicted T1 pages being re-requested)
• Each B1 hit increases p → T1 grows → more space for recently-seen pages
• ARC adapts toward LRU behavior

Workload shifts to repeated access of stable hot set:

• Many B2 ghost hits occur (stable pages being re-requested after eviction)
• Each B2 hit decreases p → T2 grows → more space for frequent pages
• ARC adapts toward LFU behavior

cat /proc/spl/kstat/zfs/arcstats | grep -E "^(c |size|hits|misses|mfu_hits|mru_hits)"