神奇的HyperLogLog演算法

基數計數基本概念

基數計數(cardinality counting)通常用來統計一個集合中不重複的元素個數，例如統計某個網站的UV，或者用戶搜索網站的關鍵詞數量。數據分析、網路監控及資料庫優化等領域都會涉及到基數計數的需求。 要實現基數計數，最簡單的做法是記錄集合中所有不重複的元素集合S_u

，當新來一個元素x_i，若S_u中不包含元素x_i，則將x_i加入S_u，否則不加入，計數值就是S_u的元素數量。這種做法存在兩個問題：

當統計的數據量變大時，相應的存儲內存也會線性增長

當集合S_u變大，判斷其是否包含新加入元素x_i的成本變大

大數據量背景下，要實現基數計數，首先需要確定存儲統計數據的方案，以及如何根據存儲的數據計算基數值；另外還有一些場景下需要融合多個獨立統計的基數值，例如對一個網站分別統計了三天的UV，現在需要知道這三天的UV總量是多少，怎麼融合多個統計值。

基數計數方法B樹

B樹最大的優勢是插入和查找效率很高，如果用B樹存儲要統計的數據，可以快速判斷新來的數據是否已經存在，並快速將元素插入B樹。要計算基數值，只需要計算B樹的節點個數。 將B樹結構維護到內存中，可以快速統計和計算，但依然存在問題，B樹結構只是加快了查找和插入效率，並沒有節省存儲內存。例如要同時統計幾萬個鏈接的UV，每個鏈接的訪問量都很大，如果把這些數據都維護到內存中，實在是夠嗆。

bitmap

代表實際數組[2,3,5,8]。新加入一個元素，只需要將已有的bit數組和新加入的數字做按位或(or)計算。bitmap中1的數量就是集合的基數值。

bitmap有一個很明顯的優勢是可以輕鬆合并多個統計結果，只需要對多個結果求異或就可以。也可以大大減少存儲內存，可以做個簡單的計算，如果要統計1億個數據的基數值，大約需要內存： 100000000/8/1024/1024approx

12M

如果用32bit的int代表每個統計數據，大約需要內存：

32*100000000/8/1024/1024approx381M

bitmap對於內存的節約量是顯而易見的，但還是不夠。統計一個對象的基數值需要12M，如果統計10000個對象，就需要將近120G了，同樣不能廣泛用於大數據場景。

概率演算法

實際上目前還沒有發現更好的在大數據場景中準確計算基數的高效演算法，因此在不追求絕對準確的情況下，使用概率演算法算是一個不錯的解決方案。概率演算法不直接存儲數據集合本身，通過一定的概率統計方法預估基數值，這種方法可以大大節省內存，同時保證誤差控制在一定範圍內。目前用於基數計數的概率演算法包括:

Linear Counting(LC)：早期的基數估計演算法，LC在空間複雜度方面並不算優秀，實際上LC的空間複雜度與上文中簡單bitmap方法是一樣的（但是有個常數項級別的降低），都是O(N_)；

LogLog Counting(LLC)：LogLog Counting相比於LC更加節省內存，空間複雜度只有O(log_2(log_2(N_)))

HyperLogLog Counting(HLL)：HyperLogLog Counting是基於LLC的優化和改進，在同樣空間複雜度情況下，能夠比LLC的基數估計誤差更小。

下面將著重講HLL的原理和計算過程。

HyperLogLog的驚人表現

上面我們計算過用bitmap存儲1一億個統計數據大概需要12M內存；而在HLL中，只需要不到1K內存就能做到；redis中實現的HyperLogLog，只需要12K內存，在標準誤差0.81%的前提下，能夠統計2^

個數據。首先容我感嘆一下數學的強大和魅力，那麼概率演算法是怎樣做到如此節省內存的，又是怎樣控制誤差的呢？

首先簡單展示一下HLL的基本做法，HLL中實際存儲的是一個長度為m

的大數組S，將待統計的數據集合劃分成m組，每組根據演算法記錄一個統計值存入數組中。數組的大小m由演算法實現方自己確定，redis中這個數組的大小是16834，m越大，基數統計的誤差越小，但需要的內存空間也越大。

