本章，我们来介绍下聚合分析底层用到的算法： 近似算法 。
什么是近似算法？
一般来讲，有些聚合分析的metric操作，是很容易在多个shard中并行执行的，比如max、min、avg这种，coordinate node拿到各个shard的返回结果后，只需要经过简单计算就能得出最终结果：
- coordinate node把请求广播到所有shard；
- 每个分片计算本地最大的字段值，返回给coordinate node；
- coordinate node选出所有shard返回的最大值，这就是最终的最大值。
上面这类算法可以随着机器数的线性增长而横向扩展，无须任何协调操作（机器之间不需要讨论中间结果），而且内存消耗很小（一个整型就能代表最大值）。
但是还有些算法，是很难并行执行的，比如说count(distinct)，并不是说在每个shard上直接过滤出distinct value就可以了，因为coordinate node需要拿到各个shard返回的结果，在内存中进行筛选操作，如果数据量非常大，这个过程非常耗时。
所以，Elasticsearch为了提升性能，采用了近似算法，它们会提供准确但不是 100% 精确的结果， 以牺牲一点小小的估算错误为代价，这些算法可以为我们换来高速的执行效率和极小的内存消耗。
一、近似算法
1.1 基本思想
近似算法的基本思想就是在 大数据 、 精确性 和 实时性 这三者之间做出权衡，一般只能选择其中的2个，有点类似于CAP。 因为对于很多应用，能够实时返回高度准确的结果要比 100% 精确结果重要得多：
精确 + 实时
数据可以存入单台机器的内存之中，我们可以随心所欲，使用任何想用的算法。结果会 100% 精确，响应会相对快速。
大数据 + 精确
传统的 Hadoop，可以处理 PB 级的数据并且为我们提供精确的答案，但它可能需要几周的时间才能为我们提供这个答案。
大数据 + 实时
近似算法为我们实时提供准确但不精确的结果。
Elasticsearch 目前支持两种近似算法（ cardinality 和 percentiles ）。 它们会提供准确但不是 100% 精确的结果，以牺牲一点小小的估算错误为代价，这些算法可以为我们换来高速的执行效率和极小的内存消耗。
二、Cardinality算法
2.1 基本使用
Cardinality算法用于统计某个字段的不同值的个数，也就是去重统计。比如，我们需要统计每个月销售的不同品牌数量，那么可以像下面这样构造查询：
GET /tvs/_search
{
"size" : 0,
"aggs" : {
"months" : {
"date_histogram": {
"field": "sold_date",
"interval": "month"
},
"aggs": {
"distinct_brand" : {
"cardinality" : {
"field" : "brand"
}
}
}
}
}
}
2.2 算法优化
Cardinality算法的统计结果并不一定精确，但是速度非常快，我们还可以通过调整参数来进一步优化。
precision_threshold
precision_threshold可以控制Cardinality算法的精确度和内存消耗，它接受 0–40000 之间的数字，更大的值还是会被当作 40000 来处理。
比如，precision_threshold设置为100，那么Elasticsearch会确保当字段唯一值在 100 以内时，会得到非常准确的结果，这个准确率几乎100%。但是，如果字段唯一值的数目高于precision_threshold，ES就会开始节省内存而牺牲准确度。
根据Elasticsearch的官方统计，
precision_threshold设置为100时，对于100万个不同的字段值，统计结果的误差可以维持在 5% 以内。
GET /tvs/_search
{
"size" : 0,
"aggs" : {
"distinct_brand" : {
"cardinality" : {
"field" : "brand",
"precision_threshold" : 100
}
}
}
}
HyperLogLog
Cardinality算法的底层是基于HyperLogLog++算法（简称HLL）实现的，HLL算法会对所有unique value取hash值，通过hash值近似求distinct count。
默认情况下，如果我们的请求里包含cardinality统计，ELasticsearch会实时对所有的field value取hash值。所以，一种优化思路就是在建立索引时，就将所有字段值的hash建立好。
比如，我们对brand字段再内建一个字段——名为“hash”，它的类型是murmur3，是一种计算hash值的算法：
PUT /tvs/
{
"mappings": {
"sales": {
"properties": {
"brand": {
"type": "text",
"fields": {
"hash": {
"type": "murmur3"
}
}
}
}
}
}
}
当我们需要统计字段的distinct value时，直接对内置字段进行cardinality统计即可：
GET /tvs/_search
{
"size" : 0,
"aggs" : {
"distinct_brand" : {
"cardinality" : {
"field" : "brand.hash",
"precision_threshold" : 100
}
}
}
}
三、Percentiles算法
Percentiles算法可以按照百分比来统计某个字段的聚合信息。
3.1 基本使用
比如，我们有一个网站，记录了每次请求的访问耗时，需要统计tp50、tp90、tp99，那么用percentiles实现就非常方便。
tp50：50%的请求的最长耗时
tp90：90%的请求的最长耗时
tp99：99%的请求的最长耗时
我们创建一个示例来进行演示：
# 创建索引
PUT /website
{
"mappings": {
"properties": {
"latency": {
"type": "long"
},
"province": {
"type": "keyword"
},
"timestamp": {
"type": "date"
}
}
}
}
# 录入数据
POST /website/logs/_bulk
{ "index": {}}
{ "latency" : 105, "province" : "江苏", "timestamp" : "2016-10-28" }
{ "index": {}}
{ "latency" : 83, "province" : "江苏", "timestamp" : "2016-10-29" }
{ "index": {}}
{ "latency" : 92, "province" : "江苏", "timestamp" : "2016-10-29" }
{ "index": {}}
{ "latency" : 112, "province" : "江苏", "timestamp" : "2016-10-28" }
{ "index": {}}
{ "latency" : 68, "province" : "江苏", "timestamp" : "2016-10-28" }
{ "index": {}}
{ "latency" : 76, "province" : "江苏", "timestamp" : "2016-10-29" }
{ "index": {}}
{ "latency" : 101, "province" : "新疆", "timestamp" : "2016-10-28" }
{ "index": {}}
{ "latency" : 275, "province" : "新疆", "timestamp" : "2016-10-29" }
{ "index": {}}
{ "latency" : 166, "province" : "新疆", "timestamp" : "2016-10-29" }
{ "index": {}}
{ "latency" : 654, "province" : "新疆", "timestamp" : "2016-10-28" }
{ "index": {}}
{ "latency" : 389, "province" : "新疆", "timestamp" : "2016-10-28" }
{ "index": {}}
{ "latency" : 302, "province" : "新疆", "timestamp" : "2016-10-29" }
下面的请求，按照latency字段的记录数百分比进行分组，然后统计组内的平均延时信息：
GET /website/_search
{
"size": 0,
"aggs": {
"latency_percentiles": {
"percentiles": {
"field": "latency",
"percents": [
50,
95,
99
]
}
},
"latency_avg": {
"avg": {
"field": "latency"
}
}
}
}
响应如下：
{
"took": 31,
"timed_out": false,
"_shards": {
"total": 5,
"successful": 5,
"failed": 0
},
"hits": {
"total": 12,
"max_score": 0,
"hits": []
},
"aggregations": {
"latency_avg": {
"value": 201.91666666666666
},
"latency_percentiles": {
"values": {
"50.0": 108.5,
"95.0": 508.24999999999983,
"99.0": 624.8500000000001
}
}
}
}
3.2 percentile_ranks
percentile_ranks可以按照字段值的区间进行分组，然后统计出每个区间的占比。
比如，我们需要统计：对于每个省份，有多少请求（百分比）的延时分别在200ms以内、1000ms以内？就可以像下面这样构造请求：
GET /website/_search
{
"size": 0,
"aggs": {
"group_by_province": {
"terms": {
"field": "province"
},
"aggs": {
"latency_percentile_ranks": {
"percentile_ranks": {
"field": "latency",
"values": [
200,
1000
]
}
}
}
}
}
}
响应如下：
{
"took": 38,
"timed_out": false,
"_shards": {
"total": 5,
"successful": 5,
"failed": 0
},
"hits": {
"total": 12,
"max_score": 0,
"hits": []
},
"aggregations": {
"group_by_province": {
"doc_count_error_upper_bound": 0,
"sum_other_doc_count": 0,
"buckets": [
{
"key": "新疆",
"doc_count": 6,
"latency_percentile_ranks": {
"values": {
"200.0": 29.40613026819923,
"1000.0": 100
}
}
},
{
"key": "江苏",
"doc_count": 6,
"latency_percentile_ranks": {
"values": {
"200.0": 100,
"1000.0": 100
}
}
}
]
}
}
}
3.3 算法优化
percentile底层采用了TDigest算法，该算法会使用很多节点来执行百分比的计算，但是存在误差，参与计算的节点越多就越精准。
percentile有一个参数compression可以用来控制节点数量，默认值是100，所以如果想要percentile算法更精准，compression值可以设置得越大。
注意：compression值越大越消耗内存，一般compression=100时，内存占用大约为：100 x 20 x 32 = 64KB。
四、总结
本章，我介绍了Elasticsearch中两种常用的近似算法：cardinality和percentile。它们的思想都是在 大数据 、 精确性 和 实时性 这三者之间做出权衡。Elasticsearch为了提升性能，采用近似算法，它们会提供准确但不是 100% 精确的结果， 以牺牲一点小小的估算错误为代价，这些算法可以为我们换来高速的执行效率和极小的内存消耗。
Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。
它的内容包括：
- 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
- 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
- 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
- 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
- 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：
想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询
同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。
