基于等差劃分的虛擬機(jī)實(shí)時遷移技術(shù)①

鄒慶欣 郝志宇 云曉春 王沖華*

(*中國科學(xué)院計算技術(shù)研究所 北京 100190)(**中國科學(xué)院大學(xué) 北京 100049)(***中國科學(xué)院信息工程研究所 北京 100193)

?

基于等差劃分的虛擬機(jī)實(shí)時遷移技術(shù)①

鄒慶欣②******郝志宇③***云曉春****王沖華*****

(*中國科學(xué)院計算技術(shù)研究所 北京 100190)(**中國科學(xué)院大學(xué) 北京 100049)(***中國科學(xué)院信息工程研究所 北京 100193)

研究了虛擬機(jī)的實(shí)時遷移。對局域網(wǎng)內(nèi)存遷移的預(yù)拷貝算法、后拷貝算法以及由這兩種算法構(gòu)成的混合拷貝算法的特性進(jìn)行分析，在改進(jìn)混合拷貝算法的基礎(chǔ)上提出了基于等差劃分的虛擬機(jī)實(shí)時遷移技術(shù)，該技術(shù)把第一輪傳輸?shù)膬?nèi)存頁劃分成近似等差數(shù)列形式的多段，以減少第二輪傳輸?shù)膬?nèi)存頁。不同工作負(fù)載條件下的試驗(yàn)表明，與混合內(nèi)存拷貝方式相比，基于等差劃分的虛擬機(jī)實(shí)時遷移技術(shù)平均減少了25%的同步內(nèi)存位圖時間，29%的后拷貝方式發(fā)送的內(nèi)存頁以及2.2%的總遷移時間，在一定程度上提高了混合內(nèi)存拷貝方式的虛擬機(jī)實(shí)時遷移性能。

實(shí)時遷移， 虛擬機(jī)， 預(yù)拷貝， 后拷貝， 混合拷貝， 等差劃分

0 引 言

云計算大數(shù)據(jù)時代到來的同時，牢牢地捆綁了虛擬化技術(shù)。虛擬機(jī)更是虛擬化技術(shù)的一個最直接而且集中的體現(xiàn)。虛擬機(jī)依靠軟件模擬的方式擁有物理計算機(jī)的全部硬件特征。而且多個虛擬機(jī)還可以同時在一臺物理機(jī)上彼此互相隔離地運(yùn)行。不僅如此，虛擬機(jī)在運(yùn)行時，在一定條件下還可以在不同的物理主機(jī)之間來回移動，用以增加虛擬化的靈活性。這被稱為虛擬機(jī)實(shí)時遷移技術(shù)。實(shí)時遷移技術(shù)在虛擬機(jī)眾多技術(shù)中無疑是一項(xiàng)卓越而實(shí)用的服務(wù)。虛擬機(jī)實(shí)時遷移有廣域網(wǎng)遷移和局域網(wǎng)遷移之分。在廣域網(wǎng)遷移中不僅要遷移虛擬機(jī)內(nèi)存，還要遷移虛擬機(jī)的磁盤鏡像文件及網(wǎng)絡(luò)狀態(tài)等。而局域網(wǎng)遷移，主要針對內(nèi)存，不必遷移虛擬機(jī)磁盤鏡像文件等，完全可以利用NFS等服務(wù)采用共享的方式。本文主要研究局域網(wǎng)遷移中的內(nèi)存遷移。

在虛擬機(jī)局域網(wǎng)內(nèi)存遷移技術(shù)中，預(yù)拷貝算法是最常用，也是最實(shí)用的算法之一。但是預(yù)拷貝算法對于讀操作密集型和寫操作密集型的虛擬機(jī)應(yīng)用負(fù)載來說，效果是截然不同的，對于預(yù)拷貝算法來說，在寫操作密集型的應(yīng)用負(fù)載運(yùn)行時，其往往達(dá)到最大迭代輪數(shù)而失效。后拷貝算法與預(yù)拷貝算法正好相反，并且只傳輸一輪內(nèi)存頁，而且對于寫操作密集型的負(fù)載很有效，但對于讀操作密集型的負(fù)載卻容易延長遷移時間。為了彌補(bǔ)預(yù)拷貝算法的缺點(diǎn)，一種結(jié)合了后拷貝算法的混合內(nèi)存拷貝算法應(yīng)運(yùn)而生。這種算法只進(jìn)行兩輪內(nèi)存頁的傳輸，第一輪預(yù)拷貝式地推送全部內(nèi)存頁，而第二輪后拷貝式地拉求部分變臟的內(nèi)存頁，充分發(fā)揮了預(yù)拷貝和后拷貝算法的優(yōu)點(diǎn)。本文對這種混合內(nèi)存拷貝方式的遷移機(jī)制進(jìn)行了研究，并提出了進(jìn)一步的改進(jìn)措施。

1 相關(guān)研究工作

文獻(xiàn)[1]首次提出實(shí)現(xiàn)了虛擬機(jī)實(shí)時遷移機(jī)制，并采用了文獻(xiàn)[2]中所提出的預(yù)拷貝算法。預(yù)拷貝算法是虛擬機(jī)實(shí)時遷移中最常用的算法。主流的虛擬化平臺均采用預(yù)拷貝算法。預(yù)拷貝算法的迭代過程如圖1所示[9]。

圖1 預(yù)拷貝算法迭代過程

