美团外卖广告智能算力的探索与实践(二)

在深度学习时代,算力的需求和消耗日益增长,如何降低算力成本,提高算力效率,逐渐成为一个重要的新课题。智能算力旨在对流量算力进行精细化和个性化分配,从而实现系统算力约束下的业务收益最大化。

本文主要介绍了美团外卖广告智能算力从线性规划算法到进化算法的技术演进过程,给出了一种基于进化算法的多动作算力分配方案,希望能给大家带来一些帮助或者启发。

​​​​​​​

1 业务背景

随着美团外卖业务的飞速发展,外卖广告系统压力变得越来越大,算力开始成为新的瓶颈。2021年上半年,外卖广告的数条业务线开始出现算力资源不足的情况,算力分配效率亟待提升。在外卖场景下,流量呈现明显的双峰结构,广告系统在高峰时段面临较大的性能压力,非高峰时段存在大量算力冗余。智能算力旨在对流量算力进行精细化和个性化分配,从而实现系统算力约束下的业务收益最大化。

c8a49ad80a09bb2a842341a1f3dc42cd.png

本文是广告智能算力系列文章的第二篇,在第一篇《美团外卖广告智能算力的探索与实践》中[1],我们对阿里DCAF[2]线性规划求解方案进行了外卖场景下的优化,落地了弹性队列局部最优算力分配方案(以下简称“第一期”)。如上图所示,外卖展示广告链路中,召回通道和模型决策均使用固定策略,在算力不足时会丢失部分优质流量带来的收益。

在本文中,我们提出了基于进化算法的多动作算力决策方法ES-MACA(Evolutionary Strategies based Multi-Action Computation Allocation)。在外卖广告链路上,同时决策弹性通道、弹性队列和弹性模型三个动作。在后置动作决策中,我们考虑前置模块的决策引起的状态变化,同时使用多任务模型联合建模实现系统仿真模拟(离线仿真+收益预估,实现不同决策动作下的收益评估功能),实现全链路最优算力分配。相对第一期内容,ES-MACA在外卖展示广告业务线上取得CPM+1.x%、收入+1.x%的效果。

2 整体思路

为了应对极大的在线流量压力和庞大的候选集,外卖广告投放系统将整个检索过程设计成候选集依次递减的漏斗型级联架构,主要包含召回、粗排、精排、机制等模块。在第一期中,我们把算力分配的手段定义为弹性动作,并结合外卖场景归纳了弹性队列、弹性模型、弹性通道和弹性链路等四种动作,具体动作的定义如下:

  • 弹性队列:线上检索是一个漏斗的过程,不同价值流量可以在级联漏斗的各模块中分配不同候选队列长度。

  • 弹性模型:在模型预估服务中,对于不同价值流量可以选择不同大小模型,大模型相对小模型预估效果更好的同时,消耗的算力也更多。

  • 弹性通道:在召回场景中,不同价值流量可以选择不同复杂度的召回通道和召回通道的路数。

  • 弹性链路:在检索链路上,不同价值流量可以选择不同复杂度的检索链路。

2.1 算力分配问题形式化描述

在一个包含M个算力决策模块的链路中,全链路最优的智能算力的目标可通用的描述为:通过智能化决策M个模块的算力档位,在整体算力满足约束的条件下,使得整体流量收益最大化

该问题的一般形式化描述为:

b5699cb76c60472bfa9f599f4cad78eb.png

以上是多个算力决策模块的场景,在外卖展示广告中,对算力和收益较为敏感的决策模块为广告召回策略、精排队列长度和精排预估模型,分别对应弹性通道、弹性队列和弹性模型三个动作。

在本期中,我们同时考虑弹性通道、弹性队列和弹性模型三个模块的算力联合决策。

0047e2345c976387149f50db09451301.png

在多个模块联合决策时,同一个请求的不同模块动作之间互相会产生影响。如下图所示,弹性通道决策结果决定了真实召回队列(包括候选队列的长度和广告类型等信息),直接影响了弹性队列的输入状态。同理,弹性队列的决策结果影响了弹性模型的输入状态。因此,在多动作联合建模中,我们增加了请求“状态”特征,让决策动作与系统产生交互,更好地拟合系统状态的过程。

