基于線性回歸與最小二乘法的物理主機狀態(tài)異常檢測方法

徐勝超，宋 娟，潘 歡

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

0 引 言

虛擬機遷移是近年來大規(guī)模節(jié)能云數(shù)據(jù)中心構(gòu)造的關(guān)鍵技術(shù)[1-3]。虛擬機遷移中最重要的一個步驟是物理主機異常狀態(tài)檢測，它通過監(jiān)視云數(shù)據(jù)中心的所有主機的物理資源使用狀態(tài)來判斷，采用一定的算法或者策略，把那些運行異常(超負(fù)載或低負(fù)載)的物理節(jié)點選擇出來[4-5]，形成侯選遷移物理主機列表。在接下來的虛擬機選擇和虛擬機放置步驟中，也有各自特定的選擇算法[6-7]、放置算法操作[8-10]。主機狀態(tài)檢測、選擇、放置這3個步驟的優(yōu)化算法還可以組合起來使用，但是最終評價標(biāo)準(zhǔn)是虛擬機遷移后的云數(shù)據(jù)中心的節(jié)能效果、物理資源利用實際效果和SLA違規(guī)效果等指標(biāo)[11-13]。

本文重點研究物理主機狀態(tài)檢測階段，這種狀態(tài)檢測策略可以分為主動法和被動法。主動的檢測方法可以使得云數(shù)據(jù)中心的物理資源被充分利用，是一類比較好的檢測方法。目前已有的物理主機狀態(tài)檢測方法大多采用被動式的或者靜態(tài)管理策略，其考慮的維度因素也比較單一，已經(jīng)不能適應(yīng)云客戶端的動態(tài)、自適應(yīng)的訪問需求。為此本文提出一種基于線性回歸與最小二乘法的物理主機狀態(tài)異常檢測方法EPADA(Efficient Physical host status Anomalous Detection Approach)。

本文的EPADA是一種主動的、自適應(yīng)的、動態(tài)的物理主機狀態(tài)檢測方法，它采用回歸操作預(yù)測出物理主機在未來的一段時間內(nèi)的資源使用率情況來確定其閾值邊界，為后續(xù)遷移步驟做準(zhǔn)備。EPADA通過CloudSim來實現(xiàn)和仿真,性能分析表明EPADA的各項性能指標(biāo)與期望的相符合。

1 物理主機狀態(tài)檢測的相關(guān)工作

早期的靜態(tài)閾值邊界管理方法不能適應(yīng)越來越復(fù)雜的云客戶端的需求[14-15]，還有一些早期的資源使用率邊界管理方法考慮的因素只有CPU這個維度[16]，比較好的物理主機狀態(tài)檢測方法應(yīng)該考慮CPU、內(nèi)存、網(wǎng)絡(luò)帶寬、網(wǎng)絡(luò)接口等綜合因素。

EPADA屬于CloudSim項目的一種后續(xù)研究工作。CloudSim工具包中已有許多物理主機異常狀態(tài)檢測方法，它把異常物理主機劃分為超負(fù)載over-utilized狀態(tài)或者低負(fù)載under-utilized狀態(tài),并且根據(jù)物理資源使用率的閾值情況來完成狀態(tài)檢測[3]。

近年來也有大量的采用智能算法進(jìn)行優(yōu)化物理主機狀態(tài)檢測的文獻(xiàn)，例如處理器溫度感知[17]、二次平滑預(yù)測法[18]、穩(wěn)定匹配算法[19]、K鄰近回歸預(yù)測法[20]等，這些文獻(xiàn)在研究思路、測試指標(biāo)等方面基本上都參考了CloudSim項目。

2 工作背景與相關(guān)術(shù)語

2.1 物理主機狀態(tài)檢測的工作場景

