Fork me on GitHub

分支路径图调度框架在 vivo 效果广告业务的落地实践

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效果广告预估服务中做了一次成功的实践。它帮助工程师降低在开发过程中的风险,提速在项目中的迭代效率。让算法预估服务的飞轮越转越快!

图片


本文地址:https://www.6aiq.com/article/1679623769756
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出