預(yù)拷貝算法試圖最小化最后一輪中傳輸?shù)膬?nèi)存頁，以保證停機(jī)時間盡可能短。在這個過程中位于源主機(jī)上的虛擬機(jī)物理內(nèi)存鏡像，通過網(wǎng)絡(luò)被傳輸?shù)侥康闹鳈C(jī)，同時源主機(jī)持續(xù)運(yùn)行。所以為了保持虛擬機(jī)內(nèi)存狀態(tài)在源主機(jī)和目標(biāo)主機(jī)之間一致，一些發(fā)送到目標(biāo)主機(jī)的內(nèi)存頁，在重新訪問修改變臟之后應(yīng)該被再次發(fā)送到目標(biāo)主機(jī)。因此預(yù)拷貝算法用一個迭代的機(jī)制來不時地檢查變臟的內(nèi)存頁并重傳它們。

在虛擬機(jī)遷移的各種算法中，針對預(yù)拷貝算法的研究相對較多，文獻(xiàn)[3-6]分別介紹了不同的壓縮機(jī)制和方法對預(yù)拷貝算法的改進(jìn)。同時文獻(xiàn)[7-9]從內(nèi)存頁不同傳輸順序的角度改進(jìn)了預(yù)拷貝算法。文獻(xiàn)[10-12]則從調(diào)節(jié)虛擬機(jī)CPU的角度改進(jìn)了預(yù)拷貝算法。

除了預(yù)拷貝算法以外，文獻(xiàn)[13]提出了后拷貝算法，與預(yù)拷貝方式相反，后拷貝技術(shù)首先從源主機(jī)端發(fā)送CPU狀態(tài)和虛擬機(jī)能夠恢復(fù)運(yùn)行的最小工作集到目標(biāo)主機(jī)，然后虛擬機(jī)在目標(biāo)主機(jī)端被重啟。隨后，虛擬機(jī)在目標(biāo)主機(jī)端啟動運(yùn)行過程中，其所需的但并不存在于目標(biāo)主機(jī)的內(nèi)存頁從源主機(jī)端被請求過來或被推送過來。與預(yù)拷貝方式相比，后拷貝算法減少了總遷移時間，但增加了停機(jī)時間。

借鑒于各自的優(yōu)缺點(diǎn)，文獻(xiàn)[14]實(shí)現(xiàn)了內(nèi)存混合復(fù)制方式的虛擬機(jī)實(shí)時遷移機(jī)制。其依次執(zhí)行全內(nèi)存同步、內(nèi)存位圖同步和臟內(nèi)存同步三個過程，與預(yù)拷貝算法相比，該機(jī)制同時降低了停機(jī)時間和總遷移時間。

專門針對混合算法的改進(jìn)工作也有相關(guān)的研究。文獻(xiàn)[15]增加了預(yù)學(xué)習(xí)階段，估計出變臟比較頻繁的內(nèi)存頁，并辨認(rèn)出工作集，從而在第一輪省去工作集的傳輸，而只在第二輪后拷貝階段傳輸，從而達(dá)到減少內(nèi)存頁傳輸?shù)哪康?，而且研究了后拷貝階段的安全性和可靠性。

文獻(xiàn)[16]的研究中，在停機(jī)階段發(fā)送緩存位圖和臟頁位圖兩種位圖，對于在兩個位圖中的頁面，采用壓縮后變量傳輸?shù)姆绞剑瑥亩倪M(jìn)了混合方式的內(nèi)存?zhèn)鬏敗?/p>

文獻(xiàn)[17]提出了一種更接近于后拷貝方式近似于混合方式的遷移技術(shù)，在停機(jī)以前其并不傳輸任何內(nèi)存頁，只是在停機(jī)時間內(nèi)，傳輸了更大的工作集，不光是寫頻繁的，就連讀和接觸的內(nèi)存頁也一并傳輸過去。

還有一些其它方式的遷移技術(shù)，例如文獻(xiàn)[18]基于日志采用檢查點(diǎn)/恢復(fù)和跟蹤/重放的技術(shù)，該技術(shù)類似于預(yù)拷貝算法，但傳輸?shù)牟皇莾?nèi)存而是日志，因此數(shù)據(jù)傳輸量較小，但實(shí)現(xiàn)相對比較復(fù)雜。文獻(xiàn)[19]采用了兩個線程并行傳輸，第一個線程從頭至尾傳輸所有內(nèi)存頁，同時另一個線程傳輸變臟的內(nèi)存頁，當(dāng)?shù)谝粋€線程遵循時間限制結(jié)束時，立刻進(jìn)入停機(jī)階段。

總之，現(xiàn)有的研究工作大部分針對預(yù)拷貝算法，另外也提出了一些其它的方法。針對混合方式遷移技術(shù)的研究還不是很多，有待研究人員進(jìn)一步地改進(jìn)。

2 混合內(nèi)存復(fù)制方式

主流虛擬化平臺上均采用預(yù)拷貝算法作為虛擬機(jī)實(shí)時遷移的默認(rèn)算法，然而當(dāng)虛擬機(jī)上負(fù)載較高時，預(yù)拷貝算法往往達(dá)到最大輪數(shù)而失效。