一個云客戶端向云數(shù)據(jù)中心的全局代理請求虛擬機，該全局代理Global Broker將虛擬機分派到具體的可用的物理主機上執(zhí)行。圖1顯示了EPADA工作模塊。在CloudSim中每個物理主機上都運行有一個本地代理Local Broker，它監(jiān)視物理主機的軟硬件資源，EPADA物理主機狀態(tài)檢測策略的實現(xiàn)代碼主要在本地代理模塊中完成。本地代理根據(jù)物理主機的處理器的利用率情況把其劃分為3類：Pnormal、Pover、Punder，即正常主機、超負(fù)載主機、低負(fù)載主機。一般CPU的利用率低于或者高于一個閾值邊界都處于Pover或Punder狀態(tài)，其他的為正常狀態(tài)Pnormal。利用率閾值邊界具體取值多少可以通過各類閾值管理策略來測試和調(diào)整。虛擬機管理器Virtual Machine Manager用來配合本地代理Local Broker具體地完成虛擬機遷移的啟動與關(guān)閉，這個工作場景在文獻(xiàn)[3]有描述。

圖1 EPADA物理主機狀態(tài)檢測的工作場景

2.2 回歸與最小二乘法技術(shù)

回歸方法可以預(yù)測數(shù)據(jù)的下一階段的值，回歸方法被廣泛使用在數(shù)據(jù)預(yù)測領(lǐng)域[21]?；貧w技術(shù)有2種模型，單個輸入的單一回歸和多個輸入的多回歸。EPADA算法采用了單一權(quán)值線性回歸來預(yù)測物理主機的資源使用率情況。該思想如公式(1)所示：

y=β0+β1x

(1)

其中，y是受依賴的變量，x是獨立的變量，β0和β1是回歸系數(shù)，輸出變量y的預(yù)測值表示數(shù)據(jù)集中每個數(shù)據(jù)點的變化情況。

(2)

(3)

(4)

(5)

簡化上面2個等式后可以得到：

(6)

(7)

2.3 EPADA狀態(tài)檢測的相關(guān)術(shù)語

1)云數(shù)據(jù)中心能源消耗模型(Energy Consumption)。

假設(shè)物理主機是空閑的，它的能源消耗的百分比是k,Pfull表示物理主機在完全滿負(fù)載工作時的能源消耗，CPUutil(i)是當(dāng)前的物理主機i的CPU使用率,這樣物理主機的能源消耗定義為公式(8)：

Ei=k×Pfull+(1-k)Pfull×CPUutil(i)

(8)

設(shè)m是云數(shù)據(jù)中心中的所有物理主機個數(shù)，整個云數(shù)據(jù)中心的能量消耗可以定義為公式(9)：

(9)

2)云數(shù)據(jù)中心SLA違規(guī)比率(SLA Violation)。

SLA違規(guī)的具體值可以通過公式(10)來計算:

SLAV=SLATAH×PDM

(10)

其中，SLATAH是活動主機的CPU具有100%的使用率所占的比例，PDM是整個系統(tǒng)因為虛擬機遷移后的性能降低情況。

3)SLA違規(guī)與能量消耗聯(lián)合指標(biāo)ESV。

CloudSim中的ESV(Energy and SLA Violations)方法可以很好地評價整個云數(shù)據(jù)中心的性能,ESV的計算公式如下：

ESV=Etotal×SLAV

(11)

其中，Etotal是云數(shù)據(jù)中心的整體能量消耗，SLAV的含義是SLA違規(guī)情況,ESV體現(xiàn)了能量與SLA違規(guī)的平衡。

3 EPADA物理主機狀態(tài)檢測算法描述

3.1 物理資源使用率預(yù)測

云數(shù)據(jù)中心中預(yù)測物理資源的未來情況和需求是十分重要的，由于目前的能量消耗模型大部分都是基于物理主機的CPU來完成計算，例如公式(8)。本文提出的EPADA模型，線性回歸的函數(shù)主要針對過去1個小時CPU使用率的情況，從而迭代出當(dāng)前CPU使用率的情況。首先解釋EPADA物理主機狀態(tài)檢測算法如何評估出物理主機的理想CPU請求，接著描述EPADA算法如何檢測出云數(shù)據(jù)中心的超負(fù)載物理主機和低負(fù)載物理主機，并且將其運用到后續(xù)的虛擬機選擇和虛擬機放置過程中。