72027933066c3a088f65bc38c155d160.png

2.2 挑战分析

外卖智能算力第一期中,我们针对外卖广告场景,在DCAF方案的基础上进行了一系列探索和改进,并初次进行了模型弹性分配的尝试,取得了不错的收益。近年,阿里CRAS[3]方案给出了一种应用于预排、粗排和精排队列联合优化的联合最优算力分配线性规划方案。从弹性动作的分类来看,该方案以一种优雅的方式解决了三个弹性队列的联合优化问题,CRAS通过一些数据分析和合理假设,将原始问题拆解为三个互相独立且相似子问题,然后分别对三个子问题进行求解。

但是已有方案是基于线性规划方案的,且仅关注一个或多个弹性队列优化问题,在面对非弹性队列动作组合,如弹性通道和弹性模型时,方案无法直接迁移。特别地,在约束条件或优化目标发生变化时,线性规划方案需要重新对特定业务问题进行建模和求解,需消耗大量的人力;此外,目前已有线性规划方案的问题建模和求解过程中往往包含一些业务数据相关的强假设,这些假设在新的业务上可能难以满足,这进一步使得已有方案难以拓展迁移到新的业务问题上。

由于外卖场景的LBS限制,外卖广告的候选队列相对非LBS电商场景较短,不需要经过复杂的预排-粗排-精排的过程。在全链路上,我们更关注召回通道、精排队列长度、精排预估模型等模块的算力分配,这些模块其实对算力更加敏感。

3c5a775211079a321a801b2d59138536.png

整体来看,美团外卖广告场景全链路最优算力分配的挑战主要包括以下两个方面。

通用化问题

  • 挑战点:已有方案与业务耦合过重,一方面,在约束条件或优化目标发生变化时,线性规划方案需要重新对特定业务问题进行建模;另一方面,对特定的业务线,往往需要根据业务数据特性增加一些强假设。外卖广告目前包括十余条业务线,每条业务线中又存在多个算力决策场景,若对每条业务线的每个场景都单独建模,人力成本巨大。

  • 应对思路:采用通用解决方案并沉淀为基础通用能力,为广告业务的不同算力决策场景赋能,降本增效。

序列决策问题

  • 挑战点:在全链路算力分配时,多个决策模块之间互相耦合,共同对影响当前流量的最终算力和收益。如下图所示,前置动作决策后,需要跟真实环境交互才能获取动作决策后的交互结果,模块之间涉及到系统状态转移,需要在最后一个决策模块完成决策后才能获得流量收益,这使得我们难以通过常规方式建模。

bc6bb23b2eecda6361dda11ed120313d.png

  • 应对思路:在全链路最优算力分配问题建模过程中,增加系统在各链路上的“状态”转移过程,后置模块根据前置模块的决策结果和请求状态进行决策。

综合考虑以上两个问题,我们将外卖广告全链路最优算力分配问题建模为多阶段决策问题(每个决策模块对应一个决策阶段),按时间顺序依次决策召回方案、截断队列和预估模型。每个阶段中,由Agent与环境交互和决策,Agent参数可使用进化算法或强化学习求解。

全链路算力分配过程可建模为马尔科夫决策过程(Markov Decision Process, MDP)或部分可观测马尔科夫决策过程(Partially Observable Markov Decision Process,POMDP)。如上图所示,状态转移发生在相邻的两个阶段之间,各阶段分别有不同的候选动作(如召回策略,截断长度和预估模型编号等),Reward则在最后一个阶段动作执行后通过系统反馈获得。

我们可以收集在线日志数据,使用离线强化学习(Offline RL)求解Agent;在不担心线上收益受损的情况下,也可以使用在线强化学习(Online RL)求解Agent。但由于业务场景复杂,各阶段算力约束难以统一,不管是离线强化学习还是在线强化学习,都面临多阶段强约束难以建模和求解的问题。

而进化算法作为一种应用广泛、鲁棒性强的全局优化方法,有以下优点:

  • 避免局部最优:进化算法参数搜索过程具有一定的随机性,不易陷入局部最优;

  • 可并行化:进化算法参数搜索过程可并行,可缓解评估过程耗时问题;

  • 应用广泛:进化算法可以能够处理不连续、不可微和非凸优化问题,且不需要过多先验知识;

  • 简单易用:一些进化算法,比如交叉熵方法(Cross-Entropy Method,CEM)可以优雅地解决各种约束问题,不需要直接求解约束问题。

