贫瘠之地

华北无浪漫，死海扬起帆
多少个夜晚，独自望着天

0%

ES cardinality 和 HyperLogLog

发表于 分类于 >

基数聚合

基数聚合属于聚合中的度量聚合，计算不同值的近似计数

需要注意，聚合出的结果是一个近似值，原因是底层结构使用的 HyperLogLog，具有一定误差

基本操作

假定 index 存储的售卖数据，希望查询有多少种不同的商品类型

1
2
3
4
5
6
7
8
9
10
POST /sales/_search?size=0
{
  "aggs": {
    "type_count": {
      "cardinality": {
        "field": "type"
      }
    }
  }
}

以之前的学生 index 为例，查询有几个班级下有女学生

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
	"query": {
		"term": {
			"gender": "female" // 结果集查询性别为女性
		}
	},
	"size": 0, // 不关注 hits 结果集
	"aggs": {
		"class_count": {
			"cardinality": {
				"field": "class"
			}
		}
	}
}

返回结果，选取 hits 和 aggregations 部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
	"hits": {
		"total": {
			"value": 2,
			"relation": "eq"
		},
		"max_score": null,
		"hits": []
	},
	"aggregations": {
		"class_count": {
			"value": 2
		}
	}
}

因为 size 为 0，所以 hits 中没有返回的文档

aggregations 下自定义结果集名称 class_count 返回的值为 2，说明班级下有女学生的班级数量为 2

近似值与精确阈值参数

由于返回结果是一个近似值，所以 cardinality 支持 precision_threshold 参数，用来设置精确阈值

阈值参数的本质是使用空间换取准确性，默认是 3000，最大支持 40000，超过 40000 的设置为按照 40000 来处理

低于阈值的计数更符合准确值，高于阈值的计数则会更加模糊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{
	"query": {
		"term": {
			"gender": "female"
		}
	},
	"size": 0,
	"aggs": {
		"class_count": {
			"cardinality": {
				"field": "class",
				"precision_threshold": 200000 // 精度阈值，事实上内部将该参数视为 40000
			}
		}
	}
}

计算精确的计数需要将值加载至哈希集合并返回大小，当基数特别大时，需要占用非常多资源

所以 ES 选择 HyperLogLog 算法来实现 cardinality，这种方式基于值的哈希计数，有一些特性：

  • 可配置的精度，可以选择用内存换取精度
  • 低基数集合中是精准的
  • 固定的内存使用率，无论唯一值有多少，只取决于设置的精度

HyperLogLog + + 算法依赖于散列值的前导零，数据集中散列的精确分布会影响基数的准确性

ES 官方文档提供的数据显示，具体的准确性取决于数据集情况，但大部分场景的准确性都还是良好的，即使阈值设置为 100，在百万、千万基数下，误差范围也控制在了 1% ~ 6%；当阈值设置为 10000，误差基本在 1% 左右

脚本 runtime field

cardinality 像其他聚合操作一样，是可以使用脚本拼接字段的

如果希望对两个字段的组合进行操作，创建一个 runtime field 组合他们然后进行基数聚合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{
	"size": 0,
	"runtime_mappings": {
		"gender_and_age": {
			"type": "keyword",
			"script": "emit(doc['gender'].value + '&' + doc['age'].value)" // 拼接 gender 和 age 字段
		}
	},
	"aggs": {
		"type_promoted_count": {
			"cardinality": {
				"field": "gender_and_age" // 根据 runtime field 进行基数操作
			}
		}
	}
}

返回结果是 6，因为有两个文档的 runtime field gender_and_age 值都为 male&20

1
2
3
4
5
6
7
{
	"aggregations": {
		"type_promoted_count": {
			"value": 6
		}
	}
}

HyperLogLog

HyperLogLog 是一种基数计数的算法，旨在使用较少内存的情况下得到基数数量的近似精确值

基数计数方式

基数计数（cardinality counting）通常用来统计一个集合中不重复的元素个数，例如统计某个网站的 UV，或者用户搜索网站的关键词数量等

如何计算计数常见的有多种方式

  • B 树
    • 利用树存储具体元素
    • 优点：插入和查找效率高，统计数据时可以快速做到记录与去重，计算基数时只需要统计叶子节点个数即可
    • 缺点：没有节省内存，需要存储数据全集
  • bitmap
    • 使用 bit 位进行标记，即抛弃具体元素内容只存储特征值
    • 优点：节约内存，结果可以进行方便的位运算操作（合并 - 与，差集 - 或）
    • 缺点：空间占用仍然较大
  • 概率算法
    • 目前用于基数计数的概率算法有：LC、LLC、HLL 等
    • 优点：LL、HLL 等能够在空间更小的情况下进行基数计算
    • 缺点：有一定误差

HLL

HLL 中实际存储的是一个长度为 m 的大数组 S，将待统计的数据集合划分成 m 组，每组根据算法记录一个统计值存入数组中

数组的大小 m 由算法实现方自己确定，Redis 中这个数组的大小是 16834，m 越大误差越小，但需要的内存空间也越大

HLL 的数学原理看不懂，大致就是 n 重伯努利原理

通过多次抛硬币，直到抛到正面为止，这是一次伯努利过程；当一直抛硬币，直到多次出现正面，将出现正面的投掷次数值记为 k1、k2、k3...kn，最大值记为 kmax，那么可以得到以下结论：

  • n 次伯努利过程的投掷次数都不大于 kmax
  • n 次伯努利过程，至少有一次投掷次数等于 kmax

最后经过一系列复杂的推论，最终的结果就是：进行了 n 次进行抛硬币实验，每次分别记录下第一次抛到正面的抛掷次数 k，那么可以用 n 次实验中最大的抛掷次数 kmax 来预估实验组数量 n；这就是 HLL 算法的数学理论基础

此外 HLL 为了提高准确性也做了其他优化

分桶平均

HLL 的基本思想是利用集合中数字的比特串第一个1出现位置的最大值来预估整体基数，但是这种预估方法存在较大误差，为了改善误差情况，HLL 中引入分桶平均的概念

为了避免一组实验中的运气影响，将统计数据划分多个桶，每个桶各自统计自己的 kmax 计算基数预估值，最终对各个桶的基数预估值进行合并，使用调和平均数的方式进一步降低误差

偏差修正

虽然调和平均数能够适当修正算法误差，但作者给出一种分阶段修正算法

当 HLL 算法开始统计数据时，统计数组中大部分位置都是空数据，并且需要一段时间才能填满数组，这种阶段引入一种小范围修正方法；当 HLL 算法中统计数组已满的时候，需要统计的数据基数很大，这时候 hash 空间会出现很多碰撞情况，这种阶段引入一种大范围修正方法

参考

Cardinality aggregation | Elasticsearch Guide 8.5

神奇的HyperLogLog算法【转载 #涉及到数学原理】 - 掘金 (juejin.cn)

Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure – AK Tech Blog (neustar.biz)