Redisの「型」を解体する：メモリの極限効率とデータ構造の裏側
Redisを単なる「キーバリューストア」と呼ぶのは、フェラーリを「移動手段」と呼ぶのと同じくらいに解像度が低い。Redisの真髄は、インメモリという制約下で、いかにCPUキャッシュ効率を最大化し、メモリアロケーションを抑制するかという「データ構造の極致」にある。
アーキテクトとして、Redisの各データ構造が内部でどのようにメモリを喰い、どのような計算量で動いているのか。その「底」を覗いてみよう。
—
1. 抽象化の罠：Redis Object (redisObject)
Redisのすべての値は、`redisObject`という構造体でラップされている。これがメモリ消費の元凶であり、柔軟性の源泉だ。
typedef struct redisObject {
unsigned type:4; // 型情報 (REDIS_STRING, LIST, etc.)
unsigned encoding:4; // エンコーディング (RAW, EMBSTR, ZIPLIST…)
unsigned lru:LRU_BITS; // LRU/LFU用
int refcount; // 参照カウント
void ptr; // 実際のデータへのポインタ
} robj;
重要なのは `encoding` だ。Redisはデータサイズや中身に応じて、動的に物理構造を差し替える。開発者が `SET` や `HSET` を叩くとき、Redisは裏で「このデータ量ならRAWよりZIPLISTの方がメモリ効率が良い」といった最適化を、ユーザーに意識させずに実行している。
2. 文字列 (SDS)：単なるバイト配列ではない
Redisの文字列は、C言語の `char` ではない。`SDS (Simple Dynamic String)` と呼ばれる独自の構造体だ。
- O(1)の長取得: 長さを構造体内に保持しているため、`strlen`で全走査する必要がない。
- バイナリセーフ: `\0`を含められる。
- メモリ再割り当ての抑制: `free`領域を持つことで、追記のたびにメモリを再確保するコストを劇的に下げている。
限界への知見: 短い文字列は `OBJ_ENCODING_EMBSTR` として `redisObject` と同じ連続したメモリ領域に確保される。これにより、キャッシュラインの局所性が向上し、ポインタデリファレンスが1回減る。この「数バイト」の戦いが、100万リクエスト/秒の世界では明暗を分ける。
3. ZipListとQuickList：メモリ断片化との戦い
リストやハッシュにおいて、データ量が少ない場合に登場するのが `ZipList` だ。これはポインタを持たず、連続したメモリブロックに全要素を詰め込む。
- なぜZipListか？: 従来のリンク付きリストは、各ノードにポインタ（8バイト）が必要で、メモリオーバーヘッドが凄まじい。ZipListは「前後の要素のサイズ」を記録することで、メモリを極限まで圧縮する。
- QuickList: 現在のRedisでは、これらを組み合わせた `QuickList` が主流だ。ZipListをリンク付きリストで繋ぐことで、挿入・削除のコストとメモリ効率のバランスを取っている。
4. SkipList：Sorted Setの心臓部
`ZSET` の背後にあるのは `SkipList` だ。B-treeではなくSkipListを選んだ理由は、実装の容易さと、範囲検索のパフォーマンス、そして「動的な要素挿入時における再バランシングコストの低さ」にある。
ハッシュマップと組み合わさることで、`ZSET` は「スコア順の検索」と「メンバーの存在確認」の双方を対数時間で行える。これは極めて強力な設計だ。
5. HyperLogLog：確率的アルゴリズムの暴力
1億ユーザーのユニークIDを数えるのに、どれほどのメモリが必要か？ `SET` なら数GBかかるが、`HyperLogLog` なら12KBで済む。
これは「値のハッシュ値に含まれる先頭の0の数」を記録するだけの確率的アルゴリズムだ。0.81%というわずかな誤差を許容する代わりに、メモリ消費をほぼ定数に抑える。このトレードオフをビジネスの要件にどう落とし込めるかが、熟練のアーキテクトの腕の見せ所だ。
—
結論：アーキテクトが意識すべき「メモリの痛み」
Redisのデータ型を使いこなすということは、「メモリレイアウトを理解する」ことと同義だ。
1. 要素数とエンコーディング: `hash-max-ziplist-entries` などの設定を理解せず、デフォルトのまま放置するのはエンジニアの怠慢だ。データ構造の切り替えポイント（遷移点）を把握せよ。
2. メモリ断片化: 大規模運用では `jemalloc` の統計情報を監視せよ。Redisがメモリを確保しても、OSに返却しないケース（断片化）がボトルネックになることは珍しくない。
3. 計算量への直感: 各データ操作の計算量を `Big O` 表記で即答できない構造を採用してはならない。
Redisは単なるキャッシュではない。メモリという極めて高価なリソースを、いかにエレガントに、かつ暴力的な速度で使い切るか。そのための道具箱が、ここに並んでいるデータ構造だ。
次に `HSET` を打つとき、その裏で `QuickList` が躍動し、メモリが最適化されている光景を想像してほしい。それこそが、エンジニアとしての視座だ。
コメント