虚拟化数据中心的负载分布优化策略

魏秀然，惠向晖

(河南农业大学 信息与管理科学学院，河南 郑州 450046)

0 引 言

负载分布优化作为负载均衡、节约电耗的常用手段，被广泛应用于大规模IDC中。负载优化可以分为两个方面：一是研究如何将新的负载部署到合适的主机上，通常称为负载放置或负载部署[1,2]；二是研究如何优化调整IDC中已有负载的分布，通常称为负载重分布或负载重分配[3,4]。无论是负载放置还是负载重分布，现有解决方案都大致分为两类，即确切方法和启发式方法。其中，确切方法[1,3,5]通常将负载分布优化问题转化为规划问题，进而使用最优化手段来求解问题，复杂度较高，难以在大规模系统中使用。所以，实际的IDC系统常常釆用启发式方法进行负载分布优化[6,7]。

近年来，已有大量负载分布优化方面的研究工作[8-12]，但是这些方案在大规模IDC中仍然存在资源利用率不均衡等问题。

本文设计了一套面向大规模IDC的负载分布优化解决方案。然而，同时优化资源供应和通信开销并非易事。一方面，同一应用的组件通常具有相似的资源需求特性，如果将同一应用的若干组件分配到同一台主机上，就会导致主机资源利用不均衡，进而影响分布式应用性能。另一方面，如果将同一应用的组件简单地分配到不同的主机上，又会产生大量的跨主机通信，这会给IDC基础通信设施带来压力，也会影响分布式应用的吞吐率和可用性。

在容器化数据中心中，本文通过容器分布优化来均衡资源利用率并降低跨主机通信开销。具体而言，本文提出了一种面向大规模IDC的容器分布优化系统Themis，以实现负载均衡和通信开销的联合优化。在IDC中部署新的分布式应用时，使用通信感知的降序匹配算法用于容器部署。

1 问题定义

本节定义了容器分布优化问题。具体而言，用一个由主机、分布式应用和容器组成的三元组来标识一个容器化数据中心IDC(H,A,C)。 在该IDC中，使用H标识主机的集合，使用A标识分布式应用的集合。每个应用a∈A被实例化为一组容器Ca， 每个容器容纳了该应用的一个或多个组件；所有应用的容器构成了容器的全集C。 为了分布式处理及鲁棒性需求，每个应用a可能会在IDC中有若干副本，a的容器也就有相应的副本。在问题中，考虑的资源种类集合为R。给定某台主机h∈H， 使用hr标识该主机的资源r的总量。给定某个容器c∈C， 使用cr标识该容器对于资源r的需求量。来自同一个应用a的容器会相互通信；特别的，来自同一个应用的两个容器分布在不同主机上时，可能产生跨主机通信，这会给IDC的网络基础设施带来压力。

1.1 目标函数

如前所述，在容器化IDC中，本文试图通过容器部署和容器重分配以最小化通信开销并均衡资源利用。需要指出的是，这两个目标都是IDC中常见且重要的优化目标，尽管很少有研究工作考虑如何同时优化二者。

1.1.1 通信开销

为了衡量IDC中的通信量，定义了通信对(communica-tion pair)这个概念。所谓一个通信对，是指属于同一个应用的两个容器，这两者之间可能产生通信。特别的，如果两个容器分布在同一台主机上，两者就构成一个主机内通信对(intra-host communication pair)，否则就构成一个主机间通信对(inter-host communication pair)。主机间通信对越多，IDC的网络带宽就被占用越多。

因此，这里使用IDC内的主机间通信对的总数来衡量该IDC中的通信开销

(1)

其中，I(ci,cj) 标识了两个不同容器是否位于同一主机上

(2)

hc表示容器c所处的主机。

1.1.2 资源利用开销

一台过载的主机可能成为整个IDC的瓶颈，进而影响IDC内分布式应用的性能。理想状态下，对于每种资源r而言，IDC中所有主机的利用率应该相等。这里，将资源r的目标利用率定义为

(3)

即希望所有主机的资源的利用率尽量趋近于资源r的需求总量与其供应总量的比值。

在此基础上，定义了Er来衡量资源r利用率的不均衡程度

(4)

(5)

这里使用不同资源的Er之和来衡量IDC中资源利用的不均衡程度。因此，资源利用开销可以表示为

(6)

1.2 容器分布优化

基于前文的论述，容器部署和重分配问题都可以表达为

两个问题的不同之处在于约束条件不完全相同。

