在移動(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è)不同賬戶訪問(wèn)量(Unique Visitor，UV))；
• 統(tǒng)計(jì)用戶每天搜索不同詞條的個(gè)數(shù)；
• 統(tǒng)計(jì)注冊(cè) IP 數(shù)。

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

今天「碼哥」分別使用不同的數(shù)據(jù)類(lèi)型來(lái)實(shí)現(xiàn)統(tǒng)計(jì)一個(gè)頁(yè)面的每天被多少個(gè)不同賬戶訪問(wèn)量這個(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)多次訪問(wèn)一個(gè)網(wǎng)站只能算作一次，所以很容易就想到通過(guò) Redis 的 Set 集合來(lái)實(shí)現(xiàn)。

比如微信 ID 為「肖菜雞」訪問(wèn) 「Redis 為什么這么快」這篇文章時(shí)，我們把這個(gè)信息存到 Set 中。

SADD Redis為什么這么快:uv 肖菜雞 謝霸哥 肖菜雞
(integer) 1

「肖菜雞」多次訪問(wèn)「Redis 為什么這么快」頁(yè)面，Set 的去重功能保證不會(huì)重復(fù)記錄同一個(gè)「微信 ID」。

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

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

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

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

即使「肖菜雞」重復(fù)訪問(wèn)頁(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 類(lèi)型的 SDS 數(shù)據(jù)結(jié)構(gòu)來(lái)保存位數(shù)組，Redis 把每個(gè)字節(jié)數(shù)組的 8 個(gè) bit 位利用起來(lái)，每個(gè) bit 位 表示一個(gè)元素的二值狀態(tài)(不是 0 就是 1)。

Bitmap 提供了 GETBIT、SETBIT 操作，通過(guò)一個(gè)偏移值 offset 對(duì) bit 數(shù)組的 offset 位置的 bit 位進(jìn)行讀寫(xiě)操作，需要注意的是 offset 從 0 開(kāi)始。

可以將 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 來(lái)統(tǒng)計(jì)頁(yè)面的獨(dú)立用戶訪問(wèn)量呢?

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

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

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

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

第一步，執(zhí)行下面指令表示「肖菜雞」的編碼為 6 并 訪問(wèn)「巧用 Redis 數(shù)據(jù)類(lèi)型實(shí)現(xiàn)億級(jí)數(shù)據(jù)統(tǒng)計(jì)」這篇文章。

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

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

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

HyperLogLog 王者

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

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

至于 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)榧系拇笮《淖?，無(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ù)。

Redis 實(shí)戰(zhàn)

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

PFADD

將訪問(wèn)頁(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

語(yǔ)法

PFMERGE destkey sourcekey [sourcekey ...]

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

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

如下所示：Redis、MySQL 兩個(gè) HyperLogLog 集合分別保存了兩個(gè)頁(yè)面用戶訪問(wèn)數(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 的可見(jiàn)集合(observed set)的并集。

user1、user2 都訪問(wèn)了 Redis 和 MySQL，只算訪問(wèn)了一次。

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 {

    @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<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)，它使用概率算法來(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 中 HyperLogLog 一共分了 2^14 個(gè)桶，也就是 16384 個(gè)桶。每個(gè)桶中是一個(gè) 6 bit 的數(shù)組，如下圖所示。

圖片來(lái)源：程序員歷小冰

關(guān)于 HyperLogLog 的原理過(guò)于復(fù)雜，如果想要了解的請(qǐng)移步：

• https://www.zhihu.com/question/53416615
• https://en.wikipedia.org/wiki/HyperLogLog
• 用戶日活月活怎么統(tǒng)計(jì) - Redis HyperLogLog 詳解

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

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

為何只需要 12 KB 呀?

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

總結(jié)

分別使用了 Hash、Bitmap、HyperLogLog 來(lái)實(shí)現(xiàn)：

• Hash：算法簡(jiǎn)單，統(tǒng)計(jì)精度高，少量數(shù)據(jù)下使用，對(duì)于海量數(shù)據(jù)會(huì)占據(jù)大量?jī)?nèi)存;
• Bitmap：位圖算法，適合用于「二值統(tǒng)計(jì)場(chǎng)景」，具體可參考我這篇文章，對(duì)于大量不同頁(yè)面數(shù)據(jù)統(tǒng)計(jì)還是會(huì)占用較大內(nèi)存。
• Set：利用去重特性實(shí)現(xiàn)，一個(gè) Set 就保存了千萬(wàn)個(gè)用戶的 ID，頁(yè)面多了消耗的內(nèi)存也太大了。

在 Redis 里面，每個(gè) HyperLogLog 鍵只需要花費(fèi) 12 KB 內(nèi)存，就可以計(jì)算接近2^64 個(gè)不同元素的基數(shù)。

因?yàn)?HyperLogLog 只會(huì)根據(jù)輸入元素來(lái)計(jì)算基數(shù)，而不會(huì)儲(chǔ)存輸入元素本身，所以 HyperLogLog 不能像集合那樣，返回輸入的各個(gè)元素。

• HyperLogLog是一種算法，并非 Redis 獨(dú)有。
• 目的是做基數(shù)統(tǒng)計(jì)，故不是集合，不會(huì)保存元數(shù)據(jù)，只記錄數(shù)量而不是數(shù)值。
• 耗空間極小，支持輸入非常體積的數(shù)據(jù)量。
• 核心是基數(shù)估算算法，主要表現(xiàn)為計(jì)算時(shí)內(nèi)存的使用和數(shù)據(jù)合并的處理。最終數(shù)值存在一定誤差。
• Redis中每個(gè)Hyperloglog key 占用了 12K 的內(nèi)存用于標(biāo)記基數(shù)(官方文檔)。
• pfadd 命令并不會(huì)一次性分配 12k 內(nèi)存，而是隨著基數(shù)的增加而逐漸增加內(nèi)存分配;而 pfmerge 操作則會(huì)將 sourcekey 合并后存儲(chǔ)在 12k 大小的 key 中，由hyperloglog合并操作的原理(兩個(gè)Hyperloglog合并時(shí)需要單獨(dú)比較每個(gè)桶的值)可以很容易理解。
• 誤差說(shuō)明：基數(shù)估計(jì)的結(jié)果是一個(gè)帶有 0.81% 標(biāo)準(zhǔn)錯(cuò)誤(standard error)的近似值。是可接受的范圍Redis 對(duì) HyperLogLog 的存儲(chǔ)進(jìn)行優(yōu)化，在計(jì)數(shù)比較小時(shí)，存儲(chǔ)空間采用稀疏矩陣存儲(chǔ)，空間占用很小，僅僅在計(jì)數(shù)慢慢變大，稀疏矩陣占用空間漸漸超過(guò)了閾值時(shí)才會(huì)一次性轉(zhuǎn)變成稠密矩陣，才會(huì)占用 12k 的空間。