這裡有個HLL demo可以看一下HLL到底是怎麼做到這種超乎想像的事情的。

通過hash函數計算輸入值對應的比特串

比特串的低t(t=log_2^m)位對應的數字用來找到數組S中對應的位置i

t+1位開始找到第一個1出現的位置k，將k記入數組S_i位置

基於數組S記錄的所有數據的統計值，計算整體的基數值，計算公式可以簡單表示為：hat=f(S)

看到這裡心裡應該有無數個問號，這樣真的就能統計到上億條數據的基數了嗎？我總結一下，先拋出三個疑問：

為什麼要記錄第一個1出現的位置？

為什麼要有分桶數組S？

通過分桶數組S計算基數的公式是什麼？

hyperloglog原理理解

舉一個我們最熟悉的拋硬幣例子，出現正反面的概率都是1/2，一直拋硬幣直到出現正面，記錄下投擲次數k

，將這種拋硬幣多次直到出現正面的過程記為一次伯努利過程，對於n次伯努利過程，我們會得到n個出現正面的投擲次數值k_1,k_2……k_n，其中最大值記為k_，那麼可以得到下面結論：

n次伯努利過程的投擲次數都不大於k_

n次伯努利過程，至少有一次投擲次數等於k_

對於第一個結論，n

次伯努利過程的拋擲次數都不大於k_的概率用數學公式表示為：

P_n(X le k_)=(1-1/2^})^n

第二個結論至少有一次等於k_

的概率用數學公式表示為：

P_n(X ge k_)=1-(1-1/2^-1})^n

當nll 2^}

時，P_n(X ge k_)approx0，即當n遠小於2^}時，上述第一條結論不成立；

當ngg 2^}時，P_n(X le k_)approx0，即當n遠大於2^}時，上述第二條結論不成立。 因此，我們似乎就可以用2^}的值來估計n的大小。

以上結論可以總結為：進行了n

次進行拋硬幣實驗，每次分別記錄下第一次拋到正面的拋擲次數k，那麼可以用n次實驗中最大的拋擲次數k_來預估實驗組數量n：hat = 2^}

可以通過一組小實驗驗證一下這種估計方法是否基本合理。

回到基數統計的問題，我們需要統計一組數據中不重複元素的個數，集合中每個元素的經過hash函數後可以表示成0和1構成的二進位數串，一個二進位串可以類比為一次拋硬幣實驗，1是拋到正面，0是反面。二進位串中從低位開始第一個1出現的位置可以理解為拋硬幣試驗中第一次出現正面的拋擲次數k

，那麼基於上面的結論，我們可以通過多次拋硬幣實驗的最大拋到正面的次數來預估總共進行了多少次實驗，同樣可以可以通過第一個1出現位置的最大值k_來預估總共有多少個不同的數字（整體基數）。

這種通過局部信息預估整體數據流特性的方法似乎有些超出我們的基本認知，需要用概率和統計的方法才能推導和驗證這種關聯關係。HyperLogLog核心在於觀察集合中每個數字對應的比特串，通過統計和記錄比特串中最大的出現1的位置來估計集合整體的基數，可以大大減少內存耗費。

現在回到第二節中關於HyperLogLog的第一個疑問，為什麼要統計hash值中第一個1出現的位置？

第一個1出現的位置可以類比為拋硬幣實驗中第一次拋到正面的拋擲次數，根據拋硬幣實驗的結論，記錄每個數據的第一個出現的位置k

，就可以通過其中最大值}推導出數據集合的基數：hat = 2^}。

hyperloglog演算法講解分桶平均

HLL的基本思想是利用集合中數字的比特串第一個1出現位置的最大值來預估整體基數，但是這種預估方法存在較大誤差，為了改善誤差情況，HLL中引入分桶平均的概念。

同樣舉拋硬幣的例子，如果只有一組拋硬幣實驗，運氣較好，第一次實驗過程就拋了10次才第一次拋到正面，顯然根據公式推導得到的實驗次數的估計誤差較大；如果100個組同時進行拋硬幣實驗，同時運氣這麼好的概率就很低了，每組分別進行多次拋硬幣實驗，並上報各自實驗過程中拋到正面的拋擲次數的最大值，就能根據100組的平均值預估整體的實驗次數了。

