作者 | 字节跳动基础架构
前言：
近日，数据库和数据工程领域的顶级学术会议之一 ICDE（IEEE International Conference on Data Engineering）在荷兰乌得勒支举行，字节跳动基础架构团队的论文《Resource Allocation with Service Affinity in Large-Scale Cloud Environments》成功入选。
背景与现状
随着云计算的普及与迅速发展，微服务架构已被越来越多的互联网公司采用。在此架构中，应用被拆分为多个微服务，每个服务负责特定功能，它们通过网络协议（RPC）高效连接，实现数据传输和通信。然而，虽然微服务架构提供了多种优势，如可扩展性、轻量级特性及故障隔离等，但其频繁的网络互动也不可避免地增加了网络负担，从而导致更高的延迟，并增加了系统的不稳定性。
为了解决这些挑战，字节跳动基础架构的服务框架团队、编排调度团队和 ByteBrain 团队合作提出了微服务亲和性部署的解决方案，它的核心思路是将有强依赖关系的服务进行同机部署，减少它们之间的调用开销，从而实现性能和成本的优化。具体而言，它包含 2 个操作：
通过策略性地重新部署服务的 Pod，尽量将频繁通信的服务 Pod 部署在同一台机器上（Collocation）；
通过调整网络通信协议，采用本地通信方式（IPC）替代网络通信，显著降低网络开销，减少请求延迟，增强系统的稳定性。
下图展示了通过模拟实验的初步验证结果：亲和性部署和本地通信策略（Collocation+IPC）显著优化了端到端延迟和请求失败率。
尽管上述方案展示了显著的潜在收益，但在实际落地过程中仍会面临诸多工程和算法上的挑战。其中比较关键的挑战之一就是如何有效地编排 Pod，以便尽可能多的相关服务可以部署在同一台机器上，从而最大化可以通过本地化通信处理的流量。
为了克服这一问题，字节跳动基础架构团队进行了数学化建模，提出了一个考虑服务亲和性的 Pod 调度问题 RASA（Resource Allocation with Service Affinity）。
注：本文中所指的服务间亲和性即服务间流量的大小
从理论到实践的挑战
RASA 问题本质上是一个二次调度（或全局调度 / 重调度）问题，旨在在满足特定约束条件下，重新编排 Pod 以最大化全局可本地化的流量（即最大化服务间的亲和性）。但随着字节跳动业务规模的迅速扩张和复杂度提升，服务数量日益增多，每个服务又包含多个运行中的 Pod，决定这些 Pod 的最佳摆放位置以最大化本地通信流量并非易事：
在制定 Pod 的摆放策略时，我们不仅需要考虑各种约束条件，还要综合考虑不同服务之间的依赖关系。在线上环境中，服务之间如同网状结构相互连接，它们需要频繁通信，这种流量关系称为“亲和性”。在这种情况下，要优化某个服务，如服务 A，常常需要重新调度多个其他亲和服务的 Pod，这不仅涉及到资源的约束（如可容纳的 Pod 数量），还要考虑不同服务 Pod 的放置比例，以确保最大化本地化流量。在这样复杂的环境中，设计一个既考虑到多种约束又能最大化本地化流量的算法极具挑战。
在字节跳动内部，由于线上服务数量众多、关系复杂，且各服务的 Pod 数量庞大，重调度的算法求解时间也成为一大限制（求解时间过长可能导致由于集群状态的变化而使得算法得出的部署方案无效）。在这种背景下，传统元启发式算法在处理大规模且约束条件及目标函数复杂的情况下，难以在短时间内有效地给出优质解。
因此，在解决 RASA 问题时，其复杂的特性和庞大的求解规模对算法提出了严峻的挑战。然而，常见的启发式和元启发式算法往往难以兼顾求解时间和解的质量，这种双重要求使得寻找高效且有效的求解方法变得尤为重要。
微服务亲和性部署二次调度方案
下图展示了字节跳动基础架构团队所提出的方案的完整优化流程：
首先，控制器会收集集群的关键数据，包括服务列表、机器列表及流量信息等（步骤 1）；
接着，控制器将这些数据打包并发送至算法模块（步骤 2）；
算法模块完成求解后，会将新的 Pod 排布方案及 Pod 迁移方案回传给控制器（步骤 3）；
最后，控制器执行 Pod 迁移方案（步骤 4）。
所有 Pod 迁移完成后，集群的 Pod 排布将与 RASA 算法推荐的新排布一致，从而实现流量本地化的优化。
下面，我们将主要介绍图中算法模块的设计和实现。我们开发了一种高效的亲和性调度算法（ 下文简称 RASA 算法），该算法能够处理大规模输入，并且能够获得高质量的解决方案。
RASA 算法的核心思想主要基于两个方面：
利用亲和性关系图的分割和算法选择技术来简化问题规模并加速求解过程；
通过对子问题运用基于数学规划求解器（Solver）的方法，以提升解的质量，获取高本地化流量比例的解。
服务分割
在字节跳动的线上环境中，集群内可能存在上百甚至上千个微服务。如果对所有微服务进行重调度计算，将导致计算量极大。为此，我们提出了一套多阶段服务流量图分割技术。这种技术依据流量图的特性，对服务进行多次分割，部分分割后的服务集合可能会被直接过滤丢弃，将原问题划分为多个规模更小的子问题。
在这些分割过程中，最关键的是主亲和性分割（Master-Affinity Partitioning）。该策略基于一个观察：大部分服务对间的流量非常小，合并它们的价值并不高，因此这些服务对无需纳入重调度算法考虑。例如，在一个约有 40 个微服务的小集群流量分布案例中，前五个服务间的流量就占了总流量的 95% 以上。只需考虑这五个服务的合并，就能实现大部分流量的本地化，从而显著降低问题的规模。
除了主亲和性分割外，我们还引入了以下几种分割技术，以进一步优化子问题的求解效率和效果：
非亲和性分割：这种分割策略旨在排除不存在流量关系的服务。
兼容性分割：此分割旨在识别可能互相冲突或不兼容的服务，确保分割后的每个子问题包含的服务都能和谐共处。
均衡分割：旨在进一步减少每个子问题的规模，同时最小化由于服务分割可能引起的最优性损失，并且尝试均衡各个子问题的计算负载。
通过这些精细化的分割策略，我们能够有效地管理大规模集群中的服务调度问题，优化资源利用率，提升服务性能。
调度算法池
在调度算法池中，为了确保获得高质量的解决方案，我们引入了两种基于数学规划求解器的算法：列生成算法（Column Generation Algorithm，CG）和混合整数规划求解算法（Mixed Integer Programming，MIP）。这些算法能够有效处理涉及整数变量的问题，并通过系统性的和技巧性的遍历解空间来寻求最优解，因此常常能获得高质量的解决方案。
以下是针对 RASA 问题设计的混合整数规划表达式。利用这一表达式，我们开发了 CG 和 MIP 两种算法，用于精确求解子问题：
算法选择
在处理分割后的子问题时，每个子问题的求解需要在一分钟内完成。尽管服务分割技术已经降低了每个子问题的规模，但子问题中的变量数目可能仍然达到上千或上万，因此无法保证所有基于求解器的算法在限定时间内都能得到最优解。实验表明，对于一部分子问题，列生成算法（CG）在一分钟内获得的解的质量（以可本地化的流量大小来评估）优于混合整数规划算法（MIP），而对于其他子问题，则是 MIP 表现更优。
为了进一步提高求解效率并在有限时间内获取更优解，我们引入了算法选择策略，即针对每个子问题在{CG, MIP}中选择更适合的算法。我们利用每个子问题的特征——包括微服务数量、机器数量和服务间的流量关系——构建特征图。在这些图中，微服务作为节点，服务间的流量大小作为边权，节点还包含服务本身的特征信息。
通过对特征图进行随机采样，我们构造了训练样本，并利用这些样本训练了一个基于图卷积网络（GCN）的二分类器。这个分类器的任务是为每个子问题选择最合适的求解算法（CG 或者 MIP）。分类器的训练过程中，我们特别注意模型的泛化能力和分类精度，以确保在实际应用中能够有效地指导算法选择。
在获得每个子问题的最佳求解算法后，我们分别用选定的算法独立求解每个子问题。求解完成后，我们将所有子问题的解合并，形成最终的解决方案。通过这种方式，我们不仅提高了求解的效率，还优化了解的质量，从而有效支持了大规模集群环境下的服务调度需求。
Running Example
为了帮助读者更深入地理解 RASA 算法，我们在此提供一个简单的实例，全面展示算法的工作过程。
在我们的示例中，包含 15 个微服务，它们之间的流量关系如上图最左侧所示，其中边权代表流量值。此外，蓝色节点表示该微服务只能部署在类型为 X 的硬件上，绿色节点表示只能部署在类型为 Y 的硬件上。服务分割的具体步骤如下：
第一步：非亲和分割（Non-Affinity Partitioning） —— 移除那些没有亲和关系的微服务，因为重调度这些服务的容器不会带来收益。
第二步：主亲和分割（Master-Affinity Partitioning） —— 分析每个节点的流入和流出总流量，并进行排序，选出流量占比超过 90% 的前几个微服务。在我们的例子中，选择了占比为 94.8% 的前 6 个微服务。这一步将问题规模缩减为原来的一半。
第三步：兼容性分割（Compatibility Partitioning） —— 因为 X 和 Y 类型硬件的微服务不能共同部署在同一台机器上，按硬件要求进一步细分，将问题规模进一步缩小。在此示例中，原先的 6 个微服务问题被分解为两个子问题，分别包含 2 个和 4 个微服务。
第四步：损失最小化均衡分割（Loss-Minimization Balanced Partitioning） —— 对于仍然规模较大的子问题，例如一个包含 4 个微服务的子问题，进行最小权重均衡分割，将其细分为两个各包含 2 个微服务的子问题。
完成服务分割后，只需为这些分割结果分配适当的机器，即可形成几个独立的 RASA 问题输入。通过这种多阶段分割策略，原本需要解决的 15 个微服务排布问题被有效地分解为 3 个仅包含 2 个微服务的子问题，且这些分割过程中的流量损失仅占总流量的 12%，实现了在最优性损失微小的情况下极大提升求解速度。
当前，我们面临多个子问题和调度算法池中的 CG（Column Generation Algorithm）与 MIP（MIP-Based Algorithm）两种算法，接下来的任务是为每个子问题选择一个最适合的调度算法进行求解。
构建每个子问题的特征图：首先，我们为每个子问题构建特征图。这一特征图是在流量关系图的基础上增加了每个节点的属性，包括对应服务的 Pod 数量和每个 Pod 的平均资源规模。这样，我们成功构建了每个子问题的特征描述。这一描述形式是一个带权图，其中边权重展示了服务间的流量关系，而节点的属性则详细表示了每个服务的特征属性。
算法选择模块的构建：接着，我们设计了一个基于图卷积网络（GCN）的二分类器来为每个子问题选择算法，决定是使用 CG 还是 MIP。具体来说，我们通过对多个集群进行随机采样，构造了 1000 个子图，进而形成了 1000 个子问题。对于每个子问题，我们分别运行 CG 和 MIP 算法，并在 1 分钟内比较两者的优化效果（通过目标函数值判断）。更优的算法将作为该子问题的标签（CG 或者 MIP）。这样，我们得到了 1000 个形如的训练样本。利用这些训练样本，我们训练 GCN 网络，得到了一个能够接受特征图输入并输出{CG, MIP}标签的图二分类器。
求解各个子问题：对于每一个子问题，我们将其特征图输入到上述图二分类器中，得到一个标签，CG 或 MIP。根据这个分类结果，我们使用相应的算法求解该子问题。最终，根据每个子问题生成的 Pod 新排布，我们构建出全局 Pod 的新排布，作为最终的解决方案。
这个过程通过机器学习方法自动适应不同的子问题特性，优化了调度算法的选择，从而提高了解的质量和求解效率。
实验评估
广泛的实验评估表明，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% 的时延降低。
未来，字节跳动基础架构团队也将继续深化亲和性部署的优化工作，以期在性能提升、稳定性增强及资源成本节约等多方面获得更多收益。
