HyperLogLogとは？大規模データのユニーク数を速く数える方法

2025年10月20日

その他

巨大なログやイベントから「ユニークユーザー数」や「固有IDの数」を知りたいとき、すべてを記録して正確に数えるのは重くなりがちです。

HyperLogLogは、わずかなメモリでユニーク数を高速に近似できるデータ構造で、データが膨大でも1回の走査で数えられます。

ここでは仕組みの直感から実装のコツまで、初心者向けに丁寧に説明します。

HyperLogLogとは？ユニーク数を高速に近似

ユニーク数(カーディナリティ)とは

なぜ「ユニーク数」が必要か

ユニーク数とは、重複を除いた要素の個数のことです。

例えばアクセス解析なら「ユニーク訪問者数」、イベント処理なら「固有デバイス数」などがカーディナリティです。

現場ではこの値がKPIや集計の基礎になります。

正確に数える方法との違い

正確に数えるにはハッシュセットやデータベースのDISTINCTを使いますが、要素が多いほどメモリや計算時間が増えます。

HyperLogLogはわざと「近似」にすることで、メモリを一定に保ちながら高速に数えられるようにした方法です。

誤差はありますが、その代わりに非常に軽量です。

大規模データで役立つ理由

メモリと時間の壁

大規模データでは、重複を除くために全要素を保持するのは困難です。

HyperLogLogは入力が何億件に増えても、メモリ消費がほぼ一定のままユニーク数を推定できます。

これがスケールする大きな理由です。

近似で十分な場面

ダッシュボードのトレンドやアラートのしきい値など、数パーセントの誤差が許容される場面は多くあります。

「正確さよりスピードと軽さ」を求める場面では、HyperLogLogの近似は十分に実用的です。

HyperLogLogアルゴリズムの特徴

高速・低メモリ

HyperLogLogは小さな配列に対して定数時間で更新し続けます。

典型的な実装ではキー1つあたり約12KB前後で、何百万〜何十億のユニーク数でも扱えます。

処理は足しこむだけなので速いです。

誤差の範囲と再現性

誤差はレジスタ数で制御でき、計算ルールが決まっているため同じ入力なら同じ結果になります。

推定には統計的なぶれがありますが、設計次第で誤差の目安を事前に見積もれます。

ハッシュセットとの違い

メモリ比較

ハッシュセットは各要素を実体として保持します。

HyperLogLogは要素そのものを保存せず、要素から得た「ヒント」だけを保存するため圧倒的に軽量です。

ユニーク数が増えるほど差が広がります。

機能比較

ハッシュセットは要素を列挙でき削除もできます。

HyperLogLogは「数」を近似する専用構造なので、要素の列挙や個別削除はできません。

ただし集合の合算は非常に簡単です。

仕組みの直感: ハッシュと先頭の0

ハッシュでランダム化

ハッシュ関数とは

入力を固定長のビット列に変換する関数です。

HyperLogLogはハッシュのビットが「コイン投げの結果のようにランダム」に見える性質を利用します。

同じ入力は必ず同じビット列になります。

64ビットを使う理由

ビット数が多いほど衝突の心配が減り、先頭の0の長さも安定します。

実装では64ビット以上のハッシュを使うのが一般的で、分布の偏りを避けやすくなります。

先頭の0の長さを見る

直感的な意味

ランダムなビット列の先頭に0が連続して並ぶ確率は急速に下がります。

例えば「先頭に0が10個続く」はかなり珍しいため、「多くの要素を見たから出会えたはず」と逆算できます。

例で理解

10回程度の入力では先頭0が5個以上は出にくいですが、100万回も見ると10個以上の0に出会う可能性が上がります。

「どれくらい長い0を見たか」は「どれくらい多くの異なる要素を見たか」のヒントになるのです。

小さな配列(レジスタ)に記録

レジスタとは

HyperLogLogは小さなスロットの配列(レジスタ)を持ち、各レジスタには「これまでに観測した先頭0の最長値」を記録します。

この配列のサイズは固定で、入力件数には依存しません。

分配のしかた(インデックスと値)

ハッシュ値の上位ビットでレジスタの位置を選び、残りのビットで「先頭0の長さ」を測ります。

各レジスタは「自分の担当分」で一番長かった0の長さだけを覚えるため、更新は最大値を取るだけです。

1回走査のストリーミング処理

追記だけでOK

新しい要素を見たら該当レジスタの値と比較して大きければ更新します。

過去データを振り返る必要がなく、ストリームに沿って1回で処理できます。

オンライン更新

到着順は自由で、後からどれだけ追加しても見積もりは自然に改善されます。

バッチでもリアルタイムでも同じロジックで動くのが扱いやすさの理由です。

ユニオン(合算)が簡単

