广州建设网站首页,提供网站建设运营公司资质,四库一平台证书查询,广州流感最新情况Redis-HyperLogLog
基于HyperLogLog算法#xff0c;使用极小的空间完成巨量运算 Redis 中HyperLogLog 基本使用
常用命令
PFADD key element [element …]: 将任意数量的元素添加到指定的 HyperLogLog 里面。PFCOUNT key [key …]: 计算hyperloglog的独立总数prmerge destk…Redis-HyperLogLog
基于HyperLogLog算法使用极小的空间完成巨量运算 Redis 中HyperLogLog 基本使用
常用命令
PFADD key element [element …]: 将任意数量的元素添加到指定的 HyperLogLog 里面。PFCOUNT key [key …]: 计算hyperloglog的独立总数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() # 5HyperLogLog 算法原理
特点
能使用极少的内存来统计巨量的数据在Redis中的HyperLogLog只需要12k内存就能统计 2642^{64}264计数存在一定的误差但误差率整体较低标准误差为 0.81%可以设置辅助计算因子减小误差
LogLog 简介
HyperLogLog 其实是 LogLog 算法的改进版Loglog源于著名的伯努利实验。
这个实验是这样的随机抛一枚硬币那么正面朝上和反面朝上的概率都应该是 50% ,那么如果一直重复抛硬币直到出现正面朝上就记作1次伯努利实验。
对于单个一次伯努利实验抛硬币的次数是不确定的有可能第一次就正面朝上那这1次就被记为1次伯努利实验也有可能抛了10次才出现正面朝上那这10次才会被记作1次伯努利实验。
假设做了n次伯努利实验第一次实验抛了 k1k_1k1 次硬币 第二次抛了 k2k_2k2 次硬币那么第 n 次实验就抛了 knk_nkn 次硬币。在 [k1−kn][k_1 -k_n][k1−kn] 之间就必然存在一个最大值 kmaxk_{max}kmax , kmaxk_{max}kmax的意义就是在这一组伯努利实验中出现正面朝上需要的最多的抛掷次数。结合极大似然估计方法得到伯努利实验的次数 nnn 和这个最大值 kmaxk_{max}kmax 存在关系: n2kmaxn 2^{k_{max}}n2kmax
例如实验0和1表示硬币的正反一轮做五次实验某轮伯努利实验的结果为
# 第一次
001
# 第二次
01
# 第三次
1
# 第四次
0001
# 第五次
001那么这一轮伯努利实验的 kmax4k_{max}4kmax4 ,按照上面的公式应该得到 52452^4524,这个误差显然太过巨大我们可以增加某一轮实验的次数用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(fk_max{k_max})通过测试当每一轮进行5000次伯努利实验时进行五轮kmaxk_{max}kmax分别为 12 12 14 11 15误差仍旧很大所以我们可以进行多轮伯努利实验求kmaxk_{max}kmax的平均值用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这时误差依旧非常大但我们发现 kmaxk_{max}kmax却浮动在4.038上下这就说明nnn和 kmaxk_{max}kmax 之间的关系确实存在但公式前面还应该有一个常数项原公式应该是 nα⋅2kmaxn \alpha · 2^{k_{max}}nα⋅2kmax
通过简单计算把 α\alphaα设为 0.36520.36520.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是用n6n6n6计算出来的但当n取其他值时这个因子也能基本将相对误差控制在0.1以内。
上面的公式便是LogLog的估算公式
DVLLconstant∗m∗2R‾DV_{LL} constant * m * 2 ^ {\overline{R}}DVLLconstant∗m∗2R
其中 DVLLDV_{LL}DVLL就是nconstant就是调和因子 m是实验轮数R‾\overline{R}R 是 kmaxk_{max}kmax的平均值。 而 HyperLogLog和LogLog的区别就是使用调和平均数计算kmaxk_{max}kmax这样如果计算的数值相差较大调和平均数可以较好的反应平均水平调和平均数的计算方式为
Hnn∑i1n1xiH_n \frac{n}{\sum_{i1} ^ n \frac{1}{x_i}}Hn∑i1nxi1n
所以 HyperLogLog 的公式就可以写为
DVHLLconst∗m∗m∑j1m12RjDV_{HLL} const * m * \frac{m}{\sum_{j1} ^ m \frac{1}{2^{R_j}}}DVHLLconst∗m∗∑j1m2Rj1m
在Redis中的实现方法
如果我们我们可以通过kmaxk_{max}kmax来估计nnn,那同样的对于一个比特串我们就可以按照这个原理估算出里面1的个数例如在 统计一个页面每日的点击量同一用户不重复计算 要实现这个功能最简单的办法就是维持一个set每当有用新户访问页面就把ID加入集合重复访问的用户也不会重复加点击量就是集合的长度但这样做最大的问题就是会浪费很多空间如果一个用户ID占8字节加入有一千万用户那就得消耗几十G的空间但Redis只用了12k就完成了相同的功能。
首先他把自己的12k划分为 16834 个 6bit 大小的 “桶”这样每个桶所能表示的最大数字为 1111(2)63{1111}_{(2)} 631111(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){110001}_{(2)}110001(2),转换成10进制也就是49而它从右往左看第3位是1所以3会被放到49桶中首先要看49桶中原来的值是不是小于3如果比3小就用3替换原来的否则不变【因为桶中存的是kmaxk_{max}kmax】, kmaxk_{max}kmax在这里最大也只能是64用6bit肯定够用。
这样不管有多少用户访问网站存储的只有这12k的数据访问量越多kmaxk_{max}kmax 越大然后根据HyperLogLog公式就可以较精确的估计出访问量。一个桶可以看作一轮伯努利实验
修正因子
constant 并不是一个固定的值他会根据实际情况而被分支设置如 Plog2mP \log_2 mPlog2m
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
