RedisのHyperLogLog：メモリの限界を突破し、数億のユニークユーザーを掌中に収める「魔法」の正体
エンジニア諸君。システム設計において「ユニーク数（カーディナリティ）」の計測は、常にメモリとの戦いだ。
「今日、サイトに訪れたユーザー数は何人か？」
「この動画をユニークで何人が視聴したか？」
これを `SET` や `HASH` で実装しようとすれば、数百万ユーザーを超えた瞬間にメモリはパンクし、Redisは悲鳴を上げる。ここで登場するのが HyperLogLog (HLL) だ。
これは単なる便利ツールではない。数学的な美しさと、極限の省メモリ性を両立させた、Redisが誇る「エンジニアの切り札」だ。今日は、このデータ構造を使いこなすための勘所を、設計のプロの視点から叩き込む。
—
1. HyperLogLogの「嘘」と「真実」
まず、心に刻んでおくべきことがある。HyperLogLogは「推定値」を出すアルゴリズムである。 厳密な計数ではない。
- 最大誤差: 標準誤差 0.81%。
- メモリ消費: 最大でも12KB。
これが何を意味するか。たとえ10億のデータだろうが、100億のデータだろうが、メモリは常に12KBで固定だ。10億のユーザーID（8バイト）を `SET` に突っ込めば数GB飛ぶが、HLLなら12KBで済む。この「0.81%の誤差」を許容できるかどうかが、設計の分かれ道だ。
2. コマンド群：最小限の作法
HLLのコマンドは非常にシンプルだ。だが、その背後にある挙動を理解しなければならない。
`PFADD`: データの投入
ユーザーIDをキーに投げ込む
PFADD active_users:2023-10-27 “user:101” “user:102” “user:103”
戻り値: 1(内部状態が変わった場合), 0(既に存在する場合)
注意点：`PFADD` は、値が実際に変更されたときだけ `1` を返す。これはアプリケーション側の論理で、重複排除の成否を判定するトリガーとして使える。
`PFCOUNT`: 推定の算出
単一、あるいは複数のキーのユニーク数を合算して返す
PFCOUNT active_users:2023-10-27
`PFCOUNT` は `O(1)` に近い速度で動くが、内部的にはマージ処理が走る場合もある。多用するなら注意が必要だ。
`PFMERGE`: 巨大な統合
複数の日次データを統合して月次ユニークを算出
PFMERGE active_users:october active_users:2023-10-27 active_users:2023-10-28
これがHLLの真骨頂だ。統合後のデータもまた12KB。過去30日分のデータをマージしても、メモリコストは微々たるものだ。
—
3. 実務で「失敗しない」ための設計パターン
パターンA：日次/月次バッチの最適化
リアルタイムで月次ユニークを計算し続けるのは無駄だ。日次で `PFADD` し、月次集計が必要な時だけ `PFMERGE` を行い、その結果を `PFCOUNT` する。これが最も効率的で堅牢なパイプラインだ。
パターンB：メモリの「見えない」恐怖
12KBという数字に油断してはならない。キーが増えすぎれば、Redisサーバー全体のメモリを圧迫する。
- 名前空間の設計: `analytics:users:{date}` のように、期限切れ（TTL）を設定できるキー設計を徹底せよ。
—
4. プロフェッショナルとしての警告
最後に、レビューで私がよく指摘する「勘違い」を列挙しておく。
1. 「正確な値」が必要な場所には絶対使うな
課金や決済のユニークカウントには使うな。それは `SET` か `Redis Bloom Filter` の仕事だ。HLLはあくまで「傾向」を掴むためのものだ。
2. `PFADD` のキーを無闇に増やすな
HLLは巨大なデータには強いが、数千万の「キー」を作れば、Redisのインデックス管理にメモリを食われる。不要になったキーは `EXPIRE` で確実に消せ。
3. マージのコストを過信するな
`PFMERGE` は強力だが、頻繁に叩けばCPUリソースを消費する。集計結果を一時キャッシュとして保持し、更新頻度を制御する設計が推奨される。
—
結論：道具を「支配」せよ
HyperLogLogは、大規模データ処理において「メモリ不足」という呪縛を解く魔法だ。しかし、その魔法は「誤差」という代償を伴う。
君たちが設計すべきは、「どの程度の誤差ならビジネス上許容できるか」という境界線を見極めることだ。それができれば、君たちは数億人のトラフィックを、わずかなメモリで平然と捌くシステムを構築できるだろう。
次は、どのデータ構造の深淵を覗きたい？ Redisの限界に挑む準備ができているなら、いつでも問いかけてくれ。
コメント