对于容器部署问题，约束条件为容量约束(每台主机的资源利用量不能超过其资源总量)、冲突约束(某个容器和其副本不能放置在同一主机)、散布约束(分布式应用应至少散布在一定数量的主机上)、关联约束(有依赖关系的组件应部署到同一主机上)；而对于容器重分配问题，除了要满足上述约束外，还要满足暂态约束(被迁移的容器只有在目标主机实例化完成后才能在源主机上销毁)。

容器部署和重分配问题实际上可以归类为非线性混合整数规划问题，这类问题是NP难的。解决容器部署和重分配问题，才能够最小化通信开销并均衡资源利用。为了解决这些问题，本文设计了一套面向大规模IDC的负载分布优化解决方案Themis。

2 体系结构及工作流程

为了解决上一节定义的容器部署问题和容器重分配问题，本文设计了一套面向大规模IDC的负载分布优化解决方案Themis。本节给出了Themis的体系结构及工作流程。

在大规模容器化IDC中，通常部署有专门的集群管理系统负责对IDC中的容器进行统一的管理调度，如创建、迁移、销毁以及资源配额调整等。如图1所示，Themis被实现为集群管理系统的一个部件。部署新的分布式应用时，Themis会被触发并计算合理的容器部署方案(即该应用的容器应当实例化在哪些主机上)；IDC中的通信开销或者资源利用开销超过安全阈值时，Themis也会被触发并计算容器重分配方案(即当前IDC中的容器该如何迁移以降低开销)。而后，容器部署方案及容器重分配方案会反馈给集群管理系统的执行模块，执行模块会进行容器的实例化或迁移等。Themis的输入有以下3类：

(1)主机信息：描述了IDC中主机的配置，包括主机ID、位置、IP地址及资源量等。这些信息存储在一个实时数据库中。在计算容器部署方案或容器重分配方案时，Themis按需从数据库中读取这些信息。

(2)应用信息：描述了IDC中分布式应用的特征，包括应用ID、资源需求、容器数量、副本数量等。应用信息也存储在实时数据库中，Themis按需从数据库读取这些信息。

(3)IDC当前状态：主要包括每个容器的位置、每台主机的资源利用率、IDC中网络带宽消耗情况等。集群管理系统的监控模块定期釆集IDC状态信息，Themis按需向监控模块请求这些信息。

图1 集成Themis的机群管理系统控制流

Themis将上述信息作为输入，计算得到合理的容器部署方案或者容器重分配方案。

上述性能分析带来一些启示。首先，应该尝试去计算最优的分类阈值来识别最有可能为无益广告请求的广告请求，而不是尝试改进分类器的预测性能去准确识别所有的无益广告请求。因此，本文分两步来识别并过滤无益广告请求：先使用一个概率分类器预测广告请求的点击概率，而后计算最优的分类阈值来分类。此外，注意到概率分类器的预测性能不是一成不变的(尽管性能相对稳定)。这是可以理解的，因为用户特征和广告特征会随着时间变化而变化。因此，应该根据概率分类器的预测性能来动态调整分类阈值，以得到最优解。

Themis以事件驱动的方式运行。若有新应用部署到IDC中，则Themis调用Deployment()函数，生成合理的容器部署方案并返回。若IDC内资源开销或者通信开销超出了安全阈值，则Themis调用Reassignment()函数，生成合理的容器重分配方案。可以看到，Deployment()函数和Reassignment()函数是Themis的核心机制，其设计细节将在后文给出。

3 容器部署机制

第2节指出，负载优化问题可以归类为非线性混合整数规划问题，这是一类较典型的NP难问题。本节设计一种通信感知的降序最差匹配策略来求解。

3.1 算法设计

如前所述，大型IDC中通常有数万台主机以及数十万个容器。因此，出于在真实系统场景中的运行效率考虑，本小节设计了一种启发式方法来解决容器部署问题。

容器部署问题的优化目标之一是资源利用均衡。而降序最差匹配策略(worst fit decreasing，WFD)是均衡资源利用的常用策略之一。WFD策略解决的是这样一个问题：如何将一系列物品装入一系列箱子中，并尽量保证所有箱子中装入的物品体积尽量相等。WFD策略首先将物品按照体积降序排列，而后依次将物品放入具有最多空闲空间的箱子中。

需要注意的是，直接将WFD应用到容器部署问题是不可行的。第一，与背包问题不同，容器部署问题面临多种资源约束和多种开销，所以很难量化主机剩余资源和容器大小。一种可行的方法是将多资源向量矢量化为一个标量，用这个标量来衡量主机剩余资源量和容器大小。然而，有多种方法可以将向量矢量化，所以首先需要确定最佳的矢量化方案。第二，WFD的目标仅仅是负载均衡，而容器部署问题则不仅需要考虑负载均衡，还要考虑通信开销优化。基于上述原因，还需要对WFD作出扩展。

