基数计数

在应用系统的开发中，我们常常会有类似这样的需求：统计某个网站的UV、用户搜索网站关键词的数量等等。我们可以使用基数计数来做这个功能。基数计数通常用来统计一个集合中不重复的元素个数。

在应用程序的数据分析、网络监控及数据库优化等等地方都需要基数计数。

要实现基数计数，最简单的方式就是使用一个set，把出现的元素add进去，然后计算set的size。但如果数据量较大，使用set就会浪费大量的空间。

前面的文章介绍了bitmaps，使用bitmaps也可以做基数计数。但如果数据量较大，使用bitmaps同样会有这个问题。如果要统计一亿个数据的基数值，大约需要12M内存。如果使用32位的int类型来代表每个数据，就需要32 * 12约为381M。

可见，使用bitmaps还是不适用大数据量下的基数计数场景。

概率算法

连bitmaps都不合适，那还有更好的方法来实现大数据的基数计数吗？

当然有，数学是神奇的。我们使用一些概率论的数学原理，在一定误差条件下，可以高效地估计出基数的近似值。

具体是什么算法呢？

LogLog Counting(LLC)被发明出来解决这个问题，空间复杂度只有log(log(N))。但LLC误差较大，HyperLogLog Counting(HLL)在LLC的基础上进行了改进，在同样空间复杂度情况下，能够比LLC的基数估计误差更小。

HLL有多强大？redis中实现的HyperLogLog，只需要12K内存，在标准误差0.81%的前提下，能够统计2^64个数据。

但是，因为HyperLogLog只会根据输入元素来计算基数，而不会储存输入元素本身，所以HyperLogLog不能像集合那样，返回输入的各个元素。

HLL的原理

以下内容请谨慎食用

HyperLogLog算法来源于论文《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》

举一个例子，假设你抛很多次硬币，如果抛到正面，就继续抛；如果抛到反面，就记录下在这之前连续抛到了多少次正面k，然后开始下一轮。

如果你告诉我，你最多的时候，连续抛了2次正面后就抛到反面了。那我认为你可能并没有抛多少轮，可能是3轮或者4轮就会发生这样的情况。

但如果你告诉我，你最多的时候，连续抛了10次正面后就抛到反面了，那我认为你可能抛的轮次比较多，因为连续抛到10次正面的概率是非常小的。那如果要根据这个已知信息估计你总共抛了多少轮硬币呢？这就是HLL的原理。

HLL背后是一个著名的数学上的概率论原理：伯努利分布。同样是上面那个抛硬币例子，出现正反面的概率都是1/2，一直抛硬币直到出现正面，记录下投掷次数k，将这种抛硬币多次直到出现正面的过程记为一次伯努利过程，对于n次伯努利过程,我们会得到n个出现正面的投掷次数值k1, k2, k3……kn，其中最大值记为k_max，可以用n次实验中最大的抛掷次数k_max来预估实验组数量n： 有以下公式

n = 2 ^ k_max

具体推导过程有点麻烦，感兴趣的朋友可以下来自己去研究一下。

回到基数统计的问题，我们需要统计一组数据中不重复元素的个数，集合中每个元素的经过hash函数后可以表示成0和1构成的二进制数串，一个二进制串可以类比为一次抛硬币实验，1是抛到正面，0是反面。

二进制串中从低位开始第一个1出现的位置可以理解为抛硬币试验中第一次出现正面的抛掷次数k，那么基于上面的结论，我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验，同样可以可以通过第一个1出现位置的最大值k_max来预估总共有多少个不同的数字（整体基数）。

那根据上面的公式，就可以计算出基数n了。

但这样误差还是有点大，而且只能是2的指数，显然并不合理。

既然误差大，那就想办法降低误差。LLC的做法是把所有的数分到不同的桶中，得到每个桶的估计值n1, n2, n3……然后计算它们的几何平均数。

但这样误差还是有点大，特别是在数据量不大的时候，某个n可能会比较大，会大幅拉升整体的评论数。比如我的工资是1000元，老板的工资是10,000元，那我们工资的几何平均数就是(1000 + 10,000) / 2 = 50500元。看来我又“被平均”了，我觉得这样并不公平，不能显示我们公司真实的薪资状况。于是我们使用调和平均数的方式来计算：

2 / (1/1000 + 1/10,000) = 1980.2

嗯，这样看起来是比较接近真实水平的。“调和平均数”的结果会倾向于集合中比较小的数。而HLL正是在LLC的基础上，使用了调和平均数。

Redis的HLL实现

Redis在2.8.9版本添加了HyperLogLog结构。

Redis首先对元素进行hash，生成64bit的数。其中14bit用来分桶，其余50位用来计算n值。每个桶所占用的元素是相对平均的。

它的实现中，设有16384个桶，即：2^14 = 16384，每个桶有6位，桶中存放的是这个桶的k_max的值，每个桶可以表达的最大数字是63，二进制为：111 111。所有桶加起来占用内存为=16834 * 6 / 8 / 1024 = 12K。

第0组     第1组                       .... 第16833组 [000 000] [000 000] [000 000] [000 000] .... [000 000]

为什么是14位，为什么是16384个桶？这是根据“相对标准误差”(relative standard deviation，简称RSD)公式计算得来的。RSD的值与分桶数m存在如下的计算关系：

因为我们可以将每个元素的hash值的二进制表示的前几位用来指示数据属于哪个桶，所以桶的数量必定是2的指数。前文提到了，Redis的标准误差是0.81%，所以得到m为2^14。

Redis在元素很少的时候使用的是稀疏矩阵，所以并不会用到12k。

Java的HLL实现

stream-lib是一个开源的Java流式计算库，里面有很多大数据估值算法的实现，里面就有HyperLogLog算法，HyperLogLog实现类的代码地址如下，有兴趣的朋友可以去研究一下：github.com/addthis/str…

Redis HLL的使用

Redis中HLL主要有三个命令：PFADD、PFCOUNT、PFMERGE。分别是添加、统计、合并两个key。

PF是什么意思？

它是HyperLogLog这个数据结构的发明人Philippe Flajolet的首字母缩写