EPADA算法利用一個線性回歸方法來設(shè)計預(yù)測函數(shù)。該函數(shù)顯示了未來的和當(dāng)前的物理主機CPU使用率之間的線性關(guān)系。

y=β0+β1x

其中，β0和β1是回歸相關(guān)系數(shù)，它們可以通過過去的k次物理主機使用率來完成計算，y是物理主機使用率的期望值，x是物理主機的當(dāng)前物理資源利用率。在EPADA中，把k設(shè)置為12，因為在云數(shù)據(jù)中心中把虛擬機遷移的周期設(shè)置為5 min，所以要預(yù)測1個小時后的資源利用率的具體值，需要完成12次迭代。EPADA物理主機狀態(tài)使用率邊界預(yù)測值的計算如算法Algorithm1所示。

Algorithm1EPADA Algorithm

Input:h

Output: predictUtil

1.// Approximate the prediction function based onkpast utilization

2.Initialize theβ0andβ1to a random small value;

3.Fori=1 tokdo

4.xi=UtilHistory (i);

5.yi=UtilHistory (i+1);

7.// Calculate the loss

9.Update theβ0value using Equation (6) overisamples ofk

10.Update theβ1using Equation (7) overisamples ofk

11.end for

12.// Use the regression function

13.PredictUtil=β0+β1*CurrTotalUtil(h)

14.return predictUtil;

該算法是EPADA物理主機狀態(tài)檢測的一個核心功能，輸入值為h，輸出值為predictUtil。最初的時候，相關(guān)系數(shù)被設(shè)置為一個比較小的隨機值(代碼第2行)，接下來執(zhí)行k次循環(huán),根據(jù)處理器的歷史數(shù)據(jù)，迭代計算出資源使用率的預(yù)測值。由于線性回歸所計算的是每個數(shù)據(jù)點的真實值和預(yù)測值之間的差值，所以每一次的迭代得到的資源使用率預(yù)測值更加接近于真實數(shù)據(jù)。

資源使用率預(yù)測值的估計值也是基于相關(guān)系數(shù)的參數(shù)和當(dāng)前的數(shù)據(jù)值，通過第7行的代碼得到過去i個數(shù)據(jù)點的殘差平方和，最后更新β0和β1的值可以繼續(xù)減少資源使用率的預(yù)測值和真實值的差異性。最后在第13行代碼中把物理主機上的所有虛擬機的總體資源使用率賦予資源使用率預(yù)測值。

3.2 高負(fù)載主機檢測過程

EPADA可以預(yù)測出所有物理主機在將來一段時間內(nèi)的資源使用情況，在實體遷移過程中被用來判斷物理主機是超負(fù)載或低負(fù)載。當(dāng)某個主機超負(fù)載時，則將一些虛擬機遷移到其他主機上以減少SLA違規(guī)率；當(dāng)某個主機低負(fù)載時，該主機切換到睡眠狀態(tài)以減少能量消耗。這些對云數(shù)據(jù)中心整體性能的提高是極其有利的操作。

EPADA的超負(fù)載物理主機檢測的偽代碼稱為算法Algorithm2。

Algorithm2Over-Loading Physical Host Detection

Input: host

Output: Boolean

1.if(UtilHistory.length <12)

2.if(CurrTotalUtil(host)>0.85*TotalUtil(host))

3.return true;

4.else

5.return false;

6.end if

7.else

8.predictUtil=EPADA(host);

9.if(predictUtil>CurrTotalUtil(host))

10.return true;

11.else

12.return false;

13.end if

14.end if

上面代碼表明，在收集了過去的12個物理資源使用率之后，如果當(dāng)前的資源使用率大于所有物理資源可用率的85%，那么該物理主機將設(shè)置為超負(fù)載狀態(tài)，這里的85%是可以調(diào)整的。通過算法Algorithm1可以預(yù)測未來的CPU使用率的情況，在資源使用的預(yù)測值大于可用的CPU計算能力的情況下，該物理主機也設(shè)置為超負(fù)載狀態(tài)。如果上面2個情況都沒有，則該物理主機不是超負(fù)載狀態(tài)。從這個代碼可以看出，通過設(shè)置一定的時間周期，EPADA檢測方法可以隨時避免出現(xiàn)超負(fù)載物理主機的情況，最終啟動虛擬機選擇和放置程序。

