キャッシュ置換アルゴリズムとは：LRU・LFU・ARCほか主要手法の定義と比較

キャッシュ置換アルゴリズム（LRU・LFU・ARCほか）を定義と比較でわかりやすく解説。性能・用途・実装差から最適な選択肢を導きます。

キャッシュアルゴリズムは、キャッシュ（高速な一時記憶領域）内の項目を管理し、キャッシュが満杯になったときにどの項目を削除するかを決定するための手法です。キャッシュの性能評価に使われる代表的指標には、キャッシュからリクエストが満たされた割合を表す「ヒット率」と、キャッシュからデータが取り出されるまでの時間を表す「レイテンシーという」があります。キャッシュアルゴリズムは、ヒット率を高めつつレイテンシーと実装コスト（メモリ・CPU）を抑えるというトレードオフを扱います。

最適解（理想）と実用アルゴリズムの立場

理論上での最適解は、将来のアクセスパターンを完全に知っていると仮定して「もっとも先に参照されなくなる（将来最も遠い将来に参照される）項目」を削除する方法で、Beladyの最適アルゴリズム（しばしば「オプティマル」や透視アルゴリズムと呼ばれています）と呼ばれます。しかし将来の参照を事前に知ることは現実的に不可能なため、実際には予測・近似手法を用いる各種のキャッシュ置換アルゴリズムが使われます。実運用では、選択したアルゴリズムの性能を最適（Belady）と比較して評価することがよく行われます。

主要な置換アルゴリズム（定義と特徴）

• Least Recently Used（LRU）：最も長い間参照されていない（＝最も最近参照されたのが最も古い）項目を削除します。直感的で効果的ですが、厳密なLRUを高速に実装するには全要素の順序管理（例：双方向連結リスト＋ハッシュ表）が必要で、管理オーバーヘッドがあります。LRU系のファミリーとしては、2Q（Theodore Johnson と Dennis Shasha）、LRU-K（Pat O'Neil、Betty O'Neil、Gerhard Weikum）などが存在します。LRUは短期的な再参照性（最近使われたものは再び使われることが多い）に適しています。
• Most Recently Used（MRU）：直近に参照された（最も最近使用された）項目を最初に削除します。アクセスが一度しかない一過性のワークロード（ストリーム的にしか参照されないデータ）が多い場面ではMRUの方が有利になることがあります。例えば一部のデータベースワークロードで見られます（データベースのキャッシュなど）。
• 擬似LRU（PLRU）：厳密なLRUの実装が難しい（特にハードウェアのCPUキャッシュなど）場合に使われる近似手法です。例えば2ウェイや4ウェイのセット別に簡易ビット（ツリー構造や「年齢ビット」）で最近性を近似します。PLRUはメタデータ（ビット数）が少なくて済む一方、真のLRUと比べると誤差（望ましくない置換）を生じることがあります。また、CLOCKアルゴリズム（セカンドチャンス）はソフトウェア領域でよく使われるLRU近似の一つです。
• Least Frequently Used（LFU）：項目ごとに参照回数をカウントし、参照頻度が最も低いものを削除します。長期的に頻繁に参照される項目を保持するのに有効ですが、古いがかつて高頻度だった項目が残り続ける「スティッキー」問題を抱えるため、頻度を時間とともに減衰（エイジング）させる工夫が必要です。
• Adaptive Replacement Cache（ARC）：LRUとLFUの良い点を動的に取り入れる適応型手法です。アクセスパターンに応じてLRUスタックとLFU的な構造の比重を変え、さまざまなワークロードに対して安定した性能を提供します。ARCは実運用で高い性能を示すことが多く、特にデータベースやストレージキャッシュで注目されています。
• Multi-Queue（MQ）キャッシング：複数の優先度キューを用いて最近性と頻度を組み合わせて管理する手法です。Y. Zhou、J.F. Philbin、Kai Liらによって提案され、ワークロードに応じてデータを段階的に昇格・降格させることで、LRUやLFUの欠点を緩和します。

ハードウェア寄り・セット連想キャッシュでの手法

