前言
好哥哥们，接上篇Redis Bitmaps 你会了吗 。正如标题，
Bitmaps好哥哥会了吗？什么，还没看吗，那别愣着呀，赶紧看看哦。看完记得点赞加关注。讲道理应该是讲清楚了吧，Bitmaps在大数据量上的场景运用的还是挺多的（没接触过大数据量的我流下了悔恨的泪水），今天HyperLogLog这玩意也是常用于大数据量下的基数统计，不过我又没有用过，找个机会在现在的项目用用，顺便挖点坑（手动狗头保命）。
概述
首先HyperLogLog 并不是一个数据结构，而是一种基数1统计算法。通过HyperLogLog可以利用极小的内存空间完成独立总数的统计，数据集可以是 IP、Email、ID 等。因为HyperLogLog 只会根据输入元素来计算基数，而不会存储输入元素本身，所以 HyperLogLog 不能想集合那样，返回输入的各个元素。
原理
在上面有提到说HyperLogLog 使用的是概率算法，通过存储元素的hash值的第一个 1 的位置，来计算元素数量。举个栗子:
有一天小明和小红在操场上快乐的玩耍。突然小明红着脸对小红说我们来玩一个玩抛硬币的游戏，我赢的话你就做我女朋友，输了的我话我就做你男朋友，规则是我来负责抛硬币，每次抛到国徽面为一个回合，我可以决定抛几个回合，最后我会告诉你我最长的那个回合抛了多少次，然后你就来猜我一共抛了几个回合。小红红着脸说好呀，但是这不好猜呀，你先抛吧，我要算算这个概率了，于是快速在脑海中绘制了一幅图。k是每回合抛到1（1 是国徽面，0 是数字面）所用的次数，我们已知的是最大的k值，用kmax表示，由于每次抛硬币的结果只有0和1两种情况。所以，kmax 在任意回合出现的概率即为
(
1
/
2
)
k
m
a
x
(1/2) ^{kmax}
(1/2)kmax ，因此可以推测 n =
2
k
m
a
x
2 ^{kmax}
2kmax 。概率学把这种问题叫做伯努利实验2。
然后小明已经完成了 n 个回合，并且告诉小红最长的一次抛了 3 次。小红胸有成竹，马上说出他的答案 8，最后的结果是：小明只抛了一回合，小红输了生气的对小明说玩游戏都不让女朋友赢你个渣男，你走吧，我们不可能了（没想到吧，哈哈哈哈）。
细心的好哥哥能发现上面的的概率算法是存在问题的（导致小红都输了)，Philippe Flajolet 教授针对于于上面的问题引入了桶的概念，计算m个桶的加权平均值，这样就能得到比较准确的答案了（实际上还要进行其他修正）。最终的公式如图
回到 Redis 的HyperLogLog，对于一个新插入的字符串，首先得到 64 位的hash值，用前 14 位来定位桶的位置（共有
2
14
2 ^{14}
214，即 16384 个桶）。后面 50 位即为伯努利过程，每个桶有6bit，记录第一次出现 1 的位置count，如果count>oldcount，就用count替换oldcount。
命令
在 Redis 中操作HyperLogLog 只提供三个命令
1 添加
## 格式，key：键 element: 元素
pfadd key element [element … ]
## 添加一个元素，添加成功返回1
127.0.0.1:6379> pfadd 2020-12-14:unique:ids "uuid-1" "uuid-2" "uuid-3" "uuid-4"
(integer) 1
2 计算基数
pfcount 用于计算一个或多个HyperLogLog的独立总数
## 格式，key：键
pfcount key [key … ]
## 返回总个数
127.0.0.1:6379> pfcount 2020-12-14:unique:ids
(integer) 4
3 合并
pfmerge 可以求出多个HyperLogLog的并集并赋值给destkey
## 格式，destkey ：结果集key， sourcekey：需要合并的键
pfmerge destkey sourcekey [sourcekey ...]
## 添加2020-12-13号添加元素
127.0.0.1:6379> pfadd 2020-12-13:unique:ids "uuid-4" "uuid-5" "uuid-6" "uuid-7"
(integer) 1
## 计算2020-12-13和2020-12-14号基数
127.0.0.1:6379> pfmerge 2020-12_13_14:unique:ids 2020-12_13:unique:ids 2020-12-14:unique:ids
OK
127.0.0.1:6379> pfcount 2020-12_13_14:unique:ids
(integer) 7
内存使用
1 初始内存统计
127.0.0.1:6379> info memory
# 内存统计
used_memory:835144
used_memory_human:815.57K
2 插入批量数据
elements=""
key="020-12-14:unique:ids"
for i in `seq 1 1000000`
do
elements="${elements} uuid-"${i}
if [[ $((i%1000)) == 0 ]];
then
redis-cli pfadd ${key} ${elements}
elements=""
fi
done
3 统计使用内存
执行完添加元素操作内存只增加了 15K 左右
info memory
# 内存统计
used_memory:850616
used_memory_human:830.68K
4 准确率分析
使用pfcount的执行结果并不是 100 万
127.0.0.1:6379> pfcount 2016_05_01:unique:ids
(integer) 1009838
使用场景
HyperLogLog 内存占用量非常小，但是存在错误率。所以在使用是需要符合以下两点
- 只为了计算独立总数，不需要获取单条数据，上面说了只会存计算基数，不会存数据本身。
- 可以容忍一定误差率， 上面准确率分析也说到了。
总结
理解HyperLogLog 需要一定的算法知识，我对算法这一块也说很头疼。但是这篇下来好哥哥们应该对HyperLogLog 有一定的了解了。具体算法这个就不深入了，一个头两个大，这个重任就交给好哥哥们去钻研吧。好哥哥，冲冲冲… 弄透了记得来分享一波（手动狗头护脸）。
本期就到这啦，有不对的地方欢迎好哥哥们评论区留言，另外求关注、求点赞