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

比如：

• 統(tǒng)計(jì)一個(gè) APP 的日活、月活數(shù)。
• 統(tǒng)計(jì)一個(gè)頁(yè)面的每天被多少個(gè)不同賬戶訪問(wèn)量（Unique Visitor，UV）。
• 統(tǒng)計(jì)用戶每天搜索不同詞條的個(gè)數(shù)。
• 統(tǒng)計(jì)注冊(cè) IP 數(shù)。

通常情況下，系統(tǒng)面臨的用戶數(shù)量以及訪問(wèn)量都是巨大的，比如百萬(wàn)、千萬(wàn)級(jí)別的用戶數(shù)量，或者千萬(wàn)級(jí)別、甚至億級(jí)別的訪問(wèn)信息，咋辦呢？

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

1. 是什么

HyperLogLog 是一種概率數(shù)據(jù)結(jié)構(gòu)，用于估計(jì)集合的基數(shù)。每個(gè) HyperLogLog 最多只需要花費(fèi) 12KB 內(nèi)存，在標(biāo)準(zhǔn)誤差 0.81%的前提下，就可以計(jì)算 2 的 64 次方個(gè)元素的基數(shù)。

HyperLogLog 的優(yōu)點(diǎn)在于它所需的內(nèi)存并不會(huì)因?yàn)榧系拇笮《淖儯瑹o(wú)論集合包含的元素有多少個(gè)，HyperLogLog 進(jìn)行計(jì)算所需的內(nèi)存總是固定的，并且是非常少的。

主要特點(diǎn)如下：

• 高效的內(nèi)存使用：HyperLogLog 的內(nèi)存消耗是固定的，與集合中的元素?cái)?shù)量無(wú)關(guān)。這使得它特別適用于處理大規(guī)模數(shù)據(jù)集，因?yàn)樗恍枰鎯?chǔ)每個(gè)不同的元素，只需要存儲(chǔ)估計(jì)基數(shù)所需的信息。
• 概率估計(jì)：HyperLogLog 提供的結(jié)果是概率性的，而不是精確的基數(shù)計(jì)數(shù)。它通過(guò)哈希函數(shù)將輸入元素映射到位圖中的某些位置，并基于位圖的統(tǒng)計(jì)信息來(lái)估計(jì)基數(shù)。由于這是一種概率性方法，因此可能存在一定的誤差，但通常在實(shí)際應(yīng)用中，這個(gè)誤差是可接受的。
• 高速計(jì)算：HyperLogLog 可以在常量時(shí)間內(nèi)計(jì)算估計(jì)的基數(shù)，無(wú)論集合的大小如何。這意味著它的性能非常好，不會(huì)受到集合大小的影響。

2. 修煉心法

基本原理

HyperLogLog 是一種概率數(shù)據(jù)結(jié)構(gòu)，它使用概率算法來(lái)統(tǒng)計(jì)集合的近似基數(shù)。而它算法的最本源則是伯努利過(guò)程。

伯努利過(guò)程就是一個(gè)拋硬幣實(shí)驗(yàn)的過(guò)程。拋一枚正常硬幣，落地可能是正面，也可能是反面，二者的概率都是 1/2 。

伯努利過(guò)程就是一直拋硬幣，直到落地時(shí)出現(xiàn)正面位置，并記錄下拋擲次數(shù)k。

比如說(shuō)，拋一次硬幣就出現(xiàn)正面了，此時(shí) k 為 1; 第一次拋硬幣是反面，則繼續(xù)拋，直到第三次才出現(xiàn)正面，此時(shí) k 為 3。

對(duì)于 n 次伯努利過(guò)程，我們會(huì)得到 n 個(gè)出現(xiàn)正面的投擲次數(shù)值 k1, k2 ... kn, 其中這里的最大值是 k_max。

根據(jù)一頓數(shù)學(xué)推導(dǎo)，我們可以得出一個(gè)結(jié)論：2^{k_ max} 來(lái)作為 n 的估計(jì)值。

也就是說(shuō)你可以根據(jù)最大投擲次數(shù)近似的推算出進(jìn)行了幾次伯努利過(guò)程。

所以 HyperLogLog 的基本思想是利用集合中數(shù)字的比特串第一個(gè) 1 出現(xiàn)位置的最大值來(lái)預(yù)估整體基數(shù)，但是這種預(yù)估方法存在較大誤差，為了改善誤差情況，HyperLogLog 中引入分桶平均的概念，計(jì)算 m 個(gè)桶的調(diào)和平均值。

