理解 Elasticsearch 中 cardinaliry aggregation

前言

我们有很多使用去重计数的业务场景，为了更好地做好这件事，我们需要深入理解所使用的工具。其中 cardinaliry aggregation 是 Elasticsearch 提供一种的计算非重复值的近似计数的单值度量聚合方法。计算结果是近似值，是因为使用了基于 HyperLogLog++ 的算法，所以只需要深入理解 HyperLogLog++ 算法。

算法原理

HyperLogLog++ 算法是一种用于近似计算基数问题（即计算一个集合中不同元素的个数）的算法，它是 HyperLogLog 算法的改进版。该算法的主要特点是具有更高的精度和更快的计算速度。

HyperLogLog++ 算法基于以下两个主要思想：

随机哈希函数：将每个元素映射为一个随机的哈希值，并将哈希值的前缀作为桶的编号；
计数器：为每个桶分配一个计数器，用于记录该桶中元素的个数。

算法表现

计算精确的计数需要将数值导入hash集合并返回集合的大小，当处理高基数集和/或较大的值时无法扩展，因为所需的内存使用情况以及在节点之间传递每个分片集的需求会占用过多的群集资源。

基数聚合基于 HyperLogLog++ 算法，该算法基于数值的哈希来计数，算法有下面一些特性：

可配置的精度，决定了如何为了精度而牺牲内存；
低基数集合的准确性很高；
固定的内存使用：不管集合中是否存在数十或者数百亿独特的值，内存的使用仅仅依赖于配置的精度。

假设精度的阈值为c，那么我们使用的实现方式需要大约c*8bytes的内存。

下面的图表显示了在精度阈值之上和阈值之下的误差变化情况：

2021-10-27T02:15:44.png

对于图中的三种阈值，在配置的阈值之前的基数计数都是准确的。尽管存在误差，但也很接近真实值。实际上，准确度是依赖于数据集。一般来说，大部分的数据集都展示了很好的准确性。我们也需要注意的是，即便阈值低至100，当对百万的数据进行计数时，误差也很低（图中显示了1-6%的误差）。

HyperLogLog++算法依赖于哈希后的值的前序0的个数，数据集哈希后的准确分布也会影响基数聚合的准确率。

ES 源码部分

项目地址：https://github.com/elastic/elasticsearch

代码位置：

第三方库源码部分

以 Golang 为主：

库文档地址：https://pkg.go.dev/github.com/clarkduvall/hyperloglog
github 地址：https://github.com/clarkduvall/hyperloglog/blob/master/hyperloglogplus.go

注意事项

cardinaliry aggregation 是使用了近似算法，precision_threshold 决定了值的精度。

precision_threshold 配置越大，精度越高，结果更接近真实去重的值；
precision_threshold 配置越大，意味着会带来更多的资源占用；
precision_threshold 阈值的官方默认值是3000，最大配置值是40000；
如果需要计算非常大基数的去重结果，可以使用预哈希计算的方法进行优化，对应插件为mapper-murmur3，murmur3 是一种取hash值的算法。

cardinaliry aggregation 对内存的开销情况，可以使用下面的方法进行计算：
假如 precision_threshold 为 10000，那么内存开销为 10000 * 8 / 1024 ，约等于80KB。

一般情况下，使用默认值就足够了，默认值是综合了精度和内存开销的情况得到的。
但是有些业务场景就是需要高准确率，那就只能把阈值调高。调高的方法一般是接近观察值的平均值就可以了。例如在使用默认值的情况下，观察到去重值平均在10000左右，那么我们可以尝试把阈值调为10000，副作用是可能支撑不了高频请求，因为会带来更大的内存开销，内存开销大了就会挤占其他资源，导致长GC，影响其他线程的工作导致服务异常。

链接

本文由 Chakhsu Lau 创作，采用知识共享署名4.0 国际许可协议进行许可。
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。