キャッシュ
概要
キャッシュ (cache) はプログラムやシステムのデータアクセスの高速化を目的としたメカニズムおよびその保存領域。アクセス頻度の高いデータや、次にアクセスされることが予測されるデータ、または生成や取得に時間がかかるデータを一時的に高速に読み取りが可能なキャッシュに保存することでアプリケーションの処理時間を短縮することを狙う。
キャッシュのサイズとアクセス方法を最適化する必要がある。キャッシュサイズが小さい場合、データの入れ替えが頻繁に発生して効率が低下する可能性がある。一方で、大きすぎるキャッシュは余分な領域が占有されるためリソースの効率が低下する。システムはデータをキャッシュから取得することで、本来の経路で取得するよりも高速にアクセスすることができる。
キャッシュはシステムの性能を向上させるために導入するため領域の実体はメモリであることが多いが、Web プロキシのようにローカルストレージを使用することもある。
Table of Contents
キャッシュ置換アルゴリズム
一般にはキャッシュの領域は有限であり、キャッシュがいっぱいになると既存のデータを破棄する必要が出てくる。キャッシュ置換アルゴリズム (cache replacement algorithm) はキャッシュからどのようにデータを破棄するかを決定するためのアルゴリズムである。
- LRU: Least Recently Used
-
最後にアクセスしてから最も長い時間が経過しているデータを破棄する戦略のアルゴリズム。最近アクセスのあったデータをキャッシュの一番上に保持することで、キャッシュの上限に達したときに一番下のデータを破棄する。LRU は理解と実装が簡単で良好な結果が得られるため、Web キャッシュで使用される最も一般的な置換アルゴリズムである。
- MRU: Most Recently Used
-
LRU とは逆に、最も最近アクセスしたデータを最初に破棄する戦略のアルゴリズム。MRU は、一度アクセスのあったデータがしばらく参照されなかったり、古いデータほどアクセスされる可能性が高い場合に使用される。
- LFU: Least Frequently Used
-
アクセス頻度の最も低いデータを破棄する戦略のアルゴリズム。このアルゴリズムはキャッシュのエントリーごとにカウンターを使用してアクセスの頻度を追跡する。一時的に高頻度のアクセスがあったがそれ以外では使用されていないデータをキャッシュアウトできない欠点がある。
- FIFO: First In First Out
-
先に追加されたものから順にデータを追い出すアルゴリズム。これはキューと同じ動作である。
Java では LinkedHashMapを簡易的なキャッシュとして使用することができる。このクラスは 
accessOrder に true を指定すると LRU アルゴリズム、false (デフォルト) を指定すると FIFO アルゴリズムの動作となる。
参考文献
- Areej M. Osman and Niemah I. Osman. A Comparison of Cache Replacement Algorithms for Video Services. International Journal of Computer Science & Information Technology (IJCSIT) Vol 10, No 2, April 2018