大家好，今天来为大家解答ElasticSearch 如何使用 TDigest 算法计算亿级数据的百分位数？-51CTO.COM这个问题的一些问题点，包括也一样很多人还不知道，因此呢，今天就来为大家分析分析，现在让我们一起来看看吧！如果解决了您的问题，还望您关注下本站哦，谢谢~
[[393929]]
本文转载自微信公众号“程序员李小兵”，作者：李小兵。转载本文请联系程序员李小兵公众号。
大家好，我叫李小兵。 ElasticSearch作为分布式开源搜索分析引擎，不仅可以进行全文匹配搜索，还可以进行聚合分析。
今天我们就来看看百分位百分位分析，这种分析比较常见的是它的聚合分析。 n个数据按数值排列，第p%位置的值称为第p个百分位数。
例如，ElasticSearch记录了每个网站请求的访问时间，需要计算其TP99，即总体请求中99%的访问时间最长的。
近似算法
当数据量较小或数据集中存储在一个位置时，执行像TP99 这样的百分位数分析很容易。
然而，当数据量不断增长时，数据的聚合分析需要在数据量、准确性和实时性之间进行权衡，而只有其中两个能够满足。
如上图所示，我们一共有三个选项：
数据计算有限：选择高精度、实时性，不可避免地无法处理较大数据量。例如MySQL对单机数据进行统计分析；离线计算：选择数据量大、精度高，导致实时性较差。例如，Hadoop可以提供PB级数据的精确分析，但可能需要很长时间；近似计算：选择较大的数据量和实时性，但会损失一定的精度，如0.5%，但提供相对准确的分析结果。 Elasticsearch 目前支持两种近似算法：基数和百分位数。
cardinality 用于计算字段的基数，即该字段的不同或唯一值的数量。基数是基于HyperLogLog (HLL) 算法实现的。
HLL首先会对数据进行哈希运算，然后根据哈希运算结果的位数进行概率估计，得到基数。有关HLL 算法的详细信息，请参阅文章《Redis HyperLogLog 详解》。
百分位数是本文的重点。
百分位数
ElasticSearch 可以使用百分位数来分析指定字段的百分位数。具体要求如下。分析日志索引下的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算法，另一种是AV L-tree聚类算法。
TDigest采用了近似算法中常用的Sketch的思想，即草图绘制。它利用部分数据来表征整个数据集的特征，就像我们日常的草图一样。虽然和真品有差距，但是看上去和真品却非常相似。能够表现物体的特征。
接下来介绍一下TDigest的原理。例如，如果-30到30之间有500个数字，我们可以使用概率密度函数（PDF）来表示这个数据集。
函数上某一点的y值是其x值出现在整个数据集中的概率。整个函数的面积之和正好为1，可以说它描绘了数据集中数据的分布（比较熟悉的正泰分布图就是这个函数）。
有了数据集对应的PDF函数，数据集的百分位数也可以用PDF函数的面积来表示。如下图所示，75%百分位数是对应75%面积的x坐标。
我们知道PDF函数曲线中的点对应于数据集中的数据。当数据量较小时，我们可以使用数据集的所有点来计算函数，但当数据量较大时，我们只能使用少量数据。替换数据集中的所有数据。
这里，我们需要对数据集进行分组，将相邻的数据分为一组，并用Mean 和Weight 替换该组。这两个数统称为Centroid（质心数），然后用这个质心数来计算PDF。这就是TDigest算法的核心思想。
如上图所示，将质心的平均个数作为x值，将个数作为y值。通过这组质心数可以粗略地画出该数据集的PDF函数。
相应地，计算百分位只需从这些质心数中找出对应位置的质心数，其平均值就是百分位值。
显然，质心数越大，代表的数据越多，丢失的信息也越大，准确度也就越低。如上图所示，如果质心数太大，精度就会损失太多。如果质心数太小，会消耗内存等资源，逼近算法无法达到较高的实时性。
因此，基于压缩比（压缩比越大，质心数代表的数据量就越多），TDigest按照百分位数控制每个质心数代表的数据量。两侧的质心数较小。精度更高，中间的质心数更大，从而达到上面提到的1%或99%百分位数比50%百分位数更准确的效果。
源码分析
ElasticSearch直接使用TDigest的开源实现，t-digest。其github地址是https://github.com/tdunning/t-digest。我们可以在ElastichSearch的TDigestState类中看到它对t-digest实现的封装。
t-digest 提供了TDigest 算法的两种实现：
MergingDigest对应于上面提到的缓冲合并算法，AVLGroupTree对应于AVL树的聚类算法。 MergingDigest用于数据集已经排序的场景，可以直接根据压缩比计算质心数，而AVLGroupTree则需要使用AVL树，根据数据的“接近程度”自信地判断数据，然后计算质心数。
MergingDigest的实现比较简单。顾名思义，该算法名称为buffer-and-merge，因此实现中使用两个数组tempWeight 和tempMean 来表示质心数数组，将数据与保存的质心数合并，然后如果超出权重限制，则创建新的质心数，否则修改当前质心数的平均值和数量。
与MergingDigest相比，AVLGroupTree多了一个步骤，即通过AVL二叉平衡树搜索最接近质心数的数据。找到最接近的质心数后，将两者合并，然后判断是否超出权重并进行修改或创建操作。
接下来我们直接看AVLGroupTree的add方法。
ElasticSearch在处理一个数据集时，会通过调用add函数不断地将数据集中的数据添加到质心数上，然后统计完成后，调用它的分位数来计算百分位数。
后记
欢迎大家继续关注程序员李小兵。后续我们将继续为大家带来数据存储、数据分析、分发相关的文章。下一篇我们会回来学习ElasticSearch其他聚合分析操作的实现原理。
关于ElasticSearch 如何使用 TDigest 算法计算亿级数据的百分位数？-51CTO.COM，的介绍到此结束，希望对大家有所帮助。
本文采摘于网络，不代表本站立场，转载联系作者并注明出处：https://www.iotsj.com//kuaixun/7295.html
用户评论
有没有想过处理亿级数据也能精准计算百分位数？
有19位网友表示赞同！
这篇文章讲的是 Elasticsearch 用Tdigest 算法做到这点了，感觉很厉害。
有9位网友表示赞同！
ElasticSearch 能处理这么多数据真的很牛啊，学习一下 TDigest 算法可以提高分析效率。
有11位网友表示赞同！
之前遇到大数据百分位数计算的问题，不知道怎么解决，看来这个方法挺不错的。
有11位网友表示赞同！
Tdigest 算法感觉很有意思，用来处理海量数据的精度也很高。
有19位网友表示赞同！
要写报表就经常用到百分位数，如果能用这种高效的方法那就更方便了。
有9位网友表示赞同！
ElasticSearch 和 Tdigest 两个关键词都非常吸引人，一定要认真看看这篇文章。
有17位网友表示赞同！
大数据处理的应用越来越广泛，学习新的算法和工具很重要。
有8位网友表示赞同！
文章好像讲的是可以快速计算百分位数，应该能节省很多时间。
有19位网友表示赞同！
对 ElasticSearch 不太熟悉，希望这篇文章能解释清楚 Tdigest 的工作原理。
有13位网友表示赞同！
处理大数据分析一直是个挑战，这个方法很有潜力。
有10位网友表示赞同！
51CTO.COM 的文章质量还是可信的，可以参考一下看看技术分享。
有9位网友表示赞同！
如果有代码示例就更好了，能够实际操作理解效果更好。
有13位网友表示赞同！
学习新的数据处理技法始终是个长期的目标，需要不断积累和实践。
有18位网友表示赞同！
看了标题很期待这个文章能够深入介绍 Tdigest 的应用场景。
有7位网友表示赞同！
这种方法是否适合我目前的工作项目呢？看文章内容才能确定。
有13位网友表示赞同！
学习 Elasticsearch 和相关算法可以提升工作能力，值得花时间去钻研。
有18位网友表示赞同！
很多时候数据分析要面对大规模数据挑战，学习这类技术的意义很大。
有8位网友表示赞同！
这篇文章能否提供一些实战案例，让我想象一下应用场景？
有5位网友表示赞同！