采用混合內(nèi)存復(fù)制方式的虛擬機(jī)實(shí)時遷移技術(shù)通常不會遇到失效問題?；旌蟽?nèi)存復(fù)制方式的虛擬機(jī)實(shí)時遷移技術(shù)的特點(diǎn)就是不像預(yù)拷貝算法那樣迭代多次，而只是重傳一次，只進(jìn)行兩輪傳輸，并且第二輪采用后拷貝的形式，混合內(nèi)存復(fù)制方式將整個內(nèi)存同步過程分為全內(nèi)存同步階段、內(nèi)存位圖同步階段和臟內(nèi)存同步階段三個過程。圖2描述了混合內(nèi)存復(fù)制算法的執(zhí)行過程。從圖中可以看到，混合內(nèi)存復(fù)制方式只傳輸了一輪就暫停了虛擬機(jī)，而且在虛擬機(jī)暫停之前要把全內(nèi)存同步到目的主機(jī)；第二階段則要把記錄內(nèi)存變臟與否的位圖同步到目的主機(jī)；第三階段目標(biāo)端向源端請求和內(nèi)存位圖相對應(yīng)的變臟的內(nèi)存頁?；旌蟽?nèi)存復(fù)制方式，虛擬機(jī)暫停后傳送的只是位圖，避免了內(nèi)存頁的傳輸，從而避免了高負(fù)載情況下預(yù)拷貝算法失效的情形。但是由于第三階段采用了后拷貝拉的方式，從而又增加了安全性的問題，因?yàn)楹罂截惙绞教摂M機(jī)在目標(biāo)主機(jī)上已經(jīng)重啟，一旦虛擬機(jī)遷移失敗，源端虛擬機(jī)將不可恢復(fù)，所以減少了第三階段傳輸?shù)膬?nèi)存頁數(shù)目和加速第三階段的過程，這是混合內(nèi)存拷貝方式的一個有待改進(jìn)的地方。本文著重研究了這個問題，并提出了行之有效的改進(jìn)方法。

圖2 混合內(nèi)存復(fù)制方式

3 等差劃分算法設(shè)計

3.1 劃分成不同的段

對于混合內(nèi)存拷貝方式來說，只重傳一次，且第一輪傳輸全部內(nèi)存頁，而且第二輪采用后拷貝方式傳輸?shù)膬?nèi)存頁是相對第一輪起始點(diǎn)變臟的內(nèi)存頁，包括相對第一輪傳輸點(diǎn)未變臟的內(nèi)存頁。這就會產(chǎn)生一種現(xiàn)象，即一個內(nèi)存頁在起始點(diǎn)和傳輸點(diǎn)之間被更改時，盡管相對于起始點(diǎn)來說是變臟的，但是相對于傳輸點(diǎn)來說是沒有變臟的，對于這樣的內(nèi)存頁，混合內(nèi)存拷貝方式在后拷貝階段是要傳輸?shù)?。但?shí)際上這樣的內(nèi)存頁是不需要傳輸?shù)模驗(yàn)樵搩?nèi)存頁在傳輸點(diǎn)以后沒有被更改，換句話說只有在傳輸點(diǎn)和結(jié)束點(diǎn)之間發(fā)生變化的內(nèi)存頁才真正需要傳輸(圖3)。

圖3 起始點(diǎn)，結(jié)束點(diǎn)和傳輸點(diǎn)位置

實(shí)際上，混合內(nèi)存復(fù)制方式重傳的一次忽略了這一細(xì)節(jié)。經(jīng)過上述分析，可以說在第二輪后拷貝階段是存在三種內(nèi)存頁的，如圖4所示。

圖4 第二輪三種內(nèi)存頁面

在原來的混合內(nèi)存拷貝方式中，第二輪只區(qū)分變臟的和干凈的兩種內(nèi)存頁，沒有對變臟的內(nèi)存頁做具體的劃分，而實(shí)際上變臟的內(nèi)存頁是可以區(qū)分成傳輸前變臟和傳輸后變臟兩種情況的。完全可以通過有效的方法來盡可能多的找出這些相對傳輸點(diǎn)來說沒有變臟的內(nèi)存頁，從而減少第二輪后拷貝階段傳輸?shù)膬?nèi)存頁(圖5)。

圖5 第二輪三種頁面關(guān)系

實(shí)際上，以4kB大小的內(nèi)存頁為例，一個512MB內(nèi)存的虛擬機(jī)就有131072個內(nèi)存頁，統(tǒng)計每一個內(nèi)存頁在傳輸前或后的狀態(tài)是不現(xiàn)實(shí)的，將拖延遷移的時間。一個有效的方法就是改點(diǎn)為段，把內(nèi)存進(jìn)行劃分，統(tǒng)計一段內(nèi)存?zhèn)鬏斍盎蚝蟮淖兓闆r(圖6)。

圖6 起始點(diǎn)、結(jié)束點(diǎn)和定位點(diǎn)位置

對于混合內(nèi)存?zhèn)鬏敺绞絹碚f，只有兩輪，第一輪傳輸全部內(nèi)存頁，同時第二輪傳輸少量內(nèi)存頁，第一輪的分段顯的很關(guān)鍵。段選擇的過大，很容易遺漏一些傳輸前變臟而傳輸后沒有變臟的內(nèi)存頁，發(fā)送一些沒有必要發(fā)送的內(nèi)存頁，段選擇的太小，又會使段的數(shù)量增多，從而增加計算時間和遷移的時間。

劃分內(nèi)存成段的點(diǎn)稱之為定位點(diǎn)，在每個定位點(diǎn)可以截取一次全部內(nèi)存的變臟情況。在第一個定位點(diǎn)位置可以截取從起始點(diǎn)到當(dāng)前定位點(diǎn)這段時間內(nèi)全內(nèi)存變臟的情況。以后每個定位點(diǎn)位置可以截取前一個定位點(diǎn)到當(dāng)前定位點(diǎn)這段時間內(nèi)全內(nèi)存的變臟情況。最后通過把所有定位點(diǎn)截取的全內(nèi)存變臟情況進(jìn)行綜合統(tǒng)計，來確定每個內(nèi)存頁到底是其所在的段傳輸前變臟還是傳輸后變臟。定位點(diǎn)的多少及其位置的不同引起了各個段之間的微妙關(guān)系，定位點(diǎn)可以是隨意的無序的。但是從有序的角度講，定位點(diǎn)引起的段劃分一般可以分為倍分、差分和均分三種情況。(見圖7)

