キャッシュアルゴリズムの情報収集
そもそもキャッシュとは
様々な情報伝達経路において、ある領域から他の領域へ情報を転送する際、その転送遅延を極力隠蔽し転送効率を向上するために考案された記憶階層の実現手段
参考
wikipediaにあるキャッシュアルゴリズムをそれぞれ調査
wikipedia のキャッシュアルゴリズムを元に、それぞれ調査
Least Recently Used (LRU) [直訳：最近使用されていない]
最近最も使われていないデータを最初に捨てる。このアルゴリズムでは、どのデータがどの時点で使われたかという情報を保持する必要があり、本当に最近最も使われていないデータを常に捨てるようにしようとすると、かなり手間がかかる。一般的実装では、キャッシュライン毎に世代ビット群（age bits）を持たせ、どのラインが最近最も使われていないかを世代ビット群で判断する。その場合、あるキャッシュラインを使うときには、常に全キャッシュラインの世代ビット群を更新する必要がある。
利用箇所とか
Oracleのバッファキャッシュなどは、このアルゴリズムだそう。
RedisもLRUがあるよう。
Most Recently Used (MRU) [直訳：最近使用された]
最近最も使われたデータを最初に捨てる。アクセスに局所性を想定できず、LRUの実装が複雑すぎる場合に使われる。MRUの使用例としてはデータベースのメモリキャッシュがある。
「最近開いたファイル」も、Most Recently Usedと呼ぶらしい（ややこしい・・・）
Pseudo-LRU (PLRU) [直訳:擬似的-最近使用されていない]
例えば、キャッシュメモリの連想度が大きい場合（4ウェイ以上）、LRUの実装コストは無視できなくなる。確率的にほぼ常に最近最もつかわれていないデータを捨てれば十分という場合、PLRUアルゴリズムを使う。この場合、キャッシュライン毎に1ビットの情報を保持するだけでよい。
| 言語 | リンク |
|---|---|
| java | LRU-Cache/PseudoLRUCacheSet.java at master · houli/LRU-Cache · GitHub |
Least Frequently Used (LFU) [直訳：使用頻度が最も低い]
各データが使われた頻度を保持する。そして、頻繁には使われていないデータを最初に捨てる。
| 言語 | リンク |
|---|---|
| javascript | Javascript/LFUCache.js at master · TheAlgorithms/Javascript · GitHub |
Adaptive Replacement Cache (ARC) [直訳:適応的置換キャッシュ]
LRU と LFU の間でバランスをとり、最適な結果を得る方式。最近キャッシュから消された情報の履歴を保持するように拡張し、その情報を使って、「かつてキャッシュされていたけれど今はキャッシュから消されている」という情報を元に、LRUとLFUの配分を動的に自動的に調整する。以下の4つのキューを使う。
- LRU (アクセス回数が1回。常にLFUよりも大きな容量を割り当てる。)
- LFU (アクセス回数が2回以上のデータ)
- かつてLRUに入っていた (これ自体もLRU)
- かつてLFUに入っていた (これ自体もLRU)
| 言語 | リンク |
|---|---|
| javascript | node-arc-cache/arc.js at master · ex1st/node-arc-cache · GitHub |
| javascript | GitHub - alexanderGugel/arc-js: An Adaptive Replacement Cache (ARC) written in JavaScript. |