进化算法能很好地解决外卖广告场景中的问题,既容易扩展到其他业务线,又能非常方便地建模各种决策问题。因此,本期我们选择进化算法来求解外卖场景全链路最优算力分配问题。在后续工作中,我们会尝试使用强化学习方案求解。

如本节迭代路径(图)所示,我们在1.5期中尝试了基于进化算法的单动作算力决策方法ES-SACA(Evolutionary Strategies based Single-Action Computation Allocation),验证了进化算法在算力分配场景的有效性。接下来,本文主要介绍基于进化算法的多动作算力决策方法ES-MACA

3 方案设计

为了实现广告系统全链路上的最优算力分配,我们设计了如下决策方案:

5d5f10630e38a8980be97d6c48bc8ea1.png

离线训练:随机选择决策Agent参数,批量回放历史流量,Agent与广告投放模拟系统进行交互,完成状态转移过程。根据系统返回的Reward优化决策Agent参数,最终输出离线最优Agent参数,并同步到线上。

在线决策:对于线上单条请求,使用离线最优Agent与线上系统进行交互和决策。

在本期中,我们使用进化算法求解Agent参数。进化算法参数寻优的核心是组合动作价值评估,由于涉及到状态转移过程,组合动作价值评估不再是一个简单的监督学习问题,Agent需要依次与系统交互并执行决策动作,直到最后一个阶段的动作完成时才能从系统中取得收益。一种简单的方案是让Agent在线学习,与系统交互的同时优化自身参数,但在线学习会影响业务收益,这对我们来说是不可接受的。为了解决这个问题,我们通过构造广告投放模拟器,模拟线上广告系统环境,由该模拟器与Agent进行交互,并反馈收益(Reward)。

3.1 全链路最优算力决策

3.1.1 问题建模

根据外卖广告的投放场景,我们基于进化算法对整个问题建模如下:

fc442fe6e44b810e0ea235e0fb83309d.png

  • 状态:上下文特征,请求队列特征等(后置决策模块的状态依赖前置模块的决策,比如弹性通道的决策直接影响了弹性队列时队列长度)。

  • 动作:在不同阶段定义不同。

    • 弹性通道:召回动作,一维向量 , 表示是否该通道是否召回。

    • 弹性队列:截断长度,整数值。

    • 弹性模型:模型编号,整数值。

  • Reward:收益目标为业务收益,为了保证求解参数符合算力约束条件,在Reward中添加算力约束条件。对于越严格的约束条件,算力系数 越大。

3.1.2 离线参数求解

ce2fec9f17c8d79d3e91716787217409.png

离线参数求解主要分为进化算法参数寻优和Reward评估两个模块。

  • 参数寻优模块:实现通用的进化算法寻参流程,负责参数初始化、参数评估(依赖Reward评估模块)、参数采样和参数进化等过程,并最终输出最优参数。

  • Reward评估模块:根据指定Agent的具体参数,批量回放线上流量,让Agent与环境进行交互(离线仿真),最后根据交互结果预估当前参数对应的收益。

3.1.2.1 参数寻优

参数寻优模块使用进化算法求解参数。本文以CEM为例,对参数求解过程进行详细讲解:

953ea3cf1c9c2f3034bc0eda6265001a.png

  1. 参数初始化:初始化参数均值和方差,根据指定的均值和方差随机采样N组参数。

  2. Reward评估

  • 离线仿真:回放流量,让当前参数对应的Agent与离线模拟器交互,完成状态转移过程,在所有模块决策完成后,离线仿真模块输出回放流量交互结果。

  • 收益预估:根据回放流量交互结果,预估当前交互结果下的期望收益。

  1. 参数挑选:按照参数合并流量期望收益,挑选使得所有流量整体收益最高的Top-K组参数。

  2. 参数进化:根据Top-K参数,计算新的参数均值和方差。

  3. 参数采样:根据新的均值和方差,重新采样N组参数,并跳转到第二步,直到参数均值和方差收敛。

