Redis HyperLogLog

HyperLogLog一般用作基数统计，如统计网站访问量，视频播放量啊等。

在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数。这和计算基数时，元素越多耗费内存就越多的集合形成鲜明对比。

 

HyperLogLog怎么实现的

HyperLogLog只需要花费12kb，就可以计算这么多基数。很明显，不是通过直接存储元素值比较实现的。那么既然不存储元素，是否这种存储方式也有误差呢？

查看其实现原理，其实就是用概率算法来统计集合的近似基数。

伯努利过程

伯努利过程就是一个抛硬币实验的过程。一直抛硬币，直到第一次出现正面位置为止，记录下抛掷次数k，此时就为一次伯努利试验。

可以通过抛掷次数k近似的推算总共进行了多少次(此处使用n表示)伯努利实验。

假设有如下实现：

第一次试验: 抛了3次才出现正面，此时 k=3

第二次试验: 抛了2次才出现正面，此时 k=2

第三次试验: 抛了6次才出现正面，此时 k=6

第n 次试验：抛了15次才出现正面，此时我们估算， n = 2^15

根据一顿数学推导(自行查阅资料)，我们可以得出一个结论，n=2^max(k)

假设我们取前三次实现来看，根据公式，我们的n=2^6=64，实际我们只进行了3次实验，实际上n=3，所以在数量少的情况下这个概率误差是很大的。

估算优化

还是使用上面的例子，我们进行了三次实验，如果根据公式得到结果n=2^6明细误差大，我们通过求平均值的方法，增加实验次数，修正误差，如同样进行三次伯努利实验，我们重复1000次，取结果的平均值.

 

这里计算的结果就是对应上面说的结果n

am：常数，经验值的修正系数

m：重复次数，如上面提到的重复1000次

Mj：这里就是我们前面提到的k

这种通过增加试验轮次，取平均数的算法优化就是LogLog的做法

而HyperLogLog是取的调和平均数

举例说明：

A有200块钱，B有400块钱

LOGLOG的平均数计算方法为：(200+400)/2=300

HyperLogLog的平均数计算方法为：2/(1/200+1/400)=216.666

 

redis的HyperLogLog

 

Redis 中 HyperLogLog 一共分了 2^14 个桶，也就是 16384 个桶。每个桶大小为6bit，可表示长度为2^6=64。所以HyperLogLog的大小为2^14*6/8/1024kb。

 

当一个元素进来，会通过hash函数，将元素转换为64为的比特值，比特值的最后14位作为桶的index，刚好对应2^14个桶，决定将元素存储到哪个桶的位置，前50位通过从右往左数，第一次出现1的位置的index值，如...001010000，第一次出现1的位置从右往左数就是5，将该值存储到每个桶 的6bit位置，即000101，6bit最多可以表示2^6=64，所以是可以表示完50位长度的数据的。如果在存放的时候发现该位置已经有值了，那就存放值更大的到6bit位置上。

从里面可以看出redis对内存的极致最求，不浪费一点一滴。同时如果数据小的时候，还会通过稀疏存储，具体可自行查阅资料稀疏数组的结构，自行阅读，这里不再赘述。

 

详细说明：

推荐一个在线模拟数据的网站：http://content.research.neustar.biz/blog/hll.html

注意这个网站的数据

前面提到的HyperLogLog 的桶是2^14个，这里实现的桶是2^6个，取元素的后6位计算桶的位置

HyperLogLog 的前50位存储第一次出现1的位置，这里取的是前15位，所以value最大是15

 

图中表示了，Value的存放过程，值15,441,201通过hash计算得到hash Value=3,156,493,611，用二进制表示为001001000100010100101011，其中最后六位“101011”表示桶的位置，十进制值为43，所以放到43号桶，前面15位001000100010100第一次(从右往左数)出现1的位置为3，所以43位存放的结果为3。