HyperLogLog 演算法的原理講解以及 Redis 是如何應用它的
如果要實現這麼一個功能：
統計 APP或網頁 的一個頁面，每天有多少使用者點選進入的次數。同一個使用者的反覆點選進入記為 1 次。
聰明的你可能會馬上想到，用 HashMap 這種資料結構就可以了，也滿足了去重。的確，這是一種解決方法，除此之外還有其它的解決方案。
問題雖不難，但當參與問題中的變數達到一定數量級的時候，再簡單的問題都會變成一個難題。假設 APP 中日活使用者達到 百萬 或 千萬以上級別 的話，我們採用 HashMap 的做法，就會導致程式中佔用大量的記憶體。
我們下面嘗試估算下 HashMap 的在應對上述問題時候的記憶體佔用。假設定義 HashMap 中 Key 為 string 型別， value 為 bool 。 key 對應使用者的 Id , value 是 是否點選進入 。明顯地，當百萬不同使用者訪問的時候。此 HashMap 的記憶體佔用空間為： 100萬 * (string + bool) 。
條件選擇
可以說，在上述問題目前現有的解決方案中， HashMap 是記憶體佔用量最多的一種。如果統計量不多，那麼可以使用這種方法解決問題，實現起來也簡單。
除此之外還有 B+ 樹 ， Bitmap 點陣圖 ，以及該文章主要介紹的 HyperLogLog 演算法解決方案。
在一定條件允許下，如果允許統計在巨量資料面前的誤差率在可接受的範圍內，1000萬瀏覽量允許最終統計出少了一兩萬這樣子，那麼就可以採用 HyperLogLog 演算法來解決上面的計數類似問題。
HyperLogLog
HyperLogLog ，下面簡稱為 HLL ，它是 LogLog 演算法的升級版，作用是能夠提供不精確的去重計數。存在以下的特點：
- 程式碼實現較難。
- 能夠使用極少的記憶體來統計巨量的資料，在
Redis中實現的HyperLogLog，只需要12K記憶體就能統計2^64個數據。 - 計數存在一定的誤差，誤差率整體較低。標準誤差為 0.81% 。
- 誤差可以被設定
輔助計算因子進行降低。
稍微對程式設計中的基礎資料型別記憶體佔用有了解的同學，應該會對其只需要 12K 記憶體就能統計 2^64 個數據而感到驚訝。為什麼這樣說呢，下面我們舉下例子：
取 Java 語言來說，一般 long 佔用8位元組，而一位元組有8位，即：1 byte = 8 bit，即 long 資料型別最大可以表示的數是： 2^63-1 。對應上面的 2^64 個數，假設此時有 2^63-1 這麼多個數，從 0 ~ 2^63-1 ，按照 long 以及 1k = 1024位元組 的規則來計算記憶體總數，就是： ((2^63-1) * 8/1024)K ，這是很龐大的一個數，儲存空間遠遠超過 12K 。而 HyperLogLog 卻可以用 12K 就能統計完。
伯努利試驗
在認識為什麼 HyperLogLog 能夠使用極少的記憶體來統計巨量的資料之前，要先認識下 伯努利試驗 。
伯努利試驗 是數學 概率論 中的一部分內容，它的典故來源於 拋硬幣 。
硬幣擁有正反兩面，一次的上拋至落下，最終出現正反面的概率都是50%。假設一直拋硬幣，直到它出現正面為止，我們記錄為一次完整的試驗，間中可能拋了一次就出現了正面，也可能拋了4次才出現正面。無論拋了多少次，只要出現了正面，就記錄為一次試驗。這個試驗就是 伯努利試驗 。
那麼對於多次的 伯努利試驗 ，假設這個多次為 n 次。就意味著出現了 n 次的正面。假設每次 伯努利試驗 所經歷了的拋擲次數為 k 。第一次 伯努利試驗 ，次數設為 k1 ，以此類推，第 n 次對應的是 kn 。
其中，對於這 n 次 伯努利試驗 中，必然會有一個最大的拋擲次數 k ，例如拋了12次才出現正面，那麼稱這個為 k_max ，代表拋了最多的次數。
伯努利試驗 容易得出有以下結論：
- n 次伯努利過程的投擲次數都不大於 k_max。
- n 次伯努利過程，至少有一次投擲次數等於 k_max
最終結合極大似然估算的方法，發現在 n 和 k_max 中存在估算關聯： n = 2^(k_max) 。這種通過區域性資訊預估整體資料流特性的方法似乎有些超出我們的基本認知，需要用概率和統計的方法才能推導和驗證這種關聯關係。
例如下面的樣子：
第一次試驗: 拋了3次才出現正面，此時 k=3，n=1 第二次試驗: 拋了2次才出現正面，此時 k=2，n=2 第三次試驗: 拋了6次才出現正面，此時 k=6，n=3 第n 次試驗：拋了12次才出現正面，此時我們估算， n = 2^12 複製程式碼
假設上面例子中實驗組數共3組，那麼 k_max = 6，最終 n=3，我們放進估算公式中去，明顯： 3 ≠ 2^6 。也即是說，當試驗次數很小的時候，這種估算方法的誤差是很大的。
估算的優化
在上面的3組例子中，我們稱為一輪的估算。如果只是進行一輪的話，當 n 足夠大的時候，估算的誤差率會相對減少，但仍然不夠小。
那麼是否可以進行多輪呢？例如進行 100 輪或者更多輪次的試驗，然後再取每輪的 k_max，再取平均數，即: k_mx/100 。最終再估算出 n。下面是 LogLog 的估算公式：
上面公式的 DVLL 對應的就是 n ， constant 是修正因子，它的具體值是不定的，可以根據實際情況而分支設定。 m 代表的是試驗的輪數。頭上有一橫的 R 就是平均數： (k_max_1 + ... + k_max_m)/m 。
這種通過增加試驗輪次，再取 k_max 平均數的演算法優化就是 LogLog 的做法。而 HyperLogLog 和 LogLog 的區別就是，它採用的不是 平均數 ，而是 調和平均數 。 調和平均數 比 平均數 的好處就是不容易受到大的數值的影響。下面舉個例子：
求平均工資:
A的是1000/月，B的30000/月。採用平均數的方式就是： (1000 + 30000) / 2 = 15500
採用調和平均數的方式就是： 2/(1/1000 + 1/30000) ≈ 1935.484
明顯地， 調和平均數 比 平均數 的效果是要更好的。下面是 調和平均數 的計算方式， ∑ 是累加符號。
扯上關係
上面的內容我們已經知道，在拋硬幣的例子中，可以通過一次伯努利試驗中出現的 k_max 來估算 n 。
那麼這種估算方法如何和下面問題有所關聯呢？
統計 APP或網頁 的一個頁面，每天有多少使用者點選進入的次數。同一個使用者的反覆點選進入記為 1 次
HyperLogLog 是這樣做的。對於輸入的資料，進行下面幾個步驟：
1.位元串
通過 hash 函式，將資料轉為 位元串 ，例如輸入5，便轉為：101。為什麼要這樣轉化呢？
是因為要和拋硬幣對應上， 位元串 中，0 代表了反面，1 代表了正面，如果一個數據最終被轉化了 10010000 ，那麼從右往左，從低位往高位看，我們可以認為，首次出現 1 的時候，就是正面。
那麼基於上面的估算結論，我們可以通過多次拋硬幣實驗的最大拋到正面的次數來預估總共進行了多少次實驗，同樣也就可以根據存入資料中，轉化後的出現了 1 的最大的位置 k_max 來估算存入了多少資料。
2.分桶
分桶就是分多少輪。抽象到計算機儲存中去，就是儲存的是一個以單位是位元(bit)，長度為 L 的大陣列 S ，將 S 平均分為 m 組，注意這個 m 組，就是對應多少輪，然後每組所佔有的位元個數是平均的，設為 P。容易得出下面的關係：
- L = S.length
- L = m * p
- 以 K 為單位，S 佔用的記憶體 = L / 8 / 1024
在 Redis 中， HyperLogLog 設定為：m=16834，p=6，L=16834 * 6。佔用記憶體為=16834 * 6 / 8 / 1024 = 12K
形象化為：
第0組第1組.... 第16833組 [000 000] [000 000] [000 000] [000 000] .... [000 000] 複製程式碼
3. 對應
現在回到我們的原始APP頁面統計使用者的問題中去。
- 設 APP 主頁的 key 為： main
- 使用者 id 為：idn , n->0,1,2,3....
在這個統計問題中，不同的使用者 id 標識了一個使用者，那麼我們可以把使用者的 id 作為被 hash 的輸入。即：
hash(id) = 位元串
不同的使用者 id，必然擁有不同的 位元串 。每一個 位元串 ，也必然會至少出現一次 1 的位置。我們類比每一個 位元串 為一次 伯努利試驗 。
現在要 分輪 ，也就是 分桶 。所以我們可以設定，每個 位元串 的前多少位轉為10進位制後，其值就對應於所在桶的標號。假設 位元串 的低兩位用來計算桶下標誌，此時有一個使用者的id的 位元串 是：1001011000011。它的所在桶下標為： 11(2) = 1*2^1 + 1*2^0 = 3 ，處於第3個桶，即第3輪中。
上面例子中，計算出桶號後，剩下的 位元串 是：10010110000，從低位到高位看，第一次出現 1 的位置是 5 。也就是說，此時第3個桶，第3輪的試驗中， k_max = 5 。5 對應的二進位制是：101，又因為每個桶有 p 個位元位。當 p>=3 時，便可以將 101 存進去。
模仿上面的流程，多個不同的使用者 id，就被分散到不同的桶中去了，且每個桶有其 k_max。然後當要統計出 mian 頁面有多少使用者點選量的時候，就是一次估算。最終結合所有桶中的 k_max，代入估算公式，便能得出估算值。
下面是 HyperLogLog 的結合了調和平均數的估算公式，變數釋意和 LogLog 的一樣:
Redis 中對 HyperLogLog 的應用
首先，在 Redis 中，HyperLogLog 是它的一種高階資料結構。提供有包含但不限於下面兩條命令：
- pfadd key value，將 key 對應的一個 value 存入
- pfcount key，統計 key 的 value 有多少個
回想一下，原始APP頁面統計使用者的問題。如果 key 對應頁面名稱，value 對應使用者id。那麼問題就剛剛好對應上了。
Redis 中的 HyperLogLog 原理
前面我們已經認識到，它的實現中，設有 16384 個桶，即：2^14 = 16384，每個桶有 6 位，每個桶可以表達的最大數字是：2^5+2^4+...+1 = 63 ，二進位制為： 111 111 。
對於命令： pfadd key value
在存入時，value 會被 hash 成 64 位，即 64 bit 的位元字串，前 14 位用來選擇這個 value 的位元串中 從右往左 第一個 1 出現的下標位置數值要存到那個桶中去，即前 14 位用來分桶。設第一個1出現位置的數值為 index 。當 index=5 時，就是: ....10000 [01 0000 0000 0000]
之所以選 14位 來表達桶編號是因為，分了 16384 個桶，而 2^14 = 16384，剛好地，最大的時候可以把桶利用完，不造成浪費。假設一個字串的前 14 位是：00 0000 0000 0010 (從右往左看) ，其十進位制值為 2。那麼 index 將會被轉化後放到編號為 2 的桶。
index 的轉化規則：
首先因為完整的 value 位元字串是 64 位形式，減去 14 後，剩下 50 位，那麼極端情況，出現 1 的位置，是在第 50 位，即位置是 50。此時 index = 50。此時先將 index 轉為 2 進位制，它是：110010 。
因為16384 個桶中，每個桶是 6 bit 組成的。剛好 110010 就被設定到了第 2 號桶中去了。請注意，50 已經是最壞的情況，且它都被容納進去了。那麼其他的不用想也肯定能被容納進去。
因為 fpadd 的 key 可以設定多個 value。例如下面的例子：
pfadd lgh golang pfadd lgh python pfadd lgh java 複製程式碼
根據上面的做法，不同的 value，會被設定到不同桶中去，如果出現了在同一個桶的，即前 14 位值是一樣的，但是後面出現 1 的位置不一樣。那麼比較原來的 index 是否比新 index 大。是，則替換。否，則不變。
最終地，一個 key 所對應的 16384 個桶都設定了很多的 value 了，每個桶有一個 k_max 。此時呼叫 pfcount 時，按照前面介紹的估算方式，便可以計算出 key 的設定了多少次 value，也就是統計值。
value 被轉為 64 位的位元串，最終被按照上面的做法記錄到每個桶中去。64 位轉為十進位制就是：2^64， HyperLogLog 僅用了： 16384 * 6 /8 / 1024 K 儲存空間就能統計多達 2^64 個數。
偏差修正
在估算的計算公式中， constant 變數不是一個定值，它會根據實際情況而被分支設定，例如下面的樣子。
假設：m為分桶數，p是m的以2為底的對數。
// m 為桶數
switch (p) {
case 4:
constant = 0.673 * m * m;
case 5:
constant = 0.697 * m * m;
case 6:
constant = 0.709 * m * m;
default:
constant = (0.7213 / (1 + 1.079 / m)) * m * m;
}
複製程式碼
巨人的肩膀
由簡單的拋硬幣試驗可以引匯出如此的震撼的演算法，數學之強大。
感謝下面兩遍博文的指引：
本文所有圖片來源於：
https://www.jianshu.com/p/55defda6dcd2
本文內容參考於：
http://www.rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html
手動直觀觀察 LogLog 和 HyperLogLog 變化的網站：
http://content.research.neustar.biz/blog/hll.html