圖7中左面三個點(diǎn)條線描繪了比例為2，同時最小內(nèi)存段分別為3單位、2單位和1單位的倍分曲線變化關(guān)系。相同段數(shù)的情況下，最小內(nèi)存段越大，則能表示的總內(nèi)存越大，隨著段數(shù)的增多，內(nèi)存段也越來越大，相鄰兩段內(nèi)存的差距也逐步增大。

同時圖7右面三條虛線也描述了每段內(nèi)存長分別為7單位、4單位和1單位的均分情況。相同段數(shù)的情況下，每段內(nèi)存越長則能表示的總內(nèi)存越大。

圖7 段長選擇

但是相同段數(shù)的情況下，倍分最小段內(nèi)存長和均分每段內(nèi)存長相等時，倍分的總內(nèi)存遠(yuǎn)遠(yuǎn)大于均分的。隨著每段內(nèi)存長的增大，均分線越來越陡峭，要趕上差分線和倍分線的變化趨勢時，每段內(nèi)存長要很大，而且段長比較單一，體現(xiàn)不出漸進(jìn)式的變化，對變臟率比較大的小段內(nèi)存非常不利，不容易辨認(rèn)出小段內(nèi)存中內(nèi)存頁具體是發(fā)送前變臟還是發(fā)送后變臟的。

最后圖7的中間3條實(shí)線也繪制了最小內(nèi)存段長分別為1單位、2單位和3單位，公差為2單位的3條差分線。而且這3條差分線靠的比較緊湊，變化趨勢基本一致。差分相對于倍分還是比較穩(wěn)定的?？傮w上來說差分的最小段和倍分的最小段以及均分的每個段相等時，差分的內(nèi)存變化率處于中間的位置。

總之，大段均分容易冗余傳輸前變臟的內(nèi)存頁，小段均分又會增加計算時間拖延遷移。倍分時，隨著段數(shù)的增加相鄰兩段內(nèi)存的差距越來越大，變化的不平穩(wěn)。而差分的方式不僅可以平穩(wěn)較快地收斂，同時又能區(qū)分小段內(nèi)存的變化情況及不拖延遷移時間，是理想的段劃分策略。

接下來介紹差分的表示公式，設(shè)等差數(shù)列a1,a2,…,an前n項(xiàng)的和為Sn，公差為d。則Sn=An2+Bn，其中A=d/2，而B=a1-d/2。

在實(shí)際的運(yùn)算中應(yīng)當(dāng)使an是大于零的整數(shù)，同時使n的取值盡可能大，所以選取d=2，A=1，同時使n等于Sn的平方根后取整。并使St=n2，這樣的話，分成兩種情況：一是St=Sn，在這種情況下B=0,a1等于1；二是St不等于Sn，在這種情況下完全可以增加臨時變量C，同時求整使B=(Sn-St)/n，并求余使臨時變量C= (Sn-St)%n。且0<(Sn-St)<(2n+1)，因?yàn)楫?dāng)(Sn-St)=(2n+1)時，Sn= (n+1)2這與已知n等于Sn的平方根后取整是相互矛盾的，n不可能等于n+1。所以根據(jù)(Sn-St)的取值范圍，B只能取值0或1或2，而且C小于整數(shù)n。當(dāng)B=2時，C只能取0。當(dāng)B=0時，C不能為0，如果為0實(shí)際上就是上述第一種情況了?？傊?dāng)C不等于0時，說明在等差數(shù)列的基礎(chǔ)上增加一個元素C而已。再把臨時變量C按其值的大小順序插入等差數(shù)列a1，a2，…,an中。以上就是等差劃分的計算公式。內(nèi)存經(jīng)過這樣的等差劃分成段以后，內(nèi)存變臟的情況就可以在每個定位點(diǎn)被截取。

3.2 等差劃分整體流程

對于第一輪每個位置上的內(nèi)存頁來說，存在著變臟率和傳輸后的延遲時間兩個要素，而變臟率越大則其再次變臟的幾率也越大，同時傳輸后的延遲時間越長則其再次變臟的幾率也越大。而變臟率和變臟的次數(shù)又是緊密相連的[9]，如果把一個內(nèi)存頁變臟的次數(shù)看成高度，延遲的時間看成長度，就能得到一個幾何抽象。

圖8 變臟次數(shù)與延遲時間

從圖8的幾何抽象中可以看出：第一位置傳輸?shù)膬?nèi)存頁的延遲時間最長為3單位，第二位置為2單位，第三位置為1單位。同時把變臟次數(shù)不同的三個內(nèi)存頁分別放在不同的位置，總共有六種放法：

對<1>: 長度A(3, 2, 1)·高度B(1 2 3)= 10。

對<2>: 長度A(3, 2,1)·高度B(1 3 2)= 11。

對<3>: 長度A(3, 2, 1)·高度B(2 1 3)= 11。

對<4>: 長度A(3, 2, 1)·高度B(2 3 1)= 13。

對<5>: 長度A(3, 2, 1)·高度B(3 1 2)= 13。

對<6>: 長度A(3, 2, 1)·高度B(3 2 1)= 14。

從所做的數(shù)量積計算結(jié)果來看：應(yīng)該避免延遲時間和變臟次數(shù)兩個要素當(dāng)中大的數(shù)值相遇，從而減少內(nèi)存頁傳輸后再次變臟的機(jī)會。

采用增加預(yù)處理階段的方式，并統(tǒng)計預(yù)處理階段內(nèi)存頁變臟的次數(shù)，使第一輪傳輸?shù)膬?nèi)存頁按照預(yù)處理階段統(tǒng)計的變臟次數(shù)由低到高的順序傳輸，就可以減少后拷貝階段變臟的內(nèi)存頁數(shù)目。

