云數據中心基于皮爾遜相關系數的虛擬機選擇策略*

徐勝超 ，宋 娟 ，潘 歡

(1.廣州華商學院 數據科學學院，廣東 廣州 511300；2.寧夏大學 寧夏沙漠信息智能感知重點實驗室，寧夏 銀川 750021)

0 引言

如何提高云數據中心的物理主機的利用效率并進行負載均衡操作至關重要[1]，目前大部分云服務提供商都采用虛擬機遷移技術[2]。虛擬機選擇是整個虛擬機遷移過程的一個重要步驟，它的功能是從云數據中心的異常物理主機中運用一定的算法選擇出需要候選遷移的虛擬機，從而為后續的虛擬機放置過程提供輸入參數。

具有高關聯度的虛擬機之間更容易觸發超負載事件，因此如何防止那些高關聯性的虛擬機在虛擬機放置過程中被分配到同一個物理節點上就是一個關鍵問題[3-4]。

文獻[5]提出了虛擬機選擇和虛擬機放置過程結合起來,可以充分提高物理資源的使用效率,具有一定的優勢；文獻[6-7]提出了貪心算法優化的虛擬機選擇策略，在選擇過程中通過動態調整物理資源利用閾值邊界，可以很好地降低能量消耗；文獻[8-9]提出了溫度感知的虛擬機選擇策略，它將物理主機的處理器的溫度作為虛擬機選擇的標準，是一種考慮硬件的虛擬機選擇策略。文獻[10]提出了數據依賴的虛擬機選擇策略，它在選擇候選遷移虛擬機的過程中考慮虛擬機之間的數據依賴關系，它的思路與本文的考慮十分相似。實驗結果表明該策略也可以提高云數據中心的各類指標性能，但是文獻[5]-[10]都沒有考慮虛擬機的關聯性。

虛擬機之間的相關性如果按照統計學的方式進行建模，考慮物理資源的歷史信息，在這種因素下考慮虛擬機選擇問題會更加接近真實的情況。本文提出一種考慮虛擬機關聯性的虛擬機選擇策略，稱為PC-VMS(Pearson Correlation coefficient Virtual Machine Selection)，即把皮爾遜相關系數的計算方法應用于虛擬機CPU歷史利用率數據，建立了衡量每對虛擬機CPU 利用率之間的相關性的數學模型；PC-VMS 會獲取每對虛擬機最近n 次的CPU 利用率，根據輸入的兩組數據來計算皮爾遜相關系數，最后在一組相關性最高的虛擬機中選擇一個CPU 利用率最高的對象作為候選遷移虛擬機，從而為后續的虛擬機放置步驟作為輸入參數。

PC-VMS 虛擬機選擇策略的仿真和測試過程是放到整個虛擬機遷移過程中完成的。經過PC-VMS 虛擬機選擇策略優化后的虛擬機遷移實驗結果表明，PC-VMS 可以穩定云計算的服務質量水平,降低能量消耗。

1 PC-VMS 虛擬機選擇策略概況

1.1 PC-VMS 的工作背景

PC-VMS 依托CloudSim 模擬器工具來工作與仿真云數據中心的各類性能指標，經過PC-VMS 優化后的虛擬機遷移過程具體包括以下4 個步驟[11]：

(1)周期性地完成云數據中心的所有物理主機狀態檢測(over-utilized 或under-utilized)，形成異常物理主機列表；

(2)針對異常的物理主機，采用PC-VMS 策略完成虛擬機的選擇,形成侯選遷移虛擬機列表；

(3)針對候選遷移的所有虛擬機，完成虛擬機放置過程；

(4)反復執行步驟(1)～(3)，通過設置一個是周期(通常是一周),達到該時間段虛擬機遷移過程就結束。

PC-VMS 與CloudSim 項目中不同的是，在步驟(2)中，著重考慮虛擬機的處理器利用率的關聯度，通過建立虛擬機之間的關聯度數學模型，設計了虛擬機之間的皮爾遜相關系數，其他的步驟(1)和步驟(3)繼續借鑒了CloudSim 項目中的已有的優化策略。

1.2 PC-VMS 的相關術語

1.2.1 皮爾遜相關系數

假設一個物理主機上面有n 個運行的虛擬機VM，假設這些虛擬機組成了一個向量，VM={VM1，VM2，…，VMn}，為了計算物理主機上虛擬機之間的相關性，本文算法使用了皮爾遜相關系數，其計算公式如下：

式中，r 表示皮爾遜相關系數，i 和n 表示虛擬機的編號，xi和yi分別表示的是虛擬機VMi最近的k 次CPU 利用率，各自表示虛擬機最近的k 次CPU 利用率的平均值。式(2)為虛擬機CPU 歷史利用率矩陣U：

式中，矩陣的行代表超負載主機上的某個虛擬機VMi的利用率，矩陣的列表示模擬器運行過程中的某個時間點tj，矩陣中的數據uij表示虛擬機VMi在時間點tj下的CPU 利用率。接下來，利用CPU 歷史利用率矩陣，根據皮爾遜相關系數的計算公式計算虛擬機之間的相關性，同樣把結果保存在一個矩陣(C)中，如式(3)所示：

