ARC（Adaptive Replacement Cache）徹底解説：仕組み・実装・ZFSやL2ARCとの関係と運用上の注意点
エバープレイ編集部概要：ARCとは何か
ARC（Adaptive Replacement Cache）は、2003年にNimrod MegiddoとDharmendra S. Modhaが提案したキャッシュ置換アルゴリズムです。従来のLRU（Least Recently Used）が持つ短期参照の扱いやスキャン耐性の問題を改善するために設計され、アクセスの「新しさ（recency）」と「頻度（frequency）」を動的にトレードオフして最適化する点が特徴です。低オーバーヘッドで自己適応的に動作するため、実運用のストレージキャッシュ（特にZFSのARC）などで広く利用されています。
基本構造：T1/T2/B1/B2の4リスト
ARCはキャッシュ内部に4つのリストを持ちます。実際にデータを保持するのはT1（recent）とT2（frequent）の2つで、それぞれ最近参照されたが頻度は低い項目、頻繁に参照される項目を管理します。B1/B2は「ゴーストリスト」と呼ばれ、最近追い出されたキーのみ（実データなし）を保持して、将来の参照パターンを学習するために使われます。
- T1：最近1回しか参照されていないがキャッシュ内にあるブロック
- T2：複数回参照された（頻度が高い）ブロック
- B1：最近T1から追い出されたキーの集合（ゴースト）
- B2：最近T2から追い出されたキーの集合（ゴースト）
動作の核心：pパラメータによる適応
ARCは内部で1つのパラメータpを持ち、これはT1（新しさ重視）に割り当てる目標サイズを示します。参照が発生したとき、その参照がT1/T2/B1/B2のどこにあったかによって振る舞いが変わり、特にゴーストリスト（B1/B2）でヒットした場合はpを増減させて新しさと頻度の重みを調整します。結果として、ワークロードがスキャン主体（大量の一回きり参照）であればpは小さく（T1を抑える）、ローカリティが強い頻繁参照ワークロードではpは大きく（T1を抑えてT2を優先）なるという自己適応が達成されます。
アルゴリズムの流れ（簡潔な擬似的説明）
典型的な参照処理は次のようになります。
- 参照がT1/T2にあればそれをT2のMRU（Most Recently Used）側へ移動（頻度を高く評価）してヒット。
- 参照がB1にあればpを増やし、該当ブロックをT2に読み戻す（過去に最近追い出したが再利用されているため頻度側を強化）。
- 参照がB2にあればpを減らし、該当ブロックをT2に読み戻す（頻度側過剰の調整）。
- 参照がどのリストにもなければミス。適宜キャッシュの空きがなければ置換を行い、新しいブロックはT1のMRUに挿入される。
- 置換ポリシーは、size(T1) > p のときはT1から、そうでなければT2から追い出すというルールで新しさ・頻度のバランスを保つ。
ARCの利点
- 自己適応性：ワークロードに応じて自動で新しさと頻度の重みを切り替えるため、追加パラメータ無しで多様なアクセスパターンに強い。
- スキャン耐性：大きな順次スキャンが発生しても、一回きりアクセス主体の領域がT1に留まり過剰にT2を追い出さないため誤った長期間の追い出しを防ぐ。
- 性能：LRUや2Q等の簡易アルゴリズムに比べ、多くの実験でヒット率が高いことが示されている（原論文およびその後の評価）。
実装上の注意点・コスト
ARCは追加でゴーストリスト（B1/B2）を保持するため、キーだけでもメモリオーバーヘッドが発生します。実データはT1/T2にのみ存在するが、追跡用の構造体とポインタ、リスト管理のオーバーヘッドは無視できません。また並行アクセスが多い環境ではロックやスケーリングの工夫が必要で、単純実装だと並行性がボトルネックになる可能性があります。
ZFSのARCとL2ARC
ZFSはメインメモリ上にARCを実装しており、ファイルデータやメタデータをキャッシュします。ZFSではさらにSSDなどを第二レベルキャッシュ（L2ARC）として利用できます。L2ARCは主に読み取りキャッシュを補強し、ARCからフラッシュデバイスへミラーリングする形で機能しますが、書き込みは非同期で実行されるため、L2ARCの設計・チューニング次第で効果が大きく変わります。
- L2ARCの注意点：書き込みI/Oの発生、SSD寿命への影響、遅延によっては期待通りヒット率が上がらないケースがある。
- メモリ比：ZFSのARCは大きく確保するとシステム全体のメモリ競合を招くため、適切な上限設定（arc_max等）が推奨される。
ARCと他アルゴリズムの比較
代表的な比較先はLRU、LFU、LIRS、2Qなどです。ARCはLRUの短所（スキャンに弱い）を克服しつつ、LFUの過去の頻度固定問題も回避します。LIRSは別アプローチで高いヒット率を示すこともありますが、実装の複雑さやオーバーヘッド、適応性という点でARCが有利なケースが多いです。実際の選定はワークロード特性・実行環境・実装コスト次第です。
運用上の現場的ポイント
- モニタリング：ARCのヒット率、T1/T2のサイズ、ゴーストリストのヒット状況を監視し、ワークロード変化を把握する。
- 上限設定：ARCがメモリを過剰に占有しないように上限（arc_max）を設定する。特にZFS環境ではOSやアプリケーションとのメモリ競合に注意。
- L2ARCの導入検討：SSDをL2ARCにする場合は書き込み増加とレイテンシ利得のトレードオフを評価する。小さすぎるL2ARCは効果が薄く、過度に大きいとSSD寿命に影響する。
- 並行性対策：高並列環境ではロック粒度の最適化やシャーディングでスケーラビリティを確保する。
まとめ
ARCは「自己適応的に新しさと頻度を制御する」という設計哲学に基づいた強力なキャッシュ置換アルゴリズムです。実装コストや並行性の課題はあるものの、ZFSなど現実のストレージシステムでの採用実績があり、多様なワークロードに対して堅牢なヒット率を提供します。導入時はメモリ制限、L2ARCの設計、モニタリングとチューニングを併せて行うことで最大限の効果を引き出せます。
参考文献
- Adaptive Replacement Cache — Wikipedia
- N. Megiddo and D. S. Modha, "ARC: A Self-Tuning, Low Overhead Replacement Cache", FAST 2003 (論文 PDF)
- OpenZFS Documentation — ARC
- OpenZFS Documentation — L2ARC
投稿者プロフィール
