図解キャッシュ置換アルゴリズム（LRU, LFU）
はじめに
私はこれまでキャッシュの更新アルゴリズムといえばLRUやLFUしか知らなかったのですが、こちらの記事で様々なキャッシュ更新アルゴリズムが存在していることを知り、それぞれのアルゴリズムについて詳しく調べてみました。
今回はそれらのキャッシュ更新アルゴリズムについて解説していきたいと思います。
ただし、いきなりそれらの発展的なアルゴリズムについて解説するのは混乱すると思うので、まずは前提知識となるLRU、LFUについて解説します。
次回の記事でこれらをベースとした発展的なキャッシュ更新アルゴリズムについて解説します。
キャッシュ更新アルゴリズムとは
キャッシュは、データの取得速度を向上させるために使用されます。
例えば、ウェブブラウザはよくアクセスするウェブページのデータをキャッシュに保存しておくことで、ページの読み込み速度を向上させます。
しかし、キャッシュの容量は比較的小さいのでキャッシュがいっぱいになった場合はどの要素を削除するか選択する必要があります。
キャッシュヒット率を高めるためには今後アクセスされる可能性が高い要素をキャッシュに残しておく必要があります。
アクセスされる可能性の予測に応じてキャッシュ内の要素を選別するアルゴリズムがキャッシュ更新アルゴリズムであり、代表的なものとしてLRUとLFUがあります。
LRU
LRU （Least Recently Used）は、キャッシュがいっぱいになった時に最も長い時間アクセスされていないキャッシュ内の要素を削除する戦略です。
LRUは時間的局所性に基づいてキャッシュを更新するアルゴリズムです。時間的局所性とは最近参照された要素は近い将来に参照される可能性が高い性質のことを表します。
つまり、最も長い間使用されていない要素は近い将来に使用される可能性が低いと想定して削除するという考え方に基づいたアルゴリズムです。
アルゴリズムの挙動
LRUでは以下のような連結リストを使用して、アクセスの時系列を表現しています。
例えば末尾のkey=7の要素にアクセスが発生したとすると以下のような状態になり、key=6の要素が最も長くアクセスされていない要素となります。
ここでキャッシュに新たな要素（key=8）が追加されると以下のようにkey=2の要素が削除されます。
メリット・デメリット
後述するLFUと比較して実装が単純であり、幅広いソフトウェアで活用されているアルゴリズムです。
また、LFUのようなアクセス頻度の管理が必要ないためキャッシュの管理に要する空間的コストも低く抑えることができます。
その一方で単純に最も昔にアクセスされた要素を削除するだけなので、例えば一回しかアクセスされないような要素が繰り返しキャッシュに流入した際に、そうしたキャッシュで保存する価値のない要素がアクセス頻度の高い要素をキャッシュから押し出して削除してしまう可能性があります。
LFU
LFU (Least Frequently Used)は、頻度ベースのアルゴリズムであり、要素を削除する際は最も使用頻度が少ないものを削除します。
アルゴリズムの挙動
LFUキャッシュでは要素が以下のようにアクセス頻度ごとに用意された連結リストに格納されます。
要素が削除される際は、以下のようにアクセス頻度が最も低い連結リストの中の最後尾の要素が削除されます。
キャッシュヒット時には参照されたキャッシュ内の要素が別の連結リストに移動します。
メリット・デメリット
このアルゴリズムのメリットは、要素のアクセス頻度が時間とともに変化しない場合、アクセス頻度の高いデータを効果的にキャッシュ内に保持できることです。
しかし、要素へのアクセス頻度が時間とともに変化する場合、以前は頻繁にアクセスされていたけれども現在はアクセス頻度が減少した要素がキャッシュから削除されなくなってしまいます。
実戦の環境ではそうした状況が多いため、LFUが有効であるケースは稀です。
また、一般的な実装では、全要素のアクセス頻度を記録することは空間的コストがかかるため行わず、キャッシュに存在する要素の頻度のみが記録されることが多いです。
そのため正確なアクセス頻度を元にキャッシュを管理することはできないという限界もあります。
まとめ
キャッシュ更新の基本的なアルゴリズムであるLRUとLFUについて解説しました。
LRU・LFUは、それぞれ独自のメリット・デメリットがあり、新たに開発されたキャッシュ更新アルゴリズムの多くは、LRU・LFUを組み合わせることで、各々の欠点を補完して克服ことを目指しています。
したがって、LRUやLFUの理解は、これらの進化したアルゴリズムを理解し、適切に利用するために重要です。
次回の記事ではこれらのアルゴリズムを発展させた新しいキャッシュ更新アルゴリズムについて解説します。
参考
Discussion