一、问题描述与技术挑战
在实际工作中，我们发现许多业务场景中都有对某一数值型指标实时统计分位数的需求，一般要求计算结果有很高准确率同时具备极低的计算延迟，实现这类需求给数据RD的开发工作带来一定的挑战，其中主要的技术挑战包括以下三个方面：
无法对全量数据进行排序：由于在实时计算场景中是逐条处理数据的，无法对全量数据排序，进而无法获得全量数据的分位数
计算逻辑复杂，计算延迟高：即时在能够排序的场景中，高复杂度的排序操作也会带来很高的计算延迟，无法满足实时计算的低延迟要求
分位数结果无法聚合：两个计算得出的分位数结果无法像求和结果那样直接累加合并得到新的结果，这为分位数计算结果的存储方式带来挑战
针对上述问题，我们基于TDigest数据结构，实现了实时计算环境下的分位数计算方法，封装为基础组件并向上提供API接口，可以在不同的业务场景（内核性能、搜索性能、PUSH等）下提供实时、准确的分位数计算。
二、基础架构与解决方案
本节我们将从计算分位数的常用数据结构、我们实现分位数计算的基础架构、解决方案三部分介绍流式计算场景下的分位数计算方法：
2.1 分位数的常用数据结构
TDigest计算分位数 TDigest是一个简单，快速，精确度高，可并行化的近似百分位算法，被Spark, ES, Kylin等系统使用。TDigest的核心思想是通过聚类的方法将离散的数据点聚集为多个不同的质心，在通过线性插值法计算分位数，线性插值法是最简单的插值算法。
通俗的讲：传统方法是对离散的数据进行排序，在排序结果中直接获得分位数。而TDigest是将离散的数据聚类为多个质心，然后对质心进行近似的“排序”，最后通过插值法求取分位数。
如上图所示，将离散的数据点(图中无色的数据点)聚类为多个不同的质心(图中彩色的数据点)，其中每个质心周围的数据点数决定了该质心所占的权重(图中质心的大小)，最后通过对所有的质心进行排序，就可以使用线性插值法求取对应的分位数，其中数据点与质心的距离和权重关系如下图所示。
特别地，在每个TDigest创建时有一个重要的compression参数，主要用于在计算的精确度与空间复杂度之间做权衡：
当compression参数设置越大时，聚类得到的质心越多，则差分法求取的分位数精确度越高
当compression参数设置越大时，TDigest数据结构占用的存储空间越大，则分位数计算的空间复杂度越高
设置合适的compression参数，能够在提高计算准确率的同时，尽可能降低存储空间，从而满足业务的实际需求
为了帮助大家在做分位数计算时能够选取合适的参数，我们选择百万级的数据量(即统计100w个随机变量的分位数)，在不同参数下的计算精确度和空间复杂的如下表所示：
针对上表所示的数据，我们将做出以下三点说明：
本次测试使用MergingDigest数据结构，该结构占用的空间与compression参数的取值有关，与统计的数据量无关；
随着数据量的增大，compression的取值应适当增大，能够有效提高计算的准确率
2.2 分位数组建的基础架构
由于实时分位数计算是一个常见统计方法，在许多业务场景都会提出类似的需求，对需求方关注的统计指标计算不同的分位数。
为节约人力成本，缩短迭代开发的时间周期，我们基于TDigest数据结构，封装了通用的基础组件，从而在不同的业务场景下快速实现实时分位数统计的开发。
如上图所示，在实时分位数计算的通用组件中，其基础架构和执行过程主要分为以下几个关键步骤：
- 从上游业务方读取需要统计分位数的原始数据
- 根据业务方需求的分组规则，按分组聚合为TDigest数据结构，将聚合结果存入Redis中，或与Redis中已存在对应的数据进行合并，以获取准确的计算结果
- 从TDigest结构中获取分位数的计算结果，并向上返回
综上所述，我们通过封装基础组件并向上提供API的方式，实现了通用、灵活且对应用方透明的分位数计算方法，能够保证实时性的同时，实现高准确率、低空间复杂度的分位数计算，目前已经在性能平台、搜索、PUSH等厂内多个业务需求中落地应用
2.3 整体实现方案
基于上述介绍的实时分位数基础组件，在厂内的大多数业务场景中，通常从消息队列中获取应用方上报的原始数据，经过一系列解析和计算后，将计算结果存储Doris等OLAP引擎或DB中，共需求方查询和生成对应报表，这是一个通用的解决方案。 根据上述分析，我们就可以得到一个分位数实时计算作业的基本架构，其架构模型如下图所示：
如上图所示，在厂内的环境中，实时分位数计算任务的常用基本架构主要包括以下几个关键步骤：
1）从消息队列中读取业务方上报的基础数据，并按业务逻辑进行数据解析；
2）通过FlatMap方法，按不同字段将一条数据展开为多条（具体内容将在第3节详细介绍）；
3）根据业务设计的查询维度，按不同的key对数据进行分组操作
4）分别将每个key的数据合并为一个TDigest数据结构
5）将聚合后的数据与Redis中存储的数据进行合并，同时将合并结果写回Redis中
6）最后根据数据聚合结构，从每个分组对应的TDigest结构中获取对应的分位数
综过以上步骤，可以实现高实时性、高精确度和低空间复杂度的实时分位数计算方法，能够满足大多数实时分位数业务的需求，在更多的业务场景中可能需要根据实际需求进行适当的调整。
三、解决分位数无法聚合的问题
3.1 问题描述
在实际的业务需求中，我们可能需要按照不同的时间、查询维度等信息检索统计的分位数。但是，已经计算好的两个分位数结果是无法进行聚合操作的。 例如：针对手百APP的用户访问时长，我们可以将某一天中每个小时访问时长的和(SUM)进行累加，从而获得这一天的访问时长总和。但我们如果记录了每个小时中访问时长的80分位数，则无法对这些分位数进行聚合，即无法求得这一天中访问时长的80分位数。这种现象被称为分位数的“不可聚合性”
因此，在实际应用中，如果业务需求要对不同时间、不同维度下的指标分位数进行任意聚合、查询等操作，就为分位数的计算和存储提出新的技术挑战。
3.2 分位数聚合方案
针对上述问题，我们提出按所有查询维度进行提前聚合计算的解决方案，即针对每一种可能出现的查询维度组合，我们都提前计算分位数并存储，这样在查询过程中直接检索对应查询维度的聚合计算结果，在解决了分位数的“不可聚合性”问题的同时，也避免了重复的聚合计算带来的时间开销，缩短了查询耗时，提升了用户体验。
接下来，我们通过一个简单实例讲解具体的聚合计算方法：假设在某业务场景中，用户关注的查询维度共有三个字段，分别为：APP版本(app_version)、厂商(manufacturer)和客户端操作系统版本(os_version)。则对于任意维度组合的查询操作，用户有可能采用 2^3=8 种聚合查询方式。因此，我们通过排列组合的方式，枚举中所有可能的聚合查询方式，分别统计分位数。假设从上游读取到的部分数据如下表所示：
并且，如果对某一字段进行聚合查询，我们将该字段的取值记为关键词 “ALL”，则这条数据共对应2^3=8 种可能的聚合查询方式。为了模拟出8种不同的维度排列组合方式，我们利用二进制排列组合的方式，让每个字段严格对应二进制数据中的一位：如果该位的取值为0，则字段内容为上报的原始值（即上表中的实际取值）；若该位的取值为1，则对应字段的取值记为关键词“ALL”。此外，二进制数据中从右至左每一位与字段的对应关系为：
第1位对应os_version
第2位对应manufacturer
第3位对应app_version
由此可得，任意字段聚合查询的排列如何方式如下表所示：
这样，我们就通过二进制排列组合的方式，枚举出所有可能的维度组合查询方式。在实际的计算过程中，可以利用流式计算的FlatMap算子，按照上述的排列组合方式，将一条数据扩展为多条数据，并进行分组聚合、计算分位数，将最终的计算结果存入Doris等存储引擎中供用户查询。此时，计算结果中实际已经包含了所有可能的聚合查询方式，业务方可以按需要直接查询到最终的分位数结果，而无需另外进行聚合计算操作，在有效提高查询效率的同时保证了用户体验。
四、结语
以上内容是我们从宏观的角度，对实时分位数计算方法的核心技术、基础架构和技术难点进行了简要介绍。如有任何问题或建议，欢迎大家随时沟通交流。
文章发表在
知乎：一种基于实时分位数计算的系统及方法 CSDN：一种基于实时分位数计算的系统及方法