具體地，統(tǒng)計變臟次數(shù)也是配合了在第一輪所進(jìn)行的等差劃分。在預(yù)處理階段，根據(jù)全部內(nèi)存的等差劃分情況，每隔一段時間記錄一次全部內(nèi)存頁變臟的情況，間隔的時間也是等差劃分的。相同間隔的情況下，每次記錄的變臟的內(nèi)存頁個數(shù)差不多，而等差間隔的情況下，每次記錄的變臟的內(nèi)存頁個數(shù)一般不同，從而有利于根據(jù)變臟次數(shù)的高低而按序傳輸。時間復(fù)雜度為O(n)的計數(shù)排序的方法用于排序內(nèi)存頁以節(jié)省時間。預(yù)處理階段基本時間是固定的，然后以這個基本時間和每個內(nèi)存段長的乘積作為一次間隔時間。

經(jīng)過等差劃分以后，每個定位點(diǎn)記錄了內(nèi)存頁在每段傳輸時間內(nèi)的變臟情況，所以在虛擬機(jī)暫停以前可以同步一次內(nèi)存位圖，這樣就形成了事實(shí)上分兩次同步內(nèi)存位圖的情形。第一次同步內(nèi)存位圖在虛擬機(jī)暫停之前，是從起始點(diǎn)到最后一個定位點(diǎn)這段時間相對于傳輸點(diǎn)來說變臟情況的內(nèi)存位圖。而第二次同步內(nèi)存位圖是發(fā)生在虛擬機(jī)暫停后，是從最后一個定位點(diǎn)到虛擬機(jī)暫停后這段時間內(nèi)存變臟情況的位圖。這樣第二次同步內(nèi)存位圖時，由于變臟位的減少，目標(biāo)端設(shè)置缺頁的行為減少，從而可以減少虛擬機(jī)暫停后同步內(nèi)存位圖的時間。

所以基于等差劃分的虛擬機(jī)實(shí)時遷移機(jī)制實(shí)際形成了圖9所示的流程，接下來將給出具體算法。

圖9 整體流程

3.3 等差劃分整體算法

經(jīng)過上面的分析討論之后，具體的算法由表1給出。

