萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 伺服器教學

巨量資料基數估算:用 1.5KB 記憶體精準統計十億不重複物件

問題背景:為什麼傳統方法失效?

假設每日收到 30 億筆事件日誌,每筆含 16 字元 ID (128 bits)。若單純用 HashSet 存放唯一 ID,即便去重比例達 2/3,仍需約 119 GB 記憶體,且不含 Java 物件開銷。若要統計數週或數月資料,硬體成本將難以負擔。

常見替代方案:位圖

位圖 將輸入透過雜湊函數映射到單一 bit,空間效率遠優於 HashSet。但統計十億基數仍需約 120 MB,且隨基數增長線性增長。稀疏位圖可壓縮,但效果有限。

突破:基數估算演算法 — 以精度換空間

基數估算 是熱門研究領域。開源專案 stream-lib 提供生產級實作。以下以統計莎士比亞全集不重複單詞為例,對比三種方法:

三種計數方法對比圖

表中可見:HyperLogLog 僅用 512 bytes 即達 3% 誤差內,而 HashMap 需近 10 MB。在網路規模運算中,這類概率計數器能節省數量級空間。

核心演算法詳解

1. 線性機率計數器 (Linear Probabilistic Counter)

適用於需控制誤差率的場景。兩階段運作:

  1. 建立位圖:分配大小為 m 的位圖 (初始全 0),對每個元素雜湊後將對應 bit 置 1。
  2. 估算基數:統計空 bit 數 Vn,代入公式 n = -m * ln(Vn) 估算基數 n。

m 可遠小於實際基數,碰撞導致誤差,但可透過調整 m 控制誤差範圍。

2. HyperLogLog (HLL) — 空間複雜度 loglog(N)

HLL 估算基數 Nmax 僅需 loglog(Nmax) + O(1) bits。核心思想:

  • 雜湊輸出視為無限二進位串 S = h(M) ∈ {0,1}^∞。
  • 將串分割為 m 個子串,觀察每個子串前導零的最大長度。
  • 取調和平均數修正偏差,精度隨 m 增長提升。

實際效能:1.5 KB 記憶體即可對十億級資料達 2% 精度,較 HashSet 的 120 MB 節省 5 個數量級。

分散式環境下的合併優勢

真實場景中資料分佈於數百台伺服器。HLL 計數器具備 可合併性:兩個相容計數器的位圖直接做 OR 運算即可合併,無需集中原始資料。這極大降低網路傳輸與協調成本,是流式處理架構 (如 Storm, Flink) 的標準組件。

下一步建議

若您使用 JVM 語言 (Java, Scala, Kotlin) 且面臨大基數統計問題,請直接整合 stream-lib。它除提供 HLL、Linear Counting 外,還包含 Top-K、頻率估算等串流處理工具,生產環境驗證成熟。

copyright © 萬盛學電腦網 all rights reserved