算法"/>
HyperLogLog算法
前言
现在很多站点基本都有统计 PV 和 UV 的需求，PV 的统计很简单，在 Redis 里面维护一个计数器，页面每访问一次计数器就 +1，获取 PV 就是读取计数器的值。
相比之下，UV 的统计就比较麻烦了，因为要对用户去重，UV 统计其实就是基数统计，最简单的做法就是记录下集合中所有不重复的元素。
比如，你可以用 Set 来统计，Set 不会存储重复的元素，用户每次访问都把 UserID 写入 Set 集合，最终调用 SCARD 命令获取集合元素数量即可。
> sadd uv 1001 1002 1003
(integer) 3
> scard uv
(integer) 3
使用 Set 的缺点是太耗内存了，假设 UserID 是 Long 类型，占用 8 字节，Set 底层用哈希表存储，Key 是 UserID，Value 是空值，但是指针本身还是会消耗 8 字节，即一个 Entry 占用 16 字节，存储一亿个 UserID 大约占用 1.49G。
或者，你还可以用 BitMap 来统计。哪个用户访问了页面，就把 UserID 对应的位设为 1，最后统计 1 的数量即可。假设有一亿个用户，就需要一亿个 Bit，大约 12MB，相比 Set 确实节省了很多内存，但是仍然不够省，假设有一千个页面需要统计，就需要消耗约 12GB 的空间。
无论是 Set 还是 BitMap 实现，它们都直接或间接的存储了元素，这种方式带来的问题是：占用的内存空间会随着统计的数据量线性增长。
在统计学里还有一种基于概率的统计算法，它不存储元素本身，所以极其节省内存，但它牺牲的是准确率。HyperLogLog 就是一种基于概率的统计算法，它仅需少量的内存空间，就可以统计超大规模的数据量，在不追求绝对准确的场景下，更推荐使用这种算法。
HyperLogLog
Redis 提供了 HyperLogLog 数据类型，使用极其简单，PFADD 命令把值写入到 HyperLogLog；PFCOUNT 命令对 HyperLogLog 做基数估算。
> pfadd uv 1001 1002 1003
(integer) 1
> pfcount uv
(integer) 3
确实可以实现我们的需求，你查阅文档发现每个 HyperLogLog 仅仅占用 12KB，就可以统计 2^64 个基数，而且误差率基本在0.81%，这效率高的离谱啊，怎么做到的呢？
最大似然估计
HyperLogLog 只有 12KB 的空间，它打死也存不下2^64个元素，所以你是无法奢求它能做到精确统计的。换言之，HyperLogLog 本身并不存储元素，它只存储元素极端值的特点，然后对基数做估算。
这里面涉及到一个数学原理：最大似然估计（MLE）
最大似然估计(maximum likelihood estimation)是一种重要而普遍的求估计量的方法。最大似然法明确地使用概率模型，其目标是寻找能够以较高概率产生观察数据的系统发生树。最大似然法是一类完全基于统计的系统发生树重建方法的代表。
通俗的理解就是，利用已知的样本数据，来反推出可能性最高的模型参数。
举个例子，现在有一个黑盒，里面放了 M 数量的白球，N 数量的黑球。你现在每次从黑盒里取出一个球记录下颜色再放回去，反复取 100 次，结果是 99 次白球，1 次黑球。由此我们可以推理出，黑盒里极有可能放了 99 个白球，1 个黑球。这个推算结果可能并不准确，但是我们认为它的误差率是最小的。
伯努利实验
伯努利试验是在同样的条件下重复地、相互独立地进行的一种随机试验，其特点是试验只有两种可能结果：成功或者失败。我们假设该项试验独立重复地进行了n次，那么就称这一系列重复独立的随机试验为n重伯努利试验，或称为伯努利概型。单个伯努利试验是没有多大意义的，然而，当我们反复进行伯努利试验，去观察这些试验有多少是成功的，多少是失败的，事情就变得有意义了，这些累计记录包含了很多潜在的非常有用的信息。
比如最简单的抛硬币过程就可以看作是一次伯努利实验，抛硬币的结果只有两种：正面朝上或反面朝上，且两种结果的概率都是 50%。
我们假设正面是成功，反面是失败，每抛到一次正面记为一次完整的试验，同时记录下所有试验里抛硬币最多的次数。试验次数记为 N，最大抛硬币次数记为 K。如下示例：
N=1 反反正 K=3
N=2 反反反正 K=4
现在我告诉你我一共进行了 N 次试验，最多一次抛了 4 次才抛到正面朝上，即 K=4，现在请你推理出 N 的数量。
我们来试着分析一下这个问题，首先我们能拿到的信息就只有 K=4，即最多的一次抛出了反反反正的结果。可能运气很好第一次就抛到了，也可能运气很背，抛了很多次才得到这个结果。具体试验了多少次我们不得而知，我们只能依靠 K=4 这个结果发生的概率去反推试验次数。
反反反正是 4 次独立的抛硬币结果，第一次反的概率是 0.5，第二次还是反的概率是0.5 * 0.5=0.25，以此类推，抛出这个结果的概率是1/16，即1/2^k，所以我们可以估算出大概率进行了 16 次试验。
发现了吗？我们仅凭一个 K=4 就可以估算出 N，虽然结果可能不准确，但确实得到了一个结果，接下来就是解决误差率的问题了。这也正是 HyperLogLog 的核心原理，它不保存每次试验的结果，它只保留 K，所以极其节省空间，最后依靠 K 来估算 N。
探寻KN的关系
基于以上理论，我们发现可以通过 K 值估算 N 值，只是估算的结果误差比较大，我们来探寻一下 KN 的关系，一步步的解决误差率，最终得到一个比较稳定和准确的 HyperLogLog 算法。
简单估算
先看一个最简单的 V1 版本，直接模拟上文中的抛硬币，记录下最大值 K，然后估算 N。
public class KN1 {int k;final int n;public KN1(int n) {this.n = n;}void test() {int counter = 1;for (int i = 0; i < n; i++) {if (nextBoolean()) {// 随机到true 代表正面，记录下最大K值if (counter > k) {k = counter;}counter = 1;} else {counter++;}}// 估算n=2的k次方long estimate = Math.round(Math.pow(2, k));DecimalFormat decimalFormat = new DecimalFormat("0.0000%");double error = Math.abs(n - estimate) / (double) n;System.err.printf("%-10s %-10s %-10s\n", n, estimate, decimalFormat.format(error));}boolean nextBoolean() {return ThreadLocalRandom.current().nextBoolean();}public static void main(String[] args) {System.err.printf("%-10s %-10s %-10s\n", "实际n", "预估n", "误差率");for (int i = 0; i <= 10000000; ) {if (i < 10) {i++;} else {i *= 10;}new KN1(i).test();}}
}
结果输出：
实际n 预估n 误差率
1 2 100.0000%
2 2 0.0000%
3 4 33.3333%
4 2 50.0000%
5 4 20.0000%
6 1 83.3333%
7 8 14.2857%
8 16 100.0000%
9 8 11.1111%
10 64 540.0000%
100 64 36.0000%
1000 1024 2.4000%
10000 16384 63.8400%
100000 262144 162.1440%
1000000 262144 73.7856%
10000000 16777216 67.7722%
100000000 33554432 66.4456%
观察结果发现，这种简单粗暴的估算，误差率非常高，肯定不是一个可用的版本，但是我们可以获得两个信息：
- K N 确实存在指数关系，至少估算的误差没有超出一个数量级，证明思路是对的
- 数据规模越小，误差率往往越大
分桶平均
思路是对的，接下来就是解决误差率的问题了。
怎么减小估算的误差呢？如果大家做过试验，应该就能想到，如果一次试验的误差率较大，那么就多做几轮试验，然后求平均值，这样就可以减小单次试验结果对最终结果的影响。
于是我们初始化 16384 个桶，每做完一次试验，就把 K 值随机写入一个桶（只保留最大K值），然后对每个桶的 K 求平均值，最终再基于 K 平均值估算 N。于是我们得到算法的 V2 版本：
public class KN2 {final int m;// 桶数量final int n;final int[] buckets;public KN2(int n) {this.m = 16384;this.n = n;this.buckets = new int[m];}void test() {int counter = 1;for (int i = 0; i < n; i++) {if (nextBoolean()) {// 把K值随机写入一个桶int index = nextBucket();if (counter > buckets[index]) {buckets[index] = counter;}counter = 1;} else {counter++;}}count();}private void count() {double sum = 0.0;int validBuckets = 0;for (int bucket : buckets) {if (bucket > 0) {// 过滤空桶sum += bucket;validBuckets++;}}// 估算的每个桶的平均值double avg = Math.pow(2, sum / validBuckets);// 估算值 = 均值*桶数量long estimate = Math.round(avg * validBuckets);DecimalFormat decimalFormat = new DecimalFormat("0.0000%");double error = Math.abs(n - estimate) / (double) n;System.err.printf("%-10s %-10s %-10s\n", n, estimate, decimalFormat.format(error));}boolean nextBoolean() {return ThreadLocalRandom.current().nextBoolean();}int nextBucket() {return ThreadLocalRandom.current().nextInt(m);}
}
结果输出：
实际n 预估n 误差率
1 2 100.0000%
2 2 0.0000%
3 2 33.3333%
4 4 0.0000%
5 4 20.0000%
6 16 166.6667%
7 11 57.1429%
8 13 62.5000%
9 16 77.7778%
10 16 60.0000%
100 222 122.0000%
1000 2016 101.6000%
10000 18362 83.6200%
100000 134363 34.3630%
1000000 1257570 25.7570%
10000000 12302338 23.0234%
100000000 124887784 24.8878%
观察结果发现，经过分桶平均后，误差率确实减小了，在数据规模比较大的情况下，误差率基本控制在20%~30%，但它仍然不是一个可用版本。
调和平均
分桶平均以后，误差率确实小了，但是还不够小。因为算数平均数有一个缺点，就是结果容易受到大值的影响，使得结果偏离整体数据的中心位置。
举个例子，小王的月薪是3000元，小李的月薪是30000元，他俩平均月薪是16500元。在小王看来这个数据就很扯蛋，自己什么时候工资这么高了，这就是算数平均数导致的，因为它的结果容易收到大值的影响。反观调和平均数，它会偏向于集合里的小数。
调和平均数：又称倒数平均数，它先对集合内的每个数求倒数，然后把所有的倒数相加得到 sum，最后用集合里的元素数量除以 sum 就可以得到调和平均数。
H = n 1 x 1 + 1 x 2 + . . . + 1 x n = n ∑ i = 1 n 1 x i H = \frac{n}{\frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_n}} = \frac{n}{\sum_{i=1}^n \frac{1}{x_i}} H=x11+x21+...+xn1n=∑i=1nxi1n
我们用调和平均数重新计算一下小王和小李的平均薪资，avg = 2/(1/3000+1/30000)结果约为 5455 元，这个数据在小王看来还是比较靠谱的。
基于以上理论，我们可以把算数平均数换成调和平均数，以此来进一步降低结果误差。于是我们得到算法的 V3 版本：
public class KN3 {final int m;final int n;final int[] buckets;public KN3(int n) {this.m = 16384;this.n = n;this.buckets = new int[m];}void test() {int counter = 1;for (int i = 0; i < n; i++) {if (nextBoolean()) {int index = nextBucket();if (counter > buckets[index]) {buckets[index] = counter;}counter = 1;} else {counter++;}}count();}private void count() {double sum = 0.0;int validBuckets = 0;for (int bucket : buckets) {if (bucket > 0) {sum += 1.0 / bucket; // 倒数相加 求调和平均数validBuckets++;}}// 每个桶的平均数double avg = Math.pow(2, validBuckets / sum);// 总的估算值long estimate = Math.round(avg * validBuckets);DecimalFormat decimalFormat = new DecimalFormat("0.0000%");double error = Math.abs(n - estimate) / (double) n;System.err.printf("%-10s %-10s %-10s\n", n, estimate, decimalFormat.format(error));}boolean nextBoolean() {return ThreadLocalRandom.current().nextBoolean();}int nextBucket() {return ThreadLocalRandom.current().nextInt(m);}
}
结果输出：
实际n 预估n 误差率
1 2 100.0000%
2 0 100.0000%
3 4 33.3333%
4 7 75.0000%
5 5 0.0000%
6 8 33.3333%
7 11 57.1429%
8 5 37.5000%
9 16 77.7778%
10 15 50.0000%
100 142 42.0000%
1000 1325 32.5000%
10000 12229 22.2900%
100000 72504 27.4960%
1000000 888320 11.1680%
10000000 10116344 1.1634%
100000000 105180060 5.1801%
观察结果发现，使用调和平均数后，误差率进一步降低了，在数据规模较大时，误差率可以控制在10%以内。但是它仍然不是一个可用的版本，主要原因有：
- 数据规模较小时，误差率还是很大
- 整体误差率还是不够小，还能不能再精确一点
HyperLogLog实现
探寻 K N 的关系，我们迭代了算法的三个版本，估算结果的误差率逐步降低，其实 V3 的算法已经很接近 HyperLogLog 了，相较于 V3，HyperLogLog 的特点主要有：
- 仍然采用 调和平均数 计算
- 数据规模较小/超大时，对结果进行过修正（解决 V3 的问题）
- 引入 constant 修正常数（进一步降低误差率）
接下来，我们就用 Java 实现一个简单的 HyperLogLog 算法，看看它比 V3 的误差率又能提升多少呢？
问题：怎么把输入的元素转换成上述抛硬币的过程？？？
对输入的元素做哈希运算，得到哈希值。把哈希值的每个二进制位看做是一次抛硬币的结果，0代表反面，1代表正面。从低位开始数，直到第一个出现 1 的位，把经过的位数记为 K 值。
问题：HyperLogLog 如何对估算结果修正？？？
HyperLogLog 采用分段偏差修正，当数据规模太小/太大时，都有专门的修正算法，针对一般规模的数据会在最终结果上乘以一个修正常数 constant。
假设 E 为估算结果，分段偏差修正算法如下：
- 当 E ≤ 5 2 m E \leq \frac{5}{2}m E≤25m时，数据规模太小
E = m ∗ l o g m / V E=m*log^{m/V} E=m∗logm/V V = 空桶数量
- 当 5 2 m < E ≤ 1 30 2 32 \frac{5}{2}m < E \leq \frac{1}{30}2^{32} 25m<E≤301232时，数据规模一般直接用 HyperLogLog 公式
E = c o n s t ∗ m ∗ m ∑ i = 1 m 1 2 R i E = const*m*\frac{m}{\sum_{i=1}^m \frac{1}{2^Ri}} E=const∗m∗∑i=1m2Ri1m
- 当 E > 1 30 2 32 E > \frac{1}{30}2^{32} E>301232时，数据规模太大
E = − 2 32 l o g ( 1 − E / 2 32 ) E=-2^{32}log(1-E/2^{32}) E=−232log(1−E/232)
修正常数 constant 是根据分桶数量决定的：
double getConstant(int buckets) {switch (buckets) {case 16:return 0.673;case 32:return 0.697;case 64:return 0.709;default:return (0.7213 / (1 + 1.079 / buckets));}
}
实现思路：
- 初始化 16384 个桶，用来做分桶平均
- 对元素做哈希运算，得到 64 位长整型哈希值 hash
- 取 hash 的低 14 位值，用作分桶索引号
- 取 hash 的高 50 位值，计算前导0的数量（从低位开始连续0的数量）lowBits
- 把 lowBits 写入到桶
- 最后先估算每个桶的 N 值，再求调和平均数，最终估算 N 值
基于这个思路，最终我们用 Java 实现的一个简版 HyperLogLog 就出来了：
public class HyperLogLog {// 定位桶的比特数 低14位private static final int BUCKET_BITS = 14;private final int m;// 桶数量private final byte[] buckets; // 桶private final double constant; // 修正常数 根据桶数量设置public HyperLogLog() {this.m = 1 << BUCKET_BITS;// 16384个桶this.buckets = new byte[m];this.constant = getConstant(m);}public void add(String val) {long hash = hash(val);int index = (int) (hash & (m - 1));// 低位连续0+1的数量n 实际估算值 k = 2^n -> 1<<nbyte lowBits = lowBits(hash >>> BUCKET_BITS);if (lowBits > buckets[index]) {buckets[index] = lowBits;}}public long count() {double sum = 0.0;int emptyBuckets = 0;for (byte num : buckets) {sum += 1.0 / (1 << num);if (num == 0) {emptyBuckets++;}}double avg = m / sum; // 调和平均数double estimate = constant * m * avg; // 估算计数值 根据公式// 存在空桶 数据量不够，偏差可能较大 做结果修正if (emptyBuckets > 0 && estimate < (5.0 / 2.0) * m) {// 求对数 空桶数越多 估算结果值越小estimate = m * Math.log((double) m / emptyBuckets);}// 这里先忽略对极大值的修正return Math.round(estimate);}private byte lowBits(long hash) {if (hash == 0) {return 64 - BUCKET_BITS;}int index = 1;while ((hash & 1) == 0) {index++;hash = hash >>> 1;}return (byte) index;}private long hash(String val) {return Hashing.murmur3_128().hashString(val, StandardCharsets.UTF_8).asLong();}private static double getConstant(int buckets) {switch (buckets) {case 16:return 0.673;case 32:return 0.697;case 64:return 0.709;default:return (0.7213 / (1 + 1.079 / buckets));}}
}
结果输出：
实际n 预估n 误差率
1 1 0.0000%
2 2 0.0000%
3 3 0.0000%
4 4 0.0000%
5 5 0.0000%
6 6 0.0000%
7 7 0.0000%
8 8 0.0000%
9 9 0.0000%
10 10 0.0000%
100 100 0.0000%
1000 1003 0.3000%
10000 9989 0.1100%
100000 99717 0.2830%
1000000 999310 0.0690%
10000000 10033112 0.3311%
100000000 99931727 0.0683%
观察结果发现，对估算结果做修正后的 HyperLogLog 算法准确率已经非常高了，在数据规模较小时，修正算法效果非常好。在数据规模较大时，误差率也控制在0.5%以内，我们可以说这是一个可用的版本了，可怕的是它只有七十行代码。
Redis实现
Redis HyperLogLog 和我们 Java 手写的实现思路是一致的，默认也是拆分了 16384 个桶，低 14 位用来定位桶索引号，高 50 位用来计算前导0的位数。
区别是 Redis 对 HyperLogLog 做了一些内存上的优化，分为：稀疏格式和紧凑格式。稀疏格式用在早期阶段，大多数桶都是 0，Redis 直接存储连续 0 桶的数量，而不是把 0 桶全都存一遍。紧凑格式就是完整的 16384 个桶，每个桶占用 6 Bit，一共 12KB 的内存空间。
感兴趣的同学可以去看下源码。
尾巴
HyperLogLog 算法是一种用于估计基数（cardinality）的概率算法，可以高效地计算一个集合中不重复元素的个数。与传统的基数估计方法相比，因为不存储元素本身，所以 HyperLogLog 具有更小的存储空间需求，却能够以极高的准确性给出估计结果。
在不准确绝对准确率的场景下，可以优先考虑 HyperLogLog 算法。
更多推荐
HyperLogLog算法
发布评论