分桶平均的基本原理是將統計數據劃分為m

個桶，每個桶分別統計各自的}並能得到各自的基數預估值hat，最終對這些hat求平均得到整體的基數估計值。LLC中使用幾何平均數預估整體的基數值，但是當統計數據量較小時誤差較大；HLL在LLC基礎上做了改進，採用調和平均數，調和平均數的優點是可以過濾掉不健康的統計值，具體的計算公式為：

hat=cfrac 1 {cfrac 1 }} + cfrac 1 }}+…+cfrac 1 }}}

回到第二節中關於HLL的第二個疑問，為什麼要有分桶數組S

？分桶數組是為了消減因偶然性帶來的誤差，提高預估的準確性。那麼分桶數組的大小m怎麼確定呢？

這是由演算法實現方自己設定的，例如上面HLL demo中，設定統計數組的大小m=64，如果函數得到的比特串是32位，需要其中6(log_264)位定位分桶數組中的桶的位置，還剩下26位（需要記錄的出現1的位置的最大值是26），那麼數組中每個桶需要5(log_226)位記錄1第一次出現的位置，整個統計數組需要花費的內存為：

5bit*64=32bit

也就是用32bit的內存能夠統計的基數數量為2^。

偏差修正

上述經過分桶平均後的估計量看似已經很不錯了，不過通過數學分析可以知道這並不是基數n的無偏估計。因此需要修正成無偏估計。這部分的具體數學分析在「Loglog Counting of Large Cardinalities」中。

hat n_ = displaystyle ext * m^2 *left (sum_^m 2^{-k_j}
ight )^{-1}

其中係數constant

由統計數組的大小m決定，具體的公式為：

constant=(mint_0^infty(log_2{frac })^mdu)^{-1}

根據論文中分析結論，HLL與LLC一樣是漸進無偏估計，漸進標準誤差表示為：

SE_(frac {hat n}n)=frac {sqrt m}

因此，統計數組大小m

越大，基數統計的標準誤差越小，但需要的存儲空間也越大，在m=2^的情況下，HLL的標準誤差為1.1%。

雖然調和平均數能夠適當修正演算法誤差，但作者給出一種分階段修正演算法。當HLL演算法開始統計數據時，統計數組中大部分位置都是空數據，並且需要一段時間才能填滿數組，這種階段引入一種小範圍修正方法；當HLL演算法中統計數組已滿的時候，需要統計的數據基數很大，這時候hash空間會出現很多碰撞情況，這種階段引入一種大範圍修正方法。最終演算法用偽代碼可以表示為如下。

m = 2^b # with b in [4...16] if m == 16: alpha = 0.673 elif m == 32: alpha = 0.697 elif m == 64: alpha = 0.709 else: alpha = 0.7213/(1 + 1.079/m) registers = [0]*m # initialize m registers to 0 ########################################################################### # Construct the HLL structure for h in hashed(data): register_index = 1 + get_register_index( h,b ) # binary address of the rightmost b bits run_length = run_of_zeros( h,b ) # length of the run of zeroes starting at bit b+1 registers[ register_index ] = max( registers[ register_index ], run_length ) ########################################################################## # Determine the cardinality DV_est = alpha * m^2 * 1/sum( 2^ -register ) # the DV estimate if DV_est

redis正是基於以上的HLL演算法實現的HyperLogLog結構，用於統計一組數據集合中不重複的數據個數。 redis中統計數組大小設置為m=16384

，hash函數生成64位bit數組，其中log_2=14位用來找到統計數組的位置，剩下50位用來記錄第一個1出現的位置，最大位置為50，需要log_2=6位記錄。

那麼統計數組需要的最大內存大小為：6bit * 16834approx12k

基數估計的標準誤差為0.81\%。可以學習一下redis中HyperLogLog的源碼實現。

參考閱讀

Redis new data structure: the HyperLogLog

HyperLogLog — Cornerstone of a Big Data Infrastructure

解讀Cardinality Estimation演算法（第四部分：HyperLogLog Counting及Adaptive Counting）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！