面向云數(shù)據(jù)中心資源均衡分配需求的聚類調(diào)度算法研究

徐雨婷， 陳世平

（上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093）

由于全球經(jīng)濟的發(fā)展，云計算已經(jīng)成為社會的一種重要計算模式[1]，并在發(fā)展過程中形成了性能佳、費用低、可靠性強等一些獨特的特點。隨著云計算數(shù)據(jù)中心數(shù)據(jù)量的快速增長，人們開始研究數(shù)據(jù)中心在進行資源分配的過程中如何提高系統(tǒng)資源利用率的方法[2-3]。

已有許多學(xué)者針對虛擬機?服務(wù)器的資源映射問題進行了研究。Selim 等[4]利用CPU 利用率差異概念，通過計算出所有物理服務(wù)器的CPU 利用率的最小方差，選擇最合適的主機分配虛擬機，但該算法僅考慮了CPU 利用率，未考慮其他資源的使用情況。Combarro 等[5]針對三層數(shù)據(jù)中心提出了一種基于功率和網(wǎng)絡(luò)感知調(diào)度模型，可通過資源整合和負載均衡調(diào)整的方式來實現(xiàn)降低能耗的目標，但未考慮資源利用率的優(yōu)化。房丙午等[6]通過建立虛擬機放置模型，基于兩個階段的啟發(fā)式算法來求解虛擬機放置模型，該啟發(fā)式算法僅針對資源分配過程中的能耗問題進行研究，未考慮資源利用率的問題。

本文主要在包簇框架[7]基礎(chǔ)上，研究數(shù)據(jù)中心資源調(diào)度策略。首先，基于包資源需求的分布密度，將資源需求（CPU 需求以及內(nèi)存需求）具有差異性的包通過改進的k-means 算法進行聚類；其次，通過皮爾遜相關(guān)系數(shù)得到資源的相關(guān)性，定義包與簇之間的距離，將包映射到最近的簇；最后，通過Hadoop 框架和實驗工具CloudSim 分別進行實驗，驗證包聚類算法以及資源調(diào)度算法的有效性。

1 傳統(tǒng)的k-means 算法

傳統(tǒng)的k-means 算法具有良好的可擴展性，kmeans 算法的思想主要是將聚類的中心點（質(zhì)心）移動到聚類中包含其他樣本點的平均位置，然后重新劃分類。k值是通過算法計算出來的參數(shù)，表示類的數(shù)量。k-means 的參數(shù)包括類的質(zhì)心位置及其內(nèi)部觀測值的位置。傳統(tǒng)的k-means 算法過程如下[8]：

步驟1輸入樣本點集合，隨機確定k個中心點；

步驟2計算樣本集合中每個點到中心點之間的距離，將集合按照最小距離原則分配到最鄰近聚類；

步驟3計算類中樣本均值，更新每個類中心點的位置；

步驟4重復(fù)步驟2 和步驟3，直到所有中心不再更新或到達設(shè)定條件停止，輸出k個類劃分和最終的聚類中心。

2 包聚類算法

2.1 改進的k-means 算法初始值選定

為了解決傳統(tǒng)的k-means 算法由于隨機確定初始值對聚類結(jié)果造成影響的問題，需首先采用canopy 算法確定k-means 算法的初始值k及其初始中心[9]，通過canopy 算法對數(shù)據(jù)的預(yù)處理，可提高k-means 算法的處理速度，同時提高聚類準確性。

為了具體地實施包的聚類任務(wù)，采用基于canopy 算法的k-means 算法來實現(xiàn)包的聚類，將包的分布密度作為參數(shù)代入到canopy 算法中，并定義與包的CPU 需求、內(nèi)存需求的相關(guān)距離度量因子，實現(xiàn)聚類過程。

將通過聚類形成的包簡稱為聚類包?，F(xiàn)定義以下幾種參數(shù)：

