Docs
Redis
核心设计与原理
HyperLogLog

HyperLogLog

如果你负责开发维护一个大型的网站，有一天老板找产品经理要网站每个网页每天的 UV（用户访问量，一个用户一天不论访问一次还是多次，都只算一次）数据，然后让你来开发这个统计模块，如何实现？

如果统计 PV（页面访问量，只要页面被访问一次，就算一次，不管用户访问了多少次）那非常好办，给每个网页一个独立的 Redis 计数器就可以了，这个计数器的 key 后缀加上当天的日期。这样来一个请求，incrby 一次，最终就可以统计出所有的 PV 数据。

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

一个非常简单的方案：

为每一个页面一个独立的 set 集合来存储所有当天访问过此页面的用户 ID。当一个请求过来时，使用 sadd 将用户 ID 塞进去就可以了。通过 scard 可以取出这个集合的大小，这个数字就是这个页面的 UV 数据。

但是，如果页面访问量非常大，比如一个爆款页面几千万的 UV，就需要一个很大的 set 集合来统计，这就非常浪费空间。如果这样的页面很多，还需要为每个页面都去创建一个 set 集合，那所需要的存储空间是惊人的。

Redis 提供了 HyperLogLog 数据结构就是用来解决这种统计问题的。HyperLogLog 提供不精确的去重计数方案，虽然不精确但是也不是非常不精确，可以满足上面的 UV 统计需求了。

使用

HyperLogLog 提供了两个指令 pfadd 和 pfcount，根据字面意义很好理解，一个是增加计数，一个是获取计数。

127.0.0.1:6379> pfadd 08-15:u:id user1
(integer) 1
127.0.0.1:6379> pfcount 08-15:u:id
(integer) 1
127.0.0.1:6379> pfadd 08-15:u:id user2
(integer) 1
127.0.0.1:6379> pfcount 08-15:u:id
(integer) 2
127.0.0.1:6379> pfadd 08-15:u:id user3
(integer) 1
127.0.0.1:6379> pfcount 08-15:u:id
(integer) 3
127.0.0.1:6379> pfadd 08-15:u:id user4
(integer) 1
127.0.0.1:6379> pfcount 08-15:u:id
(integer) 4
127.0.0.1:6379> pfadd 08-15:u:id user5
(integer) 1
127.0.0.1:6379> pfcount 08-15:u:id
(integer) 5
127.0.0.1:6379> pfadd 08-15:u:id user6
(integer) 1
127.0.0.1:6379> pfcount 08-15:u:id
(integer) 6
127.0.0.1:6379> pfadd 08-15:u:id user7 user8 user9 user10
(integer) 1
127.0.0.1:6379> pfcount 08-15:u:id
(integer) 10

但是在数据量比较大的时候，pfcount 的结果就会出现误差。

以使用集合类型和 HperLogLog 统计百万级用户访问次数的占用空间对比：

数据类型1天1个月1年
集合类型80M2.4G28G
HyperLogLog15k450k5M

可以看到，HyperLogLog 内存占用量小得惊人，但是用如此小空间来估算如此巨大的数据，必然不是 100% 的正确，其中一定存在误差率。前面说过，Redis 官方给出的数字是 0.81% 的失误率。

pfmerge

pfmerge 用于将多个 pf 计数值累加在一起形成一个新的 pf 值。

比如在网站中我们有两个内容差不多的页面，运营说需要这两个页面的数据进行合并。其中页面的 UV 访问量也需要合并，那这个时候 pfmerge 就可以派上用场了。

HyperLogLog 原理

基本原理

HyperLogLog 基于概率论中伯努利试验并结合了极大似然估算方法，并做了分桶优化。

实际上目前还没有发现更好的在大数据场景中准确计算基数的高效算法，因此在不追求绝对准确的情况下，使用概率算法算是一个不错的解决方案。概率算法不直接存储数据集合本身，通过一定的概率统计方法预估值，这种方法可以大大节省内存，同时保证误差控制在一定范围内。目前用于基数计数的概率算法包括:

  • Linear Counting(LC)：早期的基数估计算法，LC 在空间复杂度方面并不算优秀。
  • LogLog Counting(LLC)：LogLog Counting相比于 LC 更加节省内存，空间复杂度更低。
  • HyperLogLog Counting(HLL)：HyperLogLog Counting 是基于 LLC 的优化和改进，在同样空间复杂度情况下，能够比 LLC 的基数估计误差更小。

