キャッシュアルゴリズム
キャッシュアルゴリズムとは、キャッシュやデータのグループを管理するために使用されるアルゴリズムのことです。キャッシュが一杯になると、キャッシュからどの項目を削除すべきかを決定します。ヒット率という言葉は、キャッシュからリクエストがどれくらいの頻度で提供されるかを表しています。レイテンシーという用語は、キャッシュされたアイテムがどれくらいの時間得られるかを説明します。キャッシュアロリズムはヒットレートとレイテンシーのトレードオフです。
- 最も効率的なキャッシングアルゴリズムは、将来的に最も長く必要とされない情報を常に破棄することであろう。この最適な結果は、Beladyの最適アルゴリズムまたは透視アルゴリズムと呼ばれています。未来の情報がどこまで必要になるかを予測することは一般的に不可能であるため、これは一般的には実際には実装できない。実用的な最小値は実験後にのみ計算することができ、実際に選択されたキャッシュアルゴリズムの有効性を最適な最小値と比較することができる。
- Least Recently Used (LRU): 最近使用されたアイテムを最初に削除します。このアルゴリズムは、いつ何が使われたかを追跡する必要があります。アルゴリズムが常に最近使用されたものを破棄するようにしたい場合には、これはコストがかかります。この技術の一般的な実装では、キャッシュラインのための「年齢ビット」を保持し、年齢ビットに基づいて「最近使用されたもの」のキャッシュラインを追跡する必要がある。このような実装では、あるキャッシュラインが使用されるたびに、他のすべてのキャッシュラインの年齢が変化します。LRUは実際には、以下のようなメンバーを持つキャッシュアルゴリズムのファミリーです。Theodore JohnsonとDennis Shashaによる2Q、Pat O'Neil、Betty O'Neil、Gerhard WeikumによるLRU/Kなどがある。
- Most Recently Used (MRU)。このアルゴリズムは、最近使用されたアイテムを最初に削除します。このキャッシュメカニズムは、データベースのメモリキャッシュで一般的に使用されています。
- 擬似的なLRU（PLRU）。LRUの実装が非常に難しいケースがあります。そのような場合には、ほとんどの場合、最も最近使用されていない項目の1つが削除されることを知っていれば十分かもしれません。PLRUアルゴリズムは、キャッシュアイテムごとに1ビットだけで動作するため、そこで使用することができます。
- 2ウェイセット連想：PLRUですら遅い高速CPUキャッシュ用。新しいアイテムのアドレスは、キャッシュ内の2つの可能性のある場所のうちの1つを計算するために使用されます。2つのうちのLRUは破棄されます。これは、2つのうちのどちらが最も最近使用されなかったかを示すために、キャッシュラインのペアごとに1ビットを必要とする。
- ダイレクトマップキャッシュ：2ウェイセットの連想キャッシュですら遅い最高速度のCPUキャッシュ用。新しいアイテムのアドレスは、キャッシュの中で移動が許可されている1つの場所を計算するために使用されます。前にあったものは破棄されます。
- 最小使用頻度（LFU）。LFUはアイテムが必要とされる頻度をカウントします。最も使用頻度の低いものは最初に廃棄されます。
- Adaptive Replacement Cache (ARC)：LRUとLFUの間で常にバランスをとり、複合的な結果を向上させます。
- マルチキュー(MQ)キャッシングアルゴリズム。(Y. Zhou J.F. Philbin と Kai Li による)。
他にも考慮すべき点があります。
- コストの違うアイテム：入手に時間がかかるものなど、コストのかかるアイテムはキープしておきましょう。
- アイテムがより多くのキャッシュを占有しています。アイテムのサイズが異なる場合、キャッシュは大きなアイテムを捨てて小さなアイテムをいくつか収納したい場合があります。
- 時間とともに期限切れになるアイテムキャッシュの中には、期限切れの情報を保持するものがあります（ニュースキャッシュ、DNSキャッシュ、Webブラウザのキャッシュなど）。コンピュータは、期限切れのアイテムを破棄することがあります。キャッシュのサイズによっては、アイテムを廃棄するための更なるキャッシングアルゴリズムは必要ないかもしれません。
キャッシュの一貫性を維持するための様々なアルゴリズムも存在します。これは、同じデータに対して複数の独立したキャッシュが使用されている場合にのみ適用されます（例えば、複数のデータベースサーバが単一の共有データファイルを更新する場合など）。
どのメモリロケーションがどのキャッシュロケーションでキャッシュできるか
質問と回答
Q:キャッシュ・アルゴリズムとは何ですか?
A:キャッシュアルゴリズムとは、キャッシュやデータ群を管理するために使用されるアルゴリズムです。キャッシュが一杯になったときに、どの項目を削除すべきかを決定します。
Q:ヒット率とは何ですか?
A: ヒット率とは、あるリクエストがキャッシュから提供される頻度を表します。
Q:レイテンシーとは何ですか?
A: レイテンシーとは、キャッシュされたアイテムがどのくらいの時間取得できるかを表します。
Q:Beladyの最適化アルゴリズムとは何ですか?
A: Beladyの最適アルゴリズムは、千里眼アルゴリズムとも呼ばれ、将来最も長い時間必要とされない情報を常に破棄する効率的なキャッシュアルゴリズムです。この結果は、はるか先の未来に何が必要とされるかを予測する必要があるため、一般に実用化することはできません。
Q:LRU（Least Recently Used）とはどのような仕組みですか?
A:LRUは、最も最近使用されたアイテムを最初に削除し、各キャッシュラインの「年齢ビット」を使用し、年齢ビットに基づき、どれが最も最近使用されたかを追跡することによって、何がいつ使用されたかを追跡することが必要です。あるキャッシュラインが使用されるたびに、他のすべてのキャッシュラインの年齢がそれに応じて変更されます。
Q: MRU（Most Recently Used）はどのように機能するのですか?
A: MRUは最も最近使用されたアイテムを最初に削除します。このキャッシュメカニズムは、データベースのメモリキャッシュによく使用されます。
Q: キャッシュコヒーレンシーを維持するために、他にどのようなアルゴリズムがありますか?
A: 複数のデータベースサーバーが1つの共有データファイルを更新するような、共有データに対して複数の独立したキャッシュを使用する場合、キャッシュコヒーレンシを維持するための様々なアルゴリズムが存在します。
