本文转载自微信公众号《程序员李小兵》，作者李小兵。转载本文请联系程序员李小兵公众号。大家好，我是李小兵。ElasticSearch作为分布式开源搜索分析引擎，不仅可以进行全文匹配搜索，还可以进行聚合分析。今天，我们就来看看其聚合分析中较为常见的百分位百分位分析。n个数据按数值排列，p%位置的数值称为第p个百分位数。比如ElasticSearch记录每个网站请求访问的耗时，需要统计它的TP99，是99%整体请求中耗时最长的。近似算法当数据量较小或数据集中存储在同一位置时，像TP99那样进行百分位分析很容易。然而，当数据量不断增长时，数据的聚合和分析需要在数据量、准确性和实时性三个方面进行权衡，而只能满足其中的两个。如上图所示，我们有三种选择：有限的数据计算：选择高精度和实时性，一定不能处理大规模的数据，比如MySQL用于单机数据的统计分析；离线计算：选择大高数据量和精度导致实时性差。比如Hadoop可以对PB级的数据进行准确的分析，但是可能需要很长时间；近似计算：选择大数据量和实时性，但会损失一定程度的精度，如0.5%，但提供相对准确的分析结果。Elasticsearch目前支持两种近似算法，基数和百分位数。Cardinality用于计算字段的基数，即该字段的不同或唯一值的数量。Cardinality是基于HyperLogLog(HLL)算法实现的。HLL会先对数据进行哈希运算，然后根据哈希运算结果的位数进行概率估计，得到基数。关于HLL算法的详细信息可以阅读文章《Redis HyperLogLog 详解》。百分位数是本文的重点。百分位数ElasticSearch可以使用百分位数来分析指定字段的百分位数。具体要求如下。分析logs索引下latency字段的百分位，即计算网站请求的latency百分位。percentiles默认返回一组预设的百分位数值，它们是[1,5,25,50,75,95,99]。它们代表人们感兴趣的常见百分位数，极端百分位数位于范围的两侧，其他百分位数位于中间。具体返回值如下图所示。我们可以看到最小延迟大约是75ms，最大延迟将近600ms。相比之下，平均延迟约为200毫秒。与上面的基数基数一样，计算百分位数需要一个近似算法。对于少量的数据，可以通过在内存中维护一个所有值的有序列表来计算各种百分位数，但是当有数十亿的数据分布在几十个节点上时，这种算法就不现实了。因此，百分位数使用TDigest算法，这是一种近似算法，计算不同精度的百分位数，越极端的百分位数范围越准确，比如1%或99%。50%的百分位数需要准确。这是一个很好的属性，因为大多数人只关心极端的百分位数。TDigest算法TDigest是一种简单、快速、高精度、可并行的近似百分位算法，被ElasticSearch、Spark和Kylin等系统使用。TDigest主要有两种实现算法，一种是buffer-and-merge算法，一种是AVL树的聚类算法。TDigest使用的思想是近似算法中常用的Sketch，即sketch，用一部分数据来描述整体数据集的特征，就像我们日常的草图一样。虽然和实物有差距，但是看起来和实物很像。能够表现真实物体的特征。下面介绍一下TDigest的原理。比如-30到30之间有500个数，我们可以用概率密度函数（PDF）来表示这个数据集。函数上某个点的y值就是它的x值出现在整个数据集中的概率，整个函数的面积之和正好为1。可以说它描述了分布数据集中的数据（比较熟悉的正态分布图显示了这个函数）。有了数据集对应的PDF函数，数据集的百分位数也可以用PDF函数的面积来表示。如下图所示，75%percentile是75%面积被占用的x坐标。我们知道PDF函数曲线中的点对应数据集中的数据。当数据量小的时候，我们可以用数据集中所有的点来计算函数，但是当数据量大的时候，我们只能用少量的数据来代替数据集中的所有数据。这里，我们需要对数据集进行分组，将相邻的数据归为一组，用均值（Mean）和权重（Weight）来代替这组数。这两个数统称为Centroid（质心数），然后用这个质心数来计算PDF，这就是TDigest算法的核心思想。如上图所示，质心个数的平均值作为x值，个数作为y值。通过这组质心可以大致画出这个数据集的PDF函数。相应地，计算百分位数只需要从这些质心数中找出对应位置的质心数，其平均值即为百分位数。显然，质心数的值越大，代表的数据越多，丢失的信息也越大，准确度也越低。如上图所示，质心数太大会损失太多精度，质心数太小会消耗大量内存和其他资源，无法达到逼近算法的高实时性。因此，TDigest在压缩率的基础上（压缩率越大，质心数代表的数据越多），TDigest根据百分位数控制每个质心数代表的数据量，质心数在两边越小，准确率越高，中间的质心数越多，从而达到上面提到的1%或99%百分位数比50%百分位数更准确的效果。源码分析ElasticSearch直接使用了TDigest的开源实现t-digest，其github地址为https://github.com/tdunning/t-digest，我们可以在ElasticSearch的TDigestState类中看到其对t-digest实现的封装。t-digest提供了两种TDigest算法的实现：MergingDigest对应上面提到的buffer-and-merge算法AVLGroupTree对应AVL树的聚类算法。MergingDigest用在数据集已经排好序的场景，可以直接根据压缩比计算质心的个数，而AVLGroupTree则需要用AVL树根据其“接近度”来自信判断数据，然后计算质心的数量。MergingDigest的实现相对简单。顾名思义，它的算法叫做buffer-and-merge，所以实现中使用tempWeight和tempMean两个数组来表示质心数组，合并数据和保存的质心数。如果超过权重上限，则创建新的质心数，否则修改当前质心的平均值和个数。与MergingDigest相比，AVLGroupTree多了一步，通过AVL二叉平衡树搜索最接近质心数的数据。找到最接近的质心数后，同样将两者合并，然后判断权重是否超线，然后修改或创建action。接下来我们直接看AVLGroupTree的add方法。ElasticSearch在处理一个数据集时，会通过调用add函数不断将数据集中的数据添加到质心数上，统计完成后调用其分位数计算百分位数。后记欢迎大家继续关注程序员李小兵，会持续为大家带来数据存储、数据分析、分发相关的文章。下一篇我们再回过头来了解一下ElasticSearch的其他聚合分析操作的实现原理。
