共计 1992 个字符，预计需要花费 5 分钟才能阅读完成。
作者：vivo 互联网 AI 团队 - Liu Zuocheng、Zhou Baojian
本文依据周保建老师在“2022 vivo 开发者大会 ” 现场演讲内容整顿而成。公众号回复【2022 VDC】获取互联网技术分会场议题相干材料。
应用基于无限有向图的调度框架，能够管制在线服务中异步调度的流程，但这对分支门路的治理不够敌对，随着节点增多，调度流程会越来越简单而难以管制。因而咱们实现了反对分支门路的图调度框架，解决一般图调度框架可扩展性差的问题。
一、图调度框架简介
1.1 vivo 成果广告预估服务
vivo 成果广告实时在线服务是提供实时 AI 算法举荐的服务。在广告投放场景，承载了一天百亿级别数量的申请，反对 vivo 广告支出。在可用性、可扩展性等方面具备十分高的要求。服务中起到调度作用的模块，上下游依赖特地多，比方特色服务、ABT 试验平台、实时数据流、模型计算模块等等。调度模块在申请上游服务的形式都是采纳异步的形式。那么咱们是怎么治理这么多异步申请的呢？
异步调用已成为零碎设计中的支流办法。尽管异步调度晋升了零碎性能，晋升了资源的利用率，但却对系统的可扩展性和可维护性提出了挑战。回顾历史中用过的异步治理办法有以下三种。
- 面向过程办法
- 树调度
- 无限有向图治理
单纯应用 面向过程的办法，简略却粗放，随着上游服务增多，代码逻辑中产生大量的 callback 函数和类使，得系统调度过程繁冗无序，可扩展性和可维护性变差。
树调度办法，使得异步调度进入框架调控的新阶段。可扩展性方面较面向过程的办法要好很多。但树结构不能精确形容简单服务的调用流程。
无限有向图，是目前应用最为宽泛的办法。扩展性较好，能治理简单的调用流程。但这是否是一种完满的办法呢？不是的。无限有向图，对图中节点是全门路拜访，对分支门路的治理不够敌对。因而咱们仍然要摸索新的办法。
为了解释无限有向图在实时在线服务中的局限性，咱们以 vivo 成果广告预估服务的调度流程为例，进行阐明。把调度流程通过形象后，调度流程如左图一样简洁明了，但这只是现实状态。
那么现实状况又是什么样子的呢？大家来看，和所有的实时在线服务一样，咱们在零碎设计时，为了零碎强壮，总要和大量的异样和超时做奋斗。并且除了异样和超时，零碎还须要有兜底逻辑。上一个简洁明了的无限有向图曾经不复存在。
为了进一步阐明，无限有向图不能齐全把控在线服务中异步调度的流程。咱们根据方才展现的流程调度图，做了一个状态转换图。在这个图中，展现了零碎中各个状态的流转门路，总数达到了 7 条之多。无限有向图是一种全门路图调度框架，曾经难以实用复杂度一直增长的零碎。
二、分支门路图调度框架的实现
全门路图调度框架具体有什么痛点，逼迫让咱们去寻找新的办法。具体起因就在这里，无限有向图在落地实际中，应用 skip 状态变量束缚门路。零碎在解决一次工作的过程中，不通过的门路上的所有节点状态都会被设置为 skip。
全门路的图调度框架中，每削减一个节点，会导致：控制变量数量 +1，状态选集 x2，复杂度成指数增长。在如此状态下，对简单零碎增加流程或调整流程，就会变成工程师的噩梦。设计开发时必须小心甚微，上线时则如履薄冰。
为了平安开发和晋升迭代效率，新的调度办法被迫切地创立进去，那就反对分支门路的图调度框架。它的原理，则是在原有的图调度框架中，增加两处性能，一是退出了分支节点，二是对于图中节点的触发和激活反对“与”激活和“或”激活。是不是像极了逻辑电路呢？
大家是否有疑难，增加两处批改就能够了吗？这样做真的无效吗？其实根据，就来自于咱们的《编译原理》里的常见概念和常见法则。
无限有向图，是一种 NFA，即不确定的无限自动机。咱们都晓得，在实践中 NFA 实现难度很大，它不如 DFA 简洁和简略。所以论断跃然纸上，反对分支门路的图调度框架，则是把图变成 DFA。咱们还给它起了新名字，DDAG。
三、在 vivo 成果广告举荐零碎中的落地过程
实际是测验真谛的唯一标准，咱们再通过理论的落地过程看，分支门路调度框架是否满足咱们的预期。
咱们回顾一下 vivo 成果广告预估服务的调度流程，那一个充斥着异样、超时、兜底逻辑的调用图。为了便于阐明，咱们把它化简了一下，变成一个流程图，如左图，目前它还是一个全门路的调度图。应用分支门路调度框架革新后，变成右图，图中增加了判断节点，具体门路的走向则由判断逻辑来管制。大量 Skip 的状态控制变量仍然不复存在。图中蓝、青、红别离代表了 3 条门路，让门路和流程高深莫测。
当图与实时在线零碎交融在一起的时候，咱们发现了分支门路图调度框架更多的晋升空间。比方，图的整体的超时、异样治理，图中节点的超时、异样治理，以及简单图构造的自动化简，会成为咱们当前进一步降级的空间。
分支门路图调度框架在 vivo 成果广告预估服务中做了一次胜利的实际。它帮忙工程师升高在开发过程中的危险，提速在我的项目中的迭代效率。让算法预估服务的飞轮越转越快！