キャッシュアルゴリズム
最も効率的なキャッシュアルゴリズムは、今後長期に渡って必要とされないデータを常に捨てていくものである。この理想的アルゴリズムは、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)