a. 集合中2 個需求差異最大的包之間的距離L?，F(xiàn)假設(shè)集合中有點i:(xi,1,xi,2)，j:(xj,1,xj,2)，其中，xi,1和xj,1表示包的CPU 需求，xi,2和xj,2表示包的內(nèi)存需求，若在某時刻這2 個包的需求差異最大，則將它們之間的距離定義為集合中包之間的最大距離。

b. 距離因子d(xi,xj)。d(xi,xj)表示聚類的距離度量因子，xi,xj分別代表包的CPU 需求和內(nèi)存需求。

當L>0時，可由式（2）計算點i與點j之間的距離因子。以CPU 需求差異為例，若點i與點j的CPU 需求xi,1與xj,1之間的差異越大，則xi,1/L與(1?xj,1/L)的值越接近，則滿足聚類原則中距離相近的點聚為一類的條件；當L=0時，表示集合中任意2 個包之間的資源需求均相等，包之間不存在資源需求差異，此時d(xi,xj)=0。因此，若包之間的CPU 需求、內(nèi)存需求差異越大，則2 點之間的距離因子越近，最終需求差異大的2 個包將處于1 個聚類中。

c. 距離因子均值Dis。Dis為集合中所有包的距離因子的均值。n為集合中所有包樣本點的數(shù)目。

d. 包樣本點分布密度f(i)。f(i)定義為集合中與包樣本點i之間的距離因子小于Dis的包樣本點數(shù)目，表示點i的分布密度，所有滿足條件的包樣本點構(gòu)成一個聚類。

e. 聚類包中的距離因子均值 θ(i)。θ(i)表示已經(jīng)形成的聚類包的距離因子的平均值。

f. 2 個不同分布密度的聚類包的距離因子h(i)。h(i)表示聚類包中心點i與其他聚類包中心點之間的距離因子?，F(xiàn)存在2 種情形：

（a）若存在聚類包中心點j1,j2,···,jR，R為聚類包的總個數(shù)，它們的分布密度均大于f(i)，分別計算點i與它們之間的距離因子，若點i與點jr(r∈R)之間的距離因子d(i,jr)最小，則h(i)=d(i,jr)。

（b）若點i的分布密度f(i)大于任意一個聚類中心點的分布密度，分別計算點i與其他聚類中心點之間的距離，若點i與點b之間的距離因子d(i,b)最大，則h(i)=d(i,b)。

g. 聚類包的最大分布密度乘積 μ 。由上述分析可知，f(i) 值越大，則i的周圍的點就越多；θ(i)值越小，聚類包中的點就越緊密；h(i)值越大，則2 個聚類包的差異性就越大。由聚類的基本原則定義最大分布密度乘積μ, μ為聚類包中的距離因子均值、聚類包內(nèi)的分布密度、聚類以后的包之間的距離的倒數(shù)這三者的乘積。

2.2 基于資源需求差異的k-means 算法

將基于資源需求差異的k-means 算法流程分為兩部分進行描述，第一部分為基于canopy 算法確定k-means 算法的k值和中心，第二部分為k-means的算法流程。

首先介紹第一部分的算法流程。

步驟1定義由包組成的數(shù)據(jù)集D，計算集合中包的距離因子均值Dis和包樣本點分布密度f(i)。

步驟2定義數(shù)據(jù)集A。步驟1 計算出的具有最大分布密度值的包a1被選擇成為第一個聚類的中心點，將點a1加入到數(shù)據(jù)集A中，將滿足與初始類中心點a1之間的距離因子小于Dis條件的所有包樣本點從D中刪除。

步驟3計算由步驟2 確定的D中剩余包樣本點的 θ(i)，以及h(i)值，然后根據(jù)式（7）計算點i與a1之間的 μ 值，選擇具有最大 μ 值所對應(yīng)的點i，作為第二個聚類中心a2，并將a2放入集合A中。同樣，將滿足與a2之間距離因子小于Dis的包樣本點從D中刪除。

