Redis系列1：深刻理解高效能Redis的本質
 Redis系列2：資料持久化提高可用性
 Redis系列3：高可用之主從架構
 Redis系列4：高可用之Sentinel(哨兵模式）
Redis系列5：深入分析Cluster 叢集模式
 追求效能極致：Redis6.0的多執行緒模型
 追求效能極致：使用者端快取帶來的革命
 Redis系列8：Bitmap實現億萬級資料計算
 Redis系列9：Geo 型別賦能億級地圖位置計算

1 前言

我們來回顧下在這個系列的第一篇深刻理解高效能Redis的本質中介紹過Redis的幾種基本資料結構，
它服務於各種不同的業務場景而設計的，比如：

動態字串(REDIS_STRING)：整數(REDIS_ENCODING_INT)、字串(REDIS_ENCODING_RAW)
雙端列表(REDIS_ENCODING_LINKEDLIST)
壓縮列表(REDIS_ENCODING_ZIPLIST)
跳躍表(REDIS_ENCODING_SKIPLIST)
雜湊表(REDIS_HASH)
整數集合(REDIS_ENCODING_INTSET)

除了這些常見資料型別，還有一些不常用的資料型別，如 BitMap、Geo、HyperLogLog 等等，他們在各自的方向為不同的型別的資料統計給出解決方案。

點陣圖（BitMap）計算：可以應用於任何巨量資料場景下的二值計算，比如是否登入、是否線上、是否簽到、使用者性別狀態、IP黑名單、是否VIP使用者統計等等場景。
Geo型別：記錄地理空間資訊，如地理座標儲存、位置計算、距離計算等能力，普遍運用在地圖業務中的各種場景。

這一篇我們來介紹下HyperLogLog，HyperLogLog 主要用於Redis基數的統計，比如IP統計，使用者存取量，頁面存取量。

2 關於HyperLogLog

HyperLogLog 主要用於Redis 的基數統計，它的資料結構專門設計用來做資料合併和計算，並能節省大量的空間。
基數計數( cardinality counting) 通常用來統計一個集合中不重複的元素個數 , 例如統計某個網站的UV、PV或者網站搜尋的的關鍵詞數量。
在各種應用領域基數統計被廣泛應用，如資料分析、網路監控指標、儲存效能優化等。
簡單來說，基數計數就是記錄集合中所有不重複的元素S_u ,當新增元素X_a時,判斷S_u中是否包含,不包含則將其加入S_u,包含則不加入,計數值就是S_u 的元素數量總和。
當然這種做法也存在兩個問題：

當統計的資料量變大時,相應的儲存記憶體也會線性增長
當集合S_u 變大,判斷其是否包含新加入元素的成本變大

2.1 實際應用場景

很多計數類場景，比如每日註冊 IP 數、每日存取 IP 數、頁面實時存取數 PV、存取使用者數 UV等。
因為主要的目標高效、巨量地進行計數，所以對儲存的資料的內容並不關係。也就是說它只能用於統計數量，沒辦法知道具體的統計物件的內容。

統計單日一個頁面的存取量(PV)，單次存取就算一次。
統計單日一個頁面的使用者存取量(UV)，即按照使用者為維度計算，單個使用者一天內多次存取也只算一次。
多個key的合併統計，某個入口網站的所有模組的PV聚合統計就是整個網站的總PV。

2.2 高效和海量特性

如果我們使用普通集合，也能夠實現對巨量資料的儲存和統計麼，但是儲存量會大很多，效能也比較差。
以百度搜尋為例，如果要做百度指數的計算，針對來訪IP進行統計。那麼如果每天有 1000 萬 IP，一個 IP 佔位 15 位元組，那麼 1000 萬個 IP 就是 143M。

10,000,000 * 15 /(1024 * 1024)  = 143.05 M

如果使用 HyperLogLog ，那麼在 Redis 中每個鍵佔用的內容都是 12K，理論上能夠儲存 2⁶⁴ 個值，即18446744073709551616，這個數是巨量，Java中long型別也只能計算到 2⁶² 。
無論儲存何值，它一個基於基數估算的演演算法HyperLogLog Counting（簡稱HLLC），使用少量固定的記憶體去儲存並識別集合中的唯一元素。
HLLC採用了分桶平均的思想來消減誤差，在Redis中, 有16384個桶。而HyperLogLog的標準偏差公式是1.04 / sqrt(m)，m 為桶的個數。所以

1.04 / sqrt(16384) = 1.04 / 128 = 0.008125

所以這個計數的估算，是一個帶有 0.81% 標準偏差的近似值。

HyperLogLog 演演算法原理參考這兩篇，寫的很清晰：
https://zhuanlan.zhihu.com/p/77289303
http://www.javashuo.com/article/p-mmwxrmjm-ga.html

3 HyperLogLog所支援的能力

HyperLogLog資料結構的命令有三個：PFADD、PFCOUNT、PFMERGE

3.1 PFADD 新增計數

Redis Pfadd 命令將所有元素新增到 HyperLogLog 資料結構中。

語法如下：

redis > PFADD key element [element ...]

下面舉例了網站統計模組新增IP的兩種情況

/* 對存取百度網站(key=baidu:ip_address)的IP進行新增 */
redis> PFADD baidu:ip_address "192.168.0.1" "192.168.0.2" "192.168.0.3"
(integer) 1
 
/* 如果IP已經存在，則進行忽略，不對估計數量進行更新 */
redis> PFADD baidu:ip_address "192.168.0.3"  
(integer) 0  # IP已經存在

3.2 PFCOUNT 統計數量

Redis Pfcount 命令返回給定 HyperLogLog 的基數的估算值。
語法如下：

redis > PFCOUNT key [key ...]

下面估算了存取IP的基數的值，返回 1034546 。

redis> PFCOUNT baidu:ip_address
 
(integer) 1034546

3.3 PFMERGE 合併統計

Redis PFMERGE 命令將多個 HyperLogLog 合併為一個 HyperLogLog ，合併後的 HyperLogLog 的基數估算值是對給定 HyperLogLog 進行並集計算得出的。
所以有重複的會被統計成一條資料。
合併得出的 HyperLogLog 會被儲存在 destkey 鍵裡面，如果該鍵並不存在，那麼命令在執行之前，會先為該鍵建立一個空的 HyperLogLog 。
語法如下：

redis > PFMERGE destkey sourcekey [sourcekey ...]

下面演示了合併和統計的過程：

/* 統計百度 baidu:ip_address 存取IP */
redis> PFADD baidu:ip_address "192.168.0.1" "192.168.0.2" "192.168.0.3"
(integer) 1
 
 /* 統計淘寶 taobao:ip_address 存取IP */
redis> PFADD taobao:ip_address "192.168.0.3" "192.168.0.4" "192.168.0.5"
(integer) 1
 
/* 合併且去重之後放在 total:ip_address  */
redis> PFMERGE total:ip_address baidu:ip_address taobao:ip_address
OK
 
/* 結果為5 */
redis> PFCOUNT total:ip_address
(integer) 5

4 總結

基數計數是用於統計一個集合中不重複的元素個數，好比平常需求場景有，統計頁面的UV或者統計線上的使用者數、註冊IP數等。HyperLogLog 主要基於Redis能力下的基數統計。HyperLogLog的主要使用場景包括：

統計單日一個頁面的存取量(PV)，單次存取就算一次。
統計單日一個頁面的使用者存取量(UV)，即按照使用者為維度計算，單個使用者一天內多次存取也只算一次。
多個key的合併統計，某個入口網站的所有模組的PV聚合統計就是整個網站的總PV。

Redis系列10：HyperLogLog實現海量資料基數統計