HyperLogLog 算法在监控场景中的运用
背景介绍
OpsMind 低代码开发平台监控模块，为了支撑B站众多监控数据的管理场景，研发人员在分布式层做了众多优化工作。为了更好的掌握每个 metric 自身的空间占用以及各个存储节点的时序分布情况，需要对每个指标的时序数目（基数）有一个大致的预估（允许存在误差），以便于 OpsMind 系统能更加合理的均衡各个存储节点的负载。
为何选用 HyperLogLog
OpsMind 系统指标的形式与 prometheus 完全兼容（在此 prometheus 基础上做了一些拓展），一个监控指标（metric）的时序数，可以看做是该指标所有 labels 的组合（对 labels 求 fingerprint）数目。在对每个指标时序集合进行统计的过程中，如何去重是一个关键。当指标时序不多时，只需要简单通过 HashMap（比如 Golang 中，直接通过map进行去重）来实现。可是在监控的大部分场景中，随着监控对象的增加，labels的组合数将会变得越来越多，甚至达到百万级别。如果采用 HashMap 的方式进行统计，对服务端的内存占用将会越来越高。例如以 Golang map 为例，labels 的 fingerprint（uint64） 作为key，当 key 的数目达到100w级别时，内存占用大概为 7.6M 左右，当 metric 数目达到 1w 左右时，整体占用的内存空间是 74GB 左右。而B站目前管理的 metric 数目远不止 1w，显然不能使用 Golang map 来进行去重统计时序数目。
type Fingerprint uint64
type MetricLablesSet map[Fingerprint]struct{}
此时，尽量减少内存的占用（降低空间复杂度），成为主要要解决的问题。为了达到这个目的，另一种是通过 Bit-map 的方式进行基数的统计。Bit-map 的实现原理比较简单，即：使用 bit 位来标记某些元素是否存在。比如，在指标基数统计场景中，我们可以通过标记 labels fingerprint hash值在 bit 数组中的位置（与 bit 数组长度取模后得到），来进行去重。所以如果要存储 100w 个 fingerprint 是否存在的信息，至少需要占用 122KB 内存空间。1w个metric 至少占用 1GB 的空间。虽然相较于 HashMap，Bit-map 的方式极大的减少了内存空间的占用, 但是 1GB 的空间大小（实际情况下，会大很多），仍然不能满足需求。另外，实际场景中，一般会给每个 metric 预留一个较大长度的 bit 数组，当 metric 时序数较少的情况下，资源利用率会很低。即便存在其他能很好的提升资源利用率的算法（比如：Roaring Bit-map），在B站那么大数据量的场景下，依然没法很好的解决资源占用高的问题。
在满足效率的同时，内存占用能否继续降低？空间利用率能否持续提升？答案是肯定的，就是本文要介绍的算法：HyperLogLog（另一种方式是采用 Bloom Filter，不过不在本文讨论范围）。
HyperLogLog 算法介绍
HyperLogLog 利用了概览算法，存在一定的统计误差，不过这个误差在 metric 基数统计场景中是可以接受的。关于原理，读着可以带入到日常生活中常见的伯努利实验，例如：抛硬币, 出现正反面的概率都是1/2，一直抛硬币直到出现正面，记录下投掷次数 K，将这种抛硬币多次直到出现正面的过程记为一次伯努利过程，对于n次伯努利过程，可以得到n个出现正面的投掷次数值 ,
...
，其中最大值记为
。
可以得出以下结论：
-
次伯努利实验，投掷次数不大于
-
对于结论1， 次伯努利过程投掷次数都不大于
的概率为：
对于结论2，至少有一次抛了次的概率为：
继而可以得到：
- 当 n 远小于
时，
，结论1不成立；
- 当 n 远大于
，结论2不成立；
最后可以通过 来估计
的值：
这相当于知道某回合的最大投掷次数，可以估算出总共进行了几回合。而 HyperLogLog 算法的基本核心正基于此。通过统计存储元素 hash 值二进制表示中的第一个 1 的最大位置来估算元素数量，来预估存储单元基数的大小。这里，第一个 1 的位置可以类比为抛硬币场景中出现正面时的投掷次数，存储单元基数则相当于投掷了多少回合。
不过在抛硬币场景中，假如第一回合，第 3 次出现正面朝上，带入到公式中则预估出总共进行了 回合；显然存在较大误差。HyperLogLog 为了改善这种较大误差的情况，引入了分桶平均以及偏差修正的方式。将存储的hash值分到
个桶中，分别统计
，最后求得
个桶的调和平均数。公式如下：
为桶的数目,
为修正常数。
其中 的取值为：
switch (m) {
case 16:
alpha = 0.673;
case 32:
alpha = 0.697;
case 64:
alpha = 0.709;
default:
alpha = 0.7213 / (1 + 1.079 / m);
}
带入到 metric 基数统计场景，选取 的数目为 16384 (类似Redis)，每个桶的大小为 6 bit 长度；通过对 metric 的 fingerprint hash 得到一个 uint64 的数字，通过该数字前14位确定桶的位置，其余位用来做伯努利过程。则所有桶占用的内存空间为
。
为了更少的资源占用，有些 hll 的实现又引入了“稀疏存储结构”和“密集存储结构”的概念，当稀疏存储的容量达到一定规模后，会合并成密集存储结构，感兴趣的读着，可以自行搜索相关实现。
总结
在 metric 基数统计场景中，使用 HLL 对时序进行预估，可以保证较低且稳定的内存占用，又可以保证误差率在一个较低的可接受范围内。