Redis 內(nèi)部使用字符串位圖來(lái)存儲(chǔ) HyperLogLog 所有桶的計(jì)數(shù)值，一共分了 2^14 個(gè)桶，也就是 16384 個(gè)桶。每個(gè)桶中是一個(gè) 6 bit 的數(shù)組。

這段代碼描述了 Redis HyperLogLog 數(shù)據(jù)結(jié)構(gòu)的頭部定義（hyperLogLog.c 中的 hllhdr 結(jié)構(gòu)體）。以下是關(guān)于這個(gè)數(shù)據(jù)結(jié)構(gòu)的各個(gè)字段的解釋。

struct hllhdr {
    char magic[4];
    uint8_t encoding;
    uint8_t notused[3];
    uint8_t card[8];
    uint8_t registers[];
};

(1)magic[4]：這個(gè)字段是一個(gè) 4 字節(jié)的字符數(shù)組，用來(lái)表示數(shù)據(jù)結(jié)構(gòu)的標(biāo)識(shí)符。在 HyperLogLog 中，它的值始終為"HYLL"，用來(lái)標(biāo)識(shí)這是一個(gè) HyperLogLog 數(shù)據(jù)結(jié)構(gòu)。

(2)encoding：這是一個(gè) 1 字節(jié)的字段，用來(lái)表示 HyperLogLog 的編碼方式。它可以取兩個(gè)值之一：

• HLL_DENSE：表示使用稠密表示方式。
• HLL_SPARSE：表示使用稀疏表示方式。

(3)notused[3]：這是一個(gè) 3 字節(jié)的字段，目前保留用于未來(lái)的擴(kuò)展，要求這些字節(jié)的值必須為零。

(4)card[8]：這是一個(gè) 8 字節(jié)的字段，用來(lái)存儲(chǔ)緩存的基數(shù)（基數(shù)估計(jì)的值）。

(5)egisters[]：這個(gè)字段是一個(gè)可變長(zhǎng)度的字節(jié)數(shù)組，用來(lái)存儲(chǔ) HyperLogLog 的數(shù)據(jù)。

4-45

圖 2-45

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

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

出招實(shí)戰(zhàn)：網(wǎng)頁(yè)訪問(wèn)量統(tǒng)計(jì)

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

比如。

• 統(tǒng)計(jì)一個(gè) APP 的日活、月活數(shù)。
• 統(tǒng)計(jì)一個(gè)頁(yè)面的每天被多少個(gè)不同賬戶訪問(wèn)量（Unique Visitor，UV）。
• 統(tǒng)計(jì)用戶每天搜索不同詞條的個(gè)數(shù)。
• 統(tǒng)計(jì)注冊(cè) IP 數(shù)。

通常情況下，系統(tǒng)面臨的用戶數(shù)量以及訪問(wèn)量都是巨大的，比如百萬(wàn)、千萬(wàn)級(jí)別的用戶數(shù)量，或者千萬(wàn)級(jí)別、甚至億級(jí)別的訪問(wèn)信息，咋辦呢？

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

一個(gè)用戶一天內(nèi)多次訪問(wèn)一個(gè)網(wǎng)站只能算作一次，所以很容易就想到通過(guò) Redis 的 Set 集合來(lái)實(shí)現(xiàn)。

比如微信昵稱(chēng)叫 “Chaya” 的小姐姐訪問(wèn)【愛(ài)一個(gè)人總是要掉眼淚的風(fēng)險(xiǎn)】這篇文章時(shí)，我把這個(gè)微信昵稱(chēng) “Chaya” 存到 Set 集合中。

SADD 愛(ài)一個(gè)人總是要掉眼淚的風(fēng)險(xiǎn):uv 碼哥 Chaya 趙小因 Chaya
(integer) 3

“Chaya” 多次訪問(wèn)這篇文章， Set 的去重特性保證集合中只有一個(gè)記錄。接著，通過(guò) SCARD 命令，統(tǒng)計(jì)頁(yè)面 UV。指令返回這個(gè)集合的元素個(gè)數(shù)（也就是微信昵稱(chēng)個(gè)數(shù)）。

SCARD 愛(ài)一個(gè)人總是要掉眼淚的風(fēng)險(xiǎn):uv
(integer) 3

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

