HyperLogLog

HLL常用于去重统计（会有一定的误差），例如统计一个页面每天的访问量（每个用户一天访问多次也只能算一次，即UV），注意这里是UV，

如果是PV比较好办，给每个网页配一个独立的计数器即可，把这个计数器的key后缀加上当天的日期，这样每来一个请求，执行incrby指令一次，直接递增即可，最终可以统计出所有的PV，

但是UV不同，需要去重，一般去重可能考虑使用set集合去做，例如存储当天访问该页面的所有用户ID，当一个请求过来的时候，我们使用sadd将用户id塞进去即可，通过scard可以取出这个集合的大小看，这个数字就是这个页面的UV数据，这个方案看似可行，

但是如果一个页面的访问量非常大，一个页面可能有几千万个UV，那就需要很大的set集合来统计，非常浪费空间，如果这样的页面很多，那么将耗费更大的存储空间，

一般页面的访问次数统计并不需要十分精确，例如105万和106万差别并不大，HLL就是一种解决方案，可以做到去重计数的同时，还节省很多的空间，虽然不精准，但是差的并不离谱，标准误差是0.81%，这样的精准度一般可以满足UV统计需求了。

pfadd/pfcount

HLL提供了两个指令 pfadd/pfcount, 一个是增加计数，一个是获取计数，pfadd和set集合的sadd用法一样，来一个用户ID直接添加进去，pfcount则和scard用法一样，直接获取计数值。

127.0.0.1:6379> pfadd hll user1  # 给hll可以添加一个 user1 的用户id，下面都一样

(integer) 1

127.0.0.1:6379> pfadd hll user2  

(integer) 1

127.0.0.1:6379> pfadd hll user3  

(integer) 1

127.0.0.1:6379> pfadd hll user4

(integer) 1

127.0.0.1:6379> pfadd hll user4 # 此处又添加了一个user4，被过滤

(integer) 0

127.0.0.1:6379> pfadd hll user4

(integer) 0

127.0.0.1:6379> pfcount hll  # 获取总数，发现是4，说明去重成功

(integer) 4

127.0.0.1:6379> pfadd hll user5 user6 user7  # 新添加三个用户id

(integer) 1

127.0.0.1:6379> pfcount hll  # 计数成功

(integer) 7

可以从上面的结果发现，效果很好，结果也是正确的，没有出现所谓的误差率，这是因为我们的数据暂时还太少，下面我们使用脚本多跑一些数据，看看误差率会不会出现。

可以看到，我们一次性添加了10w个数据，最后获取到的总数和预期相差了0.277%，这就是误差了，不会那么精准，

同样的数据再跑一次，你会发现出来的结果和上面的相同，证明了HLL确实是可以去重的，

代码地址：https://github.com/qiaomengnan16/redis-demo/tree/main/redis-hll

pfmerge

HLL除了pfadd/pfcount之外，还提供了一个叫 pfmerge的指令，用于将多个pf计数值累加在一起形成一个新的pf值，

有什么作用呢？比如在网站上有两个内容差不多的页面，如果有天这两个页面需要进行合并，UV访问量也需要合并，此时就可以用pfmerge将这两个页面的计数值，放在一起了。

127.0.0.1:6379> pfadd hll1 a b c # hll1 的页面

(integer) 1

127.0.0.1:6379> pfadd hll2 e f g # hll2 的页面

(integer) 1

127.0.0.1:6379> pfcount hll1  # hll1页面的总数

(integer) 3

127.0.0.1:6379> pfcount hll2  # hll2页面的总数

(integer) 3

127.0.0.1:6379> pfmerge hll3 hll1 hll2 # 合并两个页面的总数到hll3中

OK

127.0.0.1:6379> pfcount hll3 # 查看hll3结果

(integer) 6

根据下方的demo同时可以发现，两个uv合并的时候也是会去重的，例如两个页面都有abc，合并在一起的时候，也会进行过滤。

127.0.0.1:6379> pfadd hll1 a b c

(integer) 1

127.0.0.1:6379> pfadd hll2 e f g

(integer) 1

127.0.0.1:6379> pfadd hll2 a b c

(integer) 1

127.0.0.1:6379> pfcount hll1

(integer) 3

127.0.0.1:6379> pfcount hll2

(integer) 6

127.0.0.1:6379> pfmerge hll3 hll1 hll2

OK

127.0.0.1:6379> pfcount hll3

(integer) 6

空间占用

HLL需要占据12KB的存储空间，一般用户量非常小的情况下可能没有空间成本的优势，但是如果用户非常多的情况下的话，12KB节省的存储空间就非常多了，相比Set存储方案，HLL使用的空间只能算是九牛一毛，

Redis对HLL的存储进行了优化，在计数比较小的时候，存储空间采用稀疏矩阵存储，空间占用很小，仅仅在计数慢慢变大、稀疏矩阵占用空间渐渐超过了阈值时，才会一次性变成稠密矩阵，占据12KB空间。