redis HyperLoglog解决基数统计问题

基数统计

基数统计(Cardinality Counting) 通常是用来统计一个集合中不重复的元素个数，例如统计网站上每个网页的 UV(独立访客，每个用户每天只记录一次)

如果统计 PV(浏览量，用户没点一次记录一次)，给每个页面配置一个独立的 Redis 计数器就可以了，把这个计数器的 key 后缀加上当天的日期。这样每来一个请求，就执行 INCRBY 指令一次，最终就可以统计出所有的 PV 数据了。

但是 UV 不同，同一个用户一天之内的多次访问请求只能计数一次。这就要求了每一个网页请求都需要带上用户的 ID，无论是登录用户还是未登录的用户，都需要一个唯一 ID 来标识。

可以为每一个页面设置一个独立的 set 集合来存储所有当天访问过此页面的用户 ID。

但是如果网站访问量一大，你需要用来存储的 set 集合就会非常大，同时聚合统计起来非常复杂。

基数统计的常用方法

B 树

B 树最大的优势就是插入和查找效率很高，如果用 B 树存储要统计的数据，可以快速判断新来的数据是否存在，并快速将元素插入 B 树。要计算基础值，只需要计算 B 树的节点个数就行了。

不过将 B 树结构维护到内存中，能够解决统计和计算的问题，但是并没有节省内存。

bitmap

bitmap 通过一个 bit 数组来存储特定数据的一种数据结构，每一个 bit 位都能独立包含信息，bit 是数据的最小存储单位，因此能大量节省空间，也可以将整个 bit 数据一次性 load 到内存计算。如果定义一个很大的 bit 数组，基础统计中每一个元素对应到 bit 数组中的一位

bitmap 还有一个明显的优势是可以轻松合并多个统计结果，只需要对多个结果求异或就可以了，也可以大大减少存储内存。可以简单做一个计算，如果要统计 1 亿个数据的基数值，大约需要的内存：100_000_000/ 8/ 1024/ 1024 ≈ 12 M，如果用 32 bit 的 int 代表 每一个 统计的数据，大约需要内存：32 * 100_000_000/ 8/ 1024/ 1024 ≈ 381 M

可以看到 bitmap 对于内存的节省显而易见，但仍然不够。统计一个对象的基数值就需要 12 M，如果统计 1 万个对象，就需要接近 120 G，对于大数据的场景仍然不适用。

概率算法

实际上目前还没有发现更好的在大数据场景 中 准确计算 基数的高效算法，因此在不追求绝对精确的情况下，使用概率算法算是一个不错的解决方案。

概率算法不直接存储数据集合本身，通过一定的概率统计方法预估基数值，这种方法可以大大节省内存，同时保证误差控制在一定范围内。

HyperLogLog概率算法

HyperLogLog算法的基础是观察到可以通过计算集合中每个数字的二进制表示中的前导零的最大数目来估计均匀分布的随机数的多重集的基数。如果观察到的前导零的最大数目是n，则集合中不同元素的数量的估计是2^n。

在HyperLogLog算法中，将哈希函数应用于原始多集中的每个元素，以获得具有与原始多集相同基数的均匀分布的随机数的多集。然后可以使用上述算法来估计该随机分布集合的基数。在HyperLogLog算法中，通过将多集合分成多个子集，计算这些子集中每个子集中的数字中的前导零的最大数量，并使用调和平均数 Harmonic mean将每个子集的这些估计值合并为全集的基数。

HyperLogLog 的表现是惊人的，上面我们简单计算过用 bitmap 存储 1 个亿 统计数据大概需要 12 M 内存，而在 HyperLoglog 中，只需要不到 1 K 内存就能够做到！在 Redis 中实现的 HyperLoglog 也只需要 12 K 内存，在标准误差 0.81% 的前提下，能够统计 264 个数据。

HyperLogLog命令

PFADD

• 将指定的元素添加到指定的HyperLogLog 结构中。
• 如果一个HyperLogLog的估计的近似基数在执行命令过程中发了变化， PFADD 返回1，否则返回0。

PFCOUNT

• 参数为一个key时,返回存储在HyperLogLog结构体的该变量的近似基数，如果该变量不存在,则返回0。
• 当参数为多个key时，返回这些HyperLogLog**并集**的近似基数，这个值是将所有给定key的HyperLoglog结构合并到一个临时的HyperLogLog结构中计算而得到的。
• 返回的可见集合基数并不是精确值， 而是一个带有 0.81% 标准错误（standard error）的近似值。

PFMERGE

• 将多个 HyperLogLog 合并（merge）为一个 HyperLogLog ， 合并后的 HyperLogLog 的基数接近于所有输入 HyperLogLog 的可见集合（observed set）的并集。
• 合并得出的 HyperLogLog 会被储存在目标变量（第一个参数）里面， 如果该键并不存在， 那么命令在执行之前， 会先为该键创建一个空的。