举个例子来理解 HyperLogLog 算法，有一天 Fox 老师和 Mark 老师玩抛硬币的游戏，规则是 Mark 老师负责抛硬币，每次抛的硬币可能正面，可能反面，每当抛到正面为一回合，Mark 老师可以自己决定进行几个回合。最后需要告诉 Fox 老师最长的那个回合抛了多少次以后出现了正面，再由 Fox 老师来猜 Mark 老师一共进行了几个回合。

hll

进行了 n 个回合试验，比如上图：

第一次: 抛了 3 次才出现正面，此时 `k=3，n=1`。
第二次试验: 抛了 2 次才出现正面，此时 `k=2，n=2`。
第三次试验: 抛了 4 次才出现正面，此时 `k=4，n=3`。
…………
第 n 次试验：抛了 7 次才出现正面，此时我们估算，`k=7，n=n`。

k 是每回合抛到 1（硬币的正面）所用的次数，我们已知的是最大的 k 值，也就是 Mark 老师告诉 Fox 老师的数，可以用 k_max 表示。由于每次抛硬币的结果只有 0 和 1 两种情况，因此，能够推测出 k_max 在任意回合出现的概率 ，并由 kmax 结合极大似然估算的方法推测出 n = 2^(k_max)。概率学把这种问题叫做伯努利实验。

现在 Mark 老师已经完成了 n 个回合，并且告诉 Fox 老师最长的一次抛了 4 次，Fox 老师此时也胸有成竹，马上说出他的答案 16，最后的结果是：Mark 老师只抛了 3 回合，这三个回合中 k_max=4，放到公式中，Fox 老师算出 n=2^4，于是推测 Mark 老师抛了 16 个回合，但是 Fox 老师输了。

所以这种预估方法存在较大误差，为了改善误差情况，HLL 中引入分桶平均的概念。

同样举抛硬币的例子，如果只有一组抛硬币实验，显然根据公式推导得到的实验次数的估计误差较大；如果 100 个组同时进行抛硬币实验，样本数变大，受运气影响的概率就很低了，每组分别进行多次抛硬币实验，并上报各自实验过程中抛到正面的抛掷次数的最大值，就能根据 100 组的平均值预估整体的实验次数了。

分桶平均的基本原理是将统计数据划分为 m 个桶，每个桶分别统计各自的 k_max,​ 并能得到各自的基数预估值，最终对这些基数预估值求平均得到整体的基数估计值。LLC 中使用几何平均数预估整体的基数值，但是当统计数据量较小时误差较大；HLL 在 LLC 基础上做了改进，采用调和平均数过滤掉不健康的统计值。

调和平均数

举个例子：

求平均工资：A 的是 1000/月，B 的 30000/月。采用平均数的方式就是：(1000 + 30000) / 2 = 15500

采用调和平均数的方式就是：2/(1/1000 + 1/30000) ≈ 1935.484。

可见调和平均数比平均数的好处就是不容易受到大的数值的影响，比平均数的效果是要更好的。

结合实例

下面我们结合实例来理解 HyperLogLog 算法。

统计网页每天的 UV 数据。

  1. 转为比特串

通过 hash 函数，将用户 ID 转为二进制数，例如用户 ID 为 5，便转为 101。

为什么要这样转化呢？

是因为要和抛硬币对应上，二进制数中，0 代表了反面，1 代表了正面，如果一个数据最终被转化了 10010000，那么从右往左，从低位往高位看，我们可以认为，首次出现 1 的时候，就是正面。

那么基于上面的估算结论，我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验，同样也就可以根据存入数据中，转化后的出现了 1 的最大的位置 k_max 来估算存入了多少数据。

  1. 分桶

