HyperLogLog，可能很多人對redis這個功能都很陌生，在日常開發中也很少用到它，或者用了它也沒有深入的了解過，下面我們將詳細介紹。HyperLogLog簡稱HLL，它是LogLog算法的升級版，其功能是能夠為大數據場景提供“不精確”的去重計數。

該算法具有以下特性：

算法實現復雜，理解難度大
計數存在一定的誤差，Redis官方公布的誤差率在0.81%左右
通過設置輔助計算因子能夠降低誤差，輔助因子要根據不同的場景設置
能夠使用極少的內存來統計巨量的數據，Redis的實現中統計2^64個數據最大占用空間為16384*6/8/1024 = 12K

HLL算法原理

伯努利試驗

要理解該算法，首先要從伯努利試驗開始，伯努利試驗的基本含義：

伯努利試驗（Bernoulli trial，或譯為白努利試驗）是只有兩種可能結果（“成功”或“失敗”）的單次隨機試驗。

拋硬幣就是一個典型的場景，硬幣擁有正反兩面，一次地上拋至落下，最終出現正反面的概率都是50%。假設一直拋一枚硬幣直到出現正面為止，只要第一次出現正面我們就記錄為一次試驗。如果經過n伯努利試驗（即出現了n次正面），假設每次試驗的投擲次數為k，第一次試驗的投擲次數為k1，類推得出第n次試驗的投擲次數為kn，那么這 k1 ~ kn 中必然會有一個最大的拋擲次數，我們記為k_max。

由此試驗我們可以得到兩個結論：

n次伯努利試驗的投擲次數都不大于k_max。
n次伯努利試驗的投擲次數至少有一次等于k_max。

結合極大似然估算的方法，發現n與k_max存在估算關聯：n=2^kmax，套用這個公式會發現，當實驗次數較小時該算法的誤差會非常大，我們來舉一個簡單的例子：

第1次實驗：拋擲1次出現正面，則k=1，n=1

第2次實驗：拋擲3次出現正面，則k=3，n=2

第3次實驗：拋擲5次出現正面，則k=5，n=3

第n次實驗：拋擲k次出現正面，則n=2^k

假設n組實驗中k_max=5，最終的實驗結果估算n=2^5，如果n很小時，等式很明顯不成立

如何減小估算誤差呢？通常的做法是增加實驗次數，但是只做一輪的話誤差率仍然不夠小。那如果我們做多個輪次然后求平均呢？

LogLog

上述多輪次求平均的算法就是LogLog算法的實現了。

HyerLogLog

HyperLogLog算法在LogLog的基礎上做了進一步的優化，為了解決k_max的出現個別大數值導致平均值波動過大的影響，HLL算法將k_max平均替換為調和平均值，具體計算方式變更為：k_max調和平均=m/（1/k_max1 + 1/k_max2 + ... + 1/k_maxn）。

HLL公式

一個可視化的HLL算法演示地址：
http://content.research.neustar.biz/blog/hll.html

Redis中的實現

上面的內容我們對伯努利試驗到HLL算法的演化過程做了一個簡單的推演，那么這種算法如何落地實現呢？如何用更少的內存，更加高性能的方式實現呢？

下面我們來看一個實際的場景：

拼刀刀有一個活動頁面，我們需要統計每天該活動頁的UV（一個用戶的多次點擊只算一次）。

我們結合上面的HLL算法很容易得出：

活動頁的UV = 預測結果n；
某個用戶點擊活動頁 = 一次試驗，m個用戶點擊就是，m輪次；
輸入條件是用戶id，那么我們可以使用用戶id計得出試驗輪次序號與每個輪次的k_max；

用戶id如何得到輪次m與每個輪次的k_max呢？我們可以把用戶id 通過hash函數計算得到一個bit串，可以使用bit串的低n位來表示實驗輪次，用剩下的bit位表示每個輪次的k_max。如圖：

用戶id計算得到的bit串結構

在Redis中采用MurmurHash64A函數計算出64位的bit串來計算輪次序號與每個輪次的k_max，其中低14位用于計算輪次序號，高50位用于計算輪次的k_max。Redis實現采用了16384輪次（剛好2^14+1次，加1是因為有0），高50位從低位到高位最先出現1的索引位置位為k_max，那么最極端的情況就是第50位出現1，50使用二進制存儲最大需要6個二進制位，因此Redis每個輪次的k_max采用了6個bit位存儲。因此得到了Redis統計2^64個數使用的空間是：16384*6/8/1024=12k。

說明：如果出現桶沖突，即低14位相同時，高50位保留k_max最大的。

數據結構

下面我們看一下HLL在Redis中的實際存儲結構，如下圖：

HLL存儲結構

