Redis HyperLogLog 是什么？這些場景使用它，讓我槍出如龍，一笑破蒼穹
在移動互聯(lián)網(wǎng)的業(yè)務(wù)場景中，數(shù)據(jù)量很大，我們需要保存這樣的信息：一個(gè) key 關(guān)聯(lián)了一個(gè)數(shù)據(jù)集合，同時(shí)對這個(gè)數(shù)據(jù)集合做統(tǒng)計(jì)。
統(tǒng)計(jì)一個(gè) APP的日活、月活數(shù)；統(tǒng)計(jì)一個(gè)頁面的每天被多少個(gè)不同賬戶訪問量（Unique Visitor，UV））； 統(tǒng)計(jì)用戶每天搜索不同詞條的個(gè)數(shù)； 統(tǒng)計(jì)注冊 IP 數(shù)。
通常情況下，我們面臨的用戶數(shù)量以及訪問量都是巨大的，比如百萬、千萬級別的用戶數(shù)量，或者千萬級別、甚至億級別的訪問信息。
今天「碼哥」分別使用不同的數(shù)據(jù)類型來實(shí)現(xiàn)統(tǒng)計(jì)一個(gè)頁面的每天被多少個(gè)不同賬戶訪問量這個(gè)功能，循序漸進(jìn)的引出 HyperLogLog的原理與 Java 中整合 Redission 實(shí)戰(zhàn)。
告訴大家一個(gè)技巧，Redis 官方網(wǎng)站現(xiàn)在能在線運(yùn)行 Redis 指令了：https://redis.io/。如圖：
使用 Set 實(shí)現(xiàn)
一個(gè)用戶一天內(nèi)多次訪問一個(gè)網(wǎng)站只能算作一次，所以很容易就想到通過 Redis 的 Set 集合來實(shí)現(xiàn)。
比如微信 ID 為「肖菜雞」訪問 「Redis 為什么這么快」這篇文章時(shí)，我們把這個(gè)信息存到 Set 中。
SADD?Redis為什么這么快:uv?肖菜雞?謝霸哥?肖菜雞
(integer)?1
「肖菜雞」多次訪問「Redis 為什么這么快」頁面，Set 的去重功能保證不會重復(fù)記錄同一個(gè)「微信 ID」。
通過 SCARD 命令，統(tǒng)計(jì)「Redis 為什么這么快」頁面 UV。指令返回一個(gè)集合的元素個(gè)數(shù)（也就是用戶 ID）。
SCARD?Redis為什么這么快:uv
(integer)?2
使用 Hash 實(shí)現(xiàn)
碼老濕，還可以利用 Hash 類型實(shí)現(xiàn)，將用戶 ID 作為 Hash 集合的 key，訪問頁面則執(zhí)行 HSET 命令將 value 設(shè)置成 1。
即使「肖菜雞」重復(fù)訪問頁面，重復(fù)執(zhí)行命令，也只會把 key 等于「肖菜雞」的 value 設(shè)置成 1。
最后，利用 HLEN 命令統(tǒng)計(jì) Hash 集合中的元素個(gè)數(shù)就是 UV。
如下：
HSET?Redis為什么這么快?肖菜雞?1
//?統(tǒng)計(jì)?UV
HLEN?Redis為什么這么快
使用 Bitmap 實(shí)現(xiàn)
Bitmap 的底層數(shù)據(jù)結(jié)構(gòu)用的是 String 類型的 SDS 數(shù)據(jù)結(jié)構(gòu)來保存位數(shù)組，Redis 把每個(gè)字節(jié)數(shù)組的 8 個(gè) bit 位利用起來，每個(gè) bit 位 表示一個(gè)元素的二值狀態(tài)（不是 0 就是 1）。
Bitmap 提供了 GETBIT、SETBIT 操作，通過一個(gè)偏移值 offset 對 bit 數(shù)組的 offset 位置的 bit 位進(jìn)行讀寫操作，需要注意的是 offset 從 0 開始。
可以將 Bitmap 看成是一個(gè) bit 為單位的數(shù)組，數(shù)組的每個(gè)單元只能存儲 0 或者 1，數(shù)組的下標(biāo)在 Bitmap 中叫做 offset 偏移量。
為了直觀展示，我們可以理解成 buf 數(shù)組的每個(gè)字節(jié)用一行表示，每一行有 8 個(gè) bit 位，8 個(gè)格子分別表示這個(gè)字節(jié)中的 8 個(gè) bit 位，如下圖所示：
8 個(gè) bit 組成一個(gè) Byte，所以 Bitmap 會極大地節(jié)省存儲空間。 這就是 Bitmap 的優(yōu)勢。
如何使用 Bitmap 來統(tǒng)計(jì)頁面的獨(dú)立用戶訪問量呢？
Bitmap 提供了 SETBIT 和 BITCOUNT 操作，前者通過一個(gè)偏移值 offset 對 bit 數(shù)組的 offset 位置的 bit 位進(jìn)行寫操作，需要注意的是 offset 從 0 開始。
后者統(tǒng)計(jì)給定指定的 bit 數(shù)組中，值 = 1 的 bit 位的數(shù)量。
需要注意的事，我們需要把「微信 ID」轉(zhuǎn)換成數(shù)字，因?yàn)?code style="font-size: 14px;border-radius: 4px;font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(155, 110, 35);background-color: rgb(255, 245, 227);padding: 3px;margin: 3px;">offset 是下標(biāo)。
假設(shè)我們將「肖菜雞」轉(zhuǎn)換成編碼6。
第一步，執(zhí)行下面指令表示「肖菜雞」的編碼為 6 并 訪問「巧用 Redis 數(shù)據(jù)類型實(shí)現(xiàn)億級數(shù)據(jù)統(tǒng)計(jì)」這篇文章。
SETBIT?巧用Redis數(shù)據(jù)類型實(shí)現(xiàn)億級數(shù)據(jù)統(tǒng)計(jì)?6?1
第二步，統(tǒng)計(jì)頁面訪問次數(shù)，使用 BITCOUNT 指令。該指令用于統(tǒng)計(jì)給定的 bit 數(shù)組中，值 = 1 的 bit 位的數(shù)量。
BITCOUNT?巧用Redis數(shù)據(jù)類型實(shí)現(xiàn)億級數(shù)據(jù)統(tǒng)計(jì)
HyperLogLog 王者
Set 雖好，如果文章非?；鸨_(dá)到千萬級別，一個(gè) Set 就保存了千萬個(gè)用戶的 ID，頁面多了消耗的內(nèi)存也太大了。
同理，Hash 數(shù)據(jù)類型也是如此。
至于 Bitmap，它更適合于「二值狀態(tài)統(tǒng)計(jì)」的使用場景，統(tǒng)計(jì)精度高，雖然內(nèi)存占用要比
HashMap少，但是對于大量數(shù)據(jù)還是會占用較大內(nèi)存。咋辦呢？
這些就是典型的「基數(shù)統(tǒng)計(jì)」應(yīng)用場景，基數(shù)統(tǒng)計(jì)：統(tǒng)計(jì)一個(gè)集合中不重復(fù)元素的個(gè)數(shù)。
HyperLogLog 的優(yōu)點(diǎn)在于它所需的內(nèi)存并不會因?yàn)榧系拇笮《淖儯瑹o論集合包含的元素有多少個(gè)，HyperLogLog 進(jìn)行計(jì)算所需的內(nèi)存總是固定的，并且是非常少的。
每個(gè) HyperLogLog 最多只需要花費(fèi) 12KB 內(nèi)存，在標(biāo)準(zhǔn)誤差 0.81%的前提下，就可以計(jì)算 2 的 64 次方個(gè)元素的基數(shù)。
Redis 實(shí)戰(zhàn)
HyperLogLog 使用太簡單了。PFADD、PFCOUNT、PFMERGE三個(gè)指令打天下。
PFADD
將訪問頁面的每個(gè)用戶 ID 添加到 HyperLogLog 中。
PFADD Redis主從同步原理:uv userID1 userID 2?useID3
PFCOUNT
利用 PFCOUNT 獲取 「Redis 主從同步原理」文章的 UV 值。
PFCOUNT Redis主從同步原理:uv
PFMERGE 使用場景
HyperLogLog?除了上面的?PFADD?和?PFCOIUNT?外，還提供了?PFMERGE
語法
PFMERGE?destkey?sourcekey?[sourcekey?...]
比如在網(wǎng)站中我們有兩個(gè)內(nèi)容差不多的頁面，運(yùn)營說需要這兩個(gè)頁面的數(shù)據(jù)進(jìn)行合并。
其中頁面的 UV 訪問量也需要合并，那這個(gè)時(shí)候 PFMERGE 就可以派上用場了，也就是同樣的用戶訪問這兩個(gè)頁面則只算做一次。
如下所示：Redis、MySQL 兩個(gè) HyperLogLog 集合分別保存了兩個(gè)頁面用戶訪問數(shù)據(jù)。
PFADD?Redis數(shù)據(jù)?user1?user2?user3
PFADD?MySQL數(shù)據(jù)?user1?user2?user4
PFMERGE?數(shù)據(jù)庫?Redis數(shù)據(jù)?MySQL數(shù)據(jù)
PFCOUNT?數(shù)據(jù)庫?//?返回值?=?4
將多個(gè) HyperLogLog 合并（merge）為一個(gè) HyperLogLog ， 合并后的 HyperLogLog 的基數(shù)接近于所有輸入 HyperLogLog 的可見集合（observed set）的并集。
user1、user2 都訪問了 Redis 和 MySQL，只算訪問了一次。
Redission 實(shí)戰(zhàn)
詳細(xì)源碼「碼哥」上傳到 GitHub 了：https://github.com/MageByte-Zero/springboot-parent-pom.git
pom 依賴
<dependency>
??<groupId>org.redissongroupId>
??<artifactId>redisson-spring-boot-starterartifactId>
??<version>3.16.7version>
dependency>
添加數(shù)據(jù)到 Log
//?添加單個(gè)元素
public??void?add(String?logName,?T?item)?{
??RHyperLogLog?hyperLogLog?=?redissonClient.getHyperLogLog(logName);
??hyperLogLog.add(item);
}
//?將集合數(shù)據(jù)添加到?HyperLogLog
public??void?addAll(String?logName,?List?items) ?{
??RHyperLogLog?hyperLogLog?=?redissonClient.getHyperLogLog(logName);
??hyperLogLog.addAll(items);
}
合并
/**
?*?將?otherLogNames?的?log?合并到?logName
?*
?*?@param?logName???????當(dāng)前?log
?*?@param?otherLogNames?需要合并到當(dāng)前?log?的其他?logs
?*?@param?
?*/
public??void?merge(String?logName,?String...?otherLogNames)?{
??RHyperLogLog?hyperLogLog?=?redissonClient.getHyperLogLog(logName);
??hyperLogLog.mergeWith(otherLogNames);
}
統(tǒng)計(jì)基數(shù)
public??long?count(String?logName)?{
??RHyperLogLog?hyperLogLog?=?redissonClient.getHyperLogLog(logName);
??return?hyperLogLog.count();
}
單元測試
@Slf4j
@RunWith(SpringRunner.class)
@SpringBootTest(classes?=?RedissionApplication.class)
public?class?HyperLogLogTest?{
????@Autowired
????private?HyperLogLogService?hyperLogLogService;
????@Test
????public?void?testAdd()?{
????????String?logName?=?"碼哥字節(jié):Redis為什么這么快:uv";
????????String?item?=?"肖菜雞";
????????hyperLogLogService.add(logName,?item);
????????log.info("添加元素[{}]到 log [{}]?中。",?item,?logName);
????}
????@Test
????public?void?testCount()?{
????????String?logName?=?"碼哥字節(jié):Redis為什么這么快:uv";
????????long?count?=?hyperLogLogService.count(logName);
????????log.info("logName?=?{}?count?=?{}.",?logName,?count);
????}
????@Test
????public?void?testMerge()?{
????????ArrayList?items?=?new?ArrayList<>();
????????items.add("肖菜雞");
????????items.add("謝霸哥");
????????items.add("陳小白");
????????String?otherLogName?=?"碼哥字節(jié):Redis多線程模型原理與實(shí)戰(zhàn):uv";
????????hyperLogLogService.addAll(otherLogName,?items);
????????log.info("添加?{}?個(gè)元素到 log [{}]?中。",?items.size(),?otherLogName);
????????String?logName?=?"碼哥字節(jié):Redis為什么這么快:uv";
????????hyperLogLogService.merge(logName,?otherLogName);
????????log.info("將?{}?合并到?{}.",?otherLogName,?logName);
????????long?count?=?hyperLogLogService.count(logName);
????????log.info("合并后的?count?=?{}.",?count);
????}
}
基本原理
HyperLogLog 是一種概率數(shù)據(jù)結(jié)構(gòu)，它使用概率算法來統(tǒng)計(jì)集合的近似基數(shù)。而它算法的最本源則是伯努利過程。
伯努利過程就是一個(gè)拋硬幣實(shí)驗(yàn)的過程。拋一枚正常硬幣，落地可能是正面，也可能是反面，二者的概率都是 1/2 。
伯努利過程就是一直拋硬幣，直到落地時(shí)出現(xiàn)正面位置，并記錄下拋擲次數(shù)k。
比如說，拋一次硬幣就出現(xiàn)正面了，此時(shí) k 為 1; 第一次拋硬幣是反面，則繼續(xù)拋，直到第三次才出現(xiàn)正面，此時(shí) k 為 3。
對于 n 次伯努利過程，我們會得到 n 個(gè)出現(xiàn)正面的投擲次數(shù)值 k1, k2 ... kn, 其中這里的最大值是 k_max。
根據(jù)一頓數(shù)學(xué)推導(dǎo)，我們可以得出一個(gè)結(jié)論：2^{k_ max} 來作為 n 的估計(jì)值。
也就是說你可以根據(jù)最大投擲次數(shù)近似的推算出進(jìn)行了幾次伯努利過程。
所以 HyperLogLog 的基本思想是利用集合中數(shù)字的比特串第一個(gè) 1 出現(xiàn)位置的最大值來預(yù)估整體基數(shù)，但是這種預(yù)估方法存在較大誤差，為了改善誤差情況，HyperLogLog 中引入分桶平均的概念，計(jì)算 m 個(gè)桶的調(diào)和平均值。
Redis 中 HyperLogLog 一共分了 2^14 個(gè)桶，也就是 16384 個(gè)桶。每個(gè)桶中是一個(gè) 6 bit 的數(shù)組，如下圖所示。
關(guān)于 HyperLogLog 的原理過于復(fù)雜，如果想要了解的請移步：
https://www.zhihu.com/question/53416615 https://en.wikipedia.org/wiki/HyperLogLog 用戶日活月活怎么統(tǒng)計(jì) - Redis HyperLogLog 詳解
Redis 對 HyperLogLog 的存儲進(jìn)行了優(yōu)化，在計(jì)數(shù)比較小的時(shí)候，存儲空間采用系數(shù)矩陣，占用空間很小。
只有在計(jì)數(shù)很大，稀疏矩陣占用的空間超過了閾值才會轉(zhuǎn)變成稠密矩陣，占用 12KB 空間。
為何只需要 12 KB 呀？
HyperLogLog 實(shí)現(xiàn)中用到的是 16384 個(gè)桶，也就是 2^14，每個(gè)桶的 maxbits 需要 6 個(gè) bits 來存儲，最大可以表示 maxbits=63，于是總共占用內(nèi)存就是2^14 * 6 / 8 = 12k字節(jié)。
總結(jié)
分別使用了 Hash、Bitmap、HyperLogLog 來實(shí)現(xiàn)：
Hash：算法簡單，統(tǒng)計(jì)精度高，少量數(shù)據(jù)下使用，對于海量數(shù)據(jù)會占據(jù)大量內(nèi)存；Bitmap：位圖算法，適合用于「二值統(tǒng)計(jì)場景」，具體可參考我這篇文章，對于大量不同頁面數(shù)據(jù)統(tǒng)計(jì)還是會占用較大內(nèi)存。Set：利用去重特性實(shí)現(xiàn)，一個(gè) Set 就保存了千萬個(gè)用戶的 ID，頁面多了消耗的內(nèi)存也太大了。
在 Redis 里面，每個(gè) HyperLogLog 鍵只需要花費(fèi) 12 KB 內(nèi)存，就可以計(jì)算接近2^64 個(gè)不同元素的基數(shù)。
因?yàn)?HyperLogLog 只會根據(jù)輸入元素來計(jì)算基數(shù)，而不會儲存輸入元素本身，所以 HyperLogLog 不能像集合那樣，返回輸入的各個(gè)元素。
HyperLogLog是一種算法，并非Redis獨(dú)有目的是做基數(shù)統(tǒng)計(jì)，故不是集合，不會保存元數(shù)據(jù)，只記錄數(shù)量而不是數(shù)值 耗空間極小，支持輸入非常體積的數(shù)據(jù)量 核心是基數(shù)估算算法，主要表現(xiàn)為計(jì)算時(shí)內(nèi)存的使用和數(shù)據(jù)合并的處理。最終數(shù)值存在一定誤差 Redis中每個(gè)Hyperloglogkey 占用了 12K 的內(nèi)存用于標(biāo)記基數(shù)（官方文檔）pfadd命令并不會一次性分配 12k 內(nèi)存，而是隨著基數(shù)的增加而逐漸增加內(nèi)存分配；而 pfmerge 操作則會將 sourcekey 合并后存儲在 12k 大小的 key 中，由hyperloglog合并操作的原理（兩個(gè)Hyperloglog合并時(shí)需要單獨(dú)比較每個(gè)桶的值）可以很容易理解。誤差說明：基數(shù)估計(jì)的結(jié)果是一個(gè)帶有 0.81%標(biāo)準(zhǔn)錯(cuò)誤（standard error）的近似值。是可接受的范圍Redis對HyperLogLog的存儲進(jìn)行優(yōu)化，在計(jì)數(shù)比較小時(shí)，存儲空間采用稀疏矩陣存儲，空間占用很小，僅僅在計(jì)數(shù)慢慢變大，稀疏矩陣占用空間漸漸超過了閾值時(shí)才會一次性轉(zhuǎn)變成稠密矩陣，才會占用 12k 的空間
好文推薦
Redis 實(shí)戰(zhàn)：巧用數(shù)據(jù)類型實(shí)現(xiàn)億級數(shù)據(jù)統(tǒng)計(jì) Redis 布?。˙loom Filter）過濾器原理與實(shí)戰(zhàn) Redis 實(shí)戰(zhàn)：巧用 Bitmap 實(shí)現(xiàn)億級海量數(shù)據(jù)統(tǒng)計(jì) Redis 實(shí)戰(zhàn)：通過 Geo 類型實(shí)現(xiàn)附近的人邂逅女神 Redis 分布式鎖的正確實(shí)現(xiàn)原理演化歷程與 Redisson 實(shí)戰(zhàn)總結(jié)
參考資料
[1]:https://www.cnblogs.com/loveLands/articles/10987055.html
[2]:Redis 使用手冊
[3]:https://zhuanlan.zhihu.com/p/265309426