近日,数据库和数据工程领域的顶级学术会议之一 ICDE(IEEE International Conference on Data Engineering)在荷兰乌得勒支举行,字节跳动基础架构团队的论文《Resource Allocation with Service Affinity in Large-Scale Cloud Environments》成功入选。
随着云计算的普及与迅速发展,微服务架构已被越来越多的互联网公司采用。在此架构中,应用被拆分为多个微服务,每个服务负责特定功能,它们通过网络协议(RPC)高效连接,实现数据传输和通信。然而,虽然微服务架构提供了多种优势,如可扩展性、轻量级特性及故障隔离等,但其频繁的网络互动也不可避免地增加了网络负担,从而导致更高的延迟,并增加了系统的不稳定性。
为了解决这些挑战,字节跳动基础架构的服务框架团队、编排调度团队和 ByteBrain 团队合作提出了微服务亲和性部署的解决方案,它的核心思路是将有强依赖关系的服务进行同机部署,减少它们之间的调用开销,从而实现性能和成本的优化。具体而言,它包含 2 个操作:
与直接将微服务合并为更大的服务相比,亲和性部署方案仍保留了微服务架构中服务的独立性、敏捷性和易扩展性等优势。下图展示了通过模拟实验的初步验证结果:亲和性部署和本地通信策略(Collocation+IPC)显著优化了端到端延迟和请求失败率。
尽管上述方案展示了显著的潜在收益,但在实际落地过程中仍会面临诸多工程和算法上的挑战。其中比较关键的挑战之一就是如何有效地编排 Pod,以便尽可能多的相关服务可以部署在同一台机器上,从而最大化可以通过本地化通信处理的流量。
为了克服这一问题,字节跳动基础架构团队进行了数学化建模,提出了一个考虑服务亲和性的 Pod 调度问题 RASA(Resource Allocation with Service Affinity)。
注:本文中所指的服务间亲和性即服务间流量的大小
RASA 问题本质上是一个二次调度(或全局调度/重调度)问题,旨在在满足特定约束条件下,重新编排 Pod 以最大化全局可本地化的流量(即最大化服务间的亲和性)。但随着字节跳动业务规模的迅速扩张和复杂度提升,服务数量日益增多,每个服务又包含多个运行中的 Pod,决定这些 Pod 的最佳摆放位置以最大化本地通信流量并非易事:
因此,在解决 RASA 问题时,其复杂的特性和庞大的求解规模对算法提出了严峻的挑战。然而,常见的启发式和元启发式算法往往难以兼顾求解时间和解的质量,这种双重要求使得寻找高效且有效的求解方法变得尤为重要。
下图展示了字节跳动基础架构团队所提出的方案的完整优化流程:
所有 Pod 迁移完成后,集群的 Pod 排布将与 RASA 算法推荐的新排布一致,从而实现流量本地化的优化。
下面,我们将主要介绍图中算法模块的设计和实现。我们开发了一种高效的亲和性调度算法(下文简称 RASA 算法),该算法能够处理大规模输入,并且能够获得高质量的解决方案。
RASA 算法的核心思想主要基于两个方面:
在字节跳动的线上环境中,集群内可能存在上百甚至上千个微服务。如果对所有微服务进行重调度计算,将导致计算量极大。为此,我们提出了一套多阶段服务流量图分割技术。这种技术依据流量图的特性,对服务进行多次分割,部分分割后的服务集合可能会被直接过滤丢弃,将原问题划分为多个规模更小的子问题。
在这些分割过程中,最关键的是主亲和性分割(Master-Affinity Partitioning)。该策略基于一个观察:大部分服务对间的流量非常小,合并它们的价值并不高,因此这些服务对无需纳入重调度算法考虑。例如,在一个约有 40 个微服务的小集群流量分布案例中,前五个服务间的流量就占了总流量的 95% 以上。只需考虑这五个服务的合并,就能实现大部分流量的本地化,从而显著降低问题的规模。
除了主亲和性分割外,我们还引入了以下几种分割技术,以进一步优化子问题的求解效率和效果:
通过这些精细化的分割策略,我们能够有效地管理大规模集群中的服务调度问题,优化资源利用率,提升服务性能。
在调度算法池中,为了确保获得高质量的解决方案,我们引入了两种基于数学规划求解器的算法:列生成算法(Column Generation Algorithm,CG)和混合整数规划求解算法(Mixed Integer Programming,MIP)。这些算法能够有效处理涉及整数变量的问题,并通过系统性的和技巧性的遍历解空间来寻求最优解,因此常常能获得高质量的解决方案。
以下是针对 RASA 问题设计的混合整数规划表达式。利用这一表达式,我们开发了 CG 和 MIP 两种算法,用于精确求解子问题:
在处理分割后的子问题时,每个子问题的求解需要在一分钟内完成。尽管服务分割技术已经降低了每个子问题的规模,但子问题中的变量数目可能仍然达到上千或上万,因此无法保证所有基于求解器的算法在限定时间内都能得到最优解。实验表明,对于一部分子问题,列生成算法(CG)在一分钟内获得的解的质量(以可本地化的流量大小来评估)优于混合整数规划算法(MIP),而对于其他子问题,则是 MIP 表现更优。
为了进一步提高求解效率并在有限时间内获取更优解,我们引入了算法选择策略,即针对每个子问题在{CG, MIP}中选择更适合的算法。我们利用每个子问题的特征——包括微服务数量、机器数量和服务间的流量关系——构建特征图。在这些图中,微服务作为节点,服务间的流量大小作为边权,节点还包含服务本身的特征信息。
通过对特征图进行随机采样,我们构造了训练样本,并利用这些样本训练了一个基于图卷积网络(GCN)的二分类器。这个分类器的任务是为每个子问题选择最合适的求解算法(CG 或者 MIP)。分类器的训练过程中,我们特别注意模型的泛化能力和分类精度,以确保在实际应用中能够有效地指导算法选择。
在获得每个子问题的最佳求解算法后,我们分别用选定的算法独立求解每个子问题。求解完成后,我们将所有子问题的解合并,形成最终的解决方案。通过这种方式,我们不仅提高了求解的效率,还优化了解的质量,从而有效支持了大规模集群环境下的服务调度需求。
为了帮助读者更深入地理解 RASA 算法,我们在此提供一个简单的实例,全面展示算法的工作过程。
我们的示例中包含 15 个微服务,它们之间的流量关系如上图最左侧所示,其中边权代表流量值,蓝色节点表示该微服务只能部署在类型为 X 的硬件上,绿色节点表示只能部署在类型为 Y 的硬件上。服务分割的具体步骤如下:
完成服务分割后,只需为这些分割结果分配适当的机器,即可形成几个独立的 RASA 问题输入。通过这种多阶段分割策略,原本需要解决的 15 个微服务排布问题被有效地分解为 3 个仅包含 2 个微服务的子问题,且这些分割过程中的流量损失仅占总流量的 12%,实现了在最优性损失微小的情况下极大提升求解速度。
当前,我们面临多个子问题和调度算法池中的 CG(Column Generation Algorithm)与 MIP(MIP-Based Algorithm)两种算法,接下来的任务是为每个子问题选择一个最适合的调度算法进行求解。
这个过程通过机器学习方法自动适应不同的子问题特性,优化了调度算法的选择,从而提高了解的质量和求解效率。
广泛的实验评估表明,RASA 算法在求解效率和解的质量上均表现出色,显著优于现有的调度算法。
下图显示了 RASA 算法与其他算法(包括不考虑亲和性的调度(Original)、基于均衡分割的亲和性调度求解器算法(POP)、以及考虑亲和性的启发式算法 K8s+和 ApplSci19)在一分钟的求解时间限制内的表现。结果表明,RASA 算法在本地化流量值上平均领先 17.66%,显著优于其他算法。
图中展示了使用 RASA 算法优化后(With RASA)与未使用 RASA 优化前(Without RASA)的服务在平均响应时延和请求错误率上的表现。结果显示,平均响应时延降低了 23.75%,请求错误率降低了 24.09%,明显提升了服务性能和可靠性。这些结果强调了 RASA 算法在提高调度效率和优化服务性能方面的有效性。
本文详细阐述了如何在微服务架构中利用服务间的亲和性来提升服务性能和增强请求的稳定性。文章引入了亲和性调度算法(RASA 算法),该算法专为优化容器部署以提高服务间亲和性而设计。RASA 算法不仅计算高效,而且解的质量卓越,满足了大规模线上应用的要求。自 2023 年在字节跳动上线以来,对于接入亲和性部署的业务,该算法已实现了 10%-70% 的时延降低。
未来,字节跳动基础架构团队也将继续深化亲和性部署的优化工作,以期在性能提升、稳定性增强及资源成本节约等多方面获得更多收益。
团队介绍:ByteBrain 是字节跳动“基础架构智能化”(AI for Infra)的落地平台。ByteBrain 利用 AI 技术对基础架构各系统的生命周期进行自动优化,主要包括智能决策(容量规划、规格推荐、资源调度)、智能优化(参数调优、SQL 优化)、智能运维(异常检测与排障)、智能助理(LLM 辅助决策、优化、运维)四大业务方向,目前已经服务了公司 30 余条业务线和产品。此外,团队在 SIGMOD、VLDB、ICDE、KDD 等顶会有多篇论文发表。
招聘:目前团队正在美国和中国招聘 AI+Infra(AI for Infra & Infra for AI),要求 Senior expert 或 PhD candidates(对标天才少年),有意向者请邮件联系:[email protected]