Tips:NES方案在本场景中效果不如CEM,原因是NES对带约束问题(特别是多约束问题)Reward设计要求过高,在真实场景中难以求解到严格满足约束的参数。

3.1.2.2 Reward评估

acbfebd25a6b635edf7504eecc839d8c.png

离线Reward评估流程:在离线训练时,对于选定的Agent和历史流量。

  • Step1:模拟器构造流量初始状态特征,并反馈给Agent。

  • Step2:Agent根据模拟器给出的流量状态特征进行召回通道档位决策。

  • Step3:模拟器按照Agent给出的召回决策结果进行队列召回,并将召回结果反馈给Agent。

  • Step4:Agent根据召回结果及初始流量状态进行队列长度决策。

  • Step5:模拟器按照Agent给出的队列长度决策结果模拟截断操作,反馈截断后的队列状态给Agent。

  • Step6:Agent根据截断队列进行预估模型编号决策。

  • Step7:模拟器根据模型编号决策给出广告列表集合以及决策相关特征。

  • Step8:将离线模拟的广告列表结果输入收益预估模型,预估每条请求对应的离线收益。

  • Step9:统计整体流量的Reward,作为当前Agent策略的评估结果。

3.1.2.2.1 离线仿真

在线环境交互面临的困境(离线仿真的必要性):理论上,决策Agent与在线环境交互能获得最真实Reward(收益)反馈,但直接利用在线流量探索会导致以下问题:

  • 在线收益损失:在线探索Agent收益的过程是有损的,特别是在策略学前期,策略决策几乎是随机的,线上算力约束和收益都无法得到保障。

  • 流量利用率低:Agent学习往往需要几十甚至上百轮的训练,每轮训练中又包含多组可行参数,为了积累置信的流量数据,每组参数的流量不能太少,总体来说训练时间和效率将是难以接受的。

离线仿真的最终目标:复现线上交互逻辑和收益反馈。

  • 基本思路:虽然无法完全复现线上的复杂环境,但参照线上环境交互逻辑,可以通过离线广告系统模拟器在效率和准确性之间做一个取舍。

  • 其他模块:为了达成这个目标,对于特定的广告队列信息,我们可以使用有监督学习模型对其流量Reward进行预估。

离线仿真+收益预估解决方案

c948db87d1f7402f9fc926e407ecbf5c.png

  • 线上随机探索流量:在线留下少量随机探索流量,随机决策每个阶段的候选动作,同时记录流量日志和线上系统的交互结果。

  • 离线仿真系统:对历史流量日志,仿照线上逻辑,模拟召回,队列截断、粗排CTR预估等逻辑生成离线交互结果。

  • 收益预估:作为离线Reward评估的核心模块,收益预估决定了参数的进化方向,我们将在下一节对收益预估方案进行详细介绍。

3.1.2.2.2 收益预估

目标和挑战点

  • 目标:基于线上空白流量和随机探索流量,预估请求在不同动作下的期望收益。

  • 挑战点:不同于传统广告中“用户-广告”粒度的局部链路CTR、CVR以及GMV预估任务,本文是请求粒度的全链路收益预估,包含了请求曝光、点击、下单(转化)的整个过程,问题更加复杂,特别是面临数据稀疏问题。

    • 数据稀疏问题:由于建模链路较长,在用户转化数据非常稀疏的情况下,大部分流量都没有转化动作发生(意味着商家收益为0)。

模型预估方案

  • 模型设计

    • 考虑到商家收益数据过于稀疏,曝光、点击数据则较为稠密,同时考虑到曝光(平台收益)、点击、下单(商家收益)等行为是强相关的行为,本次预估方案使用多任务模型联合建模。

  • 特征工程

    • 将各阶段的特征离散化后通过Embedding加入模型中。

    • 根据不同队列长度下的流量数据分布情况,将队列长度等特征进行人工分桶再通过Embedding加入模型中。

ce77344dfbe933884b3be743caf22b6a.png

3.1.3 在线决策

