前段時間產(chǎn)品提了個需求，需要統(tǒng)計APP的各個場景下的UV，如何實現(xiàn)？

1、方案

考慮到上述問題的擴展性，除了統(tǒng)計APP每日的獨立用戶登錄數(shù)，還需要統(tǒng)計打開每個頁面的獨立用戶數(shù)。

方案一：用Set統(tǒng)計

首先我們想到肯定是通過類似 redis 的 Set，將每個openid添加到對應需要統(tǒng)計的 Set 中，每一種類型用一個 Set，那計算一下，如果存儲1億個key，每個key的大小32個字符，大約存儲空間是：

100000000 * 32 * 8 = 23G

以上只是計算一種類型，如果有100種類型，那么這個存儲空間線性增長。當然，對于存儲多個類型可以通過稀疏矩陣優(yōu)化，但是實際的存儲空間還是比較大。

方案二：用bitmap統(tǒng)計

方案一最大的問題是存儲 Set，但是我們需要的信息是存在或者不存在，那么這里其實用 bitmap 位運算0或1就可以解決當前問題，那么存儲1億個key，每個key需要1個bit位，大約存儲空間是：

100000000 * 1 / 8 = 12M

如果有100種類型，那么存儲空間是1.2G左右，這種方法可以解決內(nèi)存過大的問題，但是無法擴展。

方案三：概率算法統(tǒng)計

在解決大數(shù)據(jù)量的情況下，很多實際場景不需要太精確的數(shù)據(jù)，為了節(jié)省內(nèi)存同時滿足大數(shù)據(jù)的統(tǒng)計需求，衍生了很多概率算法，如：

• Linear Counting：定義一個hash函數(shù)，function hash(x): -> [0,1,2,…,m-1]，假設該hash函數(shù)的hash結(jié)果服從均勻分布，接著定義一個長度為m的bit數(shù)組，開始每一位上都初始化為0，然后對可重復集合里的每個元素進行hash得到k，如果bitmap[k]為0則置1，最后統(tǒng)計bitmap數(shù)組里為0的位數(shù)；
• LogLog Counting：LogLog Counting優(yōu)于Linear Counting，也是利用哈希函數(shù)將輸入元素映射到一個固定大小的位數(shù)組中，估算連續(xù)數(shù)組的位數(shù)，時間復雜度為O(1)；
• HyperLogLog Counting：是基于LogLog Counting的改進方案，能實現(xiàn)更小的誤差，本文重點就介紹HyperLogLog Counting算法；

2、HyperLogLog Counting原理

用一句話概括：我們能找到連續(xù)出現(xiàn)的概率與次數(shù)的關(guān)系，能就能將其轉(zhuǎn)換為數(shù)學公式。比如我們有數(shù)組：

數(shù)組

通過上圖我們只需要末尾連續(xù)0的個數(shù)，并統(tǒng)計出執(zhí)行多少次隨機即可，我們用如下代碼實驗：

import random
import math

class LogLogV1:
    def __init__(self, maxbit: int, tries: int = 10):
        """
            maxbit: int, 連續(xù)0的個數(shù)
            tries: int, 重復次數(shù)
        """
        self.maxbit = maxbit
        self.tries = tries
        self.option = [0, 1]

    def _run_one_round(self):
        rounds = 0
        while True:
            num = 0
            while True:
                result = random.choice(self.option)
                if result == 1:
                    break
                num += 1
                rounds += 1
            if num >= self.maxbit:
                break
        return rounds
    
    def get_rounds(self):
        all_rounds = 0
        for i in range(self.tries):
            all_rounds += self._run_one_round()
        return all_rounds / self.tries

if __name__ == '__main__':
    for i in range(10, 20):
        be = LogLogV1(i)
        rounds = be.get_rounds()
        print(f"{i} rounds: {rounds}, log2: ", math.log(rounds, 2))

以上代碼的含義是，獲得連續(xù) maxbit = 0，需要執(zhí)行的次數(shù)是多少，這里通過 tries 重復次數(shù)來求平均值，最后輸出：

10 rounds: 1023.7, log2:  9.99957727351139
11 rounds: 2041.0, log2:  10.995060467032719
12 rounds: 2649.1, log2:  11.371286589215627
13 rounds: 16484.6, log2:  14.008831259883943
14 rounds: 20324.1, log2:  14.31090384726008
15 rounds: 25673.7, log2:  14.648003606393374
16 rounds: 70248.2, log2:  16.10017363855784
17 rounds: 152139.1, log2:  17.2150314501608
18 rounds: 267469.5, log2:  18.029014862371255
19 rounds: 627246.3, log2:  19.258672529927942

可以看到 2^maxbit ≈ rounds，其中誤差比較小。

3、HyperLogLog Counting分桶

為什么要分桶？假設上述的tries值比較小，那么會存在估計不準的情況，比如 2^maxbit ~ 2^(maxbit+1) 之間直接按照公式計算，誤差會比較大，所以通過求多個值得平均值來解決問題，這樣估算的值就比較平滑。

那么redis的HyperLogLog Counting是如何分桶的？代碼：https://github.com/redis/redis/blob/unstable/src/hyperloglog.c

• 2^14個桶，每個桶6bit，總共12KB；
• 每個輸入通過hash算法得出64bit哈希值hashkey；
• hashkey的低14位，用來選擇桶號（0-2^14-1號）Mi;
• hashkey的高50位,用來找K（也就是第一次出現(xiàn)1的位置，或者說0后綴的長度），把K存入Mi；

網(wǎng)上有個模擬演示地址：http://content.research.neustar.biz/blog/hll.html，有興趣可以看看詳細的執(zhí)行過程。

4、擴展

（1）HyperLogLog能滿足產(chǎn)品的需求，但是擴展到其他問題：如何實現(xiàn)長周期存儲（一年的存儲周期UV統(tǒng)計）；（2）如何實現(xiàn)分布式，本身HyperLogLog是單機算法，如何實現(xiàn)非集中式場景；

參考

https://www.cnblogs.com/wmyskxz/p/12396393.html