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

1、方案

考慮到上述問(wèn)題的擴(kuò)展性，除了統(tǒng)計(jì)APP每日的獨(dú)立用戶登錄數(shù)，還需要統(tǒng)計(jì)打開(kāi)每個(gè)頁(yè)面的獨(dú)立用戶數(shù)。

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

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

100000000 * 32 * 8 = 23G

以上只是計(jì)算一種類型，如果有100種類型，那么這個(gè)存儲(chǔ)空間線性增長(zhǎng)。當(dāng)然，對(duì)于存儲(chǔ)多個(gè)類型可以通過(guò)稀疏矩陣優(yōu)化，但是實(shí)際的存儲(chǔ)空間還是比較大。

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

方案一最大的問(wèn)題是存儲(chǔ) Set，但是我們需要的信息是存在或者不存在，那么這里其實(shí)用 bitmap 位運(yùn)算0或1就可以解決當(dāng)前問(wèn)題，那么存儲(chǔ)1億個(gè)key，每個(gè)key需要1個(gè)bit位，大約存儲(chǔ)空間是：

100000000 * 1 / 8 = 12M

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

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

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

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

2、HyperLogLog Counting原理

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

數(shù)組

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

import random
import math

class LogLogV1:
    def __init__(self, maxbit: int, tries: int = 10):
        """
            maxbit: int, 連續(xù)0的個(gè)數(shù)
            tries: int, 重復(fù)次數(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ù)是多少，這里通過(guò) tries 重復(fù)次數(shù)來(lái)求平均值，最后輸出：

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分桶

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

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

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

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

4、擴(kuò)展

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

參考

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