作者：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作用广告预估服务中做了一次成功的实践。它帮助工程师降低在开发进程中的危险，提速在项目中的迭代功率。让算法预估服务的飞轮越转越快！