表1 基于等差劃分的整體算法

} 發(fā)送D[n]位置內(nèi)存頁； }for(m=0；m

具體實(shí)現(xiàn)過程中，為了真實(shí)地展示等差劃分算法的實(shí)際效力，在混合內(nèi)存復(fù)制的第一輪，任何的優(yōu)化措施都沒有被采用，即使是全零頁面，也是原原本本地發(fā)送過去，沒有進(jìn)行壓縮。只是在第二輪采用了預(yù)取頁和類似定時推送的優(yōu)化機(jī)制。同時算法把預(yù)處理階段的基本時間utime取值為100μs。太大的話，會增加總遷移時間，太小又不能產(chǎn)生效果。

4 試驗(yàn)及分析

為了驗(yàn)證等差劃分算法的有效性，在64位操作系統(tǒng)Centos-6.4和Linux3.0.0內(nèi)核以及Xen-4.1.2虛擬化平臺上實(shí)現(xiàn)了該算法，并與混合內(nèi)存拷貝方式進(jìn)行了比較。每一個試驗(yàn)結(jié)果取3次試驗(yàn)的均值。

4.1 試驗(yàn)環(huán)境

目標(biāo)主機(jī)和源主機(jī)是同一種機(jī)型，均為聯(lián)想啟天M4300，其 CPU 類型都為 Intel(R) Core(TM) i3-2120 @ 3.30GHz，內(nèi)存大小4GB。兩臺主機(jī)由一臺百兆24口的TP-LINK交換機(jī)連接。同時利用 NFS 服務(wù)把存在于目標(biāo)主機(jī)上的虛擬機(jī)磁盤映像共享給源主機(jī)?？蛻籼摂M機(jī)運(yùn)行Ubuntu-9.04操作系統(tǒng)，同時保持每個物理主機(jī)最多只有一個虛擬機(jī)運(yùn)行，并更改了Xen-4.1.2虛擬化平臺上內(nèi)存遷移的批次大小，由256個內(nèi)存頁取代原來的1024設(shè)置。

4.2 工作負(fù)載

試驗(yàn)中為了驗(yàn)證等差劃分算法的有效性，選用了五種不同類型的工作負(fù)載：

(1)Idle:沒有特別的應(yīng)用程序在其上面運(yùn)行，這個場景被用做比較參考，代表空閑類型應(yīng)用。

(2)Nbench：這是一款用來對CPU, FPU和內(nèi)存系統(tǒng)進(jìn)行性能測試的工具。其本身是單進(jìn)程的，試驗(yàn)中shell腳本被編寫為用來同時循環(huán)運(yùn)行50個Nbench的基準(zhǔn)測試程序，同時為了避免長時間集中于某一項(xiàng)測試，控制某一項(xiàng)測試最少運(yùn)行時間的MINIMUM_SECONDS參數(shù)由5秒被調(diào)減為1秒。

(3)Sysbench：該性能測試工具可以執(zhí)行CPU、內(nèi)存、數(shù)據(jù)庫等方面的性能測試。試驗(yàn)中配置參數(shù)—test=memory來執(zhí)行內(nèi)存測試，線程數(shù)為10個，每個塊大小為256MB，總傳輸數(shù)據(jù)量為5GB。

(4)Webbench：這是一款網(wǎng)站壓力測試軟件，它能夠模擬http請求。目標(biāo)主機(jī)配置Tomcat服務(wù)器和一個50KB 的靜態(tài)網(wǎng)頁，同時虛擬機(jī)并發(fā)運(yùn)行10個Webbench客戶請求該網(wǎng)頁。

(5)Dbench：該軟件能夠產(chǎn)生輸入和輸出負(fù)載給一個文件系統(tǒng)施加壓力，試驗(yàn)中5個客戶進(jìn)程被配置用來產(chǎn)生負(fù)載。

測試中虛擬機(jī)被分配了512MB內(nèi)存，并配置了一個VCPU，同時虛擬機(jī)在源端運(yùn)行時的相關(guān)工作負(fù)載參數(shù)也被測試出來，具體如表2所示。

表2 各負(fù)載參數(shù)

對于Idle場景來說，沒有必要測量，而其它場景都是在Idle場景的基礎(chǔ)上運(yùn)行了特別的應(yīng)用。對于CPU和內(nèi)存的測試，利用了虛擬機(jī)操作系統(tǒng)自帶的top工具，而對于網(wǎng)絡(luò)速率和磁盤的性能則采用了iftop和iotop工具進(jìn)行觀測。從CPU角度來看，大部分情況下，Nbench負(fù)載單進(jìn)程時就可以占用95%至100%，而其它工作負(fù)載單進(jìn)程時都沒能達(dá)到90%，所以Nbench可以代表CPU密集型應(yīng)用；從網(wǎng)絡(luò)流量的角度來看，只有Webbench這一工作負(fù)載有網(wǎng)絡(luò)流量，而且網(wǎng)速主要集中在每秒60MB至80MB之間，其余場景基本為0，所以Webbench可以代表通信密集型應(yīng)用；從磁盤角度來看，只有Dbench場景對磁盤有讀寫操作，而且大部分時間達(dá)到了每秒5MB至20MB的速率，其余工作負(fù)載幾乎為0，所以Dbench可以代表磁盤密集型應(yīng)用；從內(nèi)存的角度來看，Sysbech負(fù)載的內(nèi)存利用率最高，大部分情況下達(dá)到了50%到55%，而其它工作負(fù)載的利用率遠(yuǎn)低于Sysbench,所以Sysbench負(fù)載可以代表內(nèi)存密集型應(yīng)用。

4.3 工作負(fù)載測試

在這一部分，介紹了各種工作負(fù)載的測試，并比較了混合內(nèi)存拷貝方式和本文提出的基于等差劃分的虛擬機(jī)實(shí)時遷移技術(shù)兩者的總遷移時間等參數(shù)，順帶也測試了3.1小節(jié)圖7中所描述的系數(shù)k為1的倍分(TM)和系數(shù)k為2的均分(EQ)的情況用作比較，混合內(nèi)存拷貝方式可以用Hybrid來指代，而等差劃分技術(shù)可以用DED來指代。

圖10給出了各種算法在不同工作負(fù)載情況下后拷貝方式傳輸?shù)膬?nèi)存頁數(shù)量情況。從圖中的數(shù)據(jù)可以看到：與混合內(nèi)存拷貝方式相比，等差劃分的方法使Idle場景減少36%，Nbench場景減少36%，Dbench場景減少10.7%，Webbench場景減少57.8%，Sysbench場景減少2.4%，平均而言減少29%。同時由于均分方式增加了第一輪的時延，很多場景下出現(xiàn)了后拷貝傳輸?shù)膬?nèi)存頁高于混合拷貝方式的情形，倍分方式由于測量數(shù)據(jù)的不穩(wěn)定性等因素也出現(xiàn)了和均分方式相同的狀況，但出現(xiàn)的幾率明顯小于均分的，而差分方式則沒有出現(xiàn)這種狀況。還要說明的是等差劃分的方法只是減少了第二輪傳輸?shù)膬?nèi)存頁數(shù)，而幾種算法第一輪預(yù)拷貝方式傳輸?shù)膬?nèi)存頁數(shù)目是相等的，都是把全部內(nèi)存發(fā)送了一遍。

圖10 后拷貝方式傳輸內(nèi)存頁數(shù)

在xen-4.1.2虛擬化平臺上，虛擬機(jī)在源主機(jī)上執(zhí)行暫停操作時，其暫停時間不固定，有一定的變化范圍，而且暫停時間遠(yuǎn)大于同步內(nèi)存位圖的時間，所以遷移時的停機(jī)時間不能準(zhǔn)確反映出同步內(nèi)存位圖的時間變化，鑒于此，在具體的試驗(yàn)中，只是截取了虛擬機(jī)在源主機(jī)上暫停后到虛擬機(jī)在目標(biāo)主機(jī)上重啟前同步內(nèi)存位圖所需要的時間。從圖11中可以看出，對于不同負(fù)載來說，同步內(nèi)存位圖的時間和后拷貝方式內(nèi)存頁的數(shù)目變化趨勢不一樣，并不是后拷貝內(nèi)存頁數(shù)目越多，同步內(nèi)存位圖的時間就越長，而是隨著負(fù)載類型的不同而有所不同；但是對于同一負(fù)載來說，后拷貝方式內(nèi)存頁數(shù)目的下降，會帶來同步內(nèi)存位圖時間的下降。與混合內(nèi)存拷貝方式相比，等差劃分的方法使Idle場景減少23.1%，Nbench場景減少31%，Dbench場景減少28%，Webbench場景減少23%，Sysbench場景減少22%，平均而言減少25%。而且倍分和差分的情景，也都出現(xiàn)了下降的趨勢，不受后拷貝方式發(fā)送的內(nèi)存頁數(shù)量的影響，可見分兩次同步內(nèi)存位圖的方法在減少虛擬機(jī)暫停后同步內(nèi)存位圖的時間的這個問題上起到了關(guān)鍵性的作用。