本小节定义了容器的主导需求来衡量容器的大小。所谓主导需求，就是在不同种类的资源中，该容器的最大需求量

(7)

此外，本小节使用各类资源剩余量的加权和来衡量主机h的剩余资源量

(8)

其中，ωr为资源r的权重。

为了实现负载均衡，经典的WFD策略会将容器依次放置到具有最多剩余资源的主机上。这里，为了将WFD扩展到容器部署问题，分两个步骤为某个新容器c选定其目标主机，以实现通信开销与资源利用开销的联合优化。第一步，强调负载均衡，选择d个有最多剩余资源的主机，主机的剩余资源量以加权和衡量；第二步，在d个候选主机中，选择那个容纳了最多的c的同辈容器(peer containers)的主机作为目标主机。

综合上述举措，本小节设计了通信感知的降序最差匹配算法(communication-aware worst fit decreasing，CA-WFD)用于容器部署。该算法首先将新容器按照其资源需求量降序排序，容器资源需求量是以其主导需求衡量的。而后进行迭代，依次将当前资源需求量最大的、还没有部署的容器部署到主机上，直到所有的容器都部署完成。在每次部署某个容器c时，CAAVFD会选取d个具有最多剩余资源的主机，主机的剩余资源量以多种资源剩余量的加权和衡量；而后选择容纳了最多的c的同辈容器的主机以最小化目标函数。

3.2 性能验证

本小节在真实IDC环境中对容器部署算法的有效性进行了评估。在评估中，试图回答如下两个问题：第一，CA-WFD算法能否有效优化通信开销和资源利用开销？第二，CA-WFD算法所釆用的容器资源需求和主机空闲资源量的衡量方法(即式(7)定义的主导需求和式(8)定义的加权和)，是否比其它衡量方法更加有效？

性能评估的主要结果总结如下。

(1)目标函数优化：评估结果表明，与当前工业界普遍釆用的容器部署策略相比，CA-WFD可以有效降低IDC的通信开销与资源利用开销。

(2)衡量方法的有效性：釆用不同方法来衡量容器资源需求和主机剩余资源量，可以看到现有衡量方法在多个IDC中性能优越且表现稳定，肯定了CA-WFD的设计选择的有效性。

3.2.1 实验环境

基于两个真实的大规模IDC对CA-WFD算法的有效性进行评估。其中，第一个IDC(记为IDC1)部署有2500+台主机和来自25个分布式应用的10000+个容器，第二个IDC(记为IDC2)部署有4300+台主机和来自29个分布式应用的25000+个容器。在实验中，计算资源开销时，考虑CPU、内存(MEM)和存储(SSD)等3种资源的均衡利用。

上述两个IDC中，代表性的主机配置见表1，代表性的应用资源需求见表2。需要注意的是，两个表格中的资源值是经过归一化处理过的，每个资源维度r中，最高的主机配置maxhr被归一化为1。此外，上述两个表格给出的仅是部分有代表性的主机和应用的情况，IDC中还存在其它配置主机和其它类型的应用。从上述真实系统的统计数据可以看到，大规模IDC在不同维度上存在着显著的异构性。

表1 主机配置

表2 应用详情

3.2.2 算法性能

考虑这样一个场景：分别部署一个新的分布式应用到IDC1和IDC2中去。其中，部署在IDC1中的应用被实例化为2000+个容器；部署在IDC2中的应用被实例化为5000+个容器。为了验证CA-WFD算法的性能，首先将该算法与当前工业界(包括Docker[13]、Swarm[14]和Amazon[15])普遍应用的容器部署策略作了对比。

(1)CA-WFD：CA-WFD算法，即本文设计的通信感知的降序最差匹配算法。在实验中，每次选取2台主机作为候选。

(2)随机策略(Random)：在不违反约束条件的前提下，将容器随机地部署到某台主机上。

(3)高可用性策略(high availability，HA)：将新容器部署在容纳c的同辈容器最少的主机上。HA致力于提升负载均衡及应用的可用性。然而，HA可能会引起较高的通信负载，因为这些容器被分配到尽量多的主机上。

(4)最空节点优先策略(emptiest node first，ENF)：总是将新容器部署在当前容纳容器最少的主机上。ENF可以在较粗的粒度上提升负载均衡程度。注意到，主机容纳的容器数量少并不一定意味着资源利用率也较低；因为某个大容器(比如表2中的B2)会比多个小容器(比如表2中的B1)占用更多的资源。

