随着美团外卖业务的飞速发展,外卖广告系统压力变得越来越大,算力开始成为新的瓶颈。2021年上半年,外卖广告的数条业务线开始出现算力资源不足的情况,算力分配效率亟待提升。在外卖场景下,流量呈现明显的双峰结构,广告系统在高峰时段面临较大的性能压力,非高峰时段存在大量算力冗余。智能算力旨在对流量算力进行精细化和个性化分配,从而实现系统算力约束下的业务收益最大化。
本文是广告智能算力系列文章的第二篇,在第一期《美团外卖广告智能算力的探索与实践》中[1],我们对阿里DCAF[2]线性规划求解方案进行了外卖场景下的优化,落地了弹性队列局部最优算力分配方案(以下简称“第一期”)。如上图所示,外卖展示广告链路中,召回通道和模型决策均使用固定策略,在算力不足时会丢失部分优质流量带来的收益。
在本文中,我们提出了基于进化算法的多动作算力决策方法ES-MACA(Evolutionary Strategies based Multi-Action Computation Allocation)。在外卖广告链路上,同时决策弹性通道、弹性队列和弹性模型三个动作。在后置动作决策中,我们考虑前置模块的决策引起的状态变化,同时使用多任务模型联合建模实现系统仿真模拟(离线仿真+收益预估,实现不同决策动作下的收益评估功能),实现全链路最优算力分配。相对第一期内容,ES-MACA在外卖展示广告业务线上取得CPM+1.x%、收入+1.x%的效果。
为了应对极大的在线流量压力和庞大的候选集,外卖广告投放系统将整个检索过程设计成候选集依次递减的漏斗型级联架构,主要包含召回、粗排、精排、机制等模块。在第一期中,我们把算力分配的手段定义为弹性动作,并结合外卖场景归纳了弹性队列、弹性模型、弹性通道和弹性链路等四种动作,具体动作的定义如下:
在一个包含M个算力决策模块的链路中,全链路最优的智能算力的目标可通用的描述为:通过智能化决策M个模块的算力档位,在整体算力满足约束的条件下,使得整体流量收益最大化。
该问题的一般形式化描述为:
以上是多个算力决策模块的场景,在外卖展示广告中,对算力和收益较为敏感的决策模块为广告召回策略、精排队列长度和精排预估模型,分别对应弹性通道、弹性队列和弹性模型三个动作。
在本期中,我们同时考虑弹性通道、弹性队列和弹性模型三个模块的算力联合决策。
在多个模块联合决策时,同一个请求的不同模块动作之间互相会产生影响。如下图所示,弹性通道决策结果决定了真实召回队列(包括候选队列的长度和广告类型等信息),直接影响了弹性队列的输入状态。同理,弹性队列的决策结果影响了弹性模型的输入状态。因此,在多动作联合建模中,我们增加了请求“状态”特征,让决策动作与系统产生交互,更好地拟合系统状态的过程。
外卖智能算力第一期中,我们针对外卖广告场景,在DCAF方案的基础上进行了一系列探索和改进,并初次进行了模型弹性分配的尝试,取得了不错的收益。近年,阿里CRAS[3]方案给出了一种应用于预排、粗排和精排队列联合优化的联合最优算力分配线性规划方案。从弹性动作的分类来看,该方案以一种优雅的方式解决了三个弹性队列的联合优化问题,CRAS通过一些数据分析和合理假设,将原始问题拆解为三个互相独立且相似子问题,然后分别对三个子问题进行求解。
但是已有方案是基于线性规划方案的,且仅关注一个或多个弹性队列优化问题,在面对非弹性队列动作组合,如弹性通道和弹性模型时,方案无法直接迁移。特别地,在约束条件或优化目标发生变化时,线性规划方案需要重新对特定业务问题进行建模和求解,需消耗大量的人力;此外,目前已有线性规划方案的问题建模和求解过程中往往包含一些业务数据相关的强假设,这些假设在新的业务上可能难以满足,这进一步使得已有方案难以拓展迁移到新的业务问题上。
由于外卖场景的LBS限制,外卖广告的候选队列相对非LBS电商场景较短,不需要经过复杂的预排-粗排-精排的过程。在全链路上,我们更关注召回通道、精排队列长度、精排预估模型等模块的算力分配,这些模块其实对算力更加敏感。
整体来看,美团外卖广告场景全链路最优算力分配的挑战主要包括以下两个方面。
通用化问题
序列决策问题
综合考虑以上两个问题,我们将外卖广告全链路最优算力分配问题建模为多阶段决策问题(每个决策模块对应一个决策阶段),按时间顺序依次决策召回方案、截断队列和预估模型。每个阶段中,由Agent与环境交互和决策,Agent参数可使用进化算法或强化学习求解。
全链路算力分配过程可建模为马尔科夫决策过程(Markov Decision Process, MDP)或部分可观测马尔科夫决策过程(Partially Observable Markov Decision Process,POMDP)。如上图所示,状态转移发生在相邻的两个阶段之间,各阶段分别有不同的候选动作(如召回策略,截断长度和预估模型编号等),Reward则在最后一个阶段动作执行后通过系统反馈获得。
我们可以收集在线日志数据,使用离线强化学习(Offline RL)求解Agent;在不担心线上收益受损的情况下,也可以使用在线强化学习(Online RL)求解Agent。但由于业务场景复杂,各阶段算力约束难以统一,不管是离线强化学习还是在线强化学习,都面临多阶段强约束难以建模和求解的问题。
而进化算法作为一种应用广泛、鲁棒性强的全局优化方法,有以下优点:
进化算法能很好地解决外卖广告场景中的问题,既容易扩展到其他业务线,又能非常方便地建模各种决策问题。因此,本期我们选择进化算法来求解外卖场景全链路最优算力分配问题。在后续工作中,我们会尝试使用强化学习方案求解。
如本节迭代路径(图)所示,我们在1.5期中尝试了基于进化算法的单动作算力决策方法ES-SACA(Evolutionary Strategies based Single-Action Computation Allocation),验证了进化算法在算力分配场景的有效性。接下来,本文主要介绍基于进化算法的多动作算力决策方法ES-MACA。
为了实现广告系统全链路上的最优算力分配,我们设计了如下决策方案:
离线训练:随机选择决策Agent参数,批量回放历史流量,Agent与广告投放模拟系统进行交互,完成状态转移过程。根据系统返回的Reward优化决策Agent参数,最终输出离线最优Agent参数,并同步到线上。
在线决策:对于线上单条请求,使用离线最优Agent与线上系统进行交互和决策。
在本期中,我们使用进化算法求解Agent参数。进化算法参数寻优的核心是组合动作价值评估,由于涉及到状态转移过程,组合动作价值评估不再是一个简单的监督学习问题,Agent需要依次与系统交互并执行决策动作,直到最后一个阶段的动作完成时才能从系统中取得收益。一种简单的方案是让Agent在线学习,与系统交互的同时优化自身参数,但在线学习会影响业务收益,这对我们来说是不可接受的。为了解决这个问题,我们通过构造广告投放模拟器,模拟线上广告系统环境,由该模拟器与Agent进行交互,并反馈收益(Reward)。
根据外卖广告的投放场景,我们基于进化算法对整个问题建模如下:
离线参数求解主要分为进化算法参数寻优和Reward评估两个模块。
3.1.2.1 参数寻优
参数寻优模块使用进化算法求解参数。本文以CEM为例,对参数求解过程进行详细讲解:
Tips:NES方案在本场景中效果不如CEM,原因是NES对带约束问题(特别是多约束问题)Reward设计要求过高,在真实场景中难以求解到严格满足约束的参数。
3.1.2.2 Reward评估
离线Reward评估流程:在离线训练时,对于选定的Agent和历史流量。
3.1.2.2.1 离线仿真
在线环境交互面临的困境(离线仿真的必要性):理论上,决策Agent与在线环境交互能获得最真实Reward(收益)反馈,但直接利用在线流量探索会导致以下问题:
离线仿真的最终目标:复现线上交互逻辑和收益反馈。
离线仿真+收益预估解决方案:
3.1.2.2.2 收益预估
目标和挑战点
模型预估方案
模型设计
特征工程
对于线上单条请求,使用离线最优Agent与线上系统进行交互和决策。和离线评估流程一致,依次按照如下流程执行决策过程:
在智能算力第一期中,我们已经完成了以决策组件为核心,以采集、调控和离线组件为支撑的智能算力系统基本建设。在本期中,我们围绕着从单动作局部最优决策扩展到多动作组合最优决策的核心需求。在系统建设上,除了多动作组合最优决策的基本能力建设外,更关注的智能算力系统的稳定性和通用性建设,从而支撑智能算力系统在外卖广告全业务线的全面应用。
决策组件Agent作为智能算力系统的客户端,嵌入到广告投放系统中各个模块,负责系统流量算力的分发决策。在本期中,我们主要在决策能力上进行了轻量化、精细化迭代,以及相关能力的标准化建设。
在决策能力上
建设轻量的多动作组合决策能力:我们基于进化算法实现了轻量的多动作组合决策能力,进化算法相关前文已经介绍,这里主要介绍下轻量化。
为什么需要轻量化:在广告投放系统中,对于线上的时延要求非常严苛,在多动作下需要进行序列决策,决策次数理论上等于决策动作的数量,因此智能算力决策必须在效果不降(或微降)下尽可能的轻量化,才能满足线上RT要求。
如何建设:(1) 模型本地化,减少网络时延,这个也是将决策能力封装到SDK而不是建设模型决策服务的主要原因。(2) 模型轻量化,通过特征工程工作,尽可能地减少特征数量,减少在线特征处理的性能压力。(3) 决策并行处理,决策动作尽量和线上已有流程并行处理,减少整体链路耗时。
轻量化效果:多动作组合决策相对单动作决策,广告链路耗时:TP99+1.8ms、TP999 +2.6ms,满足线上RT要求。
建设精细化的系统状态反馈控制能力:我们基于系统状态的实时收集和PID反馈控制算法,对算力档位参数进行微调,实现广告投放系统在动态算力分配过程中的稳定性保障。
为什么需要精细化:在广告投放系统中,稳定性非常重要,从单动作决策到复杂的多动作决策,智能算力决策的参数档位越来越多,对系统稳定性影响也越来越大,粗粒度的系统状态反馈控制已经无法保障系统稳定。在第一期弹性队列方案中也出现过稳定性调控异常的情况,在只依据粗粒度的整体集群系统状态数据进行稳定性调控时,会偶发单机性能异常引起整体集群状态变化剧烈,导致算力调控不稳定。
如何建设:一方面是系统状态数据的精细化,数据粒度从集群细化到机房和单机,同时数据指标支持细粒度的自定义扩展。另一方面是系统调控目标和策略的精细化,调控目标从集群的整体稳定细粒度到机房和单机稳定,我们将系统状态实时反馈控制的最小单位定义为一个调控器,对于每一个调控目标,需要一个或一组调控器支持。另外,为更好地支持单机粒度的反馈控制,我们将系统状态反馈控制能力从调控组件迁移复用到了决策组件,决策组件可以通过容器信息读取和拦截的方式,直接采集部分单机粒度的状态指标,并将调控结果作用到嵌入的机器,形成闭环调控;单机粒度的反馈控制不再强依赖采集组件的链路反馈,系统状态反馈的时延,也从秒级降低到了毫秒级,极大地提高了反馈控制的准确性和效率。
在标准化建设上
在多动作组合决策下对在线决策有了新的要求,一方面需要考虑通用性,做好基础能力沉淀,另一方面需要和上层业务减少耦合,从而赋能更多动作和业务场景;同时外卖广告工程架构已经完成了阶段性的平台化建设[4],其中标准化是平台化建设的基础,因此智能算力决策组件分别从功能、数据、流程上进行了标准化建设。智能算力的标准化建设,对智能算力从单动作决策到多动作组合决策再扩展到各大业务场景(点—>线—>面)的全面建设,具有重要意义。
我们将最小不可拆分的功能单元抽象为Action,在智能算力决策链路上的Action主要有:实验、特征拉取、特征计算、词典处理、参数处理、DCAF决策、ES-MACA决策、系统状态反馈控制、日志收集、监控等。通过Action的复用和扩展,提高在新动作场景和业务线上的接入效率。
在广告工程平台化建设中,使用上下文Context描述Action执行的环境依赖,包含输入依赖、配置依赖、环境参数依赖等。在智能算力在线决策中,我们在广告基础Context下扩展了智能算力Context,封装和维护智能算力的环境依赖,主要包含标准化的输入输出、决策特征、决策参数、决策策略等,Action间基于Context实现数据交互。
业务的调用流程是完成功能和数据的组合,统一的流程设计模式是业务功能复用和提效的核心手段,我们基于平台化建设的管理平台和调度引擎,通过对Action的可视化拖拽,实现了智能算力功能的DAG编排和调度。
采集组件负责实时采集广告投放系统的状态数据,并进行标准化预处理,调控组件一方面依赖状态数据实现对整个系广告投放统状态的实时感知和系统模块粒度的算力调控;另一方面作为智能算力系统的中控服务,负责智能算力系统的系统管理,包含业务管理、策略管理、动作管理以及元信息管理等。
我们将系统状态实时反馈控制的最小单位定义为一个调控器,对于每一个动作决策,会涉及一到多个模块的算力变化,而每个模块的算力变化会带来多个数据指标的变化,因此对于一个动作可能需要配置多个调控器。从单动作决策扩展到多动作,这些调控器的数量会越来越多,如何提高对调控器的管理和接入效率,是一个关键问题。这里我们主要进行了异构数据标准化、调控流程通用化建设,基本实现了新调控场景的配置化接入,无需开发和发版。
异构数据标准化
采集组件有多个异构数据源,包含来着美团监控系统CAT上报的业务数据、Falcon收集的机器指标数据,还有部分决策组件上报的数据。经过对数据格式和内容的分析,我们首先将数据以系统模块Appkey进行划分,Appkey之间数据独立,同时从数据类型(Type)出发,把数据分为业务指标(Biz)和机器指标(Host);从数据维度(Dimension)出发,把数据分为集群粒度(Cluster)、机房粒度(IDC)、单机粒度(Standalone);具体的指标(Metric)包含QPS、TP99、FailRate、其他扩展指标等。
调控流程通用化
有了异构数据的统一表达,我们就可以设计通用的调控流程,我们以ProductId作为调控业务场景的唯一标识,以ControllerId作为调控器的唯一标识,一个ProductId映射一组ControllerId,每一个调控器Controller包含输入指标、调控策略、策略参数、输出结果。通用的调控过程为:获取配置的输入指标、调控策略,基于不同的调控策略选择不同的策略参数,执行该调控策略得到对应的输出结果。
另外,我们对调控器的调控效率和稳定性进行了优化。在外卖的双峰流量场景下,在非高峰时段,PID算法的累计误差容易积累过大,导致到了高峰时段调控周期长,系统状态反馈调节慢;同时也存在系统抖动或数据毛刺产生的不必要调控的情况。
基于此,我们采用了滑动窗口准入准出的机制,来提高效率和准确性。如下图所示,我们对于每一个调控器,维护了一个系统指标的滑动统计窗口,当连续M次系统指标达到了PID目标值T-设置的阈值P,该调控器才成功准入,误差开始累计;同时当连续N次系统指标低于PID目标值T-设置的阈值Q,该调控器成功准出,累计误差清零。
离线组件负责离线模型训练和参数求解等任务,主要包含样本收集、模型训练和参数求解三个部分。
系统算力容量的选取
算力容量指标选取和第一期一致。一方面,为了保证线上系统能根据实时流量快速调整,仍选择15min作为最小的调控单元;另一方面,离线模拟选用的系统容量为过去一周的午高峰流量算力。
Baseline选取
选取无智能算力(固定决策)的流量作为对照组。
离线仿真模拟器——流量价值预估
使用过去14天非实验组数据作为训练集,进行两阶段训练(一阶段全流量训练,二阶段随机探索流量训练),使用当日随机探索流量作为测试集。
离线参数求解
外卖场景中,同环比流量变化趋势基本一致,我们通过重放过去一周流量,离线计算每个时间片内(15分钟为一个时间片)最优参数并存储为词表。
– | Reward |
---|---|
Baseline(系统算力容量=C) | +0.00% |
仅弹性通道(系统算力容量=C) | +1.x% |
仅弹性队列(系统算力容量=C) | +3.x% |
仅弹性模型(系统算力容量=C) | +1.x% |
分模块最优(系统算力容量=C) | +5.x% |
ES-MACA(系统算力容量=C) | +5.x% |
实验说明:
从离线实验的效果来看,我们有以下结论:
通过一周的线上ABTest实验,我们在外卖广告验证了本方案的收益如下:
CPM | GMV | 收入 | CTR | CVR | 机器资源 | |
---|---|---|---|---|---|---|
Baseline(系统算力容量=C) | +0.00% | +0.00% | +0.00% | +0.00% | +0.00% | +0.00% |
仅弹性队列(系统算力容量=C) | +0.x% | +2.x% | -0.x% | +0.x% | +1.x% | -0.05% |
ES-MACA(系统算力容量=C) | +1.x% | +2.x% | +1.x% | +0.x% | +1.x% | -0.41% |
实验设计说明:
这篇文章主要从全链路最优算力决策和系统建设两个方面,介绍了美团外卖广告智能算力从线性规划算法到进化算法的技术演进过程,给出了一种基于进化算法的多动作算力分配方案(ES-MACA)。
未来,在算法策略上,我们将尝试强化学习算法,对系统全链路组合下的算力最优分配问题进行更精细化的建模和求解;在系统建设上,我们还将尝试和美团内部基础架构部门进行合作,从在线系统扩展到在线/近线/离线三层系统,通过智能算力统一决策调度,充分挖掘数据和算力的潜力。
家宏、顺辉、国梁、乾龙、乐彬等,均来自美团外卖广告技术团队。