1. ユニーク数カウントは何が難しいか
「このログに何種類のユーザーIDが含まれるか」「今日のユニークアクセス数は何件か」——一見単純に見えるこの問いは、データ量が数百万〜数十億件になった瞬間に、地味だが厄介な工学上の課題に変わる。
正確に数えたければ方法は1つしかない。すでに見た要素を1件残らず記憶しておき、新しい要素が来るたびに「見たことがあるか」を照合することである。実装としては典型的にはハッシュセット(Pythonならset)を使うが、この方式にはメモリという避けられないコストが伴う。要素数が\(n\)
件あれば、ハッシュセットが消費するメモリは\(n\)
に比例して増え続ける。後の第7節で実測するが、Pythonのsetは要素1件あたり数十〜100バイト程度を消費するため、1億件のユニークIDを正確に数えようとすると、それだけで数GBのメモリが必要になる。
さらに厄介なのが分散環境でのマージである。ログがサーバー数十台に分散して溜まっている状況で「全サーバー合計のユニーク数」を求めたい場合、各サーバーが持つ集合をすべて1箇所に集めて和集合を取らなければならない。集合のサイズがそのままネットワーク転送量になるため、正確な集合ベースの手法は分散集計と本質的に相性が悪い。
この問題に対し、「多少の誤差は許容するので、メモリと通信量を劇的に減らしたい」というアプローチを取るのが確率的データ構造(probabilistic data structure)である。その源流は Philippe Flajolet と G. Nigel Martin が1985年に発表した論文 “ Probabilistic Counting Algorithms for Data Base Applications "(Journal of Computer and System Sciences)にある確率的カウント法(Flajolet–Martinアルゴリズム)まで遡る。これを土台に、LogLog法を経て2007年に Flajolet, Fusy, Gandouet, Meunier の4名が発表した論文 “ HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm "(AofA 2007)が、本記事の主役である**HyperLogLog(HLL)**である。要素をハッシュするだけの1パス処理で、標準誤差\(1.04/\sqrt{m}\) という驚くほど小さい誤差を、レジスタ数\(m\) 個ぶんの固定メモリだけで達成する。本記事ではこの理論を導入し、Pythonで自作実装したうえで、理論値と実測値がどこまで一致するかを検証する。
2. 直感: 「先頭に0がk個並ぶハッシュを見た」らどう考えるか
HyperLogLogの核心にあるアイデアは、突き詰めればコイン投げの確率と同じくらい単純である。
公正なコインを投げ続けて「表が\(k\) 回連続する」事象を考える。1回表が出る確率は\(1/2\) なので、\(k\) 回連続で表が出る確率は\(2^{-k}\) である。逆に言えば、もし「表が\(k\) 回連続」という事象を実際に1回でも観測できたなら、それはだいたい\(2^{k}\) 回に1回しか起きない事象を引き当てたということになる。
これをハッシュ値に置き換える。理想的なハッシュ関数は出力のビット列をコイン投げの列とみなせる(各ビットが独立に0/1をほぼ等確率で取る)。ある要素のハッシュ値の先頭に0が\(k\) 個連続しているのを観測したら、それは確率\(2^{-(k+1)}\) 程度の珍しい事象であり、「これまでに投入したユニーク要素の数はだいたい\(2^{k+1}\) 個くらいだったはずだ」と逆算できる。要素をどれだけ何回重複して入れても、同じ要素は同じハッシュ値になるため、この推定は重複に対して不変という嬉しい性質を持つ。
これがそのままFlajolet–Martin型のアルゴリズムの原型であり、たった1個のレジスタ\(R\) (観測した中で最大の先頭連続0の個数)を覚えておくだけで、\(2^{R}\) のオーダーでユニーク数を推定できる。次節では、この「1個のレジスタ」方式がなぜそのままでは使い物にならないかを説明する。
3. 単一推定器の分散問題とm個のレジスタ+調和平均
前節の\(R\) を使った推定には致命的な弱点がある。推定量の分散が大きすぎるのだ。\(R\) は「これまで見た中の最大値」であり、最大値の分布は裾が長い(まれに極端に大きな\(R\) を引く)。\(2^R\) のような指数関数を通すと、そのわずかな\(R\) のブレが推定値を2倍・4倍にしてしまう。1個のコインだけを見て「表が出る確率」を推定するようなもので、原理的に安定しない。
これを安定させる素朴な方法は、独立したハッシュ関数を\(m\) 個用意して\(m\) 個の\(R\) を求め、平均を取ることである。しかし\(m\) 個のハッシュ関数を毎回計算するのはハッシュ計算コストが\(m\) 倍になり非効率で、しかも本当に独立な\(m\) 個のハッシュ関数を用意すること自体が面倒である。
HyperLogLogの巧妙な点は、1回のハッシュ計算だけで\(m\) 個の独立な推定器を模擬することにある(この手法はstochastic averagingと呼ばれる)。ハッシュ値のビット列を2つに分割し、
- 上位\(b\) ビット(値は\(0\) 〜\(m-1\) 、\(m=2^b\) )をレジスタ番号 \(idx\) として使う
- 残りの\((64-b)\) ビットの中で「先頭から連続する0の個数+1」をrankとして計算する
という手順を踏む。要素を1件処理するたびに、その要素が属するレジスタ\(idx\) の値を「これまでの値」と「今回のrank」の大きい方に更新する(\(M[idx] \leftarrow \max(M[idx], \text{rank})\) )。全要素を処理し終えると、\(m\) 個のレジスタそれぞれが独立に(ただし互いに素な部分集合について)「先頭連続0が最大何個だったか」を記録した状態になる。図の下段がこの仕組みを表している。
最後の一手が調和平均である。各レジスタの値\(M_j\) から\(2^{M_j}\) を計算すると、これは「そのレジスタが担当した要素群のユニーク数」のおおよその逆数スケールの推定値になる。ここで単純な算術平均を取ると、まれに極端に大きな\(M_j\) を引いたレジスタ1つが\(2^{M_j}\) を通じて平均全体を吹き飛ばしてしまう。調和平均は大きな値の影響を強く減衰させる性質を持つため、外れ値耐性が高く、\(m\) 個のレジスタ全体の分散を\(1/m\) のオーダーまで抑え込める。これがHyperLogLogがまさに「調和平均を取る」という設計になっている理由であり、Flajolet et al. (2007)が理論的に\(1.04/\sqrt{m}\) という驚くほど小さい標準誤差を導出できた核心部分である。
4. 推定式・バイアス補正・小規模領域のlinear counting
前節の考え方を数式にする。レジスタ配列\(M[0..m-1]\) が与えられたとき、生の推定値は
\[ E = \alpha_m \, m^{2} \left( \sum_{j=0}^{m-1} 2^{-M_j} \right)^{-1} \]で計算される。\(\sum_j 2^{-M_j}\) の逆数に\(m\) を掛けた量は「\(2^{M_j}\) たちの調和平均」に\(m\) を掛けたものに等しく(調和平均の定義 \(m/\sum_j (2^{M_j})^{-1}\) そのもの)、前節で述べた「調和平均でユニーク数を推定する」という設計をそのまま数式化したものになっている。\(\alpha_m\) はバイアス補正定数で、Flajolet et al. (2007)により
\[ \alpha_m = \begin{cases} 0.673 & (m=16) \\ 0.697 & (m=32) \\ 0.709 & (m=64) \\ \dfrac{0.7213}{1+1.079/m} & (m \ge 128) \end{cases} \]と与えられている。この定数はMax推定量が持つ系統的なバイアス(Mellin変換を使った解析による)を打ち消すためのもので、本記事で扱う\(m=256\) 〜\(16{,}384\) はすべて\(m\ge128\) の式に当てはまる。
この推定式は、要素数\(n\) が十分大きい範囲では標準誤差
\[ \frac{\sigma[E]}{n} \approx \frac{1.04}{\sqrt{m}} \]を実現する。ここで重要なのは、この誤差は\(n\) に依存しないという点である。\(n\) が10万でも1億でも、\(m\) さえ固定していれば相対誤差はほぼ変わらない。これが後述するRedisやGA4がカーディナリティによらず固定サイズのスケッチで運用できる理由である。
ただし、上の式がそのまま機能するのは\(n\) がある程度大きいときに限られる。\(n\) がレジスタ数\(m\) に対して小さいと、多くのレジスタがまだ一度も更新されず0のままになり、\(E\) は不安定になる。Flajolet et al. (2007)はこれに対し、生の推定値\(E \le 2.5m\) のとき、linear countingと呼ばれる古典的な補正式に切り替えることを提案している。
\[ E^{*} = m \ln\frac{m}{V} \]ここで\(V\) は値が0のままのレジスタの個数である。これは「\(m\) 個のビンに\(n\) 個のボールを投げたとき、空のビンが\(V\) 個残る確率」というクーポン収集問題型の統計から導かれる式で、\(n\) がレジスタ数に対して小さい領域(=先頭連続0がほとんど発生しない領域)を高精度にカバーする。逆に、32bitハッシュを使う古典的な実装では\(2^{32}\) に近い超巨大なカーディナリティ向けの補正も必要になるが、本記事の実装は64bitハッシュを使っており(\(2^{64}\) は実験で扱う\(n\le100\) 万よりも桁違いに大きい)、この補正は実質的に発生しないため省略する。
5. Python実装
blake2bで64bit整数ハッシュを作り、レジスタ配列は1レジスタ1バイトのbytearrayで管理する(rankは最大でも64程度なので実際には6bitで足りるが、実装の単純さを優先した)。
import hashlib
import math
SALT = b"hyperloglog-blog-20260720"
def hash64(key: bytes) -> int:
"""blake2bで64bit整数ハッシュを得る。"""
d = hashlib.blake2b(key, salt=SALT[:16], digest_size=8).digest()
return int.from_bytes(d, "big")
def alpha_m(m: int) -> float:
"""Flajolet et al. 2007のバイアス補正係数alpha_m(m>=128の漸近式)。"""
return 0.7213 / (1 + 1.079 / m)
class HyperLogLog:
def __init__(self, b: int):
"""b: レジスタ番号に使うビット数。レジスタ数 m = 2^b。"""
self.b = b
self.m = 1 << b
self.registers = bytearray(self.m)
self.rem_bits = 64 - b
def add_hash(self, h: int) -> None:
"""64bit整数ハッシュ値を1件登録する。"""
idx = h >> self.rem_bits
remainder = h & ((1 << self.rem_bits) - 1)
if remainder == 0:
rank = self.rem_bits + 1
else:
rank = self.rem_bits - remainder.bit_length() + 1
if rank > self.registers[idx]:
self.registers[idx] = rank
def add(self, key: bytes) -> None:
self.add_hash(hash64(key))
def raw_estimate(self) -> float:
m = self.m
inv_sum = sum(2.0 ** (-r) for r in self.registers)
return alpha_m(m) * m * m / inv_sum
def estimate(self) -> float:
"""小規模補正(linear counting)込みの推定値。"""
m = self.m
e = self.raw_estimate()
if e <= 2.5 * m:
zeros = self.registers.count(0)
if zeros != 0:
return m * math.log(m / zeros)
return e
return e
def merge(self, other: "HyperLogLog") -> "HyperLogLog":
"""レジスタごとのmaxを取るだけで和集合のHLLになる。"""
assert self.b == other.b
out = HyperLogLog(self.b)
out.registers = bytearray(
max(a, b) for a, b in zip(self.registers, other.registers)
)
return out
idx = h >> self.rem_bitsでハッシュの上位\(b\)
ビットを取り出してレジスタ番号にし、残りのビットのbit_length()からrankを求めている。mergeメソッドがレジスタごとのmax(要素ごとのmax操作)を取るだけという単純さは、次の第7節で見る「分散集計への強さ」に直結する。
6. 実験1: 誤差はレジスタ数mだけで決まるか
理論上、相対標準誤差は\(1.04/\sqrt{m}\) で、真のカーディナリティ\(n\) には依存しないはずである。これを実測で確かめる。
レジスタ数\(m \in \{256, 1{,}024, 4{,}096, 16{,}384\}\) (\(b\in\{8,10,12,14\}\) )のそれぞれについて、真のカーディナリティ\(n\) を\(100{,}000\) から\(1{,}000{,}000\) まで10万刻みで10点動かし、各点で乱数シードを変えた30試行を実施した(要素はtrialごとに異なる乱数を混ぜたユニークな文字列)。各試行・各\(n\) で相対誤差\((E-n)/n\) を計算し、全体のRMS(二乗平均平方根)を「実測の相対標準誤差」とした。
| \(b\) | \(m\) | 実測RMS相対誤差 | 理論値 \(1.04/\sqrt{m}\) | 平均バイアス |
|---|---|---|---|---|
| 8 | 256 | 6.858% | 6.500% | +0.480% |
| 10 | 1,024 | 3.638% | 3.250% | -0.325% |
| 12 | 4,096 | 1.675% | 1.625% | +0.228% |
| 14 | 16,384 | 0.744% | 0.813% | +0.082% |
図から分かる通り、\(m\) を4倍にするたびに誤差はほぼ半分(=\(\sqrt{4}=2\) 分の1)になっており、対数スケール上で理論直線とほぼ完全に重なっている。また、薄く重ねた各\(n\) (10万〜100万の10点)ごとの実測誤差も、同じ\(m\) の中ではほぼ同じ水準に集まっており、誤差が\(n\) に依存せず\(m\) だけで決まるという理論の主張が実測でも成立していることが確認できた。バイアス(平均相対誤差)もすべて1%未満に収まっており、\(\alpha_m\) による補正が実際に機能していることも裏付けられた。
7. 実験2: メモリ比較とマージ可能性
メモリ比較: 正確なsetとの差
tracemallocで、Pythonのsetに文字列キーを追加し続けたときの実測メモリと、HyperLogLogのレジスタ配列(理論値: \(m \times 6\,\text{bit}\)
、実装上は1レジスタ1バイトのbytearrayだが理論上必要なのは6bitで足りる)を比較した。
| \(n\) | 正確なset実測メモリ | 1件あたり |
|---|---|---|
| 10,000 | 1,087.3 KB | 111.34 B |
| 100,000 | 9,944.7 KB | 101.83 B |
| 1,000,000 | 92,230.0 KB | 94.44 B |
| 10,000,000 | 866,527.9 KB | 88.73 B |
| \(b\) | \(m\) | HyperLogLogレジスタメモリ |
|---|---|---|
| 8 | 256 | 192 B (0.188 KB) |
| 10 | 1,024 | 768 B (0.750 KB) |
| 12 | 4,096 | 3,072 B (3.000 KB) |
| 14 | 16,384 | 12,288 B (12.000 KB) |
\(n=1{,}000{,}000\)
の時点で、正確なsetは約90MB(92,230.0 KB)を消費するのに対し、\(m=16{,}384\)
のHyperLogLogはわずか12KBで済み、その差は約7,686倍に達する。しかもHyperLogLogのメモリは\(n\)
がどれだけ増えても12KBのまま一定である(図の赤い水平線)。これが「ユニーク数を12KBで数える」という本記事タイトルの根拠であり、後述するRedisの実装が採用している値そのものでもある。
マージ可能性: 2つのHLLを合体させても誤差範囲に収まるか
分散環境での実用性を左右する最重要プロパティがマージ可能性である。\(m=16{,}384\)
のHyperLogLogを2つ用意し、\(|A|=600{,}000\)
、\(|B|=600{,}000\)
、うち\(180{,}000\)
件を共通部分とした(真の和集合サイズ\(|A\cup B|=1{,}020{,}000\)
)。レジスタごとのmaxを取るだけのmergeを実行し、和集合の推定値を求める試行を10回行った。
| 指標 | 値 |
|---|---|
| 真の和集合サイズ \(\lvert A\cup B\rvert\) | 1,020,000 |
| マージ推定値の平均相対誤差(10試行) | +0.089% |
| マージ推定値のRMS相対誤差(10試行) | 0.536% |
| 理論標準誤差 \(1.04/\sqrt{16{,}384}\) | 0.812% |
マージ後の推定誤差は理論標準誤差(0.812%)の範囲に収まっており、**「\(A\)
のHLLと\(B\)
のHLLをそれぞれ独立に作ってから、あとでレジスタごとのmaxを取るだけで、最初から\(A\cup B\)
全体を1つのHLLに投入したのと(誤差の範囲で)同じ結果が得られる」**ことが実測で裏付けられた。これは、サーバーごとにローカルでHLLを作り、中央には12KBのスケッチだけを送ってmaxを取ればグローバルなユニーク数が求まる、という分散集計アーキテクチャがそのまま成立することを意味する。第1節で述べた「正確な集合は転送量が要素数に比例して重い」という問題を、HyperLogLogは構造的に解消している。
8. 実システムでの使われ方
HyperLogLogは学術的な理論にとどまらず、大規模データ基盤の随所で実際に採用されている。
Redis PFADD/PFCOUNT/PFMERGE: RedisはPFADDでHyperLogLogに要素を追加し、PFCOUNTで推定カーディナリティを取得し、PFMERGEで複数のHLLを和集合にマージするコマンド群を提供している。
Redis公式ドキュメント
によれば、密(dense)表現は「16,384個の6bitカウンタを格納する12,288バイトの文字列」であり、標準誤差は**0.81%**とされている。これは本記事の実験2で検証した\(m=16{,}384\)
のケースとまったく同じ設定であり、理論値\(1.04/\sqrt{16384}\approx0.81\%\)
とも一致する。小さいカーディナリティの間はスパース表現に自動的に切り替わり、メモリをさらに節約する仕組みも備えている。
BigQuery HLL_COUNT関数群 / APPROX_COUNT_DISTINCT:
BigQueryのHyperLogLog++関数群
は、HLL_COUNT.INITでスケッチを作り、HLL_COUNT.MERGEで複数のスケッチを結合し、HLL_COUNT.EXTRACTでカーディナリティを取り出す設計になっている。スケッチ自体をBYTES型として中間テーブルに保存できるため、日次パーティションごとに事前計算したスケッチを後から自由にマージして「任意の期間のユニークユーザー数」を再計算できる。精度を指定しない場合はAPPROX_COUNT_DISTINCTが内部で同じHLL++を使う。ここで言う「精度(precision)」が本記事の\(b\)
(レジスタ番号ビット数)に相当し、精度を上げるほど誤差は減るがメモリは増えるというトレードオフは第6節の実験で確認した通りである。
Google Analytics 4 (GA4): Google公式のGA4解説記事 によれば、GA4は「アクティブユーザー数」「合計ユーザー数」に精度14(=\(m=16{,}384\) )、「セッション数」に精度12(=\(m=4{,}096\) )のHyperLogLog++を適用している。偶然にも、これは本記事の実験1・2で検証した\(m=4{,}096\) ・\(m=16{,}384\) のケースとぴったり同じ設定であり、GA4の管理画面に表示されるユーザー数・セッション数が「新規ユーザー数」を除いて厳密な値ではなく確率的推定値である背景には、まさに本記事で検証してきた仕組みが動いている。
ブルームフィルタとの対比: ブルームフィルタの記事 で扱ったブルームフィルタと、本記事のHyperLogLogは、どちらも「ハッシュ関数」「固定サイズの配列」「マージ可能性」という骨格を共有する確率的データ構造の兄弟分である。しかし答える問いがまったく違う。ブルームフィルタは**「この要素は集合に存在するか?(Yes/No)」というメンバーシップ判定に答え、偽陽性はあっても偽陰性は絶対に起きないという非対称な保証を持つ。一方HyperLogLogは「この集合には何種類の要素があるか?(カーディナリティ)」という個数の推定**に答え、個々の要素についての情報(その要素が入っているかどうか)は一切保持しない。実務では両者は排他的ではなく併用されることも多く、たとえば「一度でも見たURLかどうかをブルームフィルタで足切りしつつ、ユニークURL数はHyperLogLogで並行して数える」といった組み合わせが考えられる。
まとめ
HyperLogLogは、ハッシュ値の先頭連続0の個数という単純な統計量を、\(m\)
個のレジスタに分担させて調和平均で統合するだけで、標準誤差\(1.04/\sqrt{m}\)
というきわめて小さい誤差でユニーク数を推定できる確率的データ構造である。本記事の実測では、\(m=256\)
〜\(16{,}384\)
の4通りすべてで理論値と実測RMS誤差がほぼ一致し(例: \(m=16{,}384\)
で理論0.813%に対し実測0.744%)、正確なsetと比べて\(n=100\)
万件で約7,686倍省メモリであり、さらに2つのHLLをレジスタごとのmaxでマージした推定値も理論誤差の範囲に収まることを確認できた。RedisのPFCOUNT(標準誤差0.81%・12KB)、BigQueryのHLL_COUNT関数、GA4のユーザー数・セッション数集計など、実システムでの採用例もまさに本記事で検証した\(m\)
の値そのものであり、理論・実装・実測のすべてが一貫して整合していることが確認できた。
FAQ
Q1. HyperLogLogの誤差はどのくらいですか? 標準誤差は\(1.04/\sqrt{m}\) で近似でき、真のカーディナリティ\(n\) には(小規模領域を除き)ほぼ依存しない。たとえば\(m=16{,}384\) (Redisの標準的な密表現、GA4のユーザー数集計と同じ設定)なら約0.81%、\(m=4{,}096\) なら約1.6%である。本記事の実験1でこの理論値と実測RMS誤差がほぼ一致することを確認した。
Q2. なぜ算術平均ではなく調和平均を使うのですか? 各レジスタの値\(M_j\) から\(2^{M_j}\) を計算すると、まれに極端に大きな\(M_j\) を引いたレジスタ1つが算術平均全体を吹き飛ばしてしまう(裾の重い分布のため)。調和平均は大きな値の影響を強く減衰させる性質を持ち、この外れ値耐性のおかげで\(m\) 個のレジスタ全体の分散を\(1/m\) のオーダーまで小さく抑えられる。これがFlajolet et al. (2007)が\(1.04/\sqrt{m}\) という誤差を達成できた核心である。
Q3. 正確なユニーク数が必要な場合はどうすればいいですか?
課金計算や監査など、1件の誤差も許されない用途ではHyperLogLogは使うべきではない。正確なCOUNT(DISTINCT)やハッシュセットによる厳密なカウントを使う必要がある。逆に、ダッシュボードの表示用途、分散環境での概算集計、メモリ・通信量が支配的なボトルネックになる規模のデータでは、HyperLogLogの1%未満の誤差は十分許容範囲であることが多い。
Q4. ブルームフィルタとの違いは何ですか? 両者ともハッシュベースの確率的データ構造で、固定サイズの配列とマージ可能性を持つ点は共通している。しかし、ブルームフィルタは「特定の要素が集合に含まれるか(メンバーシップ判定)」に答え、偽陽性はあるが偽陰性は起きないという非対称な保証を持つのに対し、HyperLogLogは「集合に何種類の要素があるか(カーディナリティ)」を推定するだけで、個々の要素の在・不在についての情報は一切持たない。詳細は ブルームフィルタの記事 を参照してほしい。
他の分野の定番書は エンジニアにおすすめの技術書10選 にまとめている。