圖11 同步內(nèi)存位圖時間

圖12對比了總遷移時間。等差劃分的方法使Idle場景減少0.3%，Nbench場景減少1%，Dbench場景減少4%，Webbench場景減少5%，Sysbench場景減少0.7%，平均而言減少2.2%。盡管等差劃分的方法使第二輪傳輸?shù)膬?nèi)存頁數(shù)目有所減少，但第二輪發(fā)送的內(nèi)存頁數(shù)目只占全部內(nèi)存很少部分，而且又增加了預(yù)處理階段，并使算法延遲。所以總遷移時間計算下來，改進(jìn)的比例不是很高。而均分的方法，由于第一輪分的段數(shù)過多，明顯增加了總遷移時間，而倍分的方法基本和混合方式持平?？梢姴捎貌罘址绞竭€是有一定積極作用的。

圖12 總遷移時間

另外改變Sysbench場景——memory-total-size參數(shù)可以調(diào)整內(nèi)存數(shù)據(jù)傳輸量，利用這一特性測量了不同遷移方法對系統(tǒng)和應(yīng)用性能的影響見圖13，在完成不同數(shù)據(jù)傳輸量的任務(wù)時，非遷移的狀況下用時最短。而遷移的情況下，完成相同的任務(wù)量，所用時間有所增加。不同的遷移方法影響的程度也是不同的。

圖13 不同任務(wù)完成時間

四種不同的任務(wù)下，混合內(nèi)存復(fù)制方式分別損失6%，29%，23%和19%。而等差劃分方式下性能損失14%，32%，26%和23%，略高于前者。等差劃分的方法比單純的采用混合內(nèi)存復(fù)制方式造成了更大的系統(tǒng)和應(yīng)用性能損耗。

4.4 不同內(nèi)存測試

實(shí)際使用的虛擬機(jī)，內(nèi)存大小是不盡相同的，為此增加了256MB，1024MB和2048MB的內(nèi)存進(jìn)行測試。以觀察基于等差劃分的方法在不同內(nèi)存中的表現(xiàn)。并選用了Dbench場景作為工作負(fù)載。圖14～圖16給出了試驗(yàn)結(jié)果。

對于同一個應(yīng)用場景，當(dāng)內(nèi)存的大小發(fā)生變化時，后拷貝方式傳送的內(nèi)存頁也發(fā)生一定的變化，但兩種算法的變化趨勢一致，混合內(nèi)存拷貝方式增加時，等差劃分的方式也增加，減少時也相應(yīng)減少。從256MB到2048MB內(nèi)存，依次減小的比例分別為12%，11%，33%和43%。

從上圖中可以看出，同步內(nèi)存位圖的時間隨著內(nèi)存的增加而增加，并不是隨著第二輪傳輸?shù)膬?nèi)存頁數(shù)目的變化而發(fā)生改變。兩種算法的變化都有增加的趨勢。從256MB到2048MB依次減少的比例為40%，28%，43%和29%。只有2048MB內(nèi)存時，同步內(nèi)存位圖的時間減少的比列小于第二輪減少的內(nèi)存頁的比例，其余三種情況均大于。這說明傳輸內(nèi)存位圖時間與設(shè)置內(nèi)存缺頁時間的比例隨著內(nèi)存的增加，有增大的趨勢。

圖14 后拷貝方式內(nèi)存頁數(shù)

圖15 同步內(nèi)存位圖時間

圖16 總遷移時間

對于總遷移時間而言，隨著內(nèi)存的增加，兩種算法都呈現(xiàn)出上升的趨勢，從256MB到2048MB內(nèi)存，基于等差劃分遷移技術(shù)改進(jìn)的比例依次為4%，4%，5%和5%呈基本相同的態(tài)勢。可見第一輪同步全部內(nèi)存頁的時間占總遷移時間的比例很大。

5 結(jié) 論

虛擬機(jī)實(shí)時遷移技術(shù)是虛擬化領(lǐng)域的研究熱點(diǎn)之一。本文對虛擬機(jī)實(shí)時遷移中的混合內(nèi)存方式進(jìn)行了改進(jìn)，在同步整個內(nèi)存頁階段，按照等差數(shù)列的形式對整個內(nèi)存頁劃分了不同的段，提出了基于等差劃分的虛擬機(jī)實(shí)時遷移技術(shù)。同時為了配合等差劃分這種技術(shù)，又安排了計數(shù)排序的預(yù)處理階段，和分批次同步變臟的內(nèi)存頁位圖技術(shù)。試驗(yàn)結(jié)果表明，在不同工作負(fù)載的情況下，基于等差劃分的虛擬機(jī)實(shí)時遷移技術(shù)可以減少后拷貝階段傳輸?shù)膬?nèi)存頁的數(shù)量，同時帶動總遷移時間和同步位圖時間的減小。與混合內(nèi)存方式相比，最好的情況下可以使總遷移時間減少5%上下，同時使同步位圖時間減少31%左右，使后拷貝階段傳輸?shù)膬?nèi)存頁減少58%?；诘炔顒澐值奶摂M機(jī)實(shí)時遷移技術(shù)適用于不同的內(nèi)存，對于不同內(nèi)存下的同一負(fù)載，總遷移時間，同步內(nèi)存位圖時間和第二輪傳輸?shù)膬?nèi)存頁數(shù)目都有所改進(jìn)。后續(xù)工作中，將著重研究多虛擬機(jī)實(shí)時遷移中存在的問題，因?yàn)樵谀承┉h(huán)境下有些虛擬機(jī)彼此關(guān)聯(lián)，需要同時被遷移。