3.3 低負(fù)載主機檢測過程

EPADA的低負(fù)載物理主機檢測的偽代碼稱為算法Algorithm3。

Algorithm3Under-Loading Physical Host Detection

Input: host

Output: Boolean

1.if(UtilHistory.length <12)

2.if(CurrTotalUtil(host)=0)

3.return true;

4.else

5.return false;

6.end if

7.else

8.predictUtil=EPADA(host);

9.if(predictUtil<0.1*TotalUtil(host));

10.return true;

11.else

12.return false;

13.end if

14.end if

從上面的代碼可以看出，如果一個物理主機的CPU使用率為0則處于低負(fù)載狀態(tài)；在1個小時后，通過算法Algorithm1可以預(yù)測未來CPU使用率的情況，如果通過迭代后得到的當(dāng)前資源使用率小于所有物理資源可用率的10%，則該物理主機也處于低負(fù)載狀態(tài)，這里的10%是可以進(jìn)行調(diào)整的。從這個代碼可以看出，通過設(shè)置一定的時間周期，EPADA檢測方法可以隨時避免出現(xiàn)低負(fù)載物理主機的情況，運行在低負(fù)載狀態(tài)的物理主機其上運行的虛擬機將被選擇及重新放置，最終將該物理主機切換到睡眠模式或者關(guān)閉物理電源，間接地節(jié)省了云數(shù)據(jù)中心的總體能量消耗。

3.4 虛擬機遷移過程

EPADA檢測方法在后續(xù)的虛擬機遷移過程中也有涉及，稱為算法Algorithm4。

Algorithm4VMs Live Migration

1.For each host in hostList do

2.while(OverloadeingDetection (host)=true OR

UnderloadeingDetection (host)=true) then

3.VM=VMSelection(host);

4.otherHosts=hostList-host;

5.h=VMsAllocation(otherHosts, VM);

6.migrate(VM,h);

7.end while

8.end for

從上面的代碼可以看出，只要云數(shù)據(jù)中心的物理主機處于異常狀態(tài)(超負(fù)載或低負(fù)載)，都將進(jìn)入侯選遷移物理主機列表，其上運行的虛擬機將通過后續(xù)的虛擬機選擇策略而形成侯選遷移虛擬機列表，而云數(shù)據(jù)中心中的其他物理主機將在虛擬機放置階段作為容納新的虛擬機的節(jié)點存在。

4 仿真實驗與性能分析

4.1 仿真環(huán)境的設(shè)置

1)創(chuàng)建物理主機。

在實驗中，云數(shù)據(jù)中心的能量消耗模型采用的是常見的CoMon Project,也是目前典型的BenchMark模型[23]。測試指標(biāo)都參考了第2章中提到的SLA違規(guī)率、能量消耗情況。

在CloudSim項目中設(shè)置的云數(shù)據(jù)中心主要由4類物理服務(wù)器組成，物理主機總數(shù)為800臺，物理主機配置如表1所示。

表1 云數(shù)據(jù)中心物理主機硬件配置

2)創(chuàng)建虛擬機。

創(chuàng)建的虛擬機參考的是普通網(wǎng)絡(luò)客戶端的應(yīng)用程序訪問類型，不同的是每個虛擬機的CPU能力不同，并且內(nèi)存也有所改變。總共創(chuàng)建了4種虛擬機類型，配置參數(shù)如表2所示。

表2 EPADA物理主機狀態(tài)檢測方法的配置參數(shù)表

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

表3 EPADA物理主機狀態(tài)檢測方法測試時間

4.2 性能比較對象

表4 EPADA物理主機狀態(tài)異常檢測性能比較對象

