PHPでLRUキャッシュの実装｜ブログ

はじめに 現代のソフトウェア開発において、データのアクセス速度はシステム全体のパフォーマンスを左右する重要な要素です。特に、大量のデータを処理するアプリケーションでは、頻繁に使用されるデータを効率的に管理するためにキャッシュが欠かせません。 キャッシュとは、データを一時的に保存し、高速にアクセスできるようにする仕組みです。例えば、Webアプリケーションでは頻繁にアクセスされるデータをメモリ上に保持することで、データベースの負荷を軽減できます。 しかし、メモリには限りがあるため、どのデータを保持し、どのデータを削除するかを決定するアルゴリズムが必要です。 LRUキャッシュの仕組み 本記事では、キャッシュ管理の中でも LRU（Least Recently Used）キャッシュ に焦点を当てます。 LRUキャッシュは、メモリの使用量を制限しつつ、必要なデータへのアクセスを高速化するアルゴリズムで、最近使用されたデータを優先的に維持し、古いデータを削除することで、メモリを効率的に管理します。 本記事では、LRUキャッシュの仕組みを解説するとともに、PHPを用いた実装方法を詳しく紹介します。 LRUキャッシュの活用シーン LRUキャッシュは、以下のような場面で活用されます： Webアプリケーションのデータキャッシュ 頻繁にアクセスされるデータ（例: ユーザープロフィールやランキングデータ）をメモリ上に保持し、データベースの負荷を軽減する APIのレスポンス高速化 外部APIからのデータ取得結果をキャッシュし、リクエスト数を削減 OSのページ置換アルゴリズム メモリ管理の一環として、最近使用されたページを優先し、不要なページを削除する CPUキャッシュ管理 LRUアルゴリズムを用いて、L1/L2キャッシュ内のデータを効率的に更新 ハッシュマップと双方向リストの組み合わせ 効率的なLRUキャッシュを実装するには、次の2つのデータ構造を組み合わせます。 ハッシュマップ（連想配列） キーとノード（データ）のペアを保持し、O(1) の時間で検索を実現 双方向リスト データの順序を保持し、最も最近使用されたデータをリストの先頭に移動 キャッシュがいっぱいになった際に末尾のデータを削除することで、削除処理をO(1)で実行可能 時間計算量 get(key): O(1) ハッシュマップで検索し、ノードをリストの先頭に移動 put(key, value): O(1) 新しいノードをリストの先頭に追加 既存のノードを更新し、先頭に移動 キャッシュの容量を超えた場合、最も古いデータ（LRU）を削除 PHPでのLRUキャッシュの実装 以下は、PHPでのLRUキャッシュの実装例です。 capacity = $capacity; $this->cache = []; } public function get($key) { if (!isset($this->cache[$key])) { return null; // キーがキャッシュにない場合 } $node = $this->cache[$key]; $this->moveToHead($node); return $node->value; } public function put($key, $value) { if (isset($this->cache[$key])) { // 既存のノードを更新して先頭へ $node = $this->cache[$key]; $node->value = $value; $this->moveToHead($node); } else { // 新規ノードを作成 $node = new Node($key, $value); $this->cache[$key] = $node; $this->addToHead($node); if (count($this->cache) > $this->capacity) { $removedKey = $this->removeTail(); unset($this->cache[$removedKey]); } } } private function addToHead(Node $node) { if (!$this->head) { $this->head = $this->tail = $node; } else { $node->next = $this->head; $this->head->prev = $node; $this->head = $node; } } private function moveToHead(Node $node) { if ($this->head === $node) return; $this->removeNode($node); $this->addToHead($node); } private function removeNode(Node $node) { if ($node->prev) { $node->prev->next = $node->next; } else { $this->head = $node->next; } if ($node->next) { $node->next->prev = $node->prev; } else { $this->tail = $node->prev; } } private function removeTail() { if (!$this->tail) return null; $removedKey = $this->tail->key; $this->removeNode($this->tail); return $removedKey; } // 連結リストをheadからtailに向かって走査 public function printList() { $node = $this->head; while ($node) { echo $node->key . " => " . $node->value . "\n"; $node = $node->next; } } } class Node { public $key; public $value; public ?Node $prev = null; public ?Node $next = null; public function construct($key, $value) { $this->key = $key; $this->value = $value; } } // 使用例 $lruCache = new LRUCache(2); // キャッシュの容量は2です。 // 1. 最初に (1, "One") と (2, "Two") をキャッシュに追加します。 $lruCache->put(1, "One"); $lruCache->put(2, "Two"); // 現時点では (2, "Two") が先頭、(1, "One") が次になります。 // 2. 次に (1, "One") を取得し、(1, "One") がキャッシュの先頭に移動します。 echo $lruCache->get(1) . "\n"; // 出力: One // 3. (3, "Three") を追加すると、キャッシュの容量が超過するため、最も古い (2, "Two") が削除されます。 $lruCache->put(3, "Three"); echo $lruCache->get(2) . "\n"; // 出力: null // 4. (4, "Four") を追加すると、再び容量が超過するため、最も古い (1, "One") が削除されます。 $lruCache->put(4, "Four"); // (1, "One") が削除される echo $lruCache->get(1) . "\n"; // 出力: null echo $lruCache->get(3) . "\n"; // 出力: Three echo $lruCache->get(4) . "\n"; // 出力: Four // 5. 最終的にキャッシュには (4, "Four") と (3, "Three") が残り、順番は (4, "Four") が先頭、(3, "Three") が次になります。 $lruCache->printList(); // 出力: 4 => Four, 3 => Three まとめ LRUキャッシュは、最近使われたデータを維持し、古いデータを削除する ハッシュマップと双方向リストを組み合わせることで、データの取得と更新が O(1) で可能になる これにより、アプリケーションのキャッシュ管理が最適化され、パフォーマンスが向上します。