HyperLogLog 與基數估計

基數 (Cardinality) 指的是一個集合中不同元素的數量。例如：今天訪問網站的不同 IP 數。

傳統做法是用 HashSet 儲存所有 IP，但如果有 1000 萬個不同 IP，HashSet 需要數 GB 的記憶體。

HyperLogLog (HLL) 可以在只使用 1-2 KB 記憶體的情況下，以 2% 以下的誤差估計基數。

實作 HyperLogLog

import math
import mmh3
from bitarray import bitarray

class HyperLogLog:
    def __init__(self, b=10):
        """
        b: 精度參數（建議 10-16）
        記憶體使用量 = 2^b bytes
        b=10 → 1 KB, 誤差 ~3.25%
        b=14 → 16 KB, 誤差 ~0.81%
        """
        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):
        """計算 32-bit hash"""
        return mmh3.hash(str(item)) & 0xFFFFFFFF
    
    def _count_leading_zeros(self, x):
        """計算前導零的數量"""
        if x == 0:
            return 32
        return (x.bit_length() ^ 31) + 1
    
    def add(self, item):
        """加入元素"""
        x = self._hash(item)
        # 前 b 個 bit 決定暫存器索引
        idx = x & (self.m - 1)
        # 剩餘 bit 計算前導零
        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:
            # 很多暫存器還是 0
            zeros = self.registers.count(0)
            if zeros:
                estimate = self.m * math.log(self.m / zeros)
        
        # 大範圍修正
        elif estimate > (1 << 32) / 30:
            estimate = -(1 << 32) * math.log(1 - estimate / (1 << 32))
        
        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}")

print(f"\n估計基數: {hll.count():,}")
print(f"實際基數: 1,000,000")
print(f"誤差率: {abs(hll.count() - 1000000) / 1000000:.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 為一個"""
    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 bytes | | 可合併 | 兩個 HLL 可直接合併（分散式系統專用） | | 單次掃描 | 只需一次遍歷資料 | | 支援串流 | 可在無限串流上運作 | | 可並行化 | 分割資料 → 各 shard 建立 HLL → 合併 |

使用情境

網站 UV 統計：每天數億次訪問，只需 16 KB 就能即時統計
資料庫 Query 最佳化：預估 SELECT DISTINCT 的結果數量以選擇最佳查詢計畫
網路流量監控：統計不同 IP 的連線數，即時洞察流量模式
爬蟲去重：快速判斷 URL 是否已爬過
點擊流分析：統計不重複商品瀏覽數、類別、搜尋查詢

總結

超低記憶體：1-64 KB 就能處理任意大小的資料
~2% 誤差：對大多數使用場景可接受
可合併：適合分散式 MapReduce 風格的計數
基於雜湊值的前導零（丟銅板原理）
廣泛使用：Redis、PostgreSQL、AWS、Google BigQuery

為什麼 HyperLogLog 能這麼省記憶體？

你在本章中實作了 HyperLogLog，但它背後的直覺你可能還不清楚。讓我用一個簡單的比喻來說明：

想像你在拋一枚公平的硬幣。

第一次拋到「人頭」的機率是 1/2

連續拋 2 次才出現人頭的機率是 1/4

連續拋 3 次才出現人頭的機率是 1/8

連續拋 k 次才出現人頭的機率是 1/2^k

HyperLogLog 的核心洞察：如果你將每個元素透過 hash 函數變成一個二進位數字，觀察它從最低位元開始連續出現多少個 0。這個「前導零的數量」就跟拋硬幣連續出現反面的次數是一樣的——機率上，出現 10 個連續零的機率約為 1/1024。

所以如果在你的資料中，你看到了最多有 20 個連續零的元素，那合理的推測是你的資料量大約在 2^20 ≈ 100 萬左右。

當然，單一測量不準，所以 HLL 將資料分到 m 個暫存器中，各自估計再取調和平均數——這就是為什麼它精確到 ~2% 的原因。

真實案例：某電商平台的 UV 統計

# 情境：雙十一活動期間，每分鐘需要統計即時不重複訪客數
# 高峰流量：每分鐘 500 萬次請求
# 預算：不能花太多錢在 Redis 記憶體上

# 方案 A：使用 Redis Set （精準統計）
# 每分鐘 UV 約 200 萬
# Redis Set 記憶體：200萬 × ~36 bytes ≈ 72 MB
# 一天的資料量：72 MB × 1440 分鐘 = 103 GB → ❌ 不可能

# 方案 B：使用 Redis HyperLogLog
# 每個 HLL 佔用 12 KB
# 一天的資料量：12 KB × 1440 = 17 MB ✅
# 誤差：~0.81%（完全可以接受）

# Redis 指令
> PFADD uv:20241111:0930 user_12345
> PFADD uv:20241111:0930 user_67890
> PFCOUNT uv:20241111:0930
(integer) 1845327  # 估計值，誤差 ~0.8%

# 合併多個時間段的 UV
> PFMERGE uv:20241111 uv:20241111:0900 uv:20241111:0910 uv:20241111:0920
> PFCOUNT uv:20241111
(integer) 8934561  # 整天的去重訪客數

這個案例展示了 16 GB vs 17 MB——將近 1000 倍的差距，而代價只是不到 1% 的誤差。在商業分析中，UV 統計本來就允許一定誤差，HLL 是最佳人選。

下章預告：Count-Min Sketch——頻率估計

Bloom Filter 回答的是元素是否存在，HyperLogLog 回答的是有多少不同元素，而下一章的 Count-Min Sketch 回答的是另一個完全不同的問題：某個元素出現了幾次？

想像你需要即時統計串流資料中最熱門的 hashtag、最常見的錯誤類型、或是某 IP 的請求次數——Count-Min Sketch 用類似 Bloom Filter 的思路，以少量誤差換取大幅的記憶體節省。

三個機率性資料結構合在一起，就構成了大數據工程師處理串流資料的完整工具箱！