• 2ウェイセット連想：CPUキャッシュでよく使われる方式で、新しいアドレスはキャッシュ内の2つの候補位置のどちらかにマップされます。その2つのうち最近使用頻度が低い（古い）ほうを追い出します。各ペアに1ビット（どちらが最近使われたかを示す）を持つだけでPLRUの簡易版が実現できます。
• ダイレクトマップ（直接マッピング）キャッシュ：各アドレスがキャッシュ内の単一のスロットに固定マップされる方式です。置換の自由度が小さい代わりにハードウェア実装が非常にシンプルで高速です。衝突（異なるアドレスが同じスロットを使う）によるスラッシングが起きやすいのが欠点です。

実装上・運用上の追加考慮点

• コスト（取得コスト）の違い：取得に時間や資源がかかるデータ（例えば遠隔のストレージから取り寄せるオブジェクト）は、頻度や最近性に加えてコストを考慮して保持するのが合理的です。GreedyDual-Size（GDS）やGDSFのようなコスト・サイズを考慮するアルゴリズムがあります。
• サイズの違い：アイテムごとに占有するキャッシュ容量が異なる場合、単純に個数で置換を決めると効率が落ちます。大きなオブジェクトを捨てて小さなオブジェクトを多数入れる判断が必要になることがあるため、サイズを重み付けする手法が使われます。
• 有効期限（TTL）や時間依存性：ニュースやDNS、Webブラウザのキャッシュのように、データ自体に期限（TTL）がある場合は期限切れを基に破棄できます。こうしたケースでは単純な置換アルゴリズムだけではなく、期限管理のロジックが重要になります。
• 頻度と最近性のバランス：ワークロードが短期的なリファレンスに偏るか、長期にわたる人気に偏るかで適切なアルゴリズムは変わります。例えば短期局所性が強ければLRU系、長期人気を維持したいならLFU系やARCが有利です。

拡張アルゴリズムと実運用での選択

実際のシステムでは、単一の置換ポリシーだけでなく以下のような拡張・組み合わせが使われます。

• LRUの近似・簡易化：CLOCK、PLRU、セグメント化（2Q）など。実装コストを下げつつLRUに近い振る舞いを得るために使われます。
• 適応型手法：ARC や MQ のようにワークロードに応じてパラメータを動的に調整する方式は、汎用的な環境で安定した性能を出しやすいです。
• コスト・サイズを考慮した手法：GDS/GDSFやその他の重み付きスコアリング方式は、ネットワーク取得コストやデータサイズを考慮して利得の高い保持を行います。

キャッシュ一貫性（複数キャッシュが同じデータを持つ場合）

キャッシュの一貫性を保つためのアルゴリズムやプロトコルも別途重要です。これは複数の独立したキャッシュが同じデータを保持し、かつデータの更新が発生し得る状況（分散データベース、分散キャッシュ、プロキシ群など）で適用されます。主な戦略は、更新時の同期（Write-through / Write-back、ディレクトリベースのコヒーレンシ機構）や、無効化（invalidate）／更新通知（update）を行うプロトコルです。

まとめ（選び方の指針）

• 短期的な局所性（最近使ったものがまた使われる）→ LRU またはその近似（CLOCK, PLRU）
• 長期的に頻繁に使われるものを保持したい→ LFU、もしくは ARC のような適応型
• ハードウェア実装でメタデータを最小化したい→ PLRU / ダイレクトマップ / セット連想
• アイテムの取得コストやサイズが重要→ GDS/GDSF 等の重み付き手法
• ワークロードが混在・予測困難→ ARC や MQ のような適応的・多階層的手法が有効

キャッシュ設計は、アクセスパターン（短期／長期の局所性）、アイテムの性質（サイズ、取得コスト、TTL）、実装制約（メモリ、CPU、ハードウェア）を総合的に考慮して最適なアルゴリズムを選ぶことが重要です。

質問と回答

Q:キャッシュ・アルゴリズムとは何ですか?

Q:ヒット率とは何ですか?

Q:レイテンシーとは何ですか?

Q:Beladyの最適化アルゴリズムとは何ですか?

Q:LRU（Least Recently Used）とはどのような仕組みですか?

Q: MRU（Most Recently Used）はどのように機能するのですか?

Q: キャッシュコヒーレンシーを維持するために、他にどのようなアルゴリズムがありますか?

文字で検索