针对以上问题和性能分析点,进行了以下优化,分别是:
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拆分计算任务暴增后处理性能跟不上,导致汇聚队列积压影响路径计算速率,计划对这部分进行多次汇聚优化。增加一层并发汇聚,并发数可配置,进行粗粒度汇聚后降低待汇聚条数,然后再定义一个单协程二层汇聚进行最终汇聚,主动汇聚或者被动汇聚在二层汇聚里判断实现。