Redis HyperLogLogの極意：12KBの魔術で数億のユニークを制覇する方法
こんにちは。テックリードの私だ。
今日のコードレビューで、若手エンジニアからこんなプルリクエストが上がってきた。
> 「日別アクティブユーザー（DAU）を集計するため、ユーザーIDを `Set`（`SADD`）に格納し、その要素数を `SCARD` で取得する実装に変更しました」
私は即座に「Request Changes」のボタンを押した。
数百万、数千万スケールにスケールするシステムにおいて、生のIDをSetで保持することの愚かしさに気づいていない。メモリは無限ではない。OOM Killerが夜中に泣くことになる未来が見える。
「君、HyperLogLog を使ったことがあるか？」
今日は、Redisが誇る最も美しく、そして最も誤解されているアルゴリズムの一つである HyperLogLog（HLL） について、実務で即座に使えるレベルの知見を叩き込む。
—
1. なぜ Set ではダメなのか？（メモリの物理的限界）
まず前提を共有しよう。
100万人のユニークユーザー（UU）を `Set` で管理する場合を考える。
ユーザーIDがUUID（38バイト）や長めの文字列だとしよう。Redisのハッシュテーブルのオーバーヘッド、ポインタ、free list等の構造を考慮すると、1要素あたり数十バイト〜100バイト以上を消費する。
- Setの場合: 100万UU $\times$ 平均50バイト $\approx$ 約50MB
- MAU（月間アクティブユーザー）が1億人に達した場合 $\approx$ 約5GB
これを日別、週別、チャネル別、キャンペーン別に保持してみろあっという間にテラバイト級のメモリが吹き飛ぶ。Redisはインメモリデータベースだ。メモリを節約することは、インフラコストの削減ではなく、システムの生存戦略そのものなのだ。
ここで登場するのが、HyperLogLog である。
—
2. HyperLogLogとは何か？（12KBの定数メモリの魔術）
HyperLogLogは、確率的アルゴリズム（Probabilistic Algorithm）を用いた「基数推定（Cardinality Estimation）」のためのデータ構造である。
最大の特徴、そしてエンジニアとして痺れるポイントはこれだ。
> 入力データが何億件あろうとも、1つのHyperLogLogキーが消費するメモリは「常に最大 12KB」である。
正確には、12,288バイト ＋ 少々の管理ヘッダのみ。
100万件入れようが、10億件入れようが、消費メモリは12KBから1バイトたりとも増えない。その代わり、「わずか誤差（標準誤差約0.81%）」を受け入れる。
実務において、アクセスのユニーク数やユニークビジター（UV）の集計で、「正確な値から1%未満の誤差があっても致命的か？」と自問してほしい。大抵のビジネスロジック（マーケティング分析、トレンド検知、アクセス解析など）において、1億人のうちの±80万人の誤差は許容範囲内、というか正確な数字など本質的に意味がない場合がほとんどだ。
—
3. Redisにおける3種の神器（PFADD, PFCOUNT, PFMERGE）
Redisでの操作は極めてシンプルだ。名前についている `PF` は、このアルゴリズムを発案したロバート・ドゥ・コラート（Philippe Flajolet）への敬意を表している。
① `PFADD`: 要素の追加
ストリームから流れてくるユーザーIDを次々と放り込む。
日付ごとのUUを記録する
127.0.0.1:6379> PFADD hll:2023-10-27 user_1001 user_1002 user_1003
(integer) 1
既に存在する要素を追加しても内部状態は変わらず、戻り値は 0
127.0.0.1:6379> PFADD hll:2023-10-27 user_1001
(integer) 0
- 計算量: $O(1)$。爆速。
② `PFCOUNT`: ユニーク数の推定取得
現在のユニーク数概算値を出力する。
127.0.0.1:6379> PFCOUNT hll:2023-10-27
(integer) 3
さらに、複数のキーを指定して、それらの合集合（Union）のユニーク数を瞬時に計算できるのが強力だ。
10月27日と10月28日の「2日間のトータルUU」を計算
127.0.0.1:6379> PFCOUNT hll:2023-10-27 hll:2023-10-28
(integer) 154200
- 計算量: $O(1)$（単一キー）、またはキー数に比例するが非常に高速。
③ `PFMERGE`: 複数のHLLの合体
これがアーキテクチャ設計の幅を劇的に広げる。
複数日のHLLをマージして、新しいキーとして永続化できる。
2023年10月全体のウィークリー・マンスリー集計のベースを作る
127.0.0.1:6379> PFMERGE hll:2023-10 hll:2023-10-27 hll:2023-10-28
OK
127.0.0.1:6379> PFCOUNT hll:2023-10
(integer) 985200
- 計算量: $O(N)$ （$N$ はマージするキーの数）。内部的にはレジスタのビット単位のマージなので、これも極めて高速。
—
4. 【実務設計】SetからHyperLogLogへ移行する際の注意点
レビューで「じゃあ全部HLLに置き換えよう」と言い出す短絡的なエンジニアがいるが、それは待て。HLLには明確なトレードオフがある。
注意点1: 生の要素（ID）を取り出すことはできない
Set構造であれば `SMEMBERS` で全ユーザーIDのリストを取得できた。しかし、HyperLogLogは「数える」ことに特化した数学的モデル（確率密度）の塊であるため、「中身の要素を列挙する（リスト化する）」ことは構造上不可能である。
- NG要件: 「今日アクセスしたユーザーのリストを画面に一覧表示したい」 $\rightarrow$ HLLは使えない。
- OK要件: 「今日のユニークアクセス数だけが知りたい」「月間のユニーク数を効率よく合算したい」 $\rightarrow$ HLL一択。
注意点2: データの削除（PFDELETE）は存在しない
RedisのHyperLogLogには、個別の要素を削除するコマンドがない。キー単位（`DEL`）で消すことしかできない。
したがって、TTL（有効期限）を適切に設計し、古いデータはRedisに自動消去させる設計が必須になる。
—
5. 実戦で使える設計パターン：DAU / MAU の高速集計システム
では、実務でどのようにインフラ設計に落とし込むか。
私のチームで推奨している設計パターンをシェアしよう。
キー設計規約
日別UU
hll:dau:{YYYY-MM-DD} (例: hll:dau:2023-10-27)
月別MAU（日別データをマージして生成）
hll:mau:{YYYY-MM} (例: hll:mau:2023-10)
Python（Redis-py）によるパイプライン実装例
イベントストリーム（KafkaやKinesisなど）からバッチ、あるいはリアルタイムワーカーでイベントを受け取り、Redisへ書き込む際のコード片だ。
import redis
from datetime import datetime
class MetricsCollector:
def __init__(self, redis_client: redis.Redis):
self.redis = redis_client
def track_visit(self, user_id: str, timestamp: datetime):
“””
ユーザーのアクセスをHyperLogLogに記録する
“””
date_str = timestamp.strftime(“%Y-%m-%d”)
month_str = timestamp.strftime(“%Y-%m”)
dau_key = f”hll:dau:{date_str}”
mau_key = f”hll:mau:{month_str}”
# パイプラインを用いてネットワークラウンドトリップを削減
pipe = self.redis.pipeline()
# 日別HLLに追加
pipe.pfadd(dau_key, user_id)
# 日別にTTLを設定（例: 90日後に自動消去。運用コストを下げるための必須プラクティス）
pipe.expire(dau_key, 86400 90)
# 月別HLLにも直接追加（または後続のバッチで PFMERGE する設計でも可）
pipe.pfadd(mau_key, user_id)
pipe.expire(mau_key, 86400 365)
pipe.execute()
def get_monthly_uu(self, year_month: str) -> int:
“””
月間ユニークユーザー数を高速取得
“””
mau_key = f”hll:mau:{year_month}”
return self.redis.pfcount(mau_key)
—
6. チーフアーキテクトからの総括
RedisのHyperLogLogは、ビッグデータ時代の省メモリ設計における「隠し剣」だ。
「正確性」の神話から脱却し、「ビジネスに本当に必要な精度は何か？」を見極め、適切なアルゴリズムを選択することこそが、シニアエンジニアとジュニアを分ける境界線である。
次に君が「ユニーク数」という言葉を設計書で見かけたら、こう呟いてほしい。
> 「おい、そのSet、本当にメモリ足りるのか？ HyperLogLogで行こうぜ」と。
プロフェッショナルな設計を、頼むぞ。
コメント