Redisのメモリ管理の急所：なぜRedisは「真のLRU」を捨てたのか？近似LRUの深層と実務設計の鉄則
こんにちは。システムアーキテクトの私だ。
今日のコードレビューで、あるジュニアエンジニアがこんな質問をしてきた。
> 「Redisの `maxmemory-policy` を `allkeys-lru` に設定しているんですが、なぜか最近アクセスしていない古いデータが残って、直近で使ったデータが消えたりします。これってRedisのバグですか？」
ほう。実に良い着眼点だ。しかし、バグではない。それはRedisが「正確なLRU（Least Recently Used）」をあえて捨て、極限のパフォーマンスを取った代償なのだ。
今回は、Redisのメモリ管理の心臓部である「近似LRUアルゴリズム」の正体と、設定値 `maxmemory-samples` がシステムの生死をどう分けるのか、実務の現場で使える知見を交えて徹底的に解説しよう。
—
1. 理想郷の崩壊：なぜ「真のLRU」はRedisで使えないのか？
コンピュータサイエンスの教科書を開けば、LRUの実装は美しくシンプルに書かれている。
二重連結リスト（Doubly Linked List）とハッシュマップを組み合わせ、アクセスされたデータを常にリストの先頭にO(1)で移動させ、メモリ上限を超えたら末尾（最も古いデータ）をO(1)でパージする。
だが、これをインメモリデータベースであるRedisでやると、プロダクション環境では一瞬で死に至る。
メモリとCPUのトレードオフ
Redisはシングルスレッド（正確にはネットワークI/Oや非同期処理を除くメイン処理）で動作し、極限のスループットとミリ秒以下のレイテンシを叩き出す設計になっている。
もし「真のLRU」を実装した場合のコストを考えてみてほしい。
- メモリオーバヘッド: すべてのキーに対して「前後のポインタ（前後で16バイト〜32バイト）」を持たせなければならない。数億件のキーを持つ巨大なRedisインスタンスでは、ポインタの維持だけで何ギガバイトものRAMが無駄に消費される。
- ロックと競合: 高い並行性（Concurreny）の中でリストの順番を書き換えるたびに、ポインタのポインタを付け替えるアトミック操作、あるいはロックの競合が発生し、シングルスレッドのパイプラインが完全に詰まる。
Redisの創作者であるSalvatore Sanfilippo（antirez）は、この現実を直視した。
「インメモリキャッシュにおいて、ミリ秒単位で厳密なLRU順序を維持することは、リソースの無駄遣いである。必要なのは『だいたい最も使われていない古いデータ』を効率よく消すことだ」と。
こうして誕生したのが、「近似LRUアルゴリズム（Approximated LRU）」である。
—
2. Redisの近似LRUアルゴリズムのメカニズム
RedisのLRUは、完全にソートされたリストを持たない。代わりに確率的サンプリング（Random Sampling）を使用する。
内部の動き
1. タイムスタンプの保持:
Redisのすべてのオブジェクトのメタデータ（`redisObject`）には、24ビットの `lru` フィールドが存在する。ここにはオブジェクトが最後にアクセスされた時間が（秒単位、あるいはミリ秒単位で）格納されている。
2. ランダムサンプリング:
メモリ制限（`maxmemory`）を超過した時、Redisは全キーをスキャンするのではなく、設定されたサンプル数（`maxmemory-samples`）だけ、ランダムにキーをピックアップする。
3. プール（Pool）の維持:
ピックアップされたキーの中から、最も「LRU的により古い（アクセス時間が最も遠い）」キーを選び出し、内部の候補プール（Eviction Pool）に蓄積する。
4. 削除実行:
プールの中から最も古いキーを1つ選び、容赦なく削除する。これをメモリが指定量（`maxmemory`を下回るまで）になるまで繰り返す。
この仕組みにより、RedisはO(N)の全件ソートや巨大な連結リストの維持を回避し、定数時間に近い驚異的なパフォーマンスでメモリ解放を行うことに成功している。
—
3. 鍵を握るパラメータ：`maxmemory-samples` の実務的影響
ここで、冒頭の疑問に戻る。なぜ「直近で使ったデータが消え、古いデータが残る」現象が起きるのか？
その答えが、設定ファイル（`redis.conf`）に潜むこのパラメータだ。
デフォルト値
maxmemory-samples 5
この `maxmemory-samples` は、「一度のパージ処理で、何個のキーをランダムサンプリングするか」を指定する設定である。
サンプル数と精度の関係
- `maxmemory-samples 3` (デフォルトより低い設定)
- メリット: CPU負荷が極めて低い。
- デメリット: サンプリングの偏りが大きくなり、「本当は消すべきではないホットデータ」が偶然サンプリング網に引っかからず、別のデータが誤爆して消される確率が跳ね上がる。つまり、LRUの精度がガタ落ちする。
- `maxmemory-samples 10 ~ 100` (高精度設定)
- メリット: 「真のLRU」に限りなく近い精度で古いデータを特定できる。
- デメリット: メモリプレッシャーが高い状態（キャッシュが常にパンパンの状態）で頻繁に削除処理が走ると、CPU使用率がスパイクし、Redis全体のレイテンシ（レイテンシ悪化＝レイテンシ・スパイク）を引き起こす。
【設計レビューの視点】実務での適切なチューニング値
数百万件のキーを抱えるプロダクション環境において、デフォルトの `5` では精度が粗すぎるケースが多い。かといって `50` や `100` にするとCPUを焼き尽くす。
- 一般的なWebアプリケーションのキャッシュ: `maxmemory-samples 5` 〜 `10` がスイートスポット。
- 厳密なヒット率が求められるセッションストアやAPIキャッシュ: `maxmemory-samples 10` 〜 `20` に引き上げつつ、CPUの負荷状況（`INFO stats` の `expired_keys` や `evicted_keys`、CPU使用率）を必ずモニタリングする。
—
4. 2026年現在のモダンRedisにおける進化：LRU vs LFU
さらに知っておくべき現代のRedisの知見として、純粋なLRUだけでなく、LFU（Least Frequently Used：最小頻度使用）アルゴリズムも選択可能になっている点だ。
maxmemory-policy allkeys-lfu
なぜLRUよりLFUなのか？
LRUは「最後にアクセスされてからの時間」を見る。そのため、以下のようなシナリオで致命的な弱点を持つ。
> 「1時間に1回、一斉にバッチ処理で全件スキャンされるデータ」があるとする。このバッチ処理が走った瞬間、普段まったく使われないその巨大なデータ群が『最近アクセスされたデータ』として扱われ、日常的に頻繁に使われている重要なホットデータが押し出されて消えてしまう。
一方、LFUは「アクセスされた頻度（回数）」を対数カウンタ（Logarithmic Access Counter）で管理する。
バッチで1回アクセスされた程度ではカウンタは大して上がらないため、頻繁に参照される真のホットデータが保護される。
【テクニカルリードからの推奨設計】
現代の一般的なWeb/APIシステムのキャッシュ設計において、特別な理由（時系列データの直近保持など）がない限り、`maxmemory-policy` には `allkeys-lru` よりも `allkeys-lfu` または `volatile-lfu` を選択する方が、キャッシュヒット率（Hit Rate）が劇的に向上するケースが多い。ぜひ検証してみてほしい。
—
5. まとめ：トラブルを防ぐためのアーキテクチャ設計原則
1. RedisのLRUは「近似」であると知れ:
完璧な順序保証を期待してはならない。ランダムサンプリングの上で成り立っているアルゴリズムであることを前提に、データ構造を設計する。
2. `maxmemory-samples` はシルバーブレットではない:
精度を上げればCPUを消費する。負荷テスト（JMeterやwrk、memtier_benchmark等）を行い、システムのピーク時にCPUがボトルネックにならない最大値を実測して決めろ。
3. ユースケースに応じて LFU も検討せよ:
アクセスの「頻度」が重要なら、迷わずLFU（`allkeys-lfu`）を採用せよ。LRUの弱点であるバッチ処理のノイズからキャッシュを守ることができる。
メモリ管理の挙動を熟知しているか否かで、障害耐性やコスト効率は天と地ほどの差が出る。
感覚で設定するのではなく、理論と裏付けを持ってRedisを支配してくれ健闘を祈る。
コメント