一种基于实时分位数计算的系统及方法

导读：性能分析等场景对实时分位数有强烈诉求。在计算累计时长时，可以将不同时间段的时长简单相加，而分位数却无法先计算不同维度下的分位值，然后对其直接聚合，该特性对实时计算带来了较大挑战。我们基于TDigest数据结构，利用Redis和Doris等高性能存储，预先计算所有可能查询的分位值指标，既可以快速计算指标，同时可以保障查询效率。该系统已经对百度内内核性能、网络性能等业务场景进行输出，并能有效满足业务高时效的分析需求。

在实际工作中，我们发现许多业务场景中都有对某一数值型指标实时统计分位数的需求，一般要求计算结果有很高准确率同时具备极低的计算延迟，实现这类需求给数据RD的开发工作带来一定的挑战，其中主要的技术挑战包括以下三个方面：

无法对全量数据进行排序：由于在实时计算场景中是逐条处理数据的，无法对全量数据排序，进而无法获得全量数据的分位数

计算逻辑复杂，计算延迟高：即时在能够排序的场景中，高复杂度的排序操作也会带来很高的计算延迟，无法满足实时计算的低延迟要求

分位数结果无法聚合：两个计算得出的分位数结果无法像求和结果那样直接累加合并得到新的结果，这为分位数计算结果的存储方式带来挑战

针对上述问题，我们基于TDigest数据结构，实现了实时计算环境下的分位数计算方法，封装为基础组件并向上提供API接口，可以在不同的业务场景（内核性能、搜索性能、PUSH等）下提供实时、准确的分位数计算。

2.1 分位数的常用数据结构

TDigest是一个简单，快速，精确度高，可并行化的近似百分位算法，被Spark, ES, Kylin等系统使用。TDigest的核心思想是通过聚类的方法将离散的数据点聚集为多个不同的质心，在通过线性插值法计算分位数，线性插值法是最简单的插值算法。

通俗的讲：传统方法是对离散的数据进行排序，在排序结果中直接获得分位数。而TDigest是将离散的数据聚类为多个质心，然后对质心进行近似的“排序”，最后通过插值法求取分位数。

如上图所示，将离散的数据点(图中无色的数据点)聚类为多个不同的质心(图中彩色的数据点)，其中每个质心周围的数据点数决定了该质心所占的权重(图中质心的大小)，最后通过对所有的质心进行排序，就可以使用线性插值法求取对应的分位数，其中数据点与质心的距离和权重关系如下图所示。

特别地，在每个TDigest创建时有一个重要的compression参数，主要用于在计算的精确度与空间复杂度之间做权衡：

当compression参数设置越大时，聚类得到的质心越多，则差分法求取的分位数精确度越高

当compression参数设置越大时，TDigest数据结构占用的存储空间越大，则分位数计算的空间复杂度越高

设置合适的compression参数，能够在提高计算准确率的同时，尽可能降低存储空间，从而满足业务的实际需求

为了帮助大家在做分位数计算时能够选取合适的参数，我们选择百万级的数据量(即统计100w个随机变量的分位数)，在不同参数下的计算精确度和空间复杂的如下表所示：

针对上表所示的数据，我们将做出以下三点说明：

本次测试使用MergingDigest数据结构，该结构占用的空间与compression参数的取值有关，与统计的数据量无关；

由于实时分位数计算是一个常见统计方法，在许多业务场景都会提出类似的需求，对需求方关注的统计指标计算不同的分位数。

为节约人力成本，缩短迭代开发的时间周期，我们基于TDigest数据结构，封装了通用的基础组件，从而在不同的业务场景下快速实现实时分位数统计的开发。

如上图所示，在实时分位数计算的通用组件中，其基础架构和执行过程主要分为以下几个关键步骤：

1) 从上游业务方读取需要统计分位数的原始数据

2) 根据业务方需求的分组规则，按分组聚合为TDigest数据结构，将聚合结果存入Redis中，或与Redis中已存在对应的数据进行合并，以获取准确的计算结果

3) 从TDigest结构中获取分位数的计算结果，并向上返回

根据上述分析，我们就可以得到一个分位数实时计算作业的基本架构，其架构模型如下图所示：

如上图所示，在厂内的环境中，实时分位数计算任务的常用基本架构主要包括以下几个关键步骤：

1）从消息队列中读取业务方上报的基础数据，并按业务逻辑进行数据解析；

2）通过FlatMap方法，按不同字段将一条数据展开为多条（具体内容将在第3节详细介绍）；

3）根据业务设计的查询维度，按不同的key对数据进行分组操作

4）分别将每个key的数据合并为一个TDigest数据结构

5）将聚合后的数据与Redis中存储的数据进行合并，同时将合并结果写回Redis中

6）最后根据数据聚合结构，从每个分组对应的TDigest结构中获取对应的分位数

例如：针对手百APP的用户访问时长，我们可以将某一天中每个小时访问时长的和(SUM)进行累加，从而获得这一天的访问时长总和。但我们如果记录了每个小时中访问时长的80分位数，则无法对这些分位数进行聚合，即无法求得这一天中访问时长的80分位数。这种现象被称为分位数的“不可聚合性”

接下来，我们通过一个简单实例讲解具体的聚合计算方法：假设在某业务场景中，用户关注的查询维度共有三个字段，分别为：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

由此可得，任意字段聚合查询的排列如何方式如下表所示：

本期作者 | 子阳，负责百度性能平台的实时数据开发工作，主要研究方向为流式计算、智能预测等

推荐阅读

｜商业落地页端到端性能优化实践

｜详解支撑7亿用户搜索的百度图片处理收录中台

----------  END  ----------