透彻理解Elasticsearch
首页 死磕 Java 优质系列 Java 技术总览 Java 面试宝典 关于我

Elasticsearch基础（二一）——聚合分析：近似算法

转
 2023-08-08
©版权
原文作者：Ressmix 原文地址：https://www.tpvlog.com/article/146

本章，我们来介绍下聚合分析底层用到的算法： 近似算法 。

什么是近似算法？

一般来讲，有些聚合分析的metric操作，是很容易在多个shard中并行执行的，比如max、min、avg这种，coordinate node拿到各个shard的返回结果后，只需要经过简单计算就能得出最终结果：

  1. coordinate node把请求广播到所有shard；
  2. 每个分片计算本地最大的字段值，返回给coordinate node；
  3. coordinate node选出所有shard返回的最大值，这就是最终的最大值。

上面这类算法可以随着机器数的线性增长而横向扩展，无须任何协调操作（机器之间不需要讨论中间结果），而且内存消耗很小（一个整型就能代表最大值）。

但是还有些算法，是很难并行执行的，比如说count(distinct)，并不是说在每个shard上直接过滤出distinct value就可以了，因为coordinate node需要拿到各个shard返回的结果，在内存中进行筛选操作，如果数据量非常大，这个过程非常耗时。

所以，Elasticsearch为了提升性能，采用了近似算法，它们会提供准确但不是 100% 精确的结果， 以牺牲一点小小的估算错误为代价，这些算法可以为我们换来高速的执行效率和极小的内存消耗。

一、近似算法

1.1 基本思想

近似算法的基本思想就是在 大数据 、 精确性 和 实时性 这三者之间做出权衡，一般只能选择其中的2个，有点类似于CAP。 因为对于很多应用，能够实时返回高度准确的结果要比 100% 精确结果重要得多：

精确 + 实时

数据可以存入单台机器的内存之中，我们可以随心所欲，使用任何想用的算法。结果会 100% 精确，响应会相对快速。

大数据 + 精确

传统的 Hadoop，可以处理 PB 级的数据并且为我们提供精确的答案，但它可能需要几周的时间才能为我们提供这个答案。

大数据 + 实时

近似算法为我们实时提供准确但不精确的结果。

202308082147457861.png

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% 精确的结果， 以牺牲一点小小的估算错误为代价，这些算法可以为我们换来高速的执行效率和极小的内存消耗。

阅读全文
文章标签： Elasticsearch