ARC 緩存 (Adaptive Replacement)

Published: Tue Feb 17 2026 | Modified: Sat Feb 07 2026 , 4 minutes reading.

ARC 緩存：大戰略家

演算法背後的故事：兩位顧問

想像一位國王（緩存），他的城堡空間有限。他有兩位顧問：

實用主義者 (LRU)： 「留下那些最近來訪的人！她們很活躍！」
歷史學家 (LFU)： 「留下那些經常來訪的人！她們很忠誠！」

多年來，國王們被迫只能選擇一位顧問，而忽略另一位。但在 2003 年，IBM 的研究人員提出了一套新系統：同時聽取兩人的意見，並懲罰那個犯錯的人。

國王在城牆外維護著兩個「幽靈名單」。這些名單記錄了那些最近被驅逐的人的名字。

如果一個在 LRU 幽靈名單上的人回來了，國王意識到：「我不該聽歷史學家的！我需要更多空間給新近項。」 -> 他擴大了 LRU 的區域。
如果一個在 LFU 幽靈名單上的人回來了，國王意識到：「我不該聽實用主義者的！我需要更多空間給高頻項。」 -> 他擴大了 LFU 的區域。

這就是 ARC (自適應置換緩存)。她是一個能夠即時自我調優的系統。

為什麼需要它？

資料庫伺服器： 工作負載是會變的。白天，用戶可能在掃描最近的記錄（LRU 模式）。到了晚上，備份任務可能會反覆讀取相同的舊數據塊（LFU 模式）。ARC 無需重啟即可自動適應。
ZFS 檔案系統： ARC 因驅動了世界上最先進的檔案系統之一 ZFS 而聞名。她為複雜的混合工作負載提供了極高的命中率。

演算法是如何「思考」的

ARC 將緩存分為兩個動態區域：

T1 (近況)： 最近只見過一次的項。
T2 (頻率)： 至少見過兩次的項。

以及兩個幽靈區域（驅逐歷史）：

B1 (近況幽靈)： 從 T1 被驅逐的項。
B2 (頻率幽靈)： 從 T2 被驅逐的項。

魔法邏輯：

設 p 為 T1 的目標大小。
如果我們在 B1 中命中（意味著我們不該從 T1 驅逐她），我們 增加 p（給近況更多空間）。
如果我們在 B2 中命中（意味著我們不該從 T2 驅逐她），我們 減少 p（給頻率更多空間）。

這是一個反饋循環。緩存實際上是在從她自己的驅逐錯誤中學習。

工程決策：專利之牆

在很長一段時間裡，ARC 被 IBM 申請了專利，這阻止了許多開源專案（如 Linux 內核或 PostgreSQL）直接使用她。

替代方案： 這導致了 LIRS 和 Clock-Pro 的發明，她們試圖在不侵犯專利的情況下逼近 ARC 的天才構想。
現狀： 該專利大約在 2020 年過期，所以現在 ARC 可以被所有人免費使用了！

實作參考 (Python 概念版)

實作完整的 ARC 非常複雜（涉及 4 個鏈表！）。這裡也是其自適應邏輯的概念素描。

class ARCCache:
    def __init__(self, capacity):
        self.c = capacity
        self.p = 0  # T1 (近況) 的目標大小
        self.t1 = [] # 近況列表 (真實數據)
        self.t2 = [] # 頻率列表 (真實數據)
        self.b1 = [] # 近況幽靈 (僅元數據)
        self.b2 = [] # 頻率幽靈 (僅元數據)

    def access(self, key):
        # 情況 1: 緩存在 T1 或 T2 中命中
        if key in self.t1:
            self.t1.remove(key)
            self.t2.append(key) # 晉升到頻率表
            return "Hit T1"
            
        if key in self.t2:
            self.t2.remove(key)
            self.t2.append(key) # 更新位置
            return "Hit T2"

        # 情況 2: 幽靈命中 (學習時刻)
        if key in self.b1:
            # 我們太早從 T1 驅逐她了！增加 T1 的大小。
            delta = 1
            if len(self.b1) < len(self.b2):
                delta = len(self.b2) / len(self.b1)
            self.p = min(self.c, self.p + delta)
            self.replace(key)
            # 從幽靈移回真實頻率表
            self.b1.remove(key)
            self.t2.append(key)
            return "Ghost Hit B1 - 向近況調整"

        if key in self.b2:
            # 我們太早從 T2 驅逐她了！減少 T1 的大小 (偏向 T2)。
            delta = 1
            if len(self.b2) < len(self.b1):
                delta = len(self.b1) / len(self.b2)
            self.p = max(0, self.p - delta)
            self.replace(key)
            # 從幽靈移回真實頻率表
            self.b2.remove(key)
            self.t2.append(key)
            return "Ghost Hit B2 - 向頻率調整"

        # 情況 3: 完全未命中
        # 加入 T1 (新項)
        if len(self.t1) + len(self.b1) == self.c:
            if len(self.t1) < self.c:
                self.b1.pop(0)
                self.replace(key)
            else:
                self.t1.pop(0)
        
        self.t1.append(key)
        return "Miss"

    def replace(self, key):
        # 根據參數 'p' 決定殺掉誰
        if len(self.t1) > 0 and (len(self.t1) > self.p or (key in self.b2 and len(self.t1) == self.p)):
            old = self.t1.pop(0)
            self.b1.append(old) # 移入近況幽靈
        else:
            old = self.t2.pop(0)
            self.b2.append(old) # 移入頻率幽靈

小結

ARC 教會我們：僵化的規則在動態的世界裡註定失敗。透過承認自己可能會犯錯並記錄自己的「遺憾」（幽靈名單），ARC 達到了一種純 LRU 或純 LFU 都無法企及的平衡。她提醒我們，真正的智慧標誌不僅在於知道，更在於學習。

Luke Sun