Redis LFUの深層：なぜLRUを捨ててカウンターの減衰に挑むのか
テックリードの私だ。コードレビューやアーキテクチャ設計の場において、「とりあえずキャッシュの eviction policy は `allkeys-lru` にしておけばいいや」という安易な選択を見かけるたびに、私はこう問いかけてきた。
「お前は、そのデータの『アクセス頻度』と『時間軸』の相関関係を論理的に説明できるか？」と。
Redis 4.0以前、メモリ枯渇時の削除アルゴリズムの主役は一貫してLRU（Least Recently Used：最近最も使われていない）だった。しかし、LRUには致命的な欠陥がある。「一瞬だけ大量にアクセスされたバッチ処理の残骸」や「1時間に1回しか使われないが、ビジネス上の重要度が極めて高いデータ」が、LRUのサンプリングによって容易に生存し、本当に頻繁にアクセスされるホットキーが押し出されるという現象だ。
この構造的欠陥を打破するためにRedis 4.0で導入されたのが LFU（Least Frequently Used） である。今回は、Redisがどのように省メモリでアクセス頻度を近似し、どのように「時間の経過に伴う忘却（Decay）」を実現しているのか。その内部実装の深層と、実務で絶対に押さべきチューニングの作法を伝授する。
—
1. LFUの内部構造：24bitの奇跡
RedisはC言語で書かれたインメモリデータベースであり、1バイトの無駄すら許されない極限の世界だ。全エントリに対して正確なアクセス回数を保持するカウンターを持たせたらどうなるか？メモリのオーバーヘッドだけでサーバーが破綻する。
そこでRedisは、各キーのメタデータ（`redisObject`構造体）に割り当てられたわずか24bitという極小の領域に、LFUのすべてを詰め込んだ。
/ Redisの内部構造体（概念図） /
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:24; // この24bitがLRUまたはLFUとして使われる
int refcount;
void ptr;
} robj;
この24bitの内訳は、以下のように巧妙に分割されている。
+————————+————————+
| Decay time (16bit) | Counter (8bit) |
+————————+————————+
1. Counter（下位8bit）: アクセス頻度を記録する。最大値は $2^8 – 1 = 255$。
2. Decay time（上位16bit）: 最後にカウンターが減衰（デクリメント）されてからの経過時間を保持する。
「たった8bit、最大255回までしかカウントできないのか？」と思ったなら、Redisの設計思想を甘く見ている。255回でカウンターが頭打ちになるなら、10万回アクセスされるホットキーを区別できない。ここで登場するのが、確率論的カウンター更新アルゴリズムである。
—
2. 対数カウンタ（Logarithmic Counter）の数学
RedisのLFUは、アクセスされるたびにカウンターを「1増やす」わけではない。現在のカウンター値 $C$ と、最後にアクセスされてからの経過時間に応じた確率に基づいて、確率的（Probabilistic）にインクリメントする。
このアルゴリズムは、以下の式に従う対数スケールを採用している。
$$P = \frac{1}{(C – LFU\_INIT\_VAL) \times \text{lfu-log-factor} + 1}$$
- $C$: 現在の8bitカウンター値
- $\text{lfu-log-factor}$: 設定パラメータ（デフォルトは `10`）
この設計により、何が起きるか？
- アクセスが少ないうちは、1回のアクセスで確実にカウンターが1増える。
- アクセスが増え、カウンターの値が大きくなるにつれて、インクリメントされる確率が非線形に低下する。
これにより、8bit（最大255）という極小の領域で、数百万回ものアクセス頻度の差を美しく近似表現することに成功している。
—
3. 減衰ロジック（Decay Logic）：過去の栄光を忘れる仕組み
LFUのもう一つの核心は、「時間が経つとアクセス頻度が下がっていく（忘却する）」という仕組みだ。これが実装されていなければ、過去に爆発的なアクセスがあったデータが永遠にメモリを占有し続ける（Cache Poisoningの状態になる）。
ここで効いてくるのが、`lfu-decay-time` パラメータと上位16bitの Decay time である。
設定のメカニズム
- `lfu-decay-time`: カウンターが「1」減衰するために必要な時間（分単位）。
- 例えば、デフォルトの `1` であれば、最後にアクセスされてから1分経過するごとに、カウンターが確率的（または条件付き）にデクリメントされる。
Redisがキーにアクセスした際、あるいはメモリ解放（Eviction）のサンプリングを行う際に、現在の時刻と上位16bitのタイムスタンプを比較する。もし `lfu-decay-time` で指定された時間が経過していれば、カウンターを減衰させる。
—
4. 実務における設計指針とチューニングの作法
ここからが本題だ。アーキテクトとして、このLFUをどうプロダクション環境に適用すべきか。設定ファイルのデフォルト値をそのまま信じるエンジニアは、重大な障害を引き起こす。
① 評価すべき設定値
`redis.conf` における関連パラメータは以下の2つだ。
最大メモリ到達時の削除ポリシー
maxmemory-policy volatile-lfu # または allkeys-lfu
対数カウンタの成長係数 (デフォルト: 10)
lfu-log-factor 10
カウンターの減衰時間（分） (デフォルト: 1)
lfu-decay-time 1
② ワークロードに応じたチューニング戦略
ケース A: 「トレンドが激しく入れ替わるECサイトのオススメ商品キャッシュ」
- 特性: 1時間前まで爆発的に売れていた商品が、次の時間には全く見られなくなる。
- 設計指針: `lfu-decay-time` を短く（例: `1` または `0` 相当の調整）し、古いトレンドを急速に忘却させる。これにより、新しいトレンドデータが確実にメモリを陣取ることができる。
ケース B: 「参照頻度は低いが、絶対にキャッシュミスしたくないマスタデータ（静的コンテンツ）」
- 特性: アクセス頻度は数時間に数回程度だが、DB負荷が高いためメモリに残したい。
- 設計指針: `lfu-log-factor` を高めに設定し、少々のアクセスでもカウンターがすぐに飽和値（255付近）に到達するようにする。さらに減衰時間を長くすることで、忘却の波からデータを保護する。
—
5. アンチパターン：やってはいけない設計
コードレビューで私が即座にリジェクトする構成を挙げておく。
1. 「LRUで十分」という思い込みによる全システムへの `allkeys-lru` 適用
- 時系列でバッチ処理が走り、全キーをスキャンするようなバッチジョブを持つシステムでLRUを使うと、直前に読み込まれた「どうでもいいバッチ用のデータ」によって、本番のAPIキャッシュが完全に追い出される。バッチ処理が絡むシステムでは、原則として `allkeys-lfu` または `volatile-lfu` を検討すべきだ。
2. `maxmemory` 未設定のまま運用
- LFUもLRUも、`maxmemory` が設定されて初めて機能する。これが無制限であれば、メモリが枯渇してLinuxのOOM KillerにRedisプロセスが屠られる。アーキテクトとして、物理メモリの7割〜8割を `maxmemory` の上限として明示的に縛ることは絶対の義務である。
—
結びにかえて
RedisのLFUは、単なる「古いアルゴリズムの置き換え」ではない。「限られたハードウェアリソースの中で、人間の認知やアクセスの統計的偏りを、いかに美しく数学的に近似するか」という、エンジニアリングのロマンと実利が極限のレベルで融合した傑作だ。
アルゴリズムの内部構造を理解せず、「動くからいいや」で設定を放置するプログラマーであるな。メモリの1ビット、カウンターの1インクリメントの裏側にある設計思想に思いを馳せ、君のシステムのワークロードに最適化した狂いのないキャッシュ戦略を構築してほしい。
健闘を祈る。
コメント