在线资源分配在工业界有非常广泛的应用场景，例如：营销发券、流量控制、订单分配等。与此同时，实现一个灵活、高性能、可扩展的在线资源分配系统也有很多技术挑战：
- 工程链路复杂，涉及多套系统如何降低开发和运维成本。
- 涉及到大规模的线性规划问题，如何实现高性能的求解。
- 在线链路如何保障服务的高可用，SLA要求达到99.99%，也就是全年在线服务的不可用时间不超过1个小时。
本文围绕营销、搜索、广告场景，介绍基于Ray实现在线资源分配的解决方案。
1. 场景描述
在推荐、搜索、营销、广告系统中，在线决策一方面需要考虑点击率、转化率等偏好指标，另一方面可能会遇到资金、成本、流量方面的限制。如何在有限资源的前提下，实现整体ROI的最大化，我们将这类问题称为：在线资源分配问题(Online Resource Allocation)。举例来说：
如何在部分优惠券库存有限的情况下最大化平台的商品总销量 。
表1： 优惠券带来的用户 购买率增长
一共只有2张优惠券的情况下（stock=2），传统推荐的方式是先到先得，user1、user2获得优惠券，user3、user4没有机会拿到优惠券，最后优惠券平台销量的增量是0.3。而最优的推荐是不给user1和user2优惠券，让user3、user4拿到优惠券，这样平台整体收益才是最大的。
2. 在线资源分配的抽象模型
在线资源分配系统中，需要在资源约束情况下，在线为每一个到来的请求，匹配合适的资源，实现整体系统收益的最大化。结合第一部分的优惠券案例来看，这里请求的主体就是用户，资源就是优惠券。对每一个用户i，平台可以预估出该用户对j个优惠券分别的收益值
从实时决策角度看，未来的信息是不可预知的，无法提前判断出全局最优解。为了解决这个问题，需要考虑到对未来信息的预估和不确定性。一方面我们将全局的问题拆解为实时的子问题进行学习，考虑到在线应用系统面对的环境变化非常迅速，需要在子问题的规划求解上有很高的时效性(分钟级别)，另一方面需要具备对单个决策请求快速serving的能力。
在实现方案的设计上，我们拆解了不同的技术模块，包括：
- 在线决策服务
- 实时规划算法
图2：推荐系统中在线资源分配方案示意图
在线决策服务利用LP问题在对偶问题上最优解的等价形式，以实时规划算法计算出来的对偶变量入参，可以实现快速的在线serving。
实时规划算法的技术方案，围绕实时、精准的收益预估和预算调控，设计了多个算法模块，包括：
- 实时模型校准：结合实时用户反馈对前置模型的预估进行概率校准(如：CTR、CVR)，保障良好的点估计性质;
- 实时流量预估：预估未来一段时间场景、活动到来的流量，进行总预算的实时拆分平滑;
- 实时约束纠偏：考虑到部分资源的消耗有不确定性或者滞后性，需要结合资源的实际消耗，对预期的预算消耗进度进行实时纠偏；
- 大规模/Online LP优化：解决既定约束条件下，最大化收益的规划问题。
这些算法部分的实现，同时涉及到offline、nearline、online链路和不同的计算范式，下面具体介绍上述方案基于Ray的实践。
图3：在线资源分配解决方案逻辑架构
3. 工程实践
在线资源分配算法方案涉及复杂的工程实现，数据上依赖离线数据和实时数据，算法实现上同时依赖实时计算和迭代计算。我们基于Ray来构建Streaming、Serving、Iterative Calculation，物理架构如下图所示：
图4：在线资源分配解决方案物理架构
基于Ray实现实时规划算法的逻辑包括：
- Iterative Calculation拉取历史数据，使用时间序列模型来预测未来流量数据。
- Streaming用来处理实时数据，生成批量样本。当到达LP求解周期时，Streaming将批量样本发送给Serving。Serving接收批量样本后，将样本用于LP优化问题求解。我们利用Ray PlacementGroup特性，将Solver所在的actor部署到GPU机器上，利用GPU对算法并行化。
- 实时校准模型的在线学习训练，我们利用Ray actor天然组网的特性实现了Bulk Synchronous Parallel模式的迭代计算。
- 业务系统资源分配最终结果和算法决策结果会有一些gap，约束达成情况可以使用Ray Streaming对实时分配结果做累计，用于对LP算法纠偏。
对偶变量求解完成后，可以直接用于Online Rerank，Online Rerank属于在线系统，对SLA要求很高。我们基于Ray，构建了一套在线服务框架。该框架允许用户将任意的业务逻辑发布为在线服务，并进行流量管控。用户无需关心资源部署、资源伸缩和集群容灾。
图5：Online Rerank物理架构
用户创建一个在线服务实例，会在每个Ray集群创建一个Ray作业。每个Ray作业中，包含三种类别Ray Actor：
- Master Actor：负责管控该作业下的路由Actor、工作Actor。
- Router Actor：负责接收来自业务系统的请求，并根据流量管控策略，路由到指定的工作Actor。
- Worker Actor：负责接收来自Router Actor的请求，并执行用户自定义的业务逻辑。
在多机房/多集群部署的情况下，本在线服务框架包含一个名为Keeper组件，确保用户的在线服务作业在每个Ray集群中启动，并且可以进行多集群的流量切换，从而做到集群容灾。
一旦在线服务实例创建完成，在线业务系统可以通过本框架提供的Client调用在线服务。在线服务请求会被Ray作业中的Router Actor接收，并路由到某个Worker Actor执行处理逻辑。
基于Ray实现在线资源分配方案具备以下优势：
- Ray提供了简单易用的API，开发人员可以快速实现上层框架，例如：我们用50行代码实现了Bulk Synchronous Parallel模式的迭代计算。在线资源分配涉及的offline、nearline、online三部分链路都基于Ray实现，大幅降低了开发的学习成本和运维成本。
//基于Ray实现BSP模式迭代计算伪代码// Driverpublic class LpMain { public static void main(String[] args) throws Exception { // Step1: Divide offline data into partitions. // Step2: Start actors to load the data of the corresponding partition. for (…) { Ray.createActor(…) } // Step3: Start a Merger actor. merger = Ray.createActor(…) // Step4: Start solving. result = Ray.call(Merger::solve…).get(); }} // Merger@RayRemote public class LpMerger { public Result solve() { Result res = new Result(); // Iterate until the result is converged. while(res.isConverged()) { // Call all workers to start local calculation. workes.forEach(wk → { workerResult = Ray.call(LpWorker::calculate, wk, …).get(); // Merge the calculation results of the workers. res.merge(workerResult); }); }// Worker@RayRemote public class LpWorker { // Load the data of the corresponding partition. public LpWorker(…) {…} public LpWorkerResult calculate(…) {…}}
- Ray支持便捷的资源调度能力。通过PlacementGroup可以方便得将IO操作和GPU算法部署到对应资源的节点上，充分利用异构加速。算法整体流程较CPU相比有几十倍的性能提升。
- Ray Actor具备秒级的容错恢复能力，同时可以在1秒内感知到正在远程调用的actor是否异常，从而可以将请求转发给其他alive的actor，保障了服务的可用性。
4. 总结
基于Ray实现的在线资源分配解决方案，在蚂蚁集团已经稳定运行，顺利经受住双11、双12等大型活动的考验，部署规模达到了6000+核CPU。目前百万级变量、百级别约束下的LP优化问题基于Ray单机单卡实现了秒级求解。随着业务发展和业务约束增加，未来我们将基于Ray探索单机多卡以及多机多卡的LP求解方案。
蚂蚁集团基于Ray构建融合计算引擎，在线资源分配是其建设运筹优化能力的一部分。除此之外，我们也给Ray Project贡献了大量特性，例如：Java API。如果您想了解更多关于如何使用Ray的信息，请关注我们在即将到来的Ray Summit上的分享！
关于我们
我们是蚂蚁集团数据技术部，是整个蚂蚁集团数据引擎的底盘，为整个集团的各项业务发展保驾护航。我们打造的蚂蚁集团计算存储基础架构，其技术核心包括金融大数据的开放计算体系，金融级大规模图计算存储，金融智能机器学习平台及系统架构，以及适合金融场景的多模融合计算引擎等方面的研发和攻关。
依托蚂蚁集团丰富的数字金融和数字生活场景，我们致力于打造新一代大数据和AI基础设施。
我们的团队横跨美国硅谷和中国北京、上海、杭州和成都。我们追求的工程师文化是开放、简单、迭代、追求效率、用技术解决问题！