式中，矩陣的行和列都代表著虛擬機VMi；cij代表虛擬機CPU 利用率之間的皮爾遜相關系數，cij∈(-1，1)；矩陣中的數字1 是無效的值。

1.2.2 云數據中心的總體能量消耗模型

云數據中心能量消耗主要由物理主機的所有部件的能量消耗組成。一個物理主機所消耗的能量主要由處理器、內存、磁盤、網絡帶寬組成。根據這個思路，本文設計了單個物理主機的能量消耗。第j 個物理主機在[t0，t1]時間段的總體能量消耗Ej可以按照式(4)來計算：

那么整個云數據中心的能量消耗Etotal為式(5)：

其中，m 是物理主機個數。

1.2.3 SLA 違規在線時間(SLA violation Time per Active Host，SLATAH)

SLA 在線時間(SLA time per host)體現了物理主機具有高服務質量的在線時間情況。

其中，m 為云數據中心的物理主機數量，j 表示物理主機的編號，Tsj是物理主機CPU 利用率達到100%的時間，Taj是物理主機處于在線活躍狀態的時間。

1.2.4 虛擬機遷移后的性能降低(Performance Degradation due to Migrations，PDM)

其中，n 表示云數據中心的虛擬機數量，i 表示虛擬機的編號，Ddi是由于虛擬機VMi遷移導致的性能下降的估計值，Dri是請求虛擬機VMi的整個時間段內總的CPU MIPS 計算能力。

1.2.5 SLA 違規率(SLA Violation)

SLA 的違規率的計算通過式(8)計算：

SLA Violation 違規率是體現云服務提供商的高服務質量的重要指標。

2 PC-VMS 虛擬機選擇策略描述

2.1 PC-VMS 的策略描述

本小節詳細描述PC-VMS 虛擬機選擇策略涉及的算法及其工作流程。該策略使用了兩個算法，在算法1中，計算皮爾遜相關系數矩陣，接著調用算法2 來尋找相關性大小位于前k 位分別所對應的虛擬機，最后從算法2 返回的虛擬機列表中選擇一個CPU 利用率最大的虛擬機遷移出去。

(1)算法1：基于皮爾遜相關系數的虛擬機選擇策略

輸入：物理主機負載檢測階段的異常物理主機MigratedHostList

輸出：要遷出的虛擬機列表VmsToMigratedList

①獲取物理主機上的虛擬機列表，保存到變量migratableVms 列表中；

②計算當模擬器當前的時刻time，將time 除以300得到timeStep，如果timeStep<5，則啟用備用的虛擬機選擇策略，結束該算法，否則，進入步驟③；

③根據獲取的migratableVms 計算CPU 歷史利用率矩陣cpuUsage；

④根據矩陣cpuUsage 計算CPU 利用率之間的皮爾遜相關系數，結果保存到矩陣pearsonMatrix 中；

⑤調用算法2 尋找虛擬機列表，返回結果保存到列表vmList 中；

⑥在vmList 尋找一個CPU 利用率最大的虛擬機，保存該虛擬機在vmList 中的索引值index；

⑦返回vmList 中索引為index 的虛擬機，存入VmsTo-MigratedList。

(2)算法2：尋找皮爾遜相關系數大小最近的k 個所對應的虛擬機

輸入：pearsonMatrix，migratableVms，k

輸出：與最近k 個相關系數大小有關的虛擬機列表vmList

①遍歷矩陣pearsonMatrix 的行和列，取出里面的元素，存放到一個名為maxCoefficients 的HashSet 集合中；

②對maxCoefficients 中的元素進行降序排列，結果賦給一個List 集合，取名為coefficientsList；

③取出集合coefficientsList 中前k 個元素，存放到List集合top_k 中；

④遍歷pearsonMatrix 矩陣的每一行，找出這一行最大的那個元素，然后判斷top_k 列表是否包含這個元素，如果包含，則從migratableVms 列表中根據當前遍歷的行號找到一個虛擬機，添加這個虛擬機到列表vmList 中；

⑤返回vmList。算法1 和算法2 兩個算法經過少量的修改即可轉化成為代碼。

2.2 PC-VMS 的策略實現模塊

PC-VMS 依托了CloudSim 各個運行模塊，在CloudSim云模擬器中每個物理主機上都運行有一個本地代理Local Broker，PC-VMS 虛擬機選擇優化策略的實現主要在此模塊中完成，算法1 和算法2 的實現基于Java 實現。上述算法1 和算法2 的運行流程經過少量修改即可轉化為PC-VMS 的代碼。

3 PC-VMS 仿真實驗與性能分析

3.1 仿真環境的建立

(1)創建物理主機

