【テクニカル・上級編】 有効期限の内部メカニズム – Redis

霊長類最強のインメモリDB：Redisはいかにして「死んだキー」を葬っているのか

世の中の多くのエンジニアは、Redisを「高速なKVS」としてしか見ていない。`EXPIRE`コマンドを叩けば、指定した秒数後にキーが綺麗に消えてなくなる。まるで魔法のように。

だが、忘れてはならない。コンピュータの世界に魔法など存在しない。あるのは「物理法則」と「残酷なまでのリソース制約」、そして「それをねじ伏せるための極限まで洗練されたアルゴリズム」だけだ。

単一スレッド（Single-threaded）で動作するRedisが、数千万、数億のキーを抱えながら、なぜメモリを溢れさせず、かつレイテンシをマイクロ秒単位で維持できるのか？

今回は、Redisの心臓部である「有効期限（TTL）の内部メカニズム」の深層を、ソースコードの地平から解き明かす。

—

1. 忘却のデータ構造：`expires`辞書の正体

Redisのデータベース実体である `redisDb` 構造体を覗いたことがあるだろうか。
Redisの内部では、キーと値のペアを格納するメインの辞書（`dict dict`）の他に、もう一つ重要な辞書が存在する。それが `expires` 辞書だ。

typedef struct redisDb {
dict dict; // キー空間（Key-space）：実際のデータが格納される
dict expires; // 有効期限空間（Expires）：キーと絶対タイムスタンプの対応
dict blocking_keys; // BLPOP等でブロックされているキー
dict ready_keys; // PUSH等によりブロック解除待ちのキー
dict watched_keys; // MULTI/EXECのWATCHコマンド用
int id; // データベースID
long long avg_ttl; // 統計用：平均TTL
// …
} redisDb;

重要なポイントは、有効期限を設定しても、メインのキー空間（`dict`）と値が二重に複製されるわけではないという点だ。
`expires` 辞書が保持しているのは、以下のような極めてシンプルで無駄のないマッピング構造である。

  • Key: メイン辞書を指すポインタ（Stringオブジェクトへのポインタ）
  • Value: `long long` 型の絶対エポックミリ秒（Unix timestamp in milliseconds）

この分離設計により、有効期限を持たないキー群に対しては `expires` 辞書のメモリオーバーヘッドを完全にゼロに抑えつつ、期限切れ管理を独立したO(1)の空間で行うことを可能にしている。

—

2. ２つの死神：パッシブ削除とアクティブ削除

キーが期限切れを迎えたとき、Redisはそのメモリをどのように回収しているのか。
答えは「受動的（Passive）アプローチ」と「能動的（Active）アプローチ」のハイブリッドだ。

① パッシブ削除（Lazy Expiration / Passive Deletion）

最も直感的な削除メカニズム。クライアントが特定のキーに対してコマンドを発行した瞬間、Redisはそのキーが期限切れになっていないかをチェックする。

/ db.c の擬似的な概念コード /
robx lookupKeyReadWithFlags(redisDb db, robj key, int flags) {
// 1. キーが期限切れかチェック
if (expireIfNeeded(db, key)) {
// 期限切れの場合、キーを削除し、nilを返す
// …
}
// 通常のルックアップ処理
return lookupKey(db, key);
}

  • メリット: 無駄なCPUサイクルを消費しない。
  • デメリット: 二度とアクセスされない「死んだキー」は、永遠に `expires` 辞書とメイン辞書に残り続け、メモリをリークし続ける。

このパッシブ削除の「取りこぼし」を補完するために、もう一つの主役が存在する。

—

② アクティブ削除（Active Expiration / Eviction）

パッシブ削除だけでは、アクセスされないゾンビキーによってメモリが枯渇する。そのため、Redisはバックグラウンド（正確にはサーバーのメインイベントループ内）で定期的に期限切れキーの掃討作戦を実行している。これがアクティブ削除だ。

Redisはデフォルトで、1秒間に10回（`hz 10` の設定）、このパージ処理（`activeExpireCycle`）を起動する。

そのアルゴリズムの核心を見てみよう。全数走査はO(N)であり、シングルスレッドのRedisにおいて致命的なレイテンシスパイクを引き起こすため、確率的アルゴリズム（Probabilistic Algorithm）が採用されている。

`activeExpireCycle` の内部アルゴリズム

