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

• 2022 年 11 月 11 日
• 筆記
• HyperLogLog, Redis, 架構與思維, 快取, 高性能

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 的元素數量總和。
當然這種做法也存在兩個問題：

1. 當統計的數據量變大時,相應的存儲記憶體也會線性增長
2. 當集合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 演算法原理參考這兩篇，寫的很清晰：
//zhuanlan.zhihu.com/p/77289303
//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。