虛擬化數據中心的負載分布優化策略

魏秀然，惠向暉

(河南農業大學 信息與管理科學學院，河南 鄭州 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相同的最小值-最大值歸一化過程?？梢钥吹剑珼R-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。該系統將虛擬化數據中心的通信開銷及資源利用均衡性同時作為優化對象。提出了容器的主導需求衡量方法，并基于此設計了通信感知的降序匹配算法用于新容器的快速部署。性能評估結果表明，該算法在通信開銷和資源利用均衡性上比現有方法表現更好。