步驟4計算D中剩余的樣本點i與a1和a2的之間的 μ 值，分別記作 μ1和μ2，選取具有最大分布密度乘積（μ1μ2）的點i，將點i作為第三個聚類的中心a3，并將a3放入集合A中。同樣，將滿足與a3之間距離因子小于Dis的包樣本點從D中刪除。

步驟5同理，若包樣本點j與聚類中心a1，a2,…,ak?1之間具有最大分布密度乘積（μ1μ2···μk?1），則包j將被設(shè)置成第k個聚類中心。

步驟6循環(huán)步驟5，最終得到k值，以及初始類中心ai,i∈k。

由上述步驟最終確定的k值以及初始中心ai，代入到k-means 算法中，執(zhí)行k-means 算法流程：

步驟1計算集合中每個包樣本點i到ai的 距離因子。

步驟2將與ai之間的距離因子最小的樣本點分配到ai所在的類中。

步驟3計算每個類中的平均值，并更新聚類中心。

步驟4重復(fù)執(zhí)行步驟2 和步驟3，直到所有點聚類完成。

2.3 示例說明

假設(shè)在t時刻，有8 個待分配的包，如表1 所示。假設(shè)包需求為（1, 1）的含義是對CPU 的需求為1 核，對內(nèi)存的需求為1 MB。

a. 定義集合D，并將表1 中所有包需求參數(shù)放入集合D中。首先根據(jù)式（2）分別計算8 個包的距離因子，根據(jù)式（3）計算出距離因子均值Dis，再根據(jù)式（4）計算包樣本點分布密度f(i)。

b. 定義集合A，將分布密度f(i)最大的包設(shè)為第一個聚類中心點，首先選擇f(i)最大為4 的包樣本點，即編號為7 的包樣本點，作為第一個聚類中心，將其放入集合A中，并將滿足與編號為7 包樣本點之間的距離因子小于Dis的樣本點從D中刪除，刪除包編號為3，4，6，8 的樣本點。

c. 通過b 的計算，D中剩下包編號為1，2，5 的點，再分別根據(jù)式（6）計算其 θ(i)，以及它們各自的h(i)，根據(jù)式（7）分別計算它們與b 確定的編號為7 的包樣本點之間的 μ ，得出編號為1 的包樣本點具有最大 μ ，作為第二個聚類中心，并將其放入集合A中，并將滿足與編號為1 包樣本點之間的距離因子小于Dis的樣本點從D中刪除，刪除包編號為2，5 的樣本點，此時集合D為空，基于分布密度的canopy 算法結(jié)束。

d. 執(zhí)行k-means 算法聚類流程。根據(jù)上述步驟得到k值為2，初始類中心點為編號1 和7 的包。繼續(xù)計算表1 中其他樣本點與它們之間的距離因子，將距離因子與中心點最小的樣本點分配到它們所在的類中，計算平均值，更新類中心，根據(jù)k-means 算法步驟，一直循環(huán)，直至聚類完成。

本示例形成了2 個聚類包。第一個聚類包括編號3，4，6，7，8 的包，其中，編號3，4，6 為對CPU 需求較高的包樣本點，編號7，8 為對內(nèi)存需求較高的包樣本點；第二個聚類包包括編號為1，2，5 的包，其中，編號5 為對CPU 需求較高的包樣本點，編號2 為對內(nèi)存需求較高的包樣本點。形成的2 個聚類包均為需求差異較大的包，由此可知，基于canopy 算法的k-means 算法可將資源需求差異較大的包聚類，從而提高各資源的利用率。最終得到的聚類結(jié)果如圖1 所示。

表 1 包需求參數(shù)（1）Tab.1 Package demand parameters（1）

圖 1 聚類以后的包Fig. 1 Package after clustering

C1，C2 分別為第一個、第二個聚類包的聚類中心點。

3 包簇資源調(diào)度算法

3.1 包簇資源利用率及能耗定義

