學透 Redis HyperLogLog，看這篇就夠了
在移動互聯網的業務場景中，數據量很大，系統需要保存這樣的信息：一個 key 關聯了一個數據集合，同時對這個數據集合做統計做一個報表給運營人員看。
比如。
- 統計一個 APP 的日活、月活數。
- 統計一個頁面的每天被多少個不同賬戶訪問量（Unique Visitor，UV）。
- 統計用戶每天搜索不同詞條的個數。
- 統計注冊 IP 數。
通常情況下，系統面臨的用戶數量以及訪問量都是巨大的，比如百萬、千萬級別的用戶數量，或者千萬級別、甚至億級別的訪問信息，咋辦呢？
?
Redis：“這些就是典型的基數統計應用場景，基數統計：統計一個集合中不重復元素，這被稱為基數。”
1、是什么
HyperLogLog 是一種概率數據結構，用于估計集合的基數。每個 HyperLogLog 最多只需要花費 12KB 內存，在標準誤差 0.81%的前提下，就可以計算 2 的 64 次方個元素的基數。
HyperLogLog 的優點在于它所需的內存并不會因為集合的大小而改變，無論集合包含的元素有多少個，HyperLogLog 進行計算所需的內存總是固定的，并且是非常少的。
主要特點如下。
- 高效的內存使用：HyperLogLog 的內存消耗是固定的，與集合中的元素數量無關。這使得它特別適用于處理大規模數據集，因為它不需要存儲每個不同的元素，只需要存儲估計基數所需的信息。
- 概率估計：HyperLogLog 提供的結果是概率性的，而不是精確的基數計數。它通過哈希函數將輸入元素映射到位圖中的某些位置，并基于位圖的統計信息來估計基數。由于這是一種概率性方法，因此可能存在一定的誤差，但通常在實際應用中，這個誤差是可接受的。
- 高速計算：HyperLogLog 可以在常量時間內計算估計的基數，無論集合的大小如何。這意味著它的性能非常好，不會受到集合大小的影響。
2、修煉心法
基本原理
HyperLogLog 是一種概率數據結構，它使用概率算法來統計集合的近似基數。而它算法的最本源則是伯努利過程。
伯努利過程就是一個拋硬幣實驗的過程。拋一枚正常硬幣，落地可能是正面，也可能是反面，二者的概率都是 1/2 。
伯努利過程就是一直拋硬幣，直到落地時出現正面位置，并記錄下拋擲次數k。
比如說，拋一次硬幣就出現正面了，此時 k 為 1; 第一次拋硬幣是反面，則繼續拋，直到第三次才出現正面，此時 k 為 3。
對于 n 次伯努利過程，我們會得到 n 個出現正面的投擲次數值 k1, k2 ... kn, 其中這里的最大值是 k_max。
根據一頓數學推導，我們可以得出一個結論：2^{k_ max} 來作為 n 的估計值。
也就是說你可以根據最大投擲次數近似的推算出進行了幾次伯努利過程。
所以 HyperLogLog 的基本思想是利用集合中數字的比特串第一個 1 出現位置的最大值來預估整體基數，但是這種預估方法存在較大誤差，為了改善誤差情況，HyperLogLog 中引入分桶平均的概念，計算 m 個桶的調和平均值。
Redis 內部使用字符串位圖來存儲 HyperLogLog 所有桶的計數值，一共分了 2^14 個桶，也就是 16384 個桶。每個桶中是一個 6 bit 的數組。
這段代碼描述了 Redis HyperLogLog 數據結構的頭部定義（hyperLogLog.c 中的 hllhdr 結構體）。以下是關于這個數據結構的各個字段的解釋。
struct hllhdr {
char magic[4];
uint8_t encoding;
uint8_t notused[3];
uint8_t card[8];
uint8_t registers[];
};- magic[4]：這個字段是一個 4 字節的字符數組，用來表示數據結構的標識符。在 HyperLogLog 中，它的值始終為"HYLL"，用來標識這是一個 HyperLogLog 數據結構。
- encoding：這是一個 1 字節的字段，用來表示 HyperLogLog 的編碼方式。它可以取兩個值之一：
- HLL_DENSE：表示使用稠密表示方式。
- HLL_SPARSE：表示使用稀疏表示方式。
- notused[3]：這是一個 3 字節的字段，目前保留用于未來的擴展，要求這些字節的值必須為零。
- card[8]：這是一個 8 字節的字段，用來存儲緩存的基數（基數估計的值）。
- egisters[]：這個字段是一個可變長度的字節數組，用來存儲 HyperLogLog 的數據。
Redis 對 HyperLogLog 的存儲進行了優化，在計數比較小的時候，存儲空間采用系數矩陣，占用空間很小。
只有在計數很大，稀疏矩陣占用的空間超過了閾值才會轉變成稠密矩陣，占用 12KB 空間。
3、出招實戰：網頁訪問量統計
在移動互聯網的業務場景中，數據量很大，系統需要保存這樣的信息：一個 key 關聯了一個數據集合，同時對這個數據集合做統計做一個報表給運營人員看。
比如。
- 統計一個 APP 的日活、月活數。
- 統計一個頁面的每天被多少個不同賬戶訪問量（Unique Visitor，UV）。
- 統計用戶每天搜索不同詞條的個數。
- 統計注冊 IP 數。
通常情況下，系統面臨的用戶數量以及訪問量都是巨大的，比如百萬、千萬級別的用戶數量，或者千萬級別、甚至億級別的訪問信息，咋辦呢？
使用 Set 實現
一個用戶一天內多次訪問一個網站只能算作一次，所以很容易就想到通過 Redis 的 Set 集合來實現。
比如微信昵稱叫 “Chaya” 的小姐姐訪問【愛一個人總是要掉眼淚的風險】這篇文章時，我把這個微信昵稱 “Chaya” 存到 Set 集合中。
SADD 愛一個人總是要掉眼淚的風險:uv 碼哥 Chaya 趙小因 Chaya
(integer) 3“Chaya” 多次訪問這篇文章， Set 的去重特性保證集合中只有一個記錄。接著，通過 SCARD 命令，統計頁面 UV。指令返回這個集合的元素個數（也就是微信昵稱個數）。
SCARD 愛一個人總是要掉眼淚的風險:uv
(integer) 3使用 HyperLogLog 實現
?
Chaya：“Set 集合雖好，如果文章非常火爆達到千萬級別，一個 Set 集合就保存了千萬個用戶的 ID，頁面多了消耗的內存也太大了。”
不要怕，只要思想不滑坡，辦法總比困難多。這些就是典型的基數統計應用場景，基數統計：統計一個集合中不重復元素的個數。
HyperLogLog 的優點在于它所需的內存并不會因為集合的大小而改變，無論集合包含的元素有多少個，HyperLogLog 進行計算所需的內存總是固定的，并且是非常少的。
每個 HyperLogLog 最多只需要花費 12KB 內存，在標準誤差 0.81%的前提下，就可以計算 2 的 64 次方個元素的基數。
HyperLogLog 使用太簡單了。PFADD、PFCOUNT、PFMERGE三個指令打天下。
PFADD
每訪問一次頁面，調用 PFADD 指令 將這個用戶 ID 添加到 HyperLogLog 中。如下 一共有三個用戶訪問了這頁面，其中 Chaya 訪問了兩次，但只算一次。
PFADD 愛一個人總是要掉眼淚的風險:uv 碼哥 Chaya 趙小因 Chaya如果執行命令后 HyperLogLog 估計的近似基數發生變化，PFADD則返回 1，否則返回 0。如果指定的鍵不存在，該命令會自動創建一個空的 HyperLogLog 結構。
pfadd 命令并不會一次性分配 12k 內存，而是隨著基數的增加而逐漸增加內存分配。
PFCOUNT
接下來，通過 PFCOUNT 指令獲取文章【愛一個人總是要掉眼淚的風險】的 UV 值，可以看到返回值是 3 ，符合預期。
> PFCOUNT 愛一個人總是要掉眼淚的風險:uv
3PFMERGE 合并統計
?
Chaya：“還有一個變態需求，對文章進行標簽分類，運營說要把都是情感文章標簽的幾個頁面數據合并統計。”
其中頁面的 UV 訪問量也需要合并，那這個時候 PFMERGE 就可以派上用場了，也就是同樣的用戶訪問這兩個頁面則只算做一次。
如下指令，把愛一個人總是要掉眼淚的風險:uv和愛情是幸福和不委屈:uv 兩個 HyperLogLog 集合數據合并到情感分類文章:uv這個集合中。
PFADD 愛情是幸福和不委屈:uv Chaya 趙小因 幸運草
# 合并兩個頁面 UV
PFMERGE 情感分類文章:uv 愛一個人總是要掉眼淚的風險:uv 愛情是幸福和不委屈:uv接著，執行 PFCOUNT 情感分類文章:uv 統計合并后的數據。
> PFCOUNT 情感分類文章:uv
4將多個 HyperLogLog 合并（merge）為一個 HyperLogLog ， 合并后的 HyperLogLog 的基數接近于所有輸入 HyperLogLog 的可見集合（observed set）的并集。
4、Redisson 實戰
開門見山，Spring Boot 與 Redisson 集成詳見前面篇章，主要有四個方法。
- add、addAll，閱讀文章調用該方法將數據存入 HyperLogLog 中。
- count，統計基數。
- merge，合并多個 HyperLogLog 為一個。
@Service
public class HyperLogLogService {
@Autowired
private RedissonClient redissonClient;
/**
* 將數據添加到 HyperLogLog
*
* @param logName
* @param item
* @param <T>
*/
public <T> void add(String logName, T item) {
RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
hyperLogLog.add(item);
}
/**
* 將集合數據添加到 HyperLogLog
* @param logName
* @param items
* @param <T>
*/
public <T> void addAll(String logName, List<T> items) {
RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
hyperLogLog.addAll(items);
}
/**
* 將 otherLogNames 的 log 合并到 logName
*
* @param logName 當前 log
* @param otherLogNames 需要合并到當前 log 的其他 logs
* @param <T>
*/
public <T> void merge(String logName, String... otherLogNames) {
RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
hyperLogLog.mergeWith(otherLogNames);
}
/**
* 統計基數
*
* @param logName 需要統計的 logName
* @param <T>
* @return
*/
public <T> long count(String logName) {
RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
return hyperLogLog.count();
}
}