[1] Clark C, Fraser K, Hand S, et al. Live migration of virtual machines.NetworkedSystemsDesign&Implementation(NSDI), 2005, 2:273-286

[2] Theimer M M, Lantz K A, Cheriton D R. Preemptable remote execution facilities for the V-system.ACMSigopsOperatingSystemsReview,1985, 19(5):2-12

[3] Jin H, Deng L, Wu S. Live virtual machine migration with adaptive memory compression. In: Proceedings of the IEEE International Conference on Cluster Computing and Workshops, New Orleans, USA, 2009.1-10

[4] Zhang X, Huo Z G, Ma J, et al. Exploiting data deduplication to accelerate live virtual machine migration. In: Proceedings of the IEEE International Conference on Cluster Computing, Heraklion, Greece , 2010. 88-96

[5] Svard P, Hudzia B, Tordsson J, et al. Evaluation of delta compression techniques for efficient live migration of large virtual machines.Virtualexecutionenvironments(VEE), 2011, 46(7):111-120

[6] Ma Y Q, Wang H B, Dong J K, et al. ME2: efficient live migration of virtual machine with memory exploration and encoding. In: Proceedings of the IEEE International Conference on Cluster Computing, Beijing, China, 2012. 610-613

[7] Du Y Y, Yu H L, Shi G Y, et al. Microwiper: efficient memory propagation in live migration of virtual machines. In: Proceedings of the 39th International Conference on Parallel Processing, San Diego, USA, 2010. 141-149

[8] Sv?rd P, Tordsson J, Hudzia B,et al.High performance live migration through dynamic page transfer reordering and compression. In: Proceedings of the 3rd IEEE International Conference on Cloud Computing Technology and Science (CloudCom), Athens, Greece, 2011. 542-548

[9] Zou Q X, Hao Z Y, Cui X, et al. Counting sort for the live migration of virtual machine. In: Proceedings of the IEEE International Conference on Cluster Computing (CLUSTER), Indianapolis, USA, 2013. 1-5

[10] Adel A, Kamran Z. Improving the time of live migration virtual machine by optimized algorithm scheduler credit. In: Proceedings of the 4th International Conference on Computer and Knowledge Engineering (ICCKE), Mashhad, Iran, 2014. 346-351

[11] Liu Z B, Qu W Y, Liu W J, et al. Xen live migration with slowdown scheduling algorithm. In: Proceedings of the International Conference on Parallel and Distributed Computing, Ap-plications and Technologies (PDCAT), Wuhan, China, 2010. 215-221

[12] Jin H, Gao W, Wu S, et al. Optimizing the live migration of virtual machine by CPU scheduling.JournalofNetworkandComputerApplications. 2011, 34(4):1088-1096

[13] Hines M R, Deshpande U,Gopalan K. Post-copy live migration of virtual machines.ACMSigopsOperatingSystemsReview, 2009, 43(3):14-26

[14] 陳陽，懷進(jìn)鵬，胡春明. 基于內(nèi)存混合復(fù)制方式的虛擬機(jī)在線遷移機(jī)制. 計算機(jī)學(xué)報，2011， 34(12)：2278-2291

[15] Kashyap S, Dhillon J S, Purini S. RLC - A reliable approach to fast and efficient live migration of virtual machines in the clouds. In: Proceedings of the IEEE 7th International Conference on Cloud Computing (CLOUD), Anchorage, USA, 2014. 360-367

[16] Hu L, Zhao J, Xu G C, et al. HMDC: live virtual machine migration based on hybrid memory copy and delta compression.AppliedMathematics&InformationSciences(CLOUD), 2013,7(2L): 639-646

[17] Sahni S, Varma V. A hybrid approach to live migration of virtual machines. In: Proceedings of the IEEE International Conference on Cloud Computing in Emerging Markets (CCEM), Bangalore, India, 2012. 1-5

[18] Liu H K, Jin H, Liao X F, et al. Live migration of virtual machine based on full system trace and replay. In: Proceedings of the 18th ACM international Symposium on High Performance Distributed Computing (HPDC), Garching, Germany, 2009. 101-110

[19] Chanchio K, Thaenkaew P. Time-bound, thread-based live migration of virtual machines. In: Proceedings of the 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), Chicago, USA, 2014. 364-373

Division of arithmetic progression for virtual machines’ live migration

Zou Qingxin******, Hao Zhiyu***, Yun Xiaochun****， Wang Chonghua*****

(*Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)(**University of Chinese Academy of Sciences, Beijing 100049)(***Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093)

The live migration of virtual machines was studied. The performances of the pre-copy algorithm, the post-copy algorithm and the hybrid-copy algorithm for memory migration in local area networks were analyzed, and then, on the basis of the improvement of the hybrid-copy algorithm, a technique for the live migration of virtual machines based on the division of arithmetic progression was presented. The technique divides the memory pages transmitted in the first round into many segments similar to the form of arithmetic progression, so the memory pages transmitted in the second round can be decreased. The experiments performed under different workloads showed that compared with the hybrid-copyalgorithm, the proposed technique reduced the time of synchronous memory bitmap by 25%, and decreased the pages of post-copy by 29% and the total migration time by 2.2% on average, improving and decreased the performance of virtual machines’ live migrationto some extent.

live migration, virtual machine, pre-copy, post-copy, hybrid-copy, division of arithmetic progression

10.3772/j.issn.1002-0470.2016.03.001

①國家自然科學(xué)基金(61003261)和國家科技支撐計劃(2012BAH46B02)資助項(xiàng)目。

，E-mail: haozhiyu@iie.ac.cn(

2015-10-20)

②男，1982年生，博士生；研究方向：虛擬化技術(shù)；E-mail: zouqingxin@nelmail.iie.ac.cn