Redis数据结构——HyperLogLog

By | 9月 10, 2017

HyperLogLog结构用于统计基数,因为基数是不重复的,所以一个大的数据集,其基数会小很多,占用很少的空间。

HyperLogLog的标准错误是1.04 / sqrt(m),其中“m”是使用的寄存器数。
Redis使用16384个寄存器,因此标准错误为0.81%。

由于Redis实现中使用的散列函数具有64位输出,并且我们使用14位的散列输出来寻址16k寄存器,所以剩下50位,所以我们可以遇到的最长的零运行将适合一个6位寄存器。这就是为什么Redis HyperLogLog值仅对16k寄存器使用12k字节的原因。

由于使用了64位输出功能,对于我们可以计算的集合的基数没有实际的限制。此外值得注意的是,非常小的基数的误差往往很小。

命令前缀为“PF”,以纪念Philippe Flajolet,后半部分则比较容易记住:PFadd-增加,PFcount-统计,PFmerge-合并。

hyperloglog示例如下:

127.0.0.1:6379> pfadd log1 a b c d               #向指定key中添加数据,如果成功则返回1
(integer) 1
127.0.0.1:6379> pfadd log1 a b a a               #如果添加的数据是key中已有的,则返回0,添加失败
(integer) 0
127.0.0.1:6379> pfadd log1 f c d a
(integer) 1
127.0.0.1:6379> pfcount log1                     #利用pfcount命令可以查看数据集的基数是多少。
(integer) 5
127.0.0.1:6379> pfadd log1 a v r a
(integer) 1
127.0.0.1:6379> pfadd log2 y u i o p a
(integer) 1
127.0.0.1:6379> pfcount log1 log2               #利用pfcount命令也可以查看多个数据集的基数总和
(integer) 12
127.0.0.1:6379> pfcount log1 
(integer) 7
127.0.0.1:6379> pfcount log2
(integer) 6
127.0.0.1:6379> pfmerge log0 log1 log2         #pfmerge命令则是将两个hyperloglog存储到一个基数集
OK
127.0.0.1:6379> pfcount log0
(integer) 12
127.0.0.1:6379> 

 

发表评论

您的电子邮箱地址不会被公开。