户外网站模板,遵义企业做网站,网页美工设计网课,制作图片的电脑软件前言
现在很多站点基本都有统计 PV 和 UV 的需求#xff0c;PV 的统计很简单#xff0c;在 Redis 里面维护一个计数器#xff0c;页面每访问一次计数器就 1#xff0c;获取 PV 就是读取计数器的值。 相比之下#xff0c;UV 的统计就比较麻烦了#xff0c;因为要对用户去…前言
现在很多站点基本都有统计 PV 和 UV 的需求PV 的统计很简单在 Redis 里面维护一个计数器页面每访问一次计数器就 1获取 PV 就是读取计数器的值。 相比之下UV 的统计就比较麻烦了因为要对用户去重UV 统计其实就是基数统计最简单的做法就是记录下集合中所有不重复的元素。 比如你可以用 Set 来统计Set 不会存储重复的元素用户每次访问都把 UserID 写入 Set 集合最终调用 SCARD 命令获取集合元素数量即可。 sadd uv 1001 1002 1003
(integer) 3scard uv
(integer) 3使用 Set 的缺点是太耗内存了假设 UserID 是 Long 类型占用 8 字节Set 底层用哈希表存储Key 是 UserIDValue 是空值但是指针本身还是会消耗 8 字节即一个 Entry 占用 16 字节存储一亿个 UserID 大约占用 1.49G。 或者你还可以用 BitMap 来统计。哪个用户访问了页面就把 UserID 对应的位设为 1最后统计 1 的数量即可。假设有一亿个用户就需要一亿个 Bit大约 12MB相比 Set 确实节省了很多内存但是仍然不够省假设有一千个页面需要统计就需要消耗约 12GB 的空间。
无论是 Set 还是 BitMap 实现它们都直接或间接的存储了元素这种方式带来的问题是占用的内存空间会随着统计的数据量线性增长。 在统计学里还有一种基于概率的统计算法它不存储元素本身所以极其节省内存但它牺牲的是准确率。HyperLogLog 就是一种基于概率的统计算法它仅需少量的内存空间就可以统计超大规模的数据量在不追求绝对准确的场景下更推荐使用这种算法。
HyperLogLog
Redis 提供了 HyperLogLog 数据类型使用极其简单PFADD 命令把值写入到 HyperLogLogPFCOUNT 命令对 HyperLogLog 做基数估算。 pfadd uv 1001 1002 1003
(integer) 1pfcount 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。如下示例
N1 反反正 K3
N2 反反反正 K4现在我告诉你我一共进行了 N 次试验最多一次抛了 4 次才抛到正面朝上即 K4现在请你推理出 N 的数量。
我们来试着分析一下这个问题首先我们能拿到的信息就只有 K4即最多的一次抛出了反反反正的结果。可能运气很好第一次就抛到了也可能运气很背抛了很多次才得到这个结果。具体试验了多少次我们不得而知我们只能依靠 K4 这个结果发生的概率去反推试验次数。 反反反正是 4 次独立的抛硬币结果第一次反的概率是 0.5第二次还是反的概率是0.5 * 0.50.25以此类推抛出这个结果的概率是1/16即1/2^k所以我们可以估算出大概率进行了 16 次试验。
发现了吗我们仅凭一个 K4 就可以估算出 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;}}// 估算n2的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_{i1}^n \frac{1}{x_i}} Hx11x21...xn1n∑i1nxi1n
我们用调和平均数重新计算一下小王和小李的平均薪资avg 2/(1/30001/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 了相较于 V3HyperLogLog 的特点主要有
仍然采用 调和平均数 计算数据规模较小/超大时对结果进行过修正解决 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 Em*log^{m/V} Em∗logm/V V 空桶数量
当 5 2 m E ≤ 1 30 2 32 \frac{5}{2}m E \leq \frac{1}{30}2^{32} 25mE≤301232时数据规模一般直接用 HyperLogLog 公式 E c o n s t ∗ m ∗ m ∑ i 1 m 1 2 R i E const*m*\frac{m}{\sum_{i1}^m \frac{1}{2^Ri}} Econst∗m∗∑i1m2Ri1m
当 E 1 30 2 32 E \frac{1}{30}2^{32} E301232时数据规模太大 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));// 低位连续01的数量n 实际估算值 k 2^n - 1nbyte 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 做了一些内存上的优化分为稀疏格式和紧凑格式。稀疏格式用在早期阶段大多数桶都是 0Redis 直接存储连续 0 桶的数量而不是把 0 桶全都存一遍。紧凑格式就是完整的 16384 个桶每个桶占用 6 Bit一共 12KB 的内存空间。 感兴趣的同学可以去看下源码。
尾巴
HyperLogLog 算法是一种用于估计基数cardinality的概率算法可以高效地计算一个集合中不重复元素的个数。与传统的基数估计方法相比因为不存储元素本身所以 HyperLogLog 具有更小的存储空间需求却能够以极高的准确性给出估计结果。 在不准确绝对准确率的场景下可以优先考虑 HyperLogLog 算法。