对于线上单条请求,使用离线最优Agent与线上系统进行交互和决策。和离线评估流程一致,依次按照如下流程执行决策过程:

  • Step1:系统反馈流量初始状态至Agent。

  • Step2:Agent根据系统流量状态进行召回通道档位决策。

  • Step3:系统按照Agent给出的召回决策结果进行队列召回,并将召回结果反馈给Agent。

  • Step4:Agent根据召回结果及初始流量状态进行队列长度决策。

  • Step5:系统按照Agent给出的队列长度决策结果执行截断操作,反馈截断后的队列状态给Agent。

  • Step6:Agent根据截断后队列状态进行预估模型编号决策。

  • Step7:系统按照Agent给出的模型编号调用预估服务。

3.2 系统建设

01736e9ef0dd4ebbabde315754004347.png

在智能算力第一期中,我们已经完成了以决策组件为核心,以采集、调控和离线组件为支撑的智能算力系统基本建设。在本期中,我们围绕着从单动作局部最优决策扩展到多动作组合最优决策的核心需求。在系统建设上,除了多动作组合最优决策的基本能力建设外,更关注的智能算力系统的稳定性和通用性建设,从而支撑智能算力系统在外卖广告全业务线的全面应用。

3.2.1 决策组件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编排和调度。

3.2.2 采集和调控组件

采集组件负责实时采集广告投放系统的状态数据,并进行标准化预处理,调控组件一方面依赖状态数据实现对整个系广告投放统状态的实时感知和系统模块粒度的算力调控;另一方面作为智能算力系统的中控服务,负责智能算力系统的系统管理,包含业务管理、策略管理、动作管理以及元信息管理等。

我们将系统状态实时反馈控制的最小单位定义为一个调控器,对于每一个动作决策,会涉及一到多个模块的算力变化,而每个模块的算力变化会带来多个数据指标的变化,因此对于一个动作可能需要配置多个调控器。从单动作决策扩展到多动作,这些调控器的数量会越来越多,如何提高对调控器的管理和接入效率,是一个关键问题。这里我们主要进行了异构数据标准化、调控流程通用化建设,基本实现了新调控场景的配置化接入,无需开发和发版。

异构数据标准化

采集组件有多个异构数据源,包含来着美团监控系统CAT上报的业务数据、Falcon收集的机器指标数据,还有部分决策组件上报的数据。经过对数据格式和内容的分析,我们首先将数据以系统模块Appkey进行划分,Appkey之间数据独立,同时从数据类型(Type)出发,把数据分为业务指标(Biz)和机器指标(Host);从数据维度(Dimension)出发,把数据分为集群粒度(Cluster)、机房粒度(IDC)、单机粒度(Standalone);具体的指标(Metric)包含QPS、TP99、FailRate、其他扩展指标等。

7c2d2040cff6430c25a39d7e89c38378.png

调控流程通用化

有了异构数据的统一表达,我们就可以设计通用的调控流程,我们以ProductId作为调控业务场景的唯一标识,以ControllerId作为调控器的唯一标识,一个ProductId映射一组ControllerId,每一个调控器Controller包含输入指标、调控策略、策略参数、输出结果。通用的调控过程为:获取配置的输入指标、调控策略,基于不同的调控策略选择不同的策略参数,执行该调控策略得到对应的输出结果。

另外,我们对调控器的调控效率和稳定性进行了优化。在外卖的双峰流量场景下,在非高峰时段,PID算法的累计误差容易积累过大,导致到了高峰时段调控周期长,系统状态反馈调节慢;同时也存在系统抖动或数据毛刺产生的不必要调控的情况。

基于此,我们采用了滑动窗口准入准出的机制,来提高效率和准确性。如下图所示,我们对于每一个调控器,维护了一个系统指标的滑动统计窗口,当连续M次系统指标达到了PID目标值T-设置的阈值P,该调控器才成功准入,误差开始累计;同时当连续N次系统指标低于PID目标值T-设置的阈值Q,该调控器成功准出,累计误差清零。

d29a716599093d28d726323fbc6980c9.png

3.2.3 离线组件

离线组件负责离线模型训练和参数求解等任务,主要包含样本收集、模型训练和参数求解三个部分。

  • 样本收集:在线上流量中,留出少量随机探索流量,随机决策召回通道、队列长度以及不同预估模型,同时将随机动作以及系统交互数据落表。

  • 模型训练:离线处理随机流量日志,生成训练样本,训练收益预估的DNN模型。

  • 参数求解:在CEM求解过程中,对于给定的策略,模拟线上交互环境生成流量请求信息,然后使用收益预估模型预估当前广告队列的收益,从而实现CEM策略评估。

