【テクニカル・上級編】メモリ削除ポリシー (Eviction Policies) – Redis

Redisメモリ削除ポリシーの深淵：近似アルゴリズムが支配する「メモリの均衡」

Redisを単なる「高速なKVS」と呼ぶ者は、その内部で繰り広げられる精緻な生存競争を知らない。メモリ上限（`maxmemory`）に達した瞬間、Redisは過酷な「淘汰」を開始する。しかし、多くのエンジニアが誤解しているのは、それが完璧なLRUやLFUではないという点だ。

本稿では、Redisがメモリ限界を突破する際、内部で何が起きているのか、そのアルゴリズムの設計思想と「近似」という妥協がもたらす極限の挙動について解説する。

—

1. 近似LRU：なぜ「完璧」を捨てたのか

Redisの`allkeys-lru`や`volatile-lru`は、教科書的なLRU（Least Recently Used）を実装していない。もし全キーを対象に厳密なLRUを実装しようとすれば、アクセスのたびにポインタを繋ぎ変えるための二重連結リストを更新しなければならず、ロック競合やCPUキャッシュの汚染で性能は崩壊する。

内部メカニズム：サンプリングという妥協

Redisは、「サンプリングによる近似LRU」を採用している。

処理フロー: 削除が必要な際、設定された `maxmemory-samples` （デフォルト5）の数だけランダムにキーをピックアップし、その中で最も「古い」ものを一つ削除対象にする。
計算コスト: $O(1)$ である。全キーを走査するコストを捨て、定数時間で「それなりに古いもの」を捨て去ることで、ミリ秒未満のレイテンシを維持している。

このサンプリング数は `redis.conf` で調整可能だが、増やせば精度は向上する一方で、削除処理の計算コストが増大し、Redisのメインスレッド（シングルスレッド・イベントループ）をブロックするリスクが高まる。

精度とレイテンシのトレードオフ
5を指定すれば十分な精度が得られる。10に上げればより理論値に近づくがCPU負荷は増す。
maxmemory-samples 5

2. LFU（Least Frequently Used）：長期間のアクセス頻度をどう捉えるか

LFUは「最近使われていない」ではなく「頻繁に使われていない」を基準にする。しかし、LFUには「過去の頻度が未来の頻度を縛り続ける」という致命的な問題がある。Redisはこの問題を解決するために「カウンタの減衰（Decay）」を実装している。

カウンターの表現: `redisObject` 構造体の中にある 24bit の `lru` フィールドを、上位16bit（減衰用タイムスタンプ）と下位8bit（アクセス頻度カウンター）に分割して利用している。
減衰アルゴリズム: 単純な加算ではない。カウンターの増加は確率的であり、放置されると時間が経つにつれてカウンターが減少するように設計されている。

これにより、過去のバースト的なアクセスが、現在のメモリ圧迫要因になることを防いでいる。これは「時系列の変化に追従するLFU」であり、データサイエンス的なアプローチがキャッシュ戦略に持ち込まれている好例だ。

3. TTLベースの削除：パッシブとアクティブの二段構え

`volatile-lru` 等のポリシーを使う際、忘れてはならないのが Redis の TTL 削除メカニズムだ。

1. パッシブ（受動的）: キーへのアクセス時に有効期限をチェックし、切れていれば削除する。
2. アクティブ（能動的）: Redisは定期的に `activeExpireCycle` 関数を呼び出し、ランダムにキーをサンプリングして期限切れをチェックする。

ここで重要なのは、「メモリがいっぱいだからといって、必ずしもTTLが切れたキーが優先的に消えるわけではない」という事実だ。メモリ削除ポリシーは、TTLとは独立した「メモリ節約のための緊急避難」である。TTLが設定されていても、メモリ制限に達すれば、LRUやLFUのルールに従って「まだ生きているキー」が削除される可能性があることを理解しておく必要がある。

4. アーキテクトへの提言：メモリを最適化する「境界」

大規模システムにおいて、`maxmemory` に達した時の挙動を制御するのは、DBエンジニアの最後の砦だ。

`noeviction` の採用: 重要なシステムでは、メモリが溢れた時に勝手にデータを捨てる `noeviction` を推奨する。書き込みエラーを返す方が、キャッシュの不整合や意図しないデータ消失よりもデバッグが容易である。
キーの生存期間設計: そもそもLRU/LFUに頼らない設計が最強だ。データのライフサイクルをアプリケーション層で正確に管理し、`EXPIRE` を適切に付与する。これに勝るメモリ管理はない。

結論：Redisは「確率論的なエンジン」である

Redisのメモリ管理は、厳密な整合性よりも「システム全体の応答速度」を優先した統計的な近似モデルである。

我々エンジニアがすべきは、Redisを「ブラックボックスとして信じること」ではなく、このサンプリング・アルゴリズムがどのような条件下で偏り（バイアス）を生むかを理解し、キーのTTL設計や `maxmemory-policy` の選定にそれを反映させることだ。

メモリは常に足りない。だからこそ、どのデータを犠牲にするかをシステム設計の初期段階で定義することこそが、アーキテクトの真の仕事である。