分桶就是分多少轮。就是一个长度为 L 的 bitmap S，将 S 平均分为 m 组，这个 m 组，就是对应多少轮，然后每组所占有的比特个数是平均的，设为 P。容易得出下面的关系：

  • L = S.length
  • L = m * p

以 KB 为单位，S 占用的内存 = L / 8 / 1024。

  1. 对应

假设访问用户 ID 为：idn, n->0,1,2,3....

在这个统计问题中，不同的用户 ID 标识了一个用户，那么我们可以把用户的 ID 作为被 hash 的输入。即：hash(id) = 二进制数。

不同的用户 ID，拥有不同的二进制数。每一个二进制数，也必然会至少出现一次 1 的位置。我们类比每一个二进制数为一次伯努利试验。

现在要分轮，也就是分桶。所以我们可以设定，每个二进制数的前多少位转为 10 进制后，其值就对应于所在桶的标号。假设二进制数的低两位用来计算桶下标志，总共有 4 个桶，此时有一个用户的 ID 的二进制数是：1001011000011。它的所在桶下标为：1*2^1 + 1*2^0 = 3，处于第 3 个桶，即第 3 轮中。

上面例子中，计算出桶号后，剩下的二进制数是：10010110000，从右往左，从低位到高位看，第一次出现 1 的位置是 5 。也就是说，此时第 3 个桶中，k_max = 5。5 对应的二进制是：101，将 101 存入第 3 个桶。

模仿上面的流程，多个不同的用户 ID，就被分散到不同的桶中去了，且每个桶有其 k_max。然后当要统计出某个页面有多少用户点击量的时候，就是一次估算。最终结合所有桶中的 k_max，代入估算公式，便能得出估算值。

Redis 中的 HyperLogLog 实现

Redis 的实现中，HyperLogLog 占据 12KB 的大小，共设有 16384 个桶，即：2^14 = 16384，每个桶有 6 位 (占用内存=16834 * 6 / 8 / 1024 = 12K)，每个桶可以表达的最大数字是：111111=63。

对于命令：pfadd key value，它的工作原理是：

在存入时，value 会被 hash 成 64 位的二进制数，前 14 位用来分桶，剩下 50 位用来记录第一个 1 出现的位置。之所以选 14 位来表达桶编号是因为分了 16384 个桶，而 2^14 = 16384，刚好地，最大的时候可以把桶利用完，不造成浪费。假设一个字符串的前 14 位是：00000000000010 (从右往左看) ，其十进制值为 2。那么 value 对应转化后的值放到编号为 2 的桶。

index 的转化规则：

首先因为完整的 value 比特字符串是 64 位形式，减去 14 后，剩下 50 位，假设极端情况，出现 1 的位置，是在第 50 位，即位置是 50。此时 index = 50。此时先将 index 转为 2 进制，它是：50=110010，所以 6 bit 的桶足够表示。

因为 16384 个桶中，每个桶是 6 bit 组成的。于是 110010 就被设置到了第 2 号桶中去了。请注意，50 已经是最坏的情况，且它都被容纳进去了。那么其他的不用想也肯定能被容纳进去。

因为 pfadd 的 key 可以设置多个 value。例如下面的例子：

pfadd lgh golang
pfadd lgh python
pfadd lgh java

根据上面的做法，不同的 value，会被设置到不同桶中去，如果出现了在同一个桶的，即前 14 位值是一样的，但是后面出现 1 的位置不一样。那么比较原来的 index 是否比新 index 大。是，则替换。否，则不变。

最终，一个 key 所对应的 16384 个桶都设置了很多的 value 了，每个桶有一个 k_max。此时调用 pfcount 时，按照调和平均数进行估算，同时加以偏差修正，便可以计算出 key 的设置了多少次 value，也就是统计值。

value 被转为 64 位的比特串，最终被按照上面的做法记录到每个桶中去。64 位转为十进制就是：2^64，HyperLogLog 仅用了：16384 * 6 /8 / 1024 =12K 存储空间就能统计多达 2^64 个数。

最后更新于
GeoHashRedis 的过期策略和内存淘汰机制