經(jīng)過前面的聚類算法后，系統(tǒng)中共有k個待分配的聚類包，定義包集合為{x1,x2,···,xk}，定義簇集合為{y1,y2,···,yn}?，F(xiàn)假設(shè)t時刻，包v(1 ?v?k)的資源需求總量為Rv[t]，簇p(1 ?p?n)可提供資源使用總量為Sp[t]，定義簇p中已使用資源總量為Wp[t]，規(guī)定每個簇的資源只能分配給一個包，即包中使用的資源不能超過簇中擁有的總資源，資源利用率

式中，0 ?U?1。

在資源分配過程中，除了需要考慮資源利用率以外，還需考慮資源分配過程中產(chǎn)生的能源消耗，可建立資源利用率與能耗之間的關(guān)系式[10]，式（9）為混合任務(wù)負載環(huán)境下的能耗模型。

式中：Ep為能耗；Fjyp為Ep的核函數(shù)，由指數(shù)函數(shù)表示；yp為各類資源（CPU、內(nèi)存）利用率； α0，αj為核函數(shù)的參數(shù)，由模型訓(xùn)練可得；m為用于訓(xùn)練的數(shù)據(jù)集中的數(shù)據(jù)總數(shù)目。

3.2 包簇之間的距離計算

簇與聚類包之間的距離由資源之間的相關(guān)性進行定義，采用Pearson（皮爾遜）[11]相關(guān)系數(shù)描述簇中已使用的資源總量與包的需求總量之間的相關(guān)性，分別將Rv[t]，Sp[t]，Wp[t]代入相關(guān)系數(shù)，由于相關(guān)系數(shù)ρRv(t),Wp(t)的因子取值為[0,1]，所以，將Rv[t]與Wp[t]進行歸一化，再代入式（10），可得

由于相關(guān)系數(shù)的區(qū)間為[?1,1]，因此，定義簇與聚類之后的包之間的距離

式（11）表示包簇之間的距離，區(qū)間為[0,1]，當由式（11）計算得出的LRv(t),Wp(t)值處于[0,1/2)時，表示Rv[t]與Wp[t]之間具有負相關(guān)性，具有負相關(guān)性的虛擬機與物理節(jié)點之間一般具有更多的資源互補[12-13]。因此，在進行包簇資源分配過程時，首先將包映射到與其距離的區(qū)間在[0,1/2)之間的簇，且在這區(qū)間中距離值越小，代表包與簇之間的資源互補性越大，最終可在資源分配時使得包能夠集中映射到簇，從而減少簇的使用個數(shù)，提高資源利用率，降低分配過程中產(chǎn)生的能耗。

3.3 包簇資源調(diào)度算法的流程

基于改進的k-means 包簇資源調(diào)度算法（IKPC）步驟：

步驟1將所有待分配的聚類包放入隊列，計算每個聚類的包到簇的距離，并將符合條件的聚類包映射到離它最近的簇中；

步驟2若簇資源不夠分配給任何一個聚類包，則將聚類包放入隊列尾部，直到聚類包找到具有符合條件的簇進行映射；

步驟3循環(huán)步驟1 和步驟2，直到所有的經(jīng)過聚類以后的包映射到相應(yīng)的簇中。

4 相關(guān)實驗

實驗1包聚類算法驗證。

為了驗證包聚類算法的有效性，現(xiàn)定義幾種包參數(shù)，具體參數(shù)如表2 所示。包需求為（100，100）的含義是對CPU 的需求為100 核，對內(nèi)存的需求為100 MB。

表 2 包需求參數(shù)（2）Tab.2 Package demand parameters（2）

通過Hadoop 框架的MapReduce 思想進行改進的k-means 算法的驗算，實驗結(jié)果如圖2 所示。

圖 2 實驗聚類結(jié)果Fig.2 Clustering experiment results