Redis的HLL實現有兩種編碼，一種是稀疏編碼，一種是密集編碼。
稀疏編碼：在HLL初期只存入了少量的數據時，存在大量的空桶，如果這個時候仍然用16384個桶來存儲會造成很大的空間浪費，因此會利用壓縮空間來存儲。
密集編碼：當桶的數量達到一定數量時，會進行一次編碼轉換，轉換后會形成一個完整的結構，即16384個桶，每個桶占6bit。

HLL編碼

在實際的算法實現中要考慮到空間利用率問題，因此Redis設計了不同的編碼來存儲不同階段的統計數據，以此來提升空間利用率，有以下幾種編碼：

密集編碼：

HLL密集編碼

密集編碼每個桶需要了6bit，那么必然存在跨字節的情況，Redis采用了比較巧妙的方式去定位桶，具體實現如下：

#define HLL_BITS 6 /* Enough to count up to 63 leading zeroes. */
// 二進制為：00111111
#define HLL_REGISTER_MAX ((1<<HLL_BITS)-1)

/* Store the value of the register at position 'regnum' into variable 'target'.
* 'p' is an array of unsigned bytes. */
// 將位置為'regnum'的值存入變量'target'，'p'是一個無符號字節的數組
// 獲取指定桶
#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { 
    uint8_t *_p = (uint8_t*) p; 
	// 計算桶所屬哪一個字節
    unsign計算ed long _byte = regnum*HLL_BITS/8; 
	// 計算桶起始bit的所屬位置
    unsigned long _fb = regnum*HLL_BITS&7; 
	// 處理跨字節
    unsigned long _fb8 = 8 - _fb; 
	// 獲取第一個字節中的位
    unsigned long b0 = _p[_byte]; 
	// 獲取第二個字節中的位
    unsigned long b1 = _p[_byte+1]; 
	// 計算跨字節合并后的序列(第一個字節的高_fb位與第二個字節的低_fb8位合并，可結合上面圖看)
    target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; 
} while(0)

/* Set the value of the register at position 'regnum' to 'val'.
* 'p' is an array of unsigned bytes. */
 // 設置指定桶
#define HLL_DENSE_SET_REGISTER(p,regnum,val) do { 
    uint8_t *_p = (uint8_t*) p; 
    unsigned long _byte = regnum*HLL_BITS/8; 
    unsigned long _fb = regnum*HLL_BITS&7; 
    unsigned long _fb8 = 8 - _fb; 
    unsigned long _v = val; 
    // 設置跨字節的第一個字節的低_fb位
    _p[_byte] &= ~(HLL_REGISTER_MAX << _fb); 
    _p[_byte] |= _v << _fb; 
	// 設置跨字節的第二個字節的高_fb8位
    _p[_byte+1] &= ~(HLL_REGISTER_MAX >> _fb8); 
    _p[_byte+1] |= _v >> _fb8; 
} while(0)

稀疏編碼：

稀疏編碼-XZERO

稀疏編碼-ZERO+VAL

XZERO編碼：操作碼由兩個字節"01xxxxxx yyyyyyyy"模式表示，其中"xxxxxx yyyyyyyy"表示由1到16384(111111 11111111+1)個連續分組為空， "xxxxxx"為XZERO的高位，"yyyyyyyy"為低位，該編碼是HLL的初始結構，大小剛好為兩個字節（uint8_t registers[1]）。
ZERO編碼：操作碼用一個字節"00xxxxxx"模式表示，6位"xxxxxx"表示有1到64(111111+1)個連續分組為空，此編碼可以有效壓縮空桶。
VAL編碼：操作碼用一個字節"1xxxxxyy"模式表示，"xxxxx"表示投擲次數，最大次數為32（11111+1），這也是為什么大于32時會發生編碼轉換的原因，"yy"表示連續（n+1）個分組，此操作碼可以表示1到32之間的值，重復1到4次。

HLL相關命令

PFADD：將一個輸入參數存入到HyperLogLog結構中，如果輸入引起近似基數變化，該命令返回1，否則返回0。

redis> PFADD hll a b c d e f g

(integer) 1

redis> PFCOUNT hll

(integer) 7

PFCOUNT：返回指定key的近似基數值，支持多個key的查詢，當多key查詢時，會將多個key的HLL結構合并為一個臨時HLL，然后返回這個合并結果的基數值。

redis> PFADD hll foo bar zap

(integer) 1

redis> PFADD hll zap zap zap

(integer) 0

redis> PFADD hll foo bar

(integer) 0

redis> PFCOUNT hll

(integer) 3

redis> PFADD some-other-hll 1 2 3

(integer) 1

redis> PFCOUNT hll some-other-hll

(integer) 6

PFMERGE：將多個HLL結構合并為一個HHL結構。

redis> PFADD hll1 foo bar zap a

(integer) 1

redis> PFADD hll2 a b c foo

(integer) 1

redis> PFMERGE hll3 hll1 hll2

OK

redis> PFCOUNT hll3

(integer) 6