【入門編】 HyperLogLog：基数推定 – Redis

やあ。Redisの世界へようこそ。
システム開発をしていると、「このWebサイト、今日何人の『ユニークな』ユーザーが訪れたんだろう？」なんて計算をしたくなる場面は必ず訪れるよね。

普通に考えると、ユーザーIDを全部リストに溜め込んで、後で重複を削除して数える……という手順になる。でも、もしそのサイトが数百万、数千万アクセスあったらどうなると思う？メモリを食いつぶし、サーバーは悲鳴を上げ、君の貴重なPCも熱を持ってしまうはずだ。

そんな時、Redisの魔術のようなデータ構造「HyperLogLog（ハイパーログログ）」が、君の悩みを一瞬で解決してくれる。今日は、この「メモリの極限を攻める」魔法の道具について、一緒に深掘りしていこう。

—

まず、HyperLogLogを一言で言うと「誤差を許容する代わりに、メモリを死ぬほど節約するユニークカウント器」だ。

例えるなら、スタジアムにいる観客の数を正確に数えるのではなく、「まあ、大体このくらいだな」と推測する超優秀な観察者のようなもの。しかも、どれだけ人数が増えても、使うメモリ量は常に一定（最大12KB程度！）という凄まじい性質を持っているんだ。

Redisでの操作は、驚くほどシンプルだ。「PF」という接頭辞は、このアルゴリズムを考案したPhilippe Flajolet教授のイニシャルから来ている。敬意を込めて叩こう。

新しいデータ（ユーザーIDなど）をカウント対象に追加するコマンドだ。

「user:101」さんが来た！と記録する
PFADD visits “user:101”
結果：1 (新しいユニークな要素が追加された)

また「user:101」さんが来た！
PFADD visits “user:101”
結果：0 (すでに記録済みなのでカウントされない)

現在までにおおよそ何個のユニークな要素があるかを算出する。

PFADD visits “user:102” “user:103” “user:104”
PFCOUNT visits
結果：4 (おおよそ4人だと教えてくれる)

複数のHyperLogLogを合体させるコマンドだ。「昨日のアクセス」と「今日のアクセス」を合体させて、「この2日間で何人のユニークユーザーがいたか」を知るのに最適だよ。

昨日のデータと今日のデータを合体させて「total_visits」に保存
PFMERGE total_visits visits_yesterday visits_today

—

ここがエンジニアとして知っておいてほしい核心部分だ。

通常、10億人のユニークユーザーを数えようとしたら、IDを保持するだけで何ギガバイトものメモリが必要になる。しかし、HyperLogLogは「データの内容」ではなく「データのハッシュ値のパターン」を観測しているんだ。

「0がどれだけ連続して並ぶか」という確率的な性質を利用しているから、どれだけデータが膨大になっても、消費するメモリは12KB程度で固定される。「正確さ」をわずかな誤差（約0.81%）と引き換えに、「圧倒的な速度と省メモリ」を手に入れたわけだね。

逆に、「1円単位の厳密さが求められる課金データ」や「ユーザーIDの完全なリストが必要な場合」には使ってはいけない。 それは別のデータ構造（Setなど）の出番だ。

—

「完璧」を目指すあまり、すべてのデータを厳密に管理しようとすると、システムは必ずどこかで息切れする。特に大規模なアプリケーションでは、「どこまでなら誤差を許容できるか」を見極めることこそが、一流エンジニアのセンスなんだ。

HyperLogLogは、そのセンスを鍛えるための最高の武器になる。
最初は不思議に思うかもしれないけれど、実際に触って、その軽快なレスポンスを体感してみてほしい。「こんなに少ないメモリで、数百万のデータを数えられるのか！」という感動を、ぜひ君自身の手で味わってくれ。

ここをクリアした君なら、もうRedisの基本的なデータ構造の概念はバッチリマスターしたも同然だ。自信を持って、次のステップへ進もう！