由圖2 的實驗結(jié)果可得，10 個包樣本，經(jīng)過聚類最終形成3 個聚類包。第一類包編號為1，2，5，8 的聚類包，編號2，8 為對CPU 需求較高的包，編號5 為對內(nèi)存需求較高的包；第二類編號為3，4，9 的聚類包，編號3，9 為對CPU 需求較高的包，編號4 為對內(nèi)存需求較高的包；第三類編號為6，7，10 的包，編號7，10 為對CPU 需求較高的包，編號6 為對內(nèi)存需求較高的包。因此，本實驗在將包進行聚類時，具有一定的有效性和靈活性。

實驗2資源調(diào)度算法驗證。

采用云仿真軟件Cloudsim3.0[14]進行實驗，實驗環(huán)境中計算機參數(shù)為Intel Core i5-8250U CPU@1.60 GHz，內(nèi)存為8.00 GB，64 位操作系統(tǒng)。

為了說明在資源調(diào)度算法之前首先將具有需求差異的包進行聚類的重要性，將本文的IKPC 算法與未經(jīng)聚類直接采用資源調(diào)度算法（PC，package-cluster）進行對比，此外，進行對比的算法還有傳統(tǒng)啟發(fā)式算法、降序首次適應(yīng)算法（FFD）[15]，F(xiàn)FD 算法是通常用來解決資源調(diào)度問題的方法。為了驗證在包的需求更多以及簇資源規(guī)模更大時算法的有效性，現(xiàn)采用2 000 個簇和1 600 個包進行實驗。

如圖3 所示，本文中經(jīng)過包聚類以后的IKPC算法的簇使用個數(shù)最少，相比未經(jīng)過聚類，直接調(diào)用PC 算法的簇的個數(shù)少100 左右，相比于簇使用個數(shù)最多的FFD 算法，IKPC 的簇使用個數(shù)少500 左右。因此，本文中的IKPC 能在最少的簇中盡可能多地分配資源，具有一定的可用性。

圖 3 簇使用個數(shù)比較Fig.3 Cluster number comparison

如圖4 所示，本文的資源調(diào)度算法IKPC 的CPU 利用率最高，F(xiàn)FD 算法與其他兩種算法相比，其CPU 利用率最低。IKPC 算法比FFD 算法的CPU 利用率總體高10%左右，比未聚類的PC高6%左右。顯而易見，本文的資源調(diào)度算法在CPU 利用率方面更有優(yōu)勢。

如圖5 所示，IKPC 的內(nèi)存利用率最高，相比于內(nèi)存利用率最低的FFD 算法，IKPC 的內(nèi)存利用率高了將近15%，比未聚類的PC 高7%左右。因此，本文的資源調(diào)度算法IKPC 在提高內(nèi)存利用率方面具有有效性。

圖6 為3 種算法的能耗比較結(jié)果。由于本文的IKPC 算法在資源分配過程中使得包能夠集中映射到簇中，從而降低了資源分配過程中產(chǎn)生的能耗，而PC 和FFD 算法在資源分配過程中側(cè)重于尋找合理的資源分配解，忽略了能耗、資源利用率的優(yōu)化，因此，本文的IKPC 算法在降低數(shù)據(jù)中心的能耗方面具有一定的可用性。

圖 4 CPU 利用率比較Fig. 4 CPU utilization comparison

圖 5 內(nèi)存利用率比較Fig. 5 Memory utilization comparison

圖 6 能耗比較Fig. 6 Energy consumption comparison

5 結(jié)束語

針對數(shù)據(jù)中心包簇框架下的資源分配問題，本文在進行包簇資源映射工作之前，首先將具有資源需求差異的包采用改進的k-means 進行聚類，然后，通過皮爾遜相關(guān)系數(shù)將聚類以后的包的需求和簇可提供資源之間的相關(guān)性作為距離度量因子，實現(xiàn)了包簇資源的映射。實驗研究表明，改進后k-means 算法能夠有效地對包聚類，資源調(diào)度算法能夠有效地減少簇的使用個數(shù)，不僅能夠提高各類資源利用率，而且可以降低數(shù)據(jù)中心由于資源分配而產(chǎn)生的能耗。