どう合算するか

2つのHyperLogLogの合算は、対応するレジスタごとに最大値を取るだけです。

「要素の集合の和」が「レジスタの要素ごとの最大値」に変換されるため、とても高速です。

分散処理との相性

日別やシャード別に個別に数えて、最後に合算できます。

MapReduceや分散DBと組み合わせても通信量とメモリを抑えて集約できます。

使いどころと精度・メモリ

ユースケース

Webのユニーク訪問者

日次や月次のユニークユーザー数は誤差数%でも十分役立ちます。

HyperLogLogならページビューがいくら多くてもメモリは一定で、ダッシュボード更新も高速です。

イベント重複排除の見積もり

重複イベントが混じるログでも、ユニークなIDの概数をすぐに把握できます。

異常検知やピーク推定の初期指標として便利です。

誤差の目安

標準誤差の式

レジスタ数をmとすると、標準誤差はおおよそ1.04/√mです。

レジスタを4倍にすると誤差は半分程度になると覚えると直感的です。

バイアスと範囲

とても小さいユニーク数ではわずかなバイアスが出ることがありますが、多くの実装は補正を入れています。

「小さい範囲での誤差」は仕様として把握し、必要なら検証でカバーしましょう。

メモリ使用量

レジスタ数とサイズ

一般的な実装ではレジスタあたり数ビット(例: 6ビット)を使います。

メモリはレジスタ数に比例し、入力件数には依存しません。

実例のメモリ比較表

下表は6ビット/レジスタの目安です。

実装上のメタデータで多少前後します。

p(指数)	レジスタ数 m	目安誤差	メモリ目安
10	1,024	約3.2%	約0.75KB
12	4,096	約1.6%	約3KB
14	16,384	約0.8%	約12KB
15	32,768	約0.57%	約24KB

RedisのHyperLogLogはキー1つあたり約12KB(p=14相当)がデフォルトの目安です。

メリットとデメリット

メリット

メモリ一定・高速・合算が簡単・重複に強いという点が最大の利点です。

分散処理やストリーミング処理とも相性が良く、運用コストを抑えられます。

デメリット

正確な値ではなく近似であり、要素の列挙や個別削除ができません。

厳密な監査や課金などの文脈では不向きです。

不向きな場面

正確さが必須

監査、請求、在庫など1件の誤差も許されない用途では使えません。

この場合はハッシュセットや正確なDISTINCTが必要です。

小規模データ

ユニーク数がとても小さいなら、普通のセットで十分で読みやすいです。

データが小さい場面での「近似化」はむしろ複雑さを増やします。

実装の始め方と運用のコツ

RedisのHyperLogLog

最小の使い方(PFADD/PFCOUNT/PFMERGE)

RedisはHyperLogLogを標準搭載しています。

少ないコマンドで本番運用に乗せられるのが魅力です。

PFADD key value1 value2 …: 値を追加
PFCOUNT key: 推定ユニーク数を取得
PFMERGE dest src1 src2 …: 合算して保存

例:

PFADD visitors:2025-10-20 u1 u2 u3
PFCOUNT visitors:2025-10-20
PFMERGE visitors:2025 visitors:2025-10-01 visitors:2025-10-02

注意点(精度・expire)

キーに期限を設定して不要な蓄積を防ぎましょう。

expireで期間を区切り、合算用のキーだけ長く残す設計が使いやすいです。

PFCOUNTは近似なので、重要な指標はサンプリングで検証すると安心です。

Pythonで試す

ライブラリ紹介

手軽に試すならRedisを使う方法が一番簡単です。

純Pythonでも「datasketch」などのライブラリでHyperLogLogを扱えます。

Redis経由: redis-py
純Python: datasketchのHyperLogLog

例コード

Redisを使う例:

Python

import redis

r = redis.Redis(host="localhost", port=6379, db=0)

# 追加
r.pfadd("hll:visitors:2025-10-20", "u1", "u2", "u3", "u2")

# 推定ユニーク数
count = r.pfcount("hll:visitors:2025-10-20")
print("estimated uniques =", count)

# 合算(10月の合算を作成)
r.pfmerge("hll:visitors:2025-10",
          "hll:visitors:2025-10-20",
          "hll:visitors:2025-10-21")
print("estimated uniques in Oct =", r.pfcount("hll:visitors:2025-10"))

純Pythonの例(datasketch):

Python

from datasketch import HyperLogLog

hll = HyperLogLog(p=14)  # 目安誤差 ~0.8%
for uid in ["u1", "u2", "u3", "u2"]:
    hll.update(uid.encode("utf-8"))

print("estimated uniques =", int(hll.count()))

本番ではRedisなど信頼できる実装を使い、ライブラリのAPIは公式ドキュメントで確認してください。