hyperloglog實戰 - 你的過濾器選對了嗎？

一、業務背景

最近接到一個統計需求，為了監控視訊效果，我們每次浏覽視訊都要記錄uv。當量小的時候，沒有問題，随着使用者量的的增長，占用空間大的問題開始暴露。假如有1000萬使用者，采用set結構記錄UV，我們隻存儲int類型的使用者id，1000萬*4byte/1024kb/1024mb=38.14G，這是一個視訊一天的資料，很明顯存儲成本太高，必須找到一種既能滿足需求，又很少占用空間的方案。

二、技術選型

經過調研，找到了以下幾種技術方案，下面一一分析。

1、flink的state去重

MapState 是 Flink 中 KeyedState 的狀态類型，這種方式實作去重是一個精确的去重結果，将裝置 ID 儲存在 MapState 中。而state 直接存放在 RocksDB 中，RocksDB是類似HBase的kv資料庫，本地性能好，維護較大的狀态集合問題不大。

這種方案的優點是資料準确定非常高，确定是随着state增長，對checkpoint效率和成功率都有挑戰，而且需要定期清理state，無發做到長時間資料去重。

2、bitmap去重

bitmap的原理是使用一個bit來存放某種狀态，适用于大規模資料，但是狀态又不是很多的情況。假設使用redis的bitmap，首先将使用者id通過算法轉換為整數，這個整數就是偏移量，每個id占用一位，1是通路過。

這個方案的優點是占用記憶體小，查詢友善，效率高，能夠精确去重，缺點是需要計算偏移量，如果偏移量過大就占用很多空間。

3、布隆過濾器

布隆過濾器是由一個很長的二進制向量和一系列随機映射函數。它适合過濾不存的元素場景，如果判斷不存在則一定不存在，如果判斷存在，則有一定機率不存在。計算puv時，用一個變量計數，用這個過濾器判斷計數器是否增加。

這個方案的優點是空間效率高，查詢時間短。缺點是有誤判率，多個次元時，初始配置設定的空間一樣，會占用較大空間。

4、hyperloglog

hyperloglog是一種算法，目的是做基數統計，可以預估一個集合中不同資料的個數，它不會儲存中繼資料，隻記錄數量，支援輸入非常大體積的資料量。在 redis 中也存在 hyperloglog 類型的結構，能夠使用 12k 的記憶體，允許誤差在 0.81%的情況下統計 2^64 個資料。

這個方案的有點事占用空間小，空間不會随着數量的變大而無線變大。缺點是有0.81%的标準誤差率，隻能用來計數，不能用來查詢元素。

綜合上面的方案，對于1000萬使用者，統計上億視訊，允許一定誤差率的場景，方案 4 更加合适，記憶體能夠控制在12k以内，查詢速度也能滿足需求。

三、hyperloglog 原理分析

1、原理說明

HyperLogLog 算法來源于論文 HyperLogLog the analysis of a near-optimal cardinality estimation algorithm，想要了解 HLL 的原理，先要從伯努利試驗說起，伯努利實驗說的是抛硬币的事。一次伯努利實驗相當于抛硬币，不管抛多少次隻要出現一個正面，就稱為一次伯努利實驗。

我們用 k 來表示每次抛硬币的次數，n 表示第幾次抛的硬币，用 k_max 來表示抛硬币的最高次數，最終根據估算發現 n 和 k_max 存在的關系是 n=2^(k_max)，但同時我們也發現了另一個問題當試驗次數很小的時候，這種估算方法的誤差會很大，例如我們進行以下 3 次實驗：

• 第 1 次試驗：抛 3 次出現正面，此時 k=3，n=1；
• 第 2 次試驗：抛 2 次出現正面，此時 k=2，n=2；
• 第 3 次試驗：抛 6 次出現正面，此時 k=6，n=3。

對于這三組實驗來說，k_max=6，n=3，但放入估算公式明顯 3≠2^6。為了解決這個問題 HLL 引入了分桶算法和調和平均數來使這個算法更接近真實情況。

分桶算法是指把原來的資料平均分為 m 份，在每段中求平均數在乘以 m，以此來消減因偶然性帶來的誤差，提高預估的準确性，簡單來說就是把一份資料分為多份，把一輪計算，分為多輪計算。

而調和平均數指的是使用平均數的優化算法，而非直接使用平均數。

例如小明的月工資是 1000 元，而小王的月工資是 100000 元，如果直接取平均數，那小明的平均工資就變成了 (1000+100000)/2=50500‬ 元，這顯然是不準确的，而使用調和平均數算法計算的結果是 2/(1/1000+1/100000)≈1998 元，顯然此算法更符合實際平均數。

2、具體的計算流程

這是hyperloglog的線上計算網站： http://content.research.neustar.biz/blog/hll.html

• 第一步對輸入的值3,157,369進行hash獲得值2,297,270,962，hash的值轉二進制 11100000101001010101001011101110100111010
• 第二步二進制數的最後6位設定為桶的index（長16，寬4的矩形），為什麼是6位呢？因為2的6次方正好等于矩陣數組的個數64，從圖中看出index是50，紅色的方塊是要放入的位置
• 第三步擷取從右向左的第一個1，如圖看到是10，也就是2
• 最後一步多個不同的值，就被分散到不同的桶中去了，且每個桶有其 k_max。然後當要統計出總共有多少的時候，就是一次估算。最終結合所有桶中的 k_max，代入估算公式，便能得出估算值。

四、hyperloglog redis實戰

在 Redis 的 HyperLogLog 實作中用到的是 16384 個桶，也就是 2^14，每個桶的 maxbits 需要 6 個 bits 來存儲，最大可以表示 maxbits=63，于是總共占用記憶體就是2^14 * 6 / 8 = 12k位元組。\

HyperLogLog 提供了兩個指令 pfadd 和 pfcount，根據字面意義很好了解，一個是增加計數，一個是擷取計數。pfadd 用法和 set 集合的 sadd 是一樣的，來一個使用者 ID，就将使用者 ID 塞進去就是。pfcount 和 scard 用法是一樣的，直接擷取計數值。

127.0.0.1:6379> PFADD runoobkey "redis"

(integer) 1

127.0.0.1:6379> PFADD runoobkey "mongodb"

(integer) 1

127.0.0.1:6379> PFADD runoobkey "mysql"

(integer) 1

127.0.0.1:6379> PFCOUNT runoobkey
           

我們将資料增加到 10w 個，看看總量差距有多大。

public class Test {

    public static void main(String[] args) {

        //連接配接本地的redis

        Jedis jedis = new Jedis("localhost");

        System.out.println(jedis.getClient().getPort());

        System.out.println("連接配接本地的Redis伺服器成功");


        for (int i = 0; i < 100000; i++) {

            jedis.pfadd("my-user-uv", "user" + i);

        }

        long total = jedis.pfcount("my-user-uv");

        System.out.printf("%d %d\n", 100000, total);

        jedis.close();

    }

}
           

差了 275 個，按百分比是 0.275%，對于上面的 UV 統計需求來說，誤差率也不算高。然後我們把上面的腳本再跑一邊，也就相當于将資料重複加入一邊，檢視輸出，可以發現，pfcount 的結果沒有任何改變，還是 99725，說明它确實具備去重功能。

參考資料

• 優秀的基數統計算
• Redis HyperLoglog、Bloom Filter 、Bitmap

（轉自：https://juejin.cn/post/6992890603503632415）