Redis 中 HyperLogLog 的使用場景

什麼是基數估算

HyperLogLog 是一種基數估算算法。所謂基數估算,就是估算在一批數據中,不重複元素的個數有多少。

從數學上來說,基數估計這個問題的詳細描述是:對於一個數據流 {x1,x2,…,xs} 而言,它可能存在重複的元素,用 n 來表示這個數據流的不同元素的個數,並且這個集合可以表示為{e1,…,en}。目標是:使用 m 這個量級的存儲單位,可以得到 n 的估計值,其中 m<<n 。並且估計值和實際值 n 的誤差是可以控制的。

對於上面這個問題,如果是想得到精確的基數,可以使用字典(dictionary)這一個數據結構。對於新來的元素,可以查看它是否屬於這個字典;如果屬於這個字典,則整體計數保持不變;如果不屬於這個字典,則先把這個元素添加進字典,然後把整體計數增加一。當遍歷了這個數據流之後,得到的整體計數就是這個數據流的基數了。

這種算法雖然精準度很高,但是使用的空間複雜度卻很高。那麼是否存在一些近似的方法,可以估算出數據流的基數呢?HyperLogLog 就是這樣一種算法,既可以使用較低的空間複雜度,最後估算出的結果誤差又是可以接受的。

HyperLogLog 算法簡介

HyperLogLog 算法的基本思想來自伯努利過程

伯努利過程就是一個拋硬幣實驗的過程。拋一枚正常硬幣,落地可能是正面,也可能是反面,二者的概率都是 1/2 。伯努利過程就是一直拋硬幣,直到落地時出現正面位置,並記錄下拋擲次數k。比如說,拋一次硬幣就出現正面了,此時 k 為 1; 第一次拋硬幣是反面,則繼續拋,直到第三次才出現正面,此時 k 為 3。

那麼如何通過伯努利過程來估算拋了多少次硬幣呢?還是假設 1 代表拋出正面,0 代表反面。連續出現兩次 0 的序列應該為「001」,那麼它出現的概率應該是三個二分之一相乘,即八分之一。那麼可以估計大概拋了 8 次硬幣。

HyperLogLog 原理思路是通過給定 n 個的元素集合,記錄集合中數字的比特串第一個1出現位置的最大值k,也可以理解為統計二進制低位連續為零(前導零)的最大個數。通過k值可以估算集合中不重複元素的數量m,m近似等於 2^k。

img

如上圖所示,給定一定數量的用戶,通過 Hash 算法得到一串 Bitstring,記錄其中最大連續零位的計數為 4,User 的不重複個數為 2 ^ 4 = 16。

1. 分桶優化

HyperLogLog 的基本思想是利用集合中數字的比特串第一個 1 出現位置的最大值來預估整體基數,但是這種預估方法存在較大誤差,為了改善誤差情況,HyperLogLog中引入分桶平均的概念,計算 m 個桶的調和平均值。下面公式中的const是一個修正常量。

Redis 中 HyperLogLog 一共分了 2^14 個桶,也就是 16384 個桶。每個桶中是一個 6 bit 的數組,如下圖所示。

img

HyperLogLog 將上文所說的 64 位比特串的低 14 位單獨拿出,它的值就對應桶的序號,然後將剩下 50 位中第一次出現 1 的位置值設置到桶中。50位中出現1的位置值最大為50,所以每個桶中的 6 位數組正好可以表示該值。

在設置前,要設置進桶的值是否大於桶中的舊值,如果大於才進行設置,否則不進行設置。示例如下圖所示。

img

在計算近似基數時,就分別計算每個桶中的值,帶入到上文將的 DV 公式中,進行調和平均和結果修正,就能得到估算的基數值。

Redis 中的 HyperLogLog

Redis 提供了 PFADDPFCOUNTPFMERGE 三個命令來供用戶使用 HyperLogLog。

# 用於向 HyperLogLog 添加元素
# 如果 HyperLogLog 估計的近似基數在 PFADD 命令執行之後出現了變化, 那麼命令返回 1 , 否則返回 0 
# 如果命令執行時給定的鍵不存在, 那麼程序將先創建一個空的 HyperLogLog 結構, 然後再執行命令
pfadd key value1 [value2 value3]

# PFCOUNT 命令會給出 HyperLogLog 包含的近似基數
# 在計算出基數後, PFCOUNT 會將值存儲在 HyperLogLog 中進行緩存,知道下次 PFADD 執行成功前,就都不需要再次進行基數的計算。
pfcount key

# PFMERGE 將多個 HyperLogLog 合併為一個 HyperLogLog , 合併後的 HyperLogLog 的基數接近於所有輸入 HyperLogLog 的並集基數。
pfmerge destkey key1 key2 [...keyn]

應用場景

HyperLogLog 主要的應用場景就是進行基數統計。這個問題的應用場景其實是十分廣泛的。例如:對於 Google 主頁面而言,同一個賬戶可能會訪問 Google 主頁面多次。於是,在諸多的訪問流水中,如何計算出 Google 主頁面每天被多少個不同的賬戶訪問過就是一個重要的問題。那麼對於 Google 這種訪問量巨大的網頁而言,其實統計出有十億 的訪問量或者十億零十萬的訪問量其實是沒有太多的區別的,因此,在這種業務場景下,為了節省成本,其實可以只計算出一個大概的值,而沒有必要計算出精準的值。

對於上面的場景,可以使用HashMapBitMapHyperLogLog 來解決。對於這三種解決方案,這邊做下對比:

  • HashMap:算法簡單,統計精度高,對於少量數據建議使用,但是對於大量的數據會佔用很大內存空間;
  • BitMap:位圖算法,具體內容可以參考我的這篇文章,統計精度高,雖然內存佔用要比HashMap少,但是對於大量數據還是會佔用較大內存;
  • HyperLogLog :存在一定誤差,佔用內存少,穩定佔用 12k 左右內存,可以統計 2^64 個元素,對於上面舉例的應用場景,建議使用。

參考