1. 制限時間の遵守: 1回の実行に費やせる時間は決まっている（通常はCPU時間の25%以内、すなわちデフォルトの `hz 10` では最大2.5ミリ秒）。
2. データベースの走査: アクティブな全DBを順番にチェックする。
3. サンプリング: 各DBの `expires` 辞書から、ランダムに `ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP`（デフォルト20個） のキーをピックアップする。
4. 粛清: ピックアップしたキーの中で、すでに期限切れになっているものをすべて削除する。
5. 早期終了の判定:

  • もし20個中、25%以上（5個以上）のキーが期限切れであった場合。
  • 「このDBはまだゴミだらけだ」と判断し、ステップ3に戻って即座に追加のサンプリングループを回す。

この「25%ルール」は非常に巧妙だ。
メモリ上に期限切れキーが蔓延している高負荷な状態では、自動的にスキャン頻度と量を増やしてメモリを回収し、逆に期限切れキーがほとんどない健康な状態では、CPU時間を最小限（数ミリ秒以下）に抑えて即座にスリープに入る。

—

3. レプリケーションとクラスタにおける「時間と消去」の哲学

分散システムやレプリケーション環境において、時刻の同期と期限切れの扱いは悪夢のようなバグの温床となる。ここでRedisのアーキテクチャの美しさが光る。

マスター・レプリカ間の一貫性

Redisのレプリケーションにおいて、レプリカ（Slave）側で勝手にキーを期限切れ削除することはない。

もしレプリカ側が独自のクロックで「このキーは期限切れだ」と判断して勝手に削除を始めると、マスターとの間でデータ不整合が生じるリスクがある（特にネットワーク遅延やNTPの時刻ズレがある環境で致命的となる）。

したがって、メカニズムはこう定義されている。
1. マスターのみが神（Clockの権威）である。
2. マスターでキーが期限切れになると（パッシブまたはアクティブ）、マスターは自身でそのキーを削除すると同時に、全レプリカに対して `DEL` コマンドを非同期で送信する。
3. レプリカはマスターからの `DEL` を受信してはじめて、自身のメモリから該当キーを消去する。

これにより、マスター・レプリカ間で「どのデータが存在し、どのデータが消えたか」の絶対的な整合性が担保される。

—

4. 実務における最適化とアンチパターン

アーキテクトとして、この内部メカニズムを理解していれば、設計時に「やってはいけないこと」が明確に見えてくる。

アンチパターン①：ミリ秒単位の同一点での大量有効期限切れ（Expiry Stampede）

数百万のキーに対して、まったく同じ秒数（例: `EXPIRE key 3600`）を設定し、それらが一斉に1時間後に期限切れを迎える状況を想像してほしい。

アクティブ削除の「25%ルール」が火を噴く。1つの時間に数百万のキーが期限切れになり、Redisのメインスレッドは期限切れの削除処理（`activeExpireCycle`）にCPU時間を奪われ、通常のクライアントリクエストに対するレイテンシが急激に跳ね上がる（数百ミリ秒〜数秒のスパイク）。

【極限の知見による対策】
有効期限には必ずジッター（Jitter：ランダムな揺らぎ）を付与せよ。

例：1時間 ± 300秒の範囲でランダムに散らす
import random
ttl = 3600 + random.randint(-300, 300)
redis.setex(key, ttl, value)

これにより、期限切れの負荷を時間軸上に美しく分散させることができる。

アンチパターン②：無限に肥大化する `expires` 辞書

「アクセスされない古いキー」にいつまでも長いTTLを与え続ける、あるいはTTLをまったく設定しない設計。
メモリが物理限界に達したとき、Redisは `maxmemory-policy`（volatile-lru, allkeys-lruなど）に基づいてパージを開始するが、有効期限のメタデータ自体が保持するメモリコストや、スキャンにかかるコストは着実にシステムの寿命を削っていく。

本当に不要になったデータは、面倒くさがらずに明示的に `DEL` コマンドで即座に解放するか、ストリーム構造や時系列特化の設計（RedisTimeSeriesなど）への移行を検討すべきだ。

—

結言

Redisの有効期限メカニズムは、単純な「タイマー処理」ではない。
「限られたシングルスレッドのCPUリソースをいかに効率的に割り振り、メモリの整合性とリアルタイム性を高次元で両立させるか」という、エンジニアリングの粋を集めた確率制御システムである。

内部構造のバイナリレベル、アルゴリズムの収束条件まで見通すことで初めて、お前はRedisを真の意味で「支配」できるようになる。

コードを書き、設定をチューニングし、インフラの限界領域を突破せよ。それこそが、本物のエンジニアの仕事だ。

スポンサーリンク

コメント

タイトルとURLをコピーしました