LRU(エルアールユー)とは | 意味や読み方など丁寧でわかりやすい用語解説

LRUは「Least Recently Used」の略称であり、日本語では「最も長い間使用されていない」と訳される。これは、コンピュータの記憶階層において、限られた容量を持つ高速な記憶領域、すなわちキャッシュからどのデータを削除（置換）するかを決定するためのアルゴリズムの一つである。コンピュータシステムでは、処理速度の遅い主記憶装置（メインメモリ）や補助記憶装置（ディスク）と、高速なCPUとの速度差を埋めるために、より高速なキャッシュメモリが利用される。一度アクセスしたデータをキャッシュに保存しておくことで、次に同じデータが必要になった際に低速な記憶装置へアクセスすることなく、高速にデータを取り出すことができ、システム全体のパフォーマンスが向上する。しかし、キャッシュは一般的に高価で容量が小さいため、無制限にデータを保存することはできない。そのため、キャッシュが満杯になった状態で新しいデータを保存しようとすると、既存のどのデータを追い出して空き領域を作るかという選択、すなわち「置換ポリシー」が必要となる。LRUは、この置換ポリシーとして広く採用されている代表的なアルゴリズムである。

LRUアルゴリズムの基本的な考え方は、多くのプログラムが持つ「時間的局所性」という性質に基づいている。時間的局所性とは、「最近アクセスされたデータは、近い将来に再びアクセスされる可能性が高い」という経験則である。この経験則に従い、LRUはキャッシュが満杯になった際に、「最も長い間アクセスされていないデータ」を、将来最も使われる可能性が低いデータと判断し、置換対象として選択する。具体的には、キャッシュ内の各データがいつ最後にアクセスされたかを追跡し、置換が必要になった時点で最も古いアクセスタイムスタンプを持つデータを削除する。データにアクセスするたびに、そのデータの最終アクセス時刻が現在時刻に更新される。この単純明快なロジックにより、頻繁に利用されるデータをキャッシュ内に保持し続け、キャッシュのヒット率を高めることを目指す。

LRUを実装する代表的な方法として、双方向連結リストとハッシュマップを組み合わせたデータ構造が知られている。この方法では、双方向連結リストを使ってデータのアクセス順序を管理し、ハッシュマップを使って特定のデータへ高速にアクセスする。連結リストの先頭を「最も最近使われた（Most Recently Used）」データ、末尾を「最も長い間使われていない（Least Recently Used）」データとして扱う。データへのアクセスが発生すると、まずハッシュマップを用いて対象のデータがキャッシュ内に存在するかを瞬時に確認する。キャッシュヒットした場合、そのデータに対応するノードを連結リストの中から見つけ出し、リストの先頭に移動させる。これにより、そのデータが最も最近使われたものとして更新される。一方、キャッシュミスした場合、新しいデータをキャッシュに追加する必要がある。キャッシュにまだ空き容量があれば、新しいデータを格納したノードを作成し、連結リストの先頭に追加する。同時に、ハッシュマップにも新しいデータのキーとノードへの参照を登録する。もしキャッシュが満杯であれば、まず連結リストの末尾にあるノード、つまり最も長い間使われていないデータを削除する。ハッシュマップからも対応するエントリを削除し、領域を確保した上で、新しいデータを格納したノードをリストの先頭に追加し、ハッシュマップに登録する。この実装により、データの検索、追加、更新といった操作を効率的に行うことが可能となる。

LRUは時間的局所性を効果的に利用できるため、多くのアプリケーションで高いパフォーマンスを発揮する。しかし、特定のアクセスパターンに対しては弱点も存在する。例えば、巨大なデータセットに対して一度だけシーケンシャルアクセス（先頭から順番にアクセス）するような場合、アクセスされたデータが次々とキャッシュに入り、本当に重要な、繰り返し利用されるはずだったデータを追い出してしまう可能性がある。これにより、キャッシュのヒット率が著しく低下する「キャッシュ汚染」と呼ばれる現象が発生することがある。また、データにアクセスするたびに連結リストのポインタを繋ぎ変えるなどの更新処理が必要となるため、CPUのオーバーヘッドが全くないわけではない。

このような特性を持つLRUは、オペレーティングシステムの仮想メモリ管理におけるページ置換アルゴリズム、Webブラウザのキャッシュ管理、データベース管理システムのバッファプール管理、CDN（Content Delivery Network）のエッジサーバにおけるコンテンツキャッシュなど、ITインフラの様々な場面で基礎的な技術として広く応用されている。そのシンプルさと有効性から、キャッシュ戦略を学ぶ上で最初に理解すべき重要なアルゴリズムの一つとされている。