多 RID 分层路径计算性能优化

本文分享自天翼云开发者社区《多RID分层路径计算性能优化》.作者：罗****斌

针对以上问题和性能分析点，进行了以下优化，分别是：

1）基础探测图按 rid 分层染色计算所有点到点路径，零拷贝萃取整个路径算法需要修改的部分，单独创建一个临时变量用于不可避免的一次路径计算过程中写操作，防止任何一次两点路径计算更改全局基础探测图操作，这样一个频道下任意两点之间路径并按 rid 分层染色计算路径都可以在一个基础探测图里实现，而不是每次进行两点之间路径计算就拷贝一次基础探测图，赋值及循环耗时非常大。

2）按 rid 再细粒度拆分路径计算任务在之前，最小路径计算单元是点到点之间的路径计算，如果遇到一个点里有多 rid，则在计算点到点路径时串行循环计算 rid，如果 rid 很多，则此次路径计算会占用较长 cpu 时间而无法去处理其它部分。现在对这部分逻辑进行优化，原则就是按 rid 粒度拆分路径计算单元，挺高并发度，更好的利用协程效应。

3）节点按 rid 染色分层循环次数缩小至节点个数之前在图遍历时实时判断 rid 归属分层并染色，遍历次数和判断次数是：节点个数*节点个数。现在是在创建的临时变量里遍历节点个数并按 rid 提前进行分层染色，标记为某种状态，称之为预分层染色，大大减少遍历次数和判断次数。

4）路径计算协程个数及队列大小调整随着业务发展，面临的场景也在不断变化，之前的配置是按一个点到点计算一条路径来优化配置的。而现在按 rid 分层计算则使路径计算量暴增，点到点拆分出的计算任务按 rid 倍数增长，需要对其并发处理个数喝队列缓存大小进行调整。

5）json 字段优化在两两互探节点较多时，预处理模块处理性能较之前下降明显。如 500*500 节点场景下，旧版本 1.15.0 预处理模块耗时是 80 毫秒，而新版本 1.16.0 不开启 rid 计算并且每个节点携带 40 个 rid 时耗时变成 940 秒，下降 11 倍，有点触目惊心。后分析发现，耗时基本在 json.Unmarshal，预处理以往观察也确实在这块耗时较大，这说明没有引入新的函数导致了预处理模块性能下降。对此，仔细查看 json.Unmarshal 性能火焰图后发现其中在数组创建上消耗很大，联想到最近新增的 rid 字段并使用数组类型接收，有可能是这块导致。随后把 rid 字段去除上报 1.16.0 版本，预处理模块处理耗时瞬间降低到 110 毫秒，反向证明 rid 数组是罪魁祸首。

经过反复思考验证后，把 rid 字段改为字符串类型性能可到较大提升，预处理模块耗时下降到 240 毫秒，在多出 rid 字段处理情况下，性能损耗基本能接受，故新增一个 rids 字段为字符串类型，删除 rid 为组数类型字段。

6）路径汇聚优化为两重汇聚之前的汇聚是一个协程进行按频道名进行路径汇聚，现在按 rid 拆分计算任务暴增后处理性能跟不上，导致汇聚队列积压影响路径计算速率，计划对这部分进行多次汇聚优化。增加一层并发汇聚，并发数可配置，进行粗粒度汇聚后降低待汇聚条数，然后再定义一个单协程二层汇聚进行最终汇聚，主动汇聚或者被动汇聚在二层汇聚里判断实现。