一、图调度框架介绍1.1vivo效果广告预测服务vivo效果广告实时在线服务是提供实时AI算法推荐的服务。在广告场景，每天承载百亿请求，支撑vivo广告收入。在可用性、可扩展性等方面有非常高的要求，在服务中起到调度作用的模块有很多上下游依赖，比如特征服务、ABT实验平台、实时数据流、模型计算模块等。调度模块在请求下游服务时采用异步方式。那么我们如何管理这么多的异步请求呢？异步调用已经成为系统设计的主流方式。异步调度虽然提高了系统性能和资源利用率，但对系统的扩展性和可维护性提出了挑战。召回历史使用的异步管理方式有以下三种。面向过程的方法树调度是有限的，有向图管理只是简单地使用面向过程的方法，简单但广泛。随着下游服务的增多，代码逻辑中会产生大量的回调函数和类，使得系统调度过程复杂无序，扩展性和可维护性差。树调度方式使异步调度进入了框架调控的新阶段。可扩展性比面向过程的方法要好得多。但树状结构无法准确描述复杂服务的调用过程。有限有向图是目前应用最广泛的方法。它具有良好的可扩展性，可以管理复杂的调用过程。但这是一个完美的方法吗？不。有限有向图，图中节点的全路径访问，对分支路径管理不够友好。因此，我们还需要探索新的方法。为了说明有限有向图在实时在线服务中的局限性，我们以vivo的效果广告预测服务的调度过程为例进行说明。将调度流程抽象出来后，调度流程就如左图一样简单明了，但这只是理想状态。那么现实是什么样的呢？你看，和所有的实时在线服务一样，我们在设计系统的时候，为了系统的健壮性，总是要和大量的异常和超时作斗争。而且除了异常和超时之外，系统还需要有自下而上的逻辑。最后一个干净简洁的有限有向图已经一去不复返了。进一步说明，有限有向图不能完全控制在线服务中异步调度的流程。我们在刚才展示的进程调度图的基础上做了一个状态转换图。图中展示了系统中各个状态的流路，总数达到了7个。有限有向图是一种全路径图调度框架，很难应用于复杂度越来越高的系统。2.分支路径图调度框架的实现全路径图调度框架的具体痛点是什么，迫使我们寻找新的方法。具体原因在这里。在有限有向图的实现实践中，跳跃状态变量用于约束路径。当系统在处理一个任务时，所有未通过的路径上的节点的状态都会被设置为skip。在全路径图调度框架中，每增加一个节点，都会导致：控制变量的个数+1，状态的完整集合x2，复杂度呈指数级增长。在这样的状态下，给复杂的系统增加流程或调整流程就成了工程师的噩梦。设计开发要慎重，上线要小心谨慎。为了安全开发和提高迭代效率，迫切创建了一种新的调度方法，它支持分支路径的图调度框架。它的原理是在原有的图调度框架上增加了两个功能，一个是增加分支节点，一个是支持“and”激活和“or”激活，用于图中节点的触发和激活。它看起来像逻辑电路吗？大家有什么疑问，加两个修改就够了吗？这真的有效吗？其实依据是来自于我们《编译原理》中的常用概念和常用规律。有限有向图是NFA的一种，即不确定的有限自动机。我们都知道NFA在实践中实现起来非常困难，也没有DFA那么简洁和简单。所以结论呼之欲出了。支持分支路径的图调度框架就是把图变成DFA。我们还给它起了一个新名字，DDAG。3、vivo效果广告推荐系统的落地流程实践是检验真实性的唯一标准。下面通过实际落地过程看看分支路径调度框架是否符合我们的预期。我们回想一下vivo的效果广告预测服务的调度流程，这是一个充满了异常、超时、底线逻辑的调用图。为了便于说明，我们将其简化，变成了流程图，如左图所示。目前还是全路径调度图。使用分支路径调度框架改造后，就变成了右图。图中增加了判断节点，具体路径的走向由判断逻辑控制。大量Skip的状态控制变量还是没有了。图中蓝色、蓝色、红色分别代表三个路径，路径和流程一目了然。当图与实时在线系统集成时，我们发现分支路径图调度框架有更多的改进空间。比如图的整体超时和异常管理，图中节点的超时和异常管理，复杂图结构的自动简化等，都将成为未来进一步升级的空间。分支路径图调度框架在vivo的效果广告预测服务中进行了成功实践。帮助工程师降低开发过程中的风险，加快项目迭代效率。让算法预测服务的飞轮越转越快！