云數據中心的能量消耗模型是最常見的CoMon project，它是由planetlab 實驗室開發的一個項目，也是目前云數據中心的模擬器的典型BenchMark 模型[12]。測試指標都參考了1.2 節中提到的虛擬機遷移次數、SLA 違規率、能量消耗情況。物理主機配置如表1 所示。

表1 云數據中心物理主機硬件配置

(2)創建虛擬機

創建的虛擬機參考的是普通網絡客戶端的應用程序訪問類型，不同的是每個虛擬機都是CPU 能力不同，并且內存也有所改變?？偣矂摻? 種虛擬機類型，配置參數如表2 所示。

表2 PC-VMS 虛擬機配置參數表

對于虛擬機的初始化放置策略，使用的是首次適應的方法，即首次為虛擬機尋找宿主機的時候，如果找到了一個擁有足夠資源創建這個虛擬機的物理主機，就立即分配給它，而不再考慮后面的主機，即使有更合適的選擇。這樣做的好處就是在為虛擬機首次尋找目標主機的過程中節約了時間，虛擬機請求的個數如表3 所示。

表3 PC-VMS 虛擬機選擇優化策略運行時間

在實驗中的物理主機負載檢測中，采用的是魯棒局部歸約主機負載檢測，即選擇最近j 個物理主機進行規約預測出資源利用率邊界然后選擇，j 取值為10。

PC-VMS 虛擬機選擇策略將與CloudSim4.0 內置的策略進行對比，這些內置的策略包括隨機選擇策略(Random Selection，RS)、最小利用率策略(Minimum Utilization，MU)、最大關聯選擇策略(Maximum Correlation，MC)和最小時間選擇策略(Minimum Migration Time，MMT)。在虛擬機放置策略方面，實驗中采用的是遞減裝箱方法(Best-Fit-Decreasing，BFD)。

3.2 固定虛擬機數量的實驗分析

整個云客戶端被分配了1 000 個虛擬機，然后讓這些虛擬機執行2 000 個云任務，每個任務的長度是216 000 000 MI，給CloudSim 設定的模擬時間是24 h(86 400 s)。最后，每次保持上述的設置不變，在CloudSim 模擬器中測試了包括本文算法在內的5 種虛擬機選擇策略。表4 展示了它們的測試結果。

從表4 的測試的結果來看，PC-VMS 虛擬機選擇策略在降低能量消耗方面的效果要稍微好于其他策略，MU 策略的能量消耗是最大的，另外3 種策略的能耗基本持平。表4 的第3、4 列顯示了在虛擬機遷移次數以及SLA 違規次數方面的情況，PC-VMS 虛擬機選擇策略則明顯少于其他4 種策略，所以PC 虛擬機選擇策略帶來的性能下降和SLA 違規率也是最低的。PC-VMS 虛擬機選擇策略相比于其他策略擁有低能量消耗的優勢，并且大幅度地降低了SLA 違規率，這有利于企業實現綠色節能的云計算。

表4 云數據中心不同虛擬機選擇策略測試結果

從表4 也可以看出，PC-VMS 虛擬機選擇策略明顯地降低了虛擬機遷移次數，從而也降低了物理主機遭受SLA 違例的次數。由于MU 虛擬機選擇策略每次選擇CPU 利用率最低的那個虛擬機進行遷移，可能需要反復執行算法選擇多個虛擬機遷出，才能使過度負載的物理主機重新回到正常負載水平，因此該策略的能耗、SLA違規率、虛擬機遷移次數和SLA 違規次數都較高。PC-VMS虛擬機選擇策略還有一個重要的優勢是它在整個遷移過程中所導致的性能下降比率最低，這得益于該策略的虛擬機遷移次數較少，因為每次虛擬在線遷移的過程中難免會損失部分性能。

3.3 不同虛擬機數量的實驗分析

利用PC-VMS 虛擬機選擇算法優化之后，當云平臺的虛擬機的請求個數從100～600 個變化時，各個虛擬機選擇策略的總體能量消耗比較如表5 所顯示。從表5 可以看出，PC-VMS 比CloudSim4.0 中已有的策略在總體能量消耗上要節約20%～25%，能量消耗基本呈線性變化。分析原因是雖然云數據中心的整體物理主機個數為800 個，但是隨著虛擬機個數的變化，在虛擬機比較少的時候，大部分物理主機可以切換到關閉狀態，能量消耗自然降低了。

表5 各類策略總體能量消耗性能比較 (kWh)

4 結論

云數據中心利用虛擬機遷移技術來降低總的能量消耗，同時必須盡量滿足SLA 違規。作為虛擬機遷移過程的一部分，虛擬機選擇算法要從狀態異常的物理主機中精準地選擇出候選遷移的虛擬機。本文提出了一種根據虛擬機CPU 利用率之間的相關性來選擇虛擬機的PC-VMS 策略，PC-VMS 虛擬機選擇策略不僅僅限制于在CloudSim 模擬器中，還可以與其他的開源云平臺結合起來使用，或與其他更加先進的虛擬機放置算法結合起來使用，可以更好地提高云數據中心的各個性能指標[13-15]。