学透 Redis HyperLogLog，看这篇就够了 _Redis

文章插图
在移动互联网的业务场景中，数据量很大，系统需要保存这样的信息：一个 key 关联了一个数据集合，同时对这个数据集合做统计做一个报表给运营人员看。
比如。

统计一个 App 的日活、月活数。
统计一个页面的每天被多少个不同账户访问量（Unique Visitor，UV）。
统计用户每天搜索不同词条的个数。
统计注册 IP 数。

通常情况下，系统面临的用户数量以及访问量都是巨大的，比如百万、千万级别的用户数量，或者千万级别、甚至亿级别的访问信息，咋办呢？

?
redis：“这些就是典型的基数统计应用场景，基数统计：统计一个集合中不重复元素，这被称为基数。”

1、是什么HyperLogLog 是一种概率数据结构，用于估计集合的基数。每个 HyperLogLog 最多只需要花费 12KB 内存，在标准误差 0.81%的前提下，就可以计算 2 的 64 次方个元素的基数。
HyperLogLog 的优点在于它所需的内存并不会因为集合的大小而改变，无论集合包含的元素有多少个，HyperLogLog 进行计算所需的内存总是固定的，并且是非常少的。
主要特点如下。

高效的内存使用：HyperLogLog 的内存消耗是固定的，与集合中的元素数量无关。这使得它特别适用于处理大规模数据集，因为它不需要存储每个不同的元素，只需要存储估计基数所需的信息。
概率估计：HyperLogLog 提供的结果是概率性的，而不是精确的基数计数。它通过哈希函数将输入元素映射到位图中的某些位置，并基于位图的统计信息来估计基数。由于这是一种概率性方法，因此可能存在一定的误差，但通常在实际应用中，这个误差是可接受的。
高速计算：HyperLogLog 可以在常量时间内计算估计的基数，无论集合的大小如何。这意味着它的性能非常好，不会受到集合大小的影响。

2、修炼心法基本原理HyperLogLog 是一种概率数据结构，它使用概率算法来统计集合的近似基数。而它算法的最本源则是伯努利过程。
伯努利过程就是一个抛硬币实验的过程。抛一枚正常硬币，落地可能是正面，也可能是反面，二者的概率都是 1/2 。
伯努利过程就是一直抛硬币，直到落地时出现正面位置，并记录下抛掷次数k 。
比如说，抛一次硬币就出现正面了，此时 k 为 1; 第一次抛硬币是反面，则继续抛，直到第三次才出现正面，此时 k 为 3 。
对于 n 次伯努利过程，我们会得到 n 个出现正面的投掷次数值 k1, k2 ... kn, 其中这里的最大值是 k_max 。
根据一顿数学推导，我们可以得出一个结论：2^{k_ max} 来作为 n 的估计值。
也就是说你可以根据最大投掷次数近似的推算出进行了几次伯努利过程。
所以 HyperLogLog 的基本思想是利用集合中数字的比特串第一个 1 出现位置的最大值来预估整体基数，但是这种预估方法存在较大误差，为了改善误差情况，HyperLogLog 中引入分桶平均的概念，计算 m 个桶的调和平均值。
Redis 内部使用字符串位图来存储 HyperLogLog 所有桶的计数值，一共分了 2^14 个桶，也就是 16384 个桶。每个桶中是一个 6 bit 的数组。
这段代码描述了 Redis HyperLogLog 数据结构的头部定义（hyperLogLog.c 中的 hllhdr 结构体）。以下是关于这个数据结构的各个字段的解释。
struct hllhdr {char magic[4];uint8_t encoding;uint8_t notused[3];uint8_t card[8];uint8_t registers[];};

magic[4]：这个字段是一个 4 字节的字符数组，用来表示数据结构的标识符。在 HyperLogLog 中，它的值始终为"HYLL"，用来标识这是一个 HyperLogLog 数据结构。
encoding：这是一个 1 字节的字段，用来表示 HyperLogLog 的编码方式。它可以取两个值之一：