Chaya：“Set 集合雖好，如果文章非常火爆達(dá)到千萬(wàn)級(jí)別，一個(gè) Set 集合就保存了千萬(wàn)個(gè)用戶的 ID，頁(yè)面多了消耗的內(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)榧系拇笮《淖儯瑹o(wú)論集合包含的元素有多少個(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ù)。

HyperLogLog 使用太簡(jiǎn)單了。PFADD、PFCOUNT、PFMERGE三個(gè)指令打天下。

PFADD

每訪問(wèn)一次頁(yè)面，調(diào)用 PFADD 指令 將這個(gè)用戶 ID 添加到 HyperLogLog 中。如下 一共有三個(gè)用戶訪問(wèn)了這頁(yè)面，其中 Chaya 訪問(wèn)了兩次，但只算一次。

PFADD 愛(ài)一個(gè)人總是要掉眼淚的風(fēng)險(xiǎn):uv 碼哥 Chaya 趙小因 Chaya

如果執(zhí)行命令后 HyperLogLog 估計(jì)的近似基數(shù)發(fā)生變化，PFADD則返回 1，否則返回 0。如果指定的鍵不存在，該命令會(huì)自動(dòng)創(chuàng)建一個(gè)空的 HyperLogLog 結(jié)構(gòu)。

pfadd 命令并不會(huì)一次性分配 12k 內(nèi)存，而是隨著基數(shù)的增加而逐漸增加內(nèi)存分配；

PFCOUNT

接下來(lái)，通過(guò) PFCOUNT 指令獲取文章【愛(ài)一個(gè)人總是要掉眼淚的風(fēng)險(xiǎn)】的 UV 值，可以看到返回值是 3 ，符合預(yù)期。

> PFCOUNT 愛(ài)一個(gè)人總是要掉眼淚的風(fēng)險(xiǎn):uv
3

PFMERGE 合并統(tǒng)計(jì)

Chaya：“還有一個(gè)變態(tài)需求，對(duì)文章進(jìn)行標(biāo)簽分類(lèi)，運(yùn)營(yíng)說(shuō)要把都是情感文章標(biāo)簽的幾個(gè)頁(yè)面數(shù)據(jù)合并統(tǒng)計(jì)。”

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

如下指令，把愛(ài)一個(gè)人總是要掉眼淚的風(fēng)險(xiǎn):uv和愛(ài)情是幸福和不委屈:uv 兩個(gè) HyperLogLog 集合數(shù)據(jù)合并到情感分類(lèi)文章:uv這個(gè)集合中。

PFADD 愛(ài)情是幸福和不委屈:uv Chaya 趙小因 幸運(yùn)草
# 合并兩個(gè)頁(yè)面 UV
PFMERGE 情感分類(lèi)文章:uv 愛(ài)一個(gè)人總是要掉眼淚的風(fēng)險(xiǎn):uv 愛(ài)情是幸福和不委屈:uv

接著，執(zhí)行 PFCOUNT 情感分類(lèi)文章:uv 統(tǒng)計(jì)合并后的數(shù)據(jù)。

> PFCOUNT 情感分類(lèi)文章:uv
4

將多個(gè) HyperLogLog 合并（merge）為一個(gè) HyperLogLog ， 合并后的 HyperLogLog 的基數(shù)接近于所有輸入 HyperLogLog 的可見(jiàn)集合（observed set）的并集。

4. Redisson 實(shí)戰(zhàn)

開(kāi)門(mén)見(jiàn)山，Spring Boot 與 Redisson 集成詳見(jiàn)前面篇章，主要有四個(gè)方法。

• add、addAll，閱讀文章調(diào)用該方法將數(shù)據(jù)存入 HyperLogLog 中。
• count，統(tǒng)計(jì)基數(shù)。
• merge，合并多個(gè) HyperLogLog 為一個(gè)。

@Service
public class HyperLogLogService {

    @Autowired
    private RedissonClient redissonClient;

    /**
     * 將數(shù)據(jù)添加到 HyperLogLog
     *
     * @param logName
     * @param item
     * @param <T>
     */
    public <T> void add(String logName, T item) {
        RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
        hyperLogLog.add(item);
    }

    /**
     * 將集合數(shù)據(jù)添加到 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       當(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ù)
     *
     * @param logName 需要統(tǒng)計(jì)的 logName
     * @param <T>
     * @return
     */
    public <T> long count(String logName) {
        RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
        return hyperLogLog.count();
    }
}