作者 | 就是碼哥呀

來源 | 碼哥字節(jié)

在移動(dòng)互聯(lián)網(wǎng)的業(yè)務(wù)場(chǎng)景中，數(shù)據(jù)量很大，我們需要保存這樣的信息：一個(gè) key 關(guān)聯(lián)了一個(gè)數(shù)據(jù)集合，同時(shí)對(duì)這個(gè)數(shù)據(jù)集合做統(tǒng)計(jì)。

• 統(tǒng)計(jì)一個(gè) APP 的日活、月活數(shù)；

• 統(tǒng)計(jì)一個(gè)頁(yè)面的每天被多少個(gè)不同賬戶訪問量（Unique Visitor，UV））；

• 統(tǒng)計(jì)用戶每天搜索不同詞條的個(gè)數(shù)；

• 統(tǒng)計(jì)注冊(cè) IP 數(shù)。

通常情況下，我們面臨的用戶數(shù)量以及訪問量都是巨大的，比如百萬、千萬級(jí)別的用戶數(shù)量，或者千萬級(jí)別、甚至億級(jí)別的訪問信息。

今天「碼哥」分別使用不同的數(shù)據(jù)類型來實(shí)現(xiàn)統(tǒng)計(jì)一個(gè)頁(yè)面的每天被多少個(gè)不同賬戶訪問量這個(gè)功能，循序漸進(jìn)的引出 HyperLogLog的原理與 Java 中整合 Redission 實(shí)戰(zhàn)。

告訴大家一個(gè)技巧，Redis 官方網(wǎng)站現(xiàn)在能在線運(yùn)行 Redis 指令了：https://redis.io/。如圖：

Redis 在線運(yùn)行

使用 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 為什么這么快」頁(yè)面，Set 的去重功能保證不會(huì)重復(fù)記錄同一個(gè)「微信 ID」。

通過 SCARD 命令，統(tǒng)計(jì)「Redis 為什么這么快」頁(yè)面 UV。指令返回一個(gè)集合的元素個(gè)數(shù)（也就是用戶 ID）。

SCARD?Redis為什么這么快:uv (integer)?2

使用 Hash 實(shí)現(xiàn)

碼老濕，還可以利用 Hash 類型實(shí)現(xiàn)，將用戶 ID 作為 Hash 集合的 key，訪問頁(yè)面則執(zhí)行 HSET 命令將 value 設(shè)置成 1。

即使「肖菜雞」重復(fù)訪問頁(yè)面，重復(fù)執(zhí)行命令，也只會(huì)把 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 對(duì) bit 數(shù)組的 offset 位置的 bit 位進(jìn)行讀寫操作，需要注意的是 offset 從 0 開始。

可以將 Bitmap 看成是一個(gè) bit 為單位的數(shù)組，數(shù)組的每個(gè)單元只能存儲(chǔ) 0 或者 1，數(shù)組的下標(biāo)在 Bitmap 中叫做 offset 偏移量。

為了直觀展示，我們可以理解成 buf 數(shù)組的每個(gè)字節(jié)用一行表示，每一行有 8 個(gè) bit 位，8 個(gè)格子分別表示這個(gè)字節(jié)中的 8 個(gè) bit 位，如下圖所示：

Bitmap

8 個(gè) bit 組成一個(gè) Byte，所以 Bitmap 會(huì)極大地節(jié)省存儲(chǔ)空間。 這就是 Bitmap 的優(yōu)勢(shì)。

如何使用 Bitmap 來統(tǒng)計(jì)頁(yè)面的獨(dú)立用戶訪問量呢？

Bitmap 提供了 SETBIT 和 BITCOUNT 操作，前者通過一個(gè)偏移值 offset 對(duì) bit 數(shù)組的 offset 位置的 bit 位進(jìn)行寫操作，需要注意的是 offset 從 0 開始。

后者統(tǒng)計(jì)給定指定的 bit 數(shù)組中，值 = 1 的 bit 位的數(shù)量。

需要注意的事，我們需要把「微信 ID」轉(zhuǎn)換成數(shù)字，因?yàn)閛ffset 是下標(biāo)。

假設(shè)我們將「肖菜雞」轉(zhuǎn)換成編碼6。

第一步，執(zhí)行下面指令表示「肖菜雞」的編碼為 6 。

SETBIT?巧用Redis數(shù)據(jù)類型實(shí)現(xiàn)億級(jí)數(shù)據(jù)統(tǒng)計(jì)?6?1

第二步，統(tǒng)計(jì)頁(yè)面訪問次數(shù)，使用 BITCOUNT 指令。該指令用于統(tǒng)計(jì)給定的 bit 數(shù)組中，值 = 1 的 bit 位的數(shù)量。

BITCOUNT?巧用Redis數(shù)據(jù)類型實(shí)現(xiàn)億級(jí)數(shù)據(jù)統(tǒng)計(jì)

HyperLogLog 王者

Set 雖好，如果文章非?；鸨_(dá)到千萬級(jí)別，一個(gè) Set 就保存了千萬個(gè)用戶的 ID，頁(yè)面多了消耗的內(nèi)存也太大了。

同理，Hash 數(shù)據(jù)類型也是如此。

至于 Bitmap，它更適合于「二值狀態(tài)統(tǒng)計(jì)」的使用場(chǎng)景，統(tǒng)計(jì)精度高，雖然內(nèi)存占用要比HashMap少，但是對(duì)于大量數(shù)據(jù)還是會(huì)占用較大內(nèi)存。

咋辦呢？

這些就是典型的「基數(shù)統(tǒng)計(jì)」應(yīng)用場(chǎng)景，基數(shù)統(tǒng)計(jì)：統(tǒng)計(jì)一個(gè)集合中不重復(fù)元素的個(gè)數(shù)。

