HyperLogLog

🔥 Vibe プロンプト

「100万件のログから16KBメモリでHLLを使用してユニークビジターをカウント。実際の値と比較。」

HyperLogLogとは？

HyperLogLog (HLL) は、マルチセットの**カーディナリティ（異なる要素の数）**を推定する確率的アルゴリズムです。数十億のユニークアイテムをわずか1-2 KBのメモリでカウントでき、通常約2%の誤差で推定します。

直感的な理解： コインを何回投げたら3回連続で表が出る？約2^3 = 8回。HLLも同じ原理を使います。ハッシュ値の先頭にあるゼロの数（例：00001...は5個のゼロ）から、約2^5 = 32個のユニークアイテムを見たと推定します。

仕組み

1. 各アイテムを32ビットまたは64ビットのハッシュ値に変換
2. 最初のbビットを使用して、2^b個のレジスタの1つを選択
3. 残りのビットで先頭ゼロの数をカウント
4. 各レジスタの**最大**先頭ゼロ数を保存
5. 全レジスタの調和平均からカーディナリティを推定

数学的基礎

E = α_m * m * (1 / Σ(2^(-M[j])))

ここで:
  α_m = バイアス補正定数
  m = 2^b = レジスタ数
  M[j] = レジスタjの最大先頭ゼロ数 + 1

バイアス補正定数

| b (精度) | m (レジスタ) | α_m | メモリ | 誤差 | |---------|-------------|-----|-------|------| | 10 | 1,024 | 0.673 | 1 KB | ~3.25% | | 14 | 16,384 | 0.718 | 16 KB | ~1.40% | | 16 | 65,536 | 0.721 | 64 KB | ~1.00% |

実装

import math
import mmh3

class HyperLogLog:
    def __init__(self, b=14):
        """
        b: 精度パラメータ（推奨: 10-16）
        メモリ = 2^b バイト
        b=10 → 1 KB, 誤差 ~3.25%
        b=14 → 16 KB, 誤差 ~1.40%
        """
        self.b = b
        self.m = 1 << b
        self.registers = [0] * self.m
        self.alpha = self._get_alpha()
    
    def _get_alpha(self):
        if self.m == 16: return 0.673
        elif self.m == 32: return 0.697
        elif self.m == 64: return 0.709
        else: return 0.7213 / (1 + 1.079 / self.m)
    
    def _hash(self, item):
        return mmh3.hash(str(item)) & 0xFFFFFFFF
    
    def _count_leading_zeros(self, x):
        """32ビット整数の先頭ゼロをカウント"""
        if x == 0: return 32
        return (x.bit_length() ^ 31) + 1
    
    def add(self, item):
        x = self._hash(item)
        idx = x & (self.m - 1)  # 最初のbビット → レジスタ選択
        w = x >> self.b          # 残りのビット
        self.registers[idx] = max(self.registers[idx],
            self._count_leading_zeros(w) + 1)
    
    def count(self):
        """カーディナリティを推定"""
        sum_inv = sum(2.0 ** -r for r in self.registers)
        estimate = self.alpha * self.m * self.m / sum_inv
        
        # 小範囲補正（線形計数）
        if estimate <= 2.5 * self.m:
            zeros = self.registers.count(0)
            if zeros > 0:
                estimate = self.m * math.log(self.m / zeros)
        
        return int(estimate)

# 使用例
hll = HyperLogLog(b=14)  # 16 KB
print(f"レジスタ数: {hll.m:,}")
print(f"メモリ: {hll.m} bytes = {hll.m/1024:.1f} KB")

# 100万件のユニークアイテムを追加
for i in range(1000000):
    hll.add(f"user_{i}_session_{i*2}")

# 推定
estimated = hll.count()
actual = 1000000
print(f"\n推定ユニーク数: {estimated:,}")
print(f"実際のユニーク数: {actual:,}")
print(f"誤差: {abs(estimated-actual)/actual:.4%}")

メモリ比較

| アルゴリズム | 10億アイテム | メモリ | 精度 | |-----------|------------|-------|------| | HashSet | 10億IP | 16 GB | 100% | | HyperLogLog (b=10) | 任意 | 1 KB | ~96.75% | | HyperLogLog (b=14) | 任意 | 16 KB | ~98.60% | | HyperLogLog (b=16) | 任意 | 64 KB | ~99.00% |

HLLのマージ（分散カウンティング）

def merge_hll(hlls):
    """複数のHLLを1つにマージ"""
    merged = HyperLogLog(b=hlls[0].b)
    for h in hlls:
        for i in range(merged.m):
            merged.registers[i] = max(merged.registers[i], h.registers[i])
    return merged

# 例: 10台のサーバーシャード全体のユニークユーザー
shard_hlls = [build_hll_from_shard(i) for i in range(10)]
total_hll = merge_hll(shard_hlls)
print(f"全ユニークユーザー: {total_hll.count():,}")

利点

| 利点 | 理由 | |------|------| | 固定メモリ | アイテム数に関係なく常に2^bバイト | | マージ可能 | 2つのHLLをマージ可能（分散システムに最適） | | シングルパス | データの一回の走査のみ必要 | | ストリーム対応 | 無限ストリームで動作 | | 並列化可能 | データ分割→各シャードでHLL→マージ |

実世界の応用

1. リアルタイムUVダッシュボード

Google AnalyticsなどのWeb分析プラットフォームは、1日あたりのユニークビジター数をカウントするためにHLLを使用しています。数百万のビジターを16 KBで処理できます。

2. データベースカーディナリティ推定

PostgreSQLはHLLを使用して、クエリプランナーがインデックススキャンとシーケンシャルスキャンのどちらを選択するかを最適化しています。

3. ネットワークトラフィック監視

ネットワーク監視ツールは、ユニーク送信元IP、宛先IP、フロー数を追跡します。HLLにより最小メモリでリアルタイムの可視性を実現します。

4. クリックストリーム分析

Eコマースプラットフォームは、ユニークな閲覧商品、閲覧カテゴリ、検索クエリをセッションごとにカウントします。

まとめ

超低メモリ: 1-64 KBで任意サイズのデータを処理
~2%誤差: ほとんどのユースケースで許容範囲
マージ可能: 分散MapReduceスタイルのカウンティングに最適
ハッシュの先頭ゼロに基づく（コインフリップの原理）
使用例: Redis, PostgreSQL, Google BigQuery