キャッシュアルゴリズム
キャッシュアルゴリズム（英: cache algorithm）は、コンピュータ上で情報を格納するキャッシュを管理するプログラムまたはハードウェア構造を最適化するアルゴリズム群。キャッシュが一杯になったとき、このアルゴリズムで新たな情報を格納するための場所を選択し確保する。置換アルゴリズムあるいは置換ポリシーとも。
キャッシュのヒット率（hit rate）とは、探しているデータがキャッシュ上で見つかる率（頻度）である。キャッシュサイズを増やさずにヒット率を向上させるには、キャッシュアルゴリズムはより多くの使用（usage）情報を必要とする。
キャッシュのレイテンシとは、あるデータを要求してからキャッシュがそれを返すまでにかかる時間である。より高速な置換戦略は一般に、より少ない使用情報を使用していて、情報の更新にかかる時間が少ない（ダイレクトマップ式なら全く情報を持たない）。
それぞれのキャッシュアルゴリズムは、ヒット率とレイテンシの兼ね合いを考慮している。
アルゴリズム 編集
- 最も効率的なキャッシュアルゴリズムは、今後長期に渡って必要とされないデータを常に捨てていくものである。この理想的アルゴリズムは、Laszlo Belady の最適アルゴリズム、あるいは千里眼置換アルゴリズムなどと呼ばれる。実際には、あるデータを将来に渡ってどれだけ必要としないかを予測することは不可能であり、このアルゴリズムは一般には実装できない。実用上の最適解は実験して初めて得られ、実際のキャッシュアルゴリズムとその最適解との効率を比較することは可能である。
- Least Recently Used (LRU): 最近最も使われていないデータを最初に捨てる。
- Most Recently Used (MRU): 最近最も使われたデータを最初に捨てる。
- Least Frequently Used (LFU): 各データが使われた頻度を保持する。そして、頻繁には使われていないデータを最初に捨てる。
- Adaptive Replacement Cache (ARC): LRU と LFU の間でバランスをとり、最適な結果を得る方式。最近キャッシュから消された情報の履歴を保持するように拡張し、その情報を使って、「かつてキャッシュされていたけれど今はキャッシュから消されている」という情報を元に、LRUとLFUの配分を動的に自動的に調整する。以下の4つのキューを使う。
- LRU (アクセス回数が1回)
- LFU (アクセス回数が2回以上のデータ、これ自体はLRU)
- かつてLRUに入っていた (これ自体はLRU)
- かつてLFUに入っていた (これ自体はLRU)
CPUのキャッシュメモリの場合 編集
CPUのキャッシュメモリとして使用した場合、以下の特徴がある。
- Least Recently Used: このアルゴリズムでは、どのデータがどの時点で使われたかという情報を保持する必要があり、本当に最近最も使われていないデータを常に捨てるようにしようとすると、かなり手間がかかる。一般的実装では、キャッシュライン毎に世代ビット群（age bits）を持たせ、どのラインが最近最も使われていないかを世代ビット群で判断する。その場合、あるキャッシュラインを使うときには、常に全キャッシュラインの世代ビット群を更新する必要がある。
- Most Recently Used: アクセスに局所性を想定できず、LRUの実装が複雑すぎる場合に使われる。MRUの使用例としてはデータベースのメモリキャッシュがある。
- Pseudo-LRU (PLRU): 例えば、キャッシュメモリの連想度が大きい場合（4ウェイ以上）、LRUの実装コストは無視できなくなる。確率的にほぼ常に最近最もつかわれていないデータを捨てれば十分という場合、PLRUアルゴリズムを使う。この場合、キャッシュライン毎に1ビットの情報を保持するだけでよい。
以下は特にCPUのキャッシュメモリのキャッシュアルゴリズムに関する項目である。
- 2ウェイ・セットアソシアティブ: 高速なCPUキャッシュでは、Pseudo-LRU でも遅すぎる。2ウェイのキャッシュメモリではアドレスから対応するキャッシュラインが2つ選択され、その2つのキャッシュライン間でLRU方式で捨てるラインを選択する。このとき、どちらのラインがLRUかを示すことができればよいので、使用情報は1ビットで済む。
- ダイレクトマップ: さらに高速なCPUキャッシュでは、2ウェイでも遅すぎる。ダイレクトマップでは、アドレスから対応するキャッシュラインを1つだけ選択し、そのキャッシュラインが使用済みならそのデータを捨てる。
特殊なケース 編集
他に、以下のような観点を考慮する必要がある。
- データによってコストが異なる場合: 実際に存在する場所からキャッシュまで取り寄せるのにかかるコスト（例えば計算結果のキャッシュの場合は再計算にかかる時間など）を考慮する。
- データによってサイズが異なる場合: 個々のデータの大きさが異なる場合、大きいデータを捨てれば、そこに複数の小さいデータを格納できる可能性がある。
- 時間経過によってデータが無効となる場合: キャッシュによっては、時間経過と共に無効となるデータを扱う場合がある（DNSキャッシュ、ブラウザキャッシュなど）。コンピュータは無効になったデータは捨てなければならないが、キャッシュが十分大きければそのような処理は行わない場合もある。
キャッシュコヒーレンシを保つアルゴリズムも各種存在する。すなわち、複数の独立したキャッシュが同じデータを格納する場合の同期アルゴリズムである（例えば、複数のデータベースサーバが単一の共有データファイルを更新する場合）。