共计 4005 个字符，预计需要花费 11 分钟才能阅读完成。
导读：性能剖析等场景对实时分位数有强烈诉求。在计算累计时长时，能够将不同时间段的时长简略相加，而分位数却无奈先计算不同维度下的分位值，而后对其间接聚合，该个性对实时计算带来了较大挑战。咱们基于 TDigest 数据结构，利用 Redis 和 Doris 等高性能存储，事后计算所有可能查问的分位值指标，既能够疾速计算指标，同时能够保障查问效率。该零碎曾经对百度内内核性能、网络性能等业务场景进行输入，并能无效满足业务高时效的剖析需要。
全文 3663 字，预计浏览工夫 10 分钟。
一、问题形容与技术挑战
在理论工作中，咱们发现许多业务场景中都有对某一数值型指标实时统计分位数的需要，个别要求计算结果有很高准确率同时具备极低的计算提早，实现这类需要给数据 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 数据结构，封装了通用的根底组件，从而在不同的业务场景下疾速实现实时分位数统计的开发。
如上图所示，在实时分位数计算的通用组件中，其基础架构和执行过程次要分为以下几个关键步骤：
1) 从上游业务方读取须要统计分位数的原始数据
2) 依据业务方需要的分组规定，按分组聚合为 TDigest 数据结构，将聚合后果存入 Redis 中，或与 Redis 中已存在对应的数据进行合并，以获取精确的计算结果
3) 从 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 等存储引擎中供用户查问。此时，计算结果中理论曾经蕴含了所有可能的聚合查问形式，业务方能够按须要间接查问到最终的分位数后果，而无需另外进行聚合计算操作，在无效进步查问效率的同时保障了用户体验。
四、结语
以上内容是咱们从宏观的角度，对实时分位数计算方法的核心技术、基础架构和技术难点进行了简要介绍。如有任何问题或倡议，欢送大家随时沟通交流。
本期作者 | 子阳，负责百度性能平台的实时数据开发工作，次要钻研方向为流式计算、智能预测等
招聘信息
百度 APP 技术平台研发部负责百度 APP 和百家号技术平台建设，也承载着 PUSH、音讯、互动、交易、日志、性能、审核、B 端等一系列标杆中台的建设，欢送大家加盟，期待着你的到来！
无论你是后端，前端，还是大数据，这里有若干职位在等你，欢送投递简历，【联系方式同名公众号百度 Geek 说，输出内推即可】百度 APP 技术平台研发部期待你的退出！
浏览原文
|一种基于实时分位数计算的零碎及办法
举荐浏览
|商业落地页端到端性能优化实际
|详解撑持 7 亿用户搜寻的百度图片解决收录中台
———- END ———-
百度 Geek 说
百度官网技术公众号上线啦！
技术干货 · 行业资讯 · 线上沙龙 · 行业大会
招聘信息 · 内推信息 · 技术书籍 · 百度周边
欢送各位同学关注
