Redis-HyperLogLog

基于HyperLogLog算法，使用極小的空間完成巨量運算

Redis 中HyperLogLog 基本使用

常用命令

1. PFADD key element [element …]: 將任意數量的元素添加到指定的 HyperLogLog 里面。
2. PFCOUNT key [key …]: 計算hyperloglog的獨立總數
3. prmerge destkey sourcekey [sourcekey…]: 合并多個hyperloglog

python 操作Redis HyperLogLog

from MyRedis.RedisTool import RedisToolclass RedisHLL:def __init__(self):self._conn = RedisTool.redis_connection("127.0.0.1", 8100, "redis")def hll_test(self):self._conn.pfadd('test', "junebao", "python", "redis", "hyperloglog", "java")count = self._conn.pfcount("test")print(count)if __name__ == '__main__':RedisHLL().hll_test()  # 5

HyperLogLog 算法原理

特點：

• 能使用極少的內存來統計巨量的數據，在Redis中的HyperLogLog只需要12k內存就能統計 $2^{64}$
• 計數存在一定的誤差，但誤差率整體較低，標準誤差為 0.81%
• 可以設置輔助計算因子減小誤差

LogLog 簡介

HyperLogLog 其實是 LogLog 算法的改進版，Loglog源于著名的伯努利實驗。

這個實驗是這樣的：隨機拋一枚硬幣，那么正面朝上和反面朝上的概率都應該是 50% ,那么如果一直重復拋硬幣，直到出現正面朝上，就記作1次伯努利實驗。

對于單個一次伯努利實驗，拋硬幣的次數是不確定的，有可能第一次就正面朝上，那這1次就被記為1次伯努利實驗，也有可能拋了10次才出現正面朝上，那這10次才會被記作1次伯努利實驗。

假設做了n次伯努利實驗，第一次實驗拋了 $k_1$ 次硬幣， 第二次拋了 $k_2$ 次硬幣，那么第 n 次實驗就拋了 $k_n$ 次硬幣。在 $[k_1?k_n]$ 之間，就必然存在一個最大值 $k_{max}$ , $k_{max}$的意義就是在這一組伯努利實驗中，出現正面朝上需要的最多的拋擲次數。結合極大似然估計方法得到伯努利實驗的次數 $n$ 和這個最大值 $k_{max}$ 存在關系: $$n=2^{k_{max}}$$

例如：實驗0和1表示硬幣的正反，一輪做五次實驗，某輪伯努利實驗的結果為

# 第一次
001
# 第二次
01
# 第三次
1
# 第四次
0001
# 第五次
001

那么這一輪伯努利實驗的 $k_{max}=4$ ,按照上面的公式應該得到 $5=2^4$,這個誤差顯然太過巨大，我們可以增加某一輪實驗的次數，用python模擬一下

import randomclass BernoulliExp:def __init__(self, freq: int):self.freq = freqself.option = [0, 1]def run(self):k_max = 0for i in range(self.freq):num = 0while True:num += 1result = random.choice(self.option)if result == 1:break# print(f"第{i}次伯努利實驗，拋了{num}次硬幣")if num > k_max:k_max = numreturn k_maxif __name__ == '__main__':be = BernoulliExp(5000)k_max = be.run()print(f"k_max={k_max}")

通過測試，當每一輪進行5000次伯努利實驗時，進行五輪，$k_{max}$分別為 12， 12， 14， 11， 15，誤差仍舊很大，所以我們可以進行多輪伯努利實驗，求$k_{max}$的平均值，用python模擬一下

import randomclass BernoulliExp:def __init__(self, freq: int, rounds: int, num: int):"""Args:freq: int,每輪進行多少次實驗rounds: k_max 對多少輪實驗求平均num: 進行多少次這樣的實驗（求誤差）"""self.freq = freqself.option = [0, 1]self.rounds = roundsself.number_of_trials = numdef _run_one_round(self):k_max = 0for i in range(self.freq):num = 0while True:num += 1result = random.choice(self.option)if result == 1:break# print(f"第{i}次伯努利實驗，拋了{num}次硬幣")if num > k_max:k_max = numreturn k_maxdef get_k_max(self):sum_k_max = 0for i in range(self.rounds):sum_k_max += self._run_one_round()return sum_k_max / self.roundsdef deviation(self):dev = 0for i in range(self.number_of_trials):k_max = self.get_k_max()print(f"第{i}次：k_max = {k_max}")dev += (2 ** k_max) - self.freqreturn dev/self.number_of_trialsif __name__ == '__main__':be = BernoulliExp(6, 16384, 5)dev = be.deviation()print(f"誤差：{dev}")