4 实验

4.1 实验设置

系统算力容量的选取

算力容量指标选取和第一期一致。一方面,为了保证线上系统能根据实时流量快速调整,仍选择15min作为最小的调控单元;另一方面,离线模拟选用的系统容量为过去一周的午高峰流量算力。

Baseline选取

选取无智能算力(固定决策)的流量作为对照组。

离线仿真模拟器——流量价值预估

使用过去14天非实验组数据作为训练集,进行两阶段训练(一阶段全流量训练,二阶段随机探索流量训练),使用当日随机探索流量作为测试集。

离线参数求解

外卖场景中,同环比流量变化趋势基本一致,我们通过重放过去一周流量,离线计算每个时间片内(15分钟为一个时间片)最优参数并存储为词表。

4.2 离线实验

81231d1ce797fba4a2b9f0ea7961dcd3.png

实验说明:

  • Baseline:算力C下的固定决策结果。

  • 仅弹性通道:在“仅弹性通道”实验中,队列决策和模型决策使用Baseline固定方案,“仅弹性队列”和“仅决策模型”实验组则与之类似。

  • 分模块最优:依次学习弹性通道、弹性队列、弹性模型,当前模块在学习时前置模块的参数固定为已经学到的最优参数,后置模块则使用Baseline固定方案。

  • ES-MACA(全链路最优):弹性通道+弹性队列+弹性模型同时学习。

从离线实验的效果来看,我们有以下结论:

  • 三个单动作的最优结果整体收益加和大于分模块最优,也大于ES-MACA,说明三个模块策略会相互影响,联合优化时多动作的收益不是简单的加和关系。

  • 分模块最优方案效果不如ES-MACA方案效果(ES-MACA对比分模块最优有0.53%的提升),说明后置模块的策略对前置模块的决策效果也存在一定影响。

4.3 在线实验

通过一周的线上ABTest实验,我们在外卖广告验证了本方案的收益如下:

d51ed6b529a64d7b09c7eec7f12cd76a.png

实验设计说明:

  • Baseline:对照组,无任何智能算力决策。

  • 仅弹性队列:实验组1,仅决策弹性队列(与一期方案一致)。

  • ES-MACA(全链路最优:实验组2,同时决策弹性通道、弹性队列和弹性模型。

5 总结与展望

这篇文章主要从全链路最优算力决策和系统建设两个方面,介绍了美团外卖广告智能算力从线性规划算法到进化算法的技术演进过程,给出了一种基于进化算法的多动作算力分配方案(ES-MACA)。

未来,在算法策略上,我们将尝试强化学习算法,对系统全链路组合下的算力最优分配问题进行更精细化的建模和求解;在系统建设上,我们还将尝试和美团内部基础架构部门进行合作,从在线系统扩展到在线/近线/离线三层系统,通过智能算力统一决策调度,充分挖掘数据和算力的潜力。

6 参考文献

  • [1] 顺辉、家宏、宋伟、国梁、乾龙、乐彬等,美团外卖广告智能算力的探索与实践。

  • [2] Jiang, B., Zhang, P., Chen, R., Luo, X., Yang, Y., Wang, G., ... & Gai, K. (2020). DCAF: A Dynamic Computation Allocation Framework for Online Serving System. arXiv preprint arXiv:2006.09684.

  • [3] Yang, X., Wang, Y., Chen, C., Tan, Q., Yu, C., Xu, J., & Zhu, X. (2021). Computation Resource Allocation Solution in Recommender Systems. arXiv preprint arXiv:2103.02259.

  • [4] 乐彬、国梁、玉龙、吴亮、磊兴、王焜、刘研、思远等,广告平台化的探索与实践 | 美团外卖广告工程实践专题连载。

7 本文作者

家宏、顺辉、国梁、乾龙、乐彬等,均来自美团外卖广告技术团队。

对于数据库来说,慢查询往往意味着风险。SQL执行得越慢,消耗的CPU资源或IO资源也会越大。大量的慢查询可直接引发业务故障,关注慢查询即是关注故障本身。本文主要介绍了美团如何利用数据库的代价优化器来优化慢查询, ...