HyperLogLog (HLL)

引言：「獨立訪客」問題

你是一家社交媒體網站的 CTO。你想統計今天有多少 獨立 (Unique) 使用者訪問了某個特定頁面（即基數估計）。

• 集合法： 將每個使用者 ID 存入 Hash Set。1 億個 ID $imes$ 8 位元組 $\approx$ 800MB。如果有 10,000 個頁面，你需要 8TB 記憶體。這根本不現實。
• HyperLogLog： 僅使用 1.5 KB 記憶體即可統計這 1 億個使用者，誤差約為 2%。

HyperLogLog 是一種解決 去重計數 (Count-Distinct) 問題的概率演算法。它是 Redis、BigQuery 和 AWS Redshift 處理海量數據的核心工具。

演算法要解決什麼問題？

• 輸入： 元素流。
• 輸出： 已見過的 唯一 元素數量的估算值。
• 承諾： 記憶體佔用極小且固定，無論你統計的數據量是 1 萬還是 10 億。

核心思想 (直覺版)

想像 拋硬幣。

• 如果我告訴你：「我拋硬幣，開頭連續出了 3 個反面 (TTT…)」，你會猜我大概拋了 8 次左右。
• 如果我告訴你：「我開頭連續出了 20 個反面 (TTTT…TT)」，你會猜我大概拋了上百萬次。

HyperLogLog 將這種邏輯應用到了數據上：

1. 將元素雜湊為二進位字串。
2. 觀察雜湊值中 前導零的數量。
3. 看到的前導零越多，說明集合中存在的唯一元素可能就越多。
4. 為了避免偶然性，她將數據分到多個「桶」中並取平均值。

為什麼要用她？

• ✅ 極致省錢： 她是空間的絕對王者。她能在比一條推文還小的空間裡統計數十億項數據。
• ✅ 可合併性： 你可以分別計算「週一」和「週二」的 HLL，然後直接合併她們，得到「整週」的去重計數，結果非常準確。

典型業務場景

• ✅ DAU/MAU 統計： 即時估算日活/月活使用者數。

• ✅ 廣告技術： 在數十億次廣告展示中，統計有多少個獨立使用者看過了廣告。

• ✅ 網路安全： 統計連接到伺服器的唯一 IP 數量，以檢測 DDoS 攻擊。

• ❌ 需要精確值： 如果出於計費或法律原因需要精確到個位數的數值，HLL 不適合你。她的標準誤差約為 2%。

性能與複雜度總結

• 時間： 添加和查詢均為 $O(1)$。
• 空間： $O(\log \log N)$（在實踐中幾乎是常數，如 1.5KB）。

小結：一句話記住它

「HyperLogLog 是『估算的奇蹟』。她將統計數十億數據的任務轉化為一個關於『數零』的統計遊戲。當『足夠接近』能換取一萬倍的記憶體節省時，請使用她。」