第0次：k_max = 4.03546142578125
第1次：k_max = 4.034423828125
第2次：k_max = 4.05010986328125
第3次：k_max = 4.02423095703125
第4次：k_max = 4.045654296875
誤差：10.427087015403654

這時誤差依舊非常大，但我們發現 $k_{max}$卻浮動在4.038上下，這就說明$n$和 $k_{max}$ 之間的關系確實存在，但公式前面還應該有一個常數項，原公式應該是 $$n=\alpha ?2^{k_{max}}$$

通過簡單計算，把 $\alpha$設為 $0.3652$:

第0次：k_max = 4.055908203125
第1次：k_max = 4.0262451171875
第2次：k_max = 4.03045654296875
第3次：k_max = 4.04534912109375
第4次：k_max = 4.048095703125
誤差：0.01269833279264585

這里0.3652是用$n=6$計算出來的，但當n取其他值時，這個因子也能基本將相對誤差控制在0.1以內。

上面的公式，便是LogLog的估算公式

$$D{V}_{LL}=constant?m?2^{\overline{R}}$$

其中 $D{V}_{LL}$就是n，constant就是調和因子， m是實驗輪數，$\overline{R}$ 是 $k_{max}$的平均值。

---

而 HyperLogLog和LogLog的區別就是使用調和平均數計算$k_{max}$，這樣如果計算的數值相差較大，調和平均數可以較好的反應平均水平，調和平均數的計算方式為：

$$H_n=\frac{n}{{\sum }_{i=1}^n\frac{1}{x_i}}$$

所以 HyperLogLog 的公式就可以寫為

$$D{V}_{HLL}=const?m?\frac{m}{{\sum }_{j=1}^m\frac{1}{2^{R_j}}}$$

在Redis中的實現方法

如果我們我們可以通過$k_{max}$來估計$n$,那同樣的，對于一個比特串，我們就可以按照這個原理估算出里面1的個數，例如在

統計一個頁面每日的點擊量（同一用戶不重復計算）

要實現這個功能，最簡單的辦法就是維持一個set，每當有用新戶訪問頁面，就把ID加入集合（重復訪問的用戶也不會重復加），點擊量就是集合的長度，但這樣做最大的問題就是會浪費很多空間，如果一個用戶ID占8字節，加入有一千萬用戶，那就得消耗幾十G的空間，但Redis只用了12k就完成了相同的功能。

首先，他把自己的12k劃分為 16834 個 6bit 大小的 “桶”，這樣每個桶所能表示的最大數字為 ${1111}_{(2)}=63$, 在存入時，把用戶ID作為Value傳入，這個value會被轉換為一個64bit的比特串，前14位用來選擇這個比特串從右往左看，第一次出現1的下標要儲存的桶號。

例如一個value經過Hash轉換后的比特串為

[0000 0000 0000 1100 01]01 0010 1010 1011 0110 1010 0111 0101 0110 1110 0110 0100

這個比特串前14位是 ${110001}_{(2)}$,轉換成10進制也就是49，而它從右往左看，第3位是1，所以3會被放到49桶中（首先要看49桶中原來的值是不是小于3，如果比3小，就用3替換原來的，否則不變，【因為桶中存的是$k_{max}$】）, $k_{max}$在這里最大也只能是64，用6bit肯定夠用。

這樣不管有多少用戶訪問網站，存儲的只有這12k的數據，訪問量越多，$k_{max}$ 越大，然后根據HyperLogLog公式，就可以較精確的估計出訪問量。（一個桶可以看作一輪伯努利實驗）

修正因子

constant 并不是一個固定的值，他會根據實際情況而被分支設置，如： $$P={\log }_{2}m$$

m 是分桶數

switch (p) {case 4:constant = 0.673 * m * m;case 5:constant = 0.697 * m * m;case 6:constant = 0.709 * m * m;default:constant = (0.7213 / (1 + 1.079 / m)) * m * m;
}

參考

https://www.cnblogs.com/linguanh/p/10460421.html#commentform

https://chenxiao.blog.csdn.net/article/details/104195908