CloudSim中原始的虛擬機遷移模型稱之為LRR-MMT-BFD策略，將它作為首要比較對象[3]。還與其他主機檢測方法進(jìn)行了比較，例如AEEVC[16]檢測方法、ATEA檢測方法[5]、穩(wěn)定匹配虛擬機遷移[19]、關(guān)聯(lián)性虛擬機遷移[24]、蟻群優(yōu)化的虛擬機遷移[13]等，分析這些物理主機異常狀態(tài)檢測對云數(shù)據(jù)中心的性能改變情況，如表4所示。

4.3 仿真結(jié)果與性能分析

1)云數(shù)據(jù)中心總體能量消耗。

從圖2可以看出，有了物理主機異常檢測算法EPADA后，EPADA-MMT-BFD遷移模型比CloudSim中的LRR-MMT-BFD遷移策略在總體能量消耗上要節(jié)約25%到30%，比Stable-Matching策略、Correlation-Based策略和ACS-VMM策略的能量消耗也要低，因為EPADA能夠每次回歸檢測到狀態(tài)異常的超負(fù)載物理主機和低負(fù)載物理主機，關(guān)閉這些物理主機可以達(dá)到節(jié)能的效果。

圖2 各類虛擬機遷移策略的總能量消耗比較

2)虛擬機遷移次數(shù)。

圖3顯示了EPADA-MMT-BFD的虛擬機遷移次數(shù)都低于其他策略。Stable-Matching策略、Correlation-Based策略和ACS-VMM策略的優(yōu)化主要在虛擬機放置階段，很難降低虛擬機遷移次數(shù)，要想減少虛擬機遷移次數(shù)，必須在虛擬機選擇階段、物理主機狀態(tài)檢測階段完成優(yōu)化。

圖3 各類虛擬機遷移策略的虛擬機遷移次數(shù)

3)SLA違規(guī)率分析。

從圖4可以看出，EPADA-MMT-BFD遷移策略的SLA違規(guī)率比LRR-MMT-BFD遷移策略要低。這是因為EPADA-MMT-BFD周期性地完成超負(fù)載物理主機檢測，它可以避免物理主機出現(xiàn)100%的CPU利用率的機會。Stable-Matching策略、Correlation-Based策略和ACS-VMM策略在虛擬機放置階段都采用另外的優(yōu)化算法，它們的SLA違規(guī)率在某些時候還優(yōu)于EPADA-MMT-BFD策略。

圖4 各類虛擬機遷移策略的SLA違規(guī)率比較

4)能量與SLA違規(guī)的聯(lián)合指標(biāo)ESV。

從圖5可以看到，EPADA-MMT-BFD遷移策略的ESV也低于LRR-MMT-BFD遷移策略，但是它與其他的遷移模型比較起來，也不是最好的。所以虛擬機遷移策略應(yīng)該屬于一種多目標(biāo)優(yōu)化問題，關(guān)鍵看各類算法的目標(biāo)函數(shù)設(shè)置情況。ACS-VMM的綜合性能指標(biāo)最優(yōu)，但是它是以犧牲能量消耗與虛擬機遷移次數(shù)為代價的。

圖5 各類虛擬機遷移的能量消耗聯(lián)合指標(biāo)ESV

5 結(jié)束語

低能量消耗與高服務(wù)質(zhì)量是云數(shù)據(jù)中心的主要性能目標(biāo)，目前國內(nèi)外的研究主要采用虛擬機遷移技術(shù)來達(dá)到這2個目標(biāo)。物理主機異常狀態(tài)檢測是虛擬機遷移的重要步驟，本文提出了云數(shù)據(jù)中心中一種新的物理主機狀態(tài)異常檢測算法EPADA。EPADA具有自適應(yīng)性、動態(tài)性的特點，它利用統(tǒng)計學(xué)中回歸函數(shù)及最小二乘法，經(jīng)過多次循環(huán)迭代預(yù)測出云數(shù)據(jù)中心的物理資源使用率的情況。實驗表明，EPADA-MMT-BFD比近3年來的虛擬機遷移策略性能優(yōu)秀，EPADA物理主機狀態(tài)檢測算法可以為其他節(jié)能綠色云數(shù)據(jù)中心的構(gòu)造提供參考。