HyperLogLog 的優(yōu)點(diǎn)在于它所需的內(nèi)存并不會(huì)因?yàn)榧系拇笮《淖?#xff0c;無論集合包含的元素有多少個(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 使用太簡(jiǎn)單了。PFADD、PFCOUNT、PFMERGE三個(gè)指令打天下。

PFADD

將訪問頁(yè)面的每個(gè)用戶 ID 添加到 HyperLogLog 中。

PFADD Redis主從同步原理:uv userID1 userID 2?useID3

PFCOUNT

利用 PFCOUNT 獲取 「Redis 主從同步原理」文章的 UV 值。

PFCOUNT Redis主從同步原理:uv

PFMERGE 使用場(chǎng)景

HyperLogLog?除了上面的?PFADD?和?PFCOIUNT?外，還提供了?PFMERGE

語法

PFMERGE?destkey?sourcekey?[sourcekey?...]

比如在網(wǎng)站中我們有兩個(gè)內(nèi)容差不多的頁(yè)面，運(yùn)營(yíng)說需要這兩個(gè)頁(yè)面的數(shù)據(jù)進(jìn)行合并。

其中頁(yè)面的 UV 訪問量也需要合并，那這個(gè)時(shí)候 PFMERGE 就可以派上用場(chǎng)了，也就是同樣的用戶訪問這兩個(gè)頁(yè)面則只算做一次。

如下所示：Redis、MySQL 兩個(gè) HyperLogLog 集合分別保存了兩個(gè)頁(yè)面用戶訪問數(shù)據(jù)。

PFADD?Redis數(shù)據(jù)?user1?user2?user3 PFADD?MySQL數(shù)據(jù)?user1?user2?user4 PFMERGE?數(shù)據(jù)庫(kù)?Redis數(shù)據(jù)?MySQL數(shù)據(jù) PFCOUNT?數(shù)據(jù)庫(kù)?//?返回值?=?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.redisson</groupId><artifactId>redisson-spring-boot-starter</artifactId><version>3.16.7</version> </dependency>

添加數(shù)據(jù)到 Log

//?添加單個(gè)元素 public?<T>?void?add(String?logName,?T?item)?{RHyperLogLog<T>?hyperLogLog?=?redissonClient.getHyperLogLog(logName);hyperLogLog.add(item); }//?將集合數(shù)據(jù)添加到?HyperLogLog public?<T>?void?addAll(String?logName,?List<T>?items)?{RHyperLogLog<T>?hyperLogLog?=?redissonClient.getHyperLogLog(logName);hyperLogLog.addAll(items); }

合并

/***?將?otherLogNames?的?log?合并到?logName**?@param?logName???????當(dāng)前?log*?@param?otherLogNames?需要合并到當(dāng)前?log?的其他?logs*?@param?<T>*/ public?<T>?void?merge(String?logName,?String...?otherLogNames)?{RHyperLogLog<T>?hyperLogLog?=?redissonClient.getHyperLogLog(logName);hyperLogLog.mergeWith(otherLogNames); }

統(tǒng)計(jì)基數(shù)

public?<T>?long?count(String?logName)?{RHyperLogLog<T>?hyperLogLog?=?redissonClient.getHyperLogLog(logName);return?hyperLogLog.count(); }

單元測(cè)試

@Slf4j @RunWith(SpringRunner.class) @SpringBootTest(classes?=?RedissionApplication.class) public?class?HyperLogLogTest?{@Autowiredprivate?HyperLogLogService?hyperLogLogService;@Testpublic?void?testAdd()?{String?logName?=?"碼哥字節(jié):Redis為什么這么快:uv";String?item?=?"肖菜雞";hyperLogLogService.add(logName,?item);log.info("添加元素[{}]到 log [{}]?中。",?item,?logName);}@Testpublic?void?testCount()?{String?logName?=?"碼哥字節(jié):Redis為什么這么快:uv";long?count?=?hyperLogLogService.count(logName);log.info("logName?=?{}?count?=?{}.",?logName,?count);}@Testpublic?void?testMerge()?{ArrayList<String>?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。

對(duì)于 n 次伯努利過程，我們會(huì)得到 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ù)組。

Redis 對(duì) HyperLogLog 的存儲(chǔ)進(jìn)行了優(yōu)化，在計(jì)數(shù)比較小的時(shí)候，存儲(chǔ)空間采用系數(shù)矩陣，占用空間很小。

只有在計(jì)數(shù)很大，稀疏矩陣占用的空間超過了閾值才會(huì)轉(zhuǎn)變成稠密矩陣，占用 12KB 空間。

為何只需要 12 KB 呀？

HyperLogLog 實(shí)現(xiàn)中用到的是 16384 個(gè)桶，也就是 2^14，每個(gè)桶的 maxbits 需要 6 個(gè) bits 來存儲(chǔ)，最大可以表示 maxbits=63，于是總共占用內(nèi)存就是2^14 * 6 / 8 = 12k字節(jié)。

參考資料

[1]:https://www.cnblogs.com/loveLands/articles/10987055.html

[2]:Redis 使用手冊(cè)

[3]:https://zhuanlan.zhihu.com/p/265309426

往期推薦

如果讓你來設(shè)計(jì)網(wǎng)絡(luò)

寫時(shí)復(fù)制就這么幾行代碼，還是不會(huì)？

JavaScript 數(shù)組你都掰扯不明白，還敢說精通 JavaScript ？

明明還有大量?jī)?nèi)存，為啥報(bào)錯(cuò)“無法分配內(nèi)存”？

點(diǎn)分享

點(diǎn)收藏

點(diǎn)點(diǎn)贊

點(diǎn)在看

總結(jié)

以上是生活随笔為你收集整理的Redis HyperLogLog 是什么？这些场景使用它~的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。