Quicklistの深層：なぜRedisは「双方向リスト」を捨ててハイブリッド構造を選んだのか
テックリードの私だ。今日のコードレビューで、何気なく `LPUSH` や `RPUSH` を連発しているジュニアエンジニアのプルリクエストを見つけた。
「リスト型だから Linked List だろう」という素朴な理解で巨大なデータを流し込んでいる。これでは本番環境でメモリが爆発し、OOM Killerの餌食になるのがオチだ。
Redisの内部構造において、メモリ管理とパフォーマンスのトレードオフを最も美しく（そして泥臭く）解決しているのが Quicklist だ。
今回は、Redis 3.2以降のリスト型の裏側を支える Quicklist のアーキテクチャと、実務で絶対に押さえておかなければならないメモリ最適化の極意を伝授しよう。
—
1. 幻想の否定：なぜ素の Linked List も Ziplist も実務で使えないのか
Redisの List 型を語る上で、過去の亡霊を知る必要がある。
伝統的な Linked List の悲劇
C言語の標準的な双方向連結リスト（`adlist.c`）を思い出してほしい。各ノードは前後のポインタ（`prev`, `next`）を持ち、実際のデータへのポインタを保持する。
- ポインタのオーバーヘッド: 64bit環境では、ポインタだけで1ノードあたり `8バイト (prev) + 8バイト (next) + 8バイト (value) = 24バイト` を消費する。
- メモリフラグメンテーションの悪夢: 小さなデータ構造が無数の独立したメモリブロックとしてヒープ上に散らばるため、jemallocなどのメモリアロケータにとって最悪のワークロードとなる。キャッシュヒット率も当然最悪だ。
Ziplist という極端な最適化
このメモリオーバーヘッドへの反省から生まれたのが Ziplist だ。データをメモリ上で完全に連続した一つのチャンク（連続領域）として保持し、ポインタを一切持たずにオフセットで要素を管理する。
- 圧倒的な密度: ポインタのオーバーヘッドがゼロ。
- 致命的な代償: すべての要素が可変長のため、要素の挿入・削除（`LINSERT` など）が発生すると、メモリの再割り当て（`realloc`）とメモリのコピーが必ず発生する。計算量は最悪の場合 $O(N^2)$。数万件の要素を持つ Ziplist をいじると、Redisのシングルスレッドイベントループが完全にブロックされる。
「ポインタのオーバーヘッドを削りたいが、全域のメモリコピーは避けたい」。
このジレンマを打破するために誕生したのが、Quicklist である。
—
2. Quicklist のアーキテクチャ：ハイブリッド構造の真髄
Quicklist（`quicklist.c`）の正体は極めてシンプルだ。
一言で言えば、「双方向連結リストのノードの中に、それぞれ Ziplist を詰め込んだ構造」である。
[Quicklist Head] <---> [Quicklist Node] <---> [Quicklist Tail]
|
+———v———+
| Ziplist Container |
| [Elem 1][Elem 2]…|
+——————-+
- マクロ構造: ノード同士は通常の双方向リストで繋がっている。そのため、リストの両端への追加・削除は $O(1)$ であり、巨大なリスト全体を作り直す必要はない。
- ミクロ構造: 各ノードが持つ実データ領域は、ポインタではなく連続したメモリブロック（Ziplist）である。これにより、ポインタのオーバヘッドを最小限に抑えつつ、キャッシュ効率を最大化している。
実務において、この構造が何を意味するか？
「適度なサイズに分割された Ziplist のチェイン」であるため、要素の挿入コストが局所化され、巨大なリストであってもパフォーマンスの劣化を防げるのだ。
—
3. 現場で効くチューニング：圧縮設定（Compression Depth）の極意
Quicklist を語る上で避けて通れないのが、メモリ圧縮（Compression）の仕組みである。
Redisは、アクセス頻度が低い中央付近のノードの Ziplist を、内部でLZFアルゴリズムを使って圧縮することができる。
これを制御するのが `list-max-ziplist-size` と `list-compress-depth` という二大パラメータだ。`redis.conf` を覗いてみよう。
各quicklistノードのziplistのサイズ制限
正の値なら「要素数」、負の値なら「バイト数（バイト単位の制限）」を指定
-2: 最大 8KB（プロダクション環境のデフォルトとして非常に洗練された値）
list-max-ziplist-size -2
圧縮の深さ（両端から数えて何個のノードを圧縮対象外にするか）
0: すべて圧縮する（両端も含めて）
1: リストの先頭1つ、末尾1つを除くノードを圧縮
2: リストの先頭2つ、末尾2つを除くノードを圧縮
list-compress-depth 0
チューニングの指針：いつ `list-compress-depth` をいじるべきか？
1. Queue（キュー）や Stack（スタック）として使う場合 (`LPUSH` / `RPOP`)
- 常に両端（ヘッドとテール）しかアクセスされない。
- もし `list-compress-depth 1` または `2` に設定した場合、頻繁にアクセスされる両端のノードが非圧縮状態に保たれ、中央の「古い・触られないデータ」だけが圧縮されるため、CPU負荷を上げずにメモリを劇的に節約できる。
2. ランダムアクセスや全件走査が多い場合 (`LINDEX`, `LRANGE`)
- 圧縮されたノードにアクセスするたび、RedisはCPUを使ってオンザフライで解凍（Decompression）を行う。
- これが多発すると、CPU使用率が跳ね上がる。リードヘビーで、かつ高速なランダムアクセスが求められるシステムでは、`list-compress-depth 0`（圧縮なし）にあえて設定し、メモリとCPUのトレードオフをCPU側に寄せる判断が必要になる。
—
4. 実務設計のアンチパターンとコードレビューの視点
シニアエンジニアとして、チームのメンバーが書いたコードや設計を見る際、以下のポイントを厳しくチェックしている。
アンチパターン 1: 1つの List に数百万件の要素を詰め込む
「ログやイベント履歴を全部 1 つの Redis List に放り込む」という設計を見かけたら即座に差し戻せ。
確かに Quicklist は Ziplist のチェインだが、リストの長さが数百万を超えると、`LINDEX` などのインデックスアクセス（$O(N)$）でノードを辿るコストが無視できなくなる。
正しい設計:
- データには必ず TTL（有効期限）を設けるか、時系列でキーを分割する（例: `logs:2023-10-27`）。
- 1つのリストあたりの要素数は、実用上数千〜数万程度に抑えるのがインメモリDBとしてのベストプラクティスだ。
アンチパターン 2: サイズ制限のデフォルトを無条件で信用する
`list-max-ziplist-size -2`（8KB）は万能ではない。
格納するデータ（文字列の長さ）が極端に大きい場合、1つの Ziplist に含まれる要素数が自然と 1 や 2 になり、結局ただのメモリアロケータの無駄遣い（内部断片化）になる。
逆に、要素が数十バイト程度と極小なら、もう少しサイズを大きくしてメモリ密度を高める余地がある。
—
5. まとめ：プロフェッショナルなメモリ管理へ
Redisの Quicklist は、「ポインタのオーバーヘッド」「メモリ連続性によるキャッシュ効率」「挿入・削除のコスト」という相反する課題を高度に調停した、マスターピースと言えるデータ構造だ。
単に「Redisの List 型は便利だから使う」のではなく、
- 自社のワークロードは書き込み偏重か？
- 両端アクセスのみか、中間へのランダムアクセスが必要か？
- メモリ制限とCPU負荷のバランスはどこに置くべきか？
これらをロジカルに突き詰め、`redis.conf` のパラメータチューニングやキー設計に落とし込むこと。それこそが、システムをスケールさせるテクニカルリードの仕事である。
次のコードレビューでは、君たちの洗練された設計論を聞かせてもらうとしよう。期待している。
コメント