在移動互聯網的業務場景中，數據量很大，我們需要保存這樣的信息：一個 key 關聯了一個數據集合，同時對這個數據集合做統計。

• 統計一個 APP 的日活、月活數；
• 統計一個頁面的每天被多少個不同賬戶訪問量(Unique Visitor，UV))；
• 統計用戶每天搜索不同詞條的個數；
• 統計注冊 IP 數。

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

今天「碼哥」分別使用不同的數據類型來實現統計一個頁面的每天被多少個不同賬戶訪問量這個功能，循序漸進的引出 HyperLogLog的原理與 Java 中整合 Redission 實戰。

告訴大家一個技巧，Redis 官方網站現在能在線運行 Redis 指令了：https://redis.io/。如圖：

Redis 在線運行

使用 Set 實現

一個用戶一天內多次訪問一個網站只能算作一次，所以很容易就想到通過 Redis 的 Set 集合來實現。

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

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

「肖菜雞」多次訪問「Redis 為什么這么快」頁面，Set 的去重功能保證不會重復記錄同一個「微信 ID」。

通過 SCARD 命令，統計「Redis 為什么這么快」頁面 UV。指令返回一個集合的元素個數(也就是用戶 ID)。

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

使用 Hash 實現

碼老濕，還可以利用 Hash 類型實現，將用戶 ID 作為 Hash 集合的 key，訪問頁面則執行 HSET 命令將 value 設置成 1。

即使「肖菜雞」重復訪問頁面，重復執行命令，也只會把 key 等于「肖菜雞」的 value 設置成 1。

最后，利用 HLEN 命令統計 Hash 集合中的元素個數就是 UV。

如下：

HSET Redis為什么這么快 肖菜雞 1
// 統計 UV
HLEN Redis為什么這么快

使用 Bitmap 實現

Bitmap 的底層數據結構用的是 String 類型的 SDS 數據結構來保存位數組，Redis 把每個字節數組的 8 個 bit 位利用起來，每個 bit 位 表示一個元素的二值狀態(不是 0 就是 1)。

Bitmap 提供了 GETBIT、SETBIT 操作，通過一個偏移值 offset 對 bit 數組的 offset 位置的 bit 位進行讀寫操作，需要注意的是 offset 從 0 開始。

可以將 Bitmap 看成是一個 bit 為單位的數組，數組的每個單元只能存儲 0 或者 1，數組的下標在 Bitmap 中叫做 offset 偏移量。

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

Bitmap

8 個 bit 組成一個 Byte，所以 Bitmap 會極大地節省存儲空間。 這就是 Bitmap 的優勢。

如何使用 Bitmap 來統計頁面的獨立用戶訪問量呢?

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

后者統計給定指定的 bit 數組中，值 = 1 的 bit 位的數量。

需要注意的事，我們需要把「微信 ID」轉換成數字，因為offset 是下標。

假設我們將「肖菜雞」轉換成編碼6。

第一步，執行下面指令表示「肖菜雞」的編碼為 6 并 訪問「巧用 Redis 數據類型實現億級數據統計」這篇文章。

SETBIT 巧用Redis數據類型實現億級數據統計 6 1

第二步，統計頁面訪問次數，使用 BITCOUNT 指令。該指令用于統計給定的 bit 數組中，值 = 1 的 bit 位的數量。

BITCOUNT 巧用Redis數據類型實現億級數據統計

HyperLogLog 王者

Set 雖好，如果文章非常火爆達到千萬級別，一個 Set 就保存了千萬個用戶的 ID，頁面多了消耗的內存也太大了。

同理，Hash 數據類型也是如此。

至于 Bitmap，它更適合于「二值狀態統計」的使用場景，統計精度高，雖然內存占用要比HashMap少，但是對于大量數據還是會占用較大內存。

咋辦呢?

這些就是典型的「基數統計」應用場景，基數統計：統計一個集合中不重復元素的個數。

