vivo 互联网AI团队- Liu Zuocheng、Zhou Baojian

使用基于有限有向图的调度框架，可以控制在线服务中异步调度的流程，但这对分支路径的管理不够友好，随着节点增多，调度流程会越来越复杂而难以控制。因此我们实现了支路径的图调度框架，解决普通图调度框架可扩展性差的问题。

一、图调度框架简介

1.1 vivo效果广告预估服务

vivo效果广告实时在线服务是提供实时AI算法推荐的服务。在广告投放场景，承载了一天百亿级别数量的请求，支持vivo广告收入。在可用性、可扩展性等方面具有非常高的要求。服务中起到调度作用的模块，上下游依赖特别多，比如特征服务、ABT实验平台、实时数据流、模型计算模块等等。调度模块在请求下游服务的方式都是采用异步的方式。那么我们是怎么管理这么多异步请求的呢？

异步调用已成为系统设计中的主流方法。虽然异步调度提升了系统性能，提升了资源的利用率，但却对系统的可扩展性和可维护性提出了挑战。回忆历史中用过的异步管理方法有以下三种。

• 面向过程方法
• 树调度
• 有限有向图管理

单纯使用 面向过程的方法 ，简单却粗放，随着下游服务增多，代码逻辑中产生大量的callback函数和类使，得系统调度过程繁杂无序，可扩展性和可维护性变差。

树调度方法 ，使得异步调度进入框架调控的新阶段。可扩展性方面较面向过程的方法要好很多。但树结构不能准确描述复杂服务的调用流程。

有限有向图 ，是目前使用最为广泛的方法。扩展性较好，能管理复杂的调用流程。但这是否是一种完美的方法呢？不是的。有限有向图，对图中节点是全路径访问，对分支路径的管理不够友好。因此我们依然要探索新的方法。

为了解释有限有向图在实时在线服务中的局限性，我们以vivo效果广告预估服务的调度流程为例，进行说明。把调度流程经过抽象后，调度流程如左图一样简洁明了，但这只是理想状态。

那么现实状况又是什么样子的呢？大家来看，和所有的实时在线服务一样，我们在系统设计时，为了系统健壮，总要和大量的异常和超时做斗争。并且除了异常和超时，系统还需要有兜底逻辑。上一个简洁明了的有限有向图已经不复存在。

为了进一步说明，有限有向图不能完全把控在线服务中异步调度的流程。我们依据刚才展示的流程调度图，做了一个状态转换图。在这个图中，展示了系统中各个状态的流转路径，总数达到了7条之多。有限有向图是一种全路径图调度框架，已经难以适用复杂度不断增长的系统。

二、分支路径图调度框架的实现

全路径图调度框架具体有什么痛点，逼迫让我们去寻找新的方法。具体原因就在这里，有限有向图在落地实践中，使用skip状态变量约束路径。系统在处理一次任务的过程中，不经过的路径上的所有节点状态都会被设置为skip。

全路径的图调度框架中，每增添一个节点，会导致：控制变量数量 +1，状态全集 x2， 复杂度成指数增长。在如此状态下，对复杂系统添加流程或调整流程，就会变成工程师的噩梦。设计开发时必须小心甚微，上线时则如履薄冰。

为了安全开发和提升迭代效率，新的调度方法被迫切地创建出来，那就支持分支路径的图调度框架。它的原理，则是在原有的图调度框架中，添加两处功能，一是加入了分支节点，二是对于图中节点的触发和激活支持“与”激活和“或”激活。是不是像极了逻辑电路呢？

大家是否有疑问，添加两处修改就可以了吗？这样做真的有效吗？其实依据，就来自于我们的《编译原理》里的常见概念和常见规律。

有限有向图，是一种NFA，即不确定的有限自动机。我们都知道，在实践中NFA实现难度很大，它不如DFA简洁和简单。所以结论呼之欲出，支持分支路径的图调度框架，则是把图变成DFA。我们还给它起了新名字，DDAG。

三、在vivo 效果广告推荐系统中的落地过程

实践是检验真理的唯一标准，我们再通过实际的落地过程看，分支路径调度框架是否满足我们的预期。

我们回忆一下vivo效果广告预估服务的调度流程，那一个充满着异常、超时、兜底逻辑的调用图。为了便于说明，我们把它化简了一下，变成一个流程图，如左图，目前它还是一个全路径的调度图。使用分支路径调度框架改造后，变成右图，图中添加了判断节点，具体路径的走向则由判断逻辑来控制。大量Skip的状态控制变量依然不复存在。图中蓝、青、红分别代表了3条路径，让路径和流程一目了然。

当图与实时在线系统融合在一起的时候，我们发现了分支路径图调度框架更多的提升空间。比如，图的整体的超时、异常管理，图中节点的超时、异常管理，以及复杂图结构的自动化简，会成为我们以后进一步升级的空间。

分支路径图调度框架在vivo效果广告预估服务中做了一次成功的实践。它帮助工程师降低在开发过程中的风险，提速在项目中的迭代效率。让算法预估服务的飞轮越转越快！