(5)装箱策略(Binpack)：将新容器部署到剩余CPU资源最少的主机上。Binpack试图将应用部署在尽量少的主机上，进而节省耗电量。

表3给出了以不同算法将新应用的容器部署到IDC中后的系统开销值。为了简明，表格中的开销值经过了最小值-最大值标准化，每项开销的下界和上界被分别归一化为0和1。每项开销的下界和上界是在理想状态下计算得到的。以通信开销为例：其上界，是该应用的容器部署在尽量多的主机上时的通信开销；其下界，则是这些容器部署在尽量少的主机上时的通信开销。可以看到，从任何一种开销来看，CA-WFD均明显优于其它算法。通信开销方面，CA-WFD表现最佳；HA表现最差，因为HA总是将容器分布在尽量多的主机上，这会引入大量的跨主机通信开销。资源利用开销方面，在IDC1上，CA-WFD的性能最多比其它方法好57.7%；在IDC2上，CA-WFD的性能最多比其它方法好45.5%；ENF的性能仅次于CA-WFD，这是因为CA-WFD和ENF算法都倾向于将容器部署在拥有更多剩余资源的主机上，这有利于负载均衡；然而ENF算法认为主机容纳的容器数量越少则主机剩余资源越多，这是不准确的。Binpack策略的资源利用开销最高，因为将容器部署在少数主机上明显对资源的均衡利用有害。

表3 容器部署完成后的系统开销值

图2、图3和图4给出了IDC1中容器部署完成之后，主机资源利用率的分布情况，图的横轴为IDC中的主机，纵轴为对应主机的资源利用率。可以看到，CA-WFD下的负载均衡情况明显优于其它方案，这与表3中的结果一致。由于主机的资源利用均衡程度影响了IDC在压力下的性能，因此可以预期，CA-WFD可以提升IDC在突发流量下的应用吞吐率。

图3 IDC1中容器部署完成之后的内存利用率

图4 IDC1中容器部署完成之后的储存资源利用率

3.2.3 算法性能

如前所述，CA-WFD使用主导需求来衡量容器的资源需求量，以剩余资源的加权和来衡量主机的剩余资源量。受文献[16]启发，本小节对CA-WFD算法的几个变种算法的性能进行了评估，用来说明上述两个衡量指标的有效性。这些变种算法的运行流程与CA-WFD的流程相同，但是以不同的指标来衡量容器资源需求量和主机剩余资源量。

(1)主导需求-加权和(dominant requirement-weighted sum，DR-WS)：本文采用的衡量方法。

(2)加权和-点积(weighted sum-dot product，WS-DP)：使用容器的资源需求向量的加权和，即来衡量容器的资源需求量。文献[16]所做的模拟实验结果表明，WS-DP在向量化装箱问题上表现优越。

(3)CPU-CPU(C-C)：使用容器的CPU需求量衡量其资源需求量，使用主机的剩余CPU资源量衡量其剩余资源量。这种衡量方法实际上是一个单维度版本的CA-WFD算法，其在容器部署过程中仅考虑CPU资源。

表4比较了CA-WFD及其变种的性能。表格中的开销值也经过了和表4相同的最小值-最大值归一化过程。可以看到，DR-WS(即CA-WFD目前釆用的衡量方法)在两个IDC中均优于其它设计选择。然而，需要注意的是，WS-DP在IDC2的表现比其在IDC1中的表现要差，这说明WS-DP不能有效捕捉到异构环境下的资源特征(表1所示，IDC2的异构程度明显高于IDC1)。C-C在资源利用开销方面表现较差，这是因为C-C倾向于将容器部署在具有高端CPU配置的主机上，而优化单一维度的资源负载均衡，会导致其它资源利用均衡程度的恶化。

表4 变种算法的性能对比

总之，与当前工业界普遍釆用的负载部署策略相比，CA-WFD算法可以有效优化通信开销及资源利用的均衡程度；此外，CA-WFD算法釆用的评估指标优于其它的设计选择。

4 结束语

近年来，伴随着IDC虚拟化技术迅猛发展，一个突出问题是如何同时优化虚拟化数据中心的通信开销及资源利用均衡。本文以容器化数据中心为具体背景，设计了一种高效通用的负载分布优化系统Themis。该系统将虚拟化数据中心的通信开销及资源利用均衡性同时作为优化对象。提出了容器的主导需求衡量方法，并基于此设计了通信感知的降序匹配算法用于新容器的快速部署。性能评估结果表明，该算法在通信开销和资源利用均衡性上比现有方法表现更好。