HyperLogLog 的優點在于它所需的內存并不會因為集合的大小而改變，無論集合包含的元素有多少個，HyperLogLog 進行計算所需的內存總是固定的，并且是非常少的。

每個 HyperLogLog 最多只需要花費 12KB 內存，在標準誤差 0.81%的前提下，就可以計算 2 的 64 次方個元素的基數。

Redis 實戰

HyperLogLog 使用太簡單了。PFADD、PFCOUNT、PFMERGE三個指令打天下。

PFADD

將訪問頁面的每個用戶 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 ...]

比如在網站中我們有兩個內容差不多的頁面，運營說需要這兩個頁面的數據進行合并。

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

如下所示：Redis、MySQL 兩個 HyperLogLog 集合分別保存了兩個頁面用戶訪問數據。

PFADD Redis數據 user1 user2 user3
PFADD MySQL數據 user1 user2 user4
PFMERGE 數據庫 Redis數據 MySQL數據
PFCOUNT 數據庫 // 返回值 = 4

將多個 HyperLogLog 合并(merge)為一個 HyperLogLog ， 合并后的 HyperLogLog 的基數接近于所有輸入 HyperLogLog 的可見集合(observed set)的并集。

user1、user2 都訪問了 Redis 和 MySQL，只算訪問了一次。

Redission 實戰

詳細源碼「碼哥」上傳到 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>

添加數據到 Log

// 添加單個元素
public <T> void add(String logName, T item) {
  RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
  hyperLogLog.add(item);
}

// 將集合數據添加到 HyperLogLog
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);
}

統計基數

public <T> long count(String logName) {
  RHyperLogLog<T> 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 = "碼哥字節:Redis為什么這么快:uv";
        String item = "肖菜雞";
        hyperLogLogService.add(logName, item);
        log.info("添加元素[{}]到 log [{}] 中。", item, logName);
    }

    @Test
    public void testCount() {
        String logName = "碼哥字節: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 = "碼哥字節:Redis多線程模型原理與實戰:uv";
        hyperLogLogService.addAll(otherLogName, items);
        log.info("添加 {} 個元素到 log [{}] 中。", items.size(), otherLogName);

        String logName = "碼哥字節:Redis為什么這么快:uv";
        hyperLogLogService.merge(logName, otherLogName);
        log.info("將 {} 合并到 {}.", otherLogName, logName);

        long count = hyperLogLogService.count(logName);
        log.info("合并后的 count = {}.", count);
    }
}

基本原理

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 的數組，如下圖所示。

圖片來源：程序員歷小冰

關于 HyperLogLog 的原理過于復雜，如果想要了解的請移步：

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

Redis 對 HyperLogLog 的存儲進行了優化，在計數比較小的時候，存儲空間采用系數矩陣，占用空間很小。

只有在計數很大，稀疏矩陣占用的空間超過了閾值才會轉變成稠密矩陣，占用 12KB 空間。

為何只需要 12 KB 呀?

HyperLogLog 實現中用到的是 16384 個桶，也就是 2^14，每個桶的 maxbits 需要 6 個 bits 來存儲，最大可以表示 maxbits=63，于是總共占用內存就是2^14 * 6 / 8 = 12k字節。

總結

分別使用了 Hash、Bitmap、HyperLogLog 來實現：

• Hash：算法簡單，統計精度高，少量數據下使用，對于海量數據會占據大量內存;
• Bitmap：位圖算法，適合用于「二值統計場景」，具體可參考我這篇文章，對于大量不同頁面數據統計還是會占用較大內存。
• Set：利用去重特性實現，一個 Set 就保存了千萬個用戶的 ID，頁面多了消耗的內存也太大了。

在 Redis 里面，每個 HyperLogLog 鍵只需要花費 12 KB 內存，就可以計算接近2^64 個不同元素的基數。

因為 HyperLogLog 只會根據輸入元素來計算基數，而不會儲存輸入元素本身，所以 HyperLogLog 不能像集合那樣，返回輸入的各個元素。

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