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

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

?

基于等差劃分的虛擬機實時遷移技術①

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

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

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

實時遷移， 虛擬機， 預拷貝， 后拷貝， 混合拷貝， 等差劃分

0 引 言

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

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

1 相關研究工作

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

圖1 預拷貝算法迭代過程

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

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

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

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

專門針對混合算法的改進工作也有相關的研究。文獻[15]增加了預學習階段，估計出變臟比較頻繁的內存頁，并辨認出工作集，從而在第一輪省去工作集的傳輸，而只在第二輪后拷貝階段傳輸，從而達到減少內存頁傳輸的目的，而且研究了后拷貝階段的安全性和可靠性。

文獻[16]的研究中，在停機階段發(fā)送緩存位圖和臟頁位圖兩種位圖，對于在兩個位圖中的頁面，采用壓縮后變量傳輸的方式，從而改進了混合方式的內存?zhèn)鬏敗?/p>

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

還有一些其它方式的遷移技術，例如文獻[18]基于日志采用檢查點/恢復和跟蹤/重放的技術，該技術類似于預拷貝算法，但傳輸的不是內存而是日志，因此數據傳輸量較小，但實現相對比較復雜。文獻[19]采用了兩個線程并行傳輸，第一個線程從頭至尾傳輸所有內存頁，同時另一個線程傳輸變臟的內存頁，當第一個線程遵循時間限制結束時，立刻進入停機階段。

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

2 混合內存復制方式

主流虛擬化平臺上均采用預拷貝算法作為虛擬機實時遷移的默認算法，然而當虛擬機上負載較高時，預拷貝算法往往達到最大輪數而失效。

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

圖2 混合內存復制方式

3 等差劃分算法設計

3.1 劃分成不同的段

對于混合內存拷貝方式來說，只重傳一次，且第一輪傳輸全部內存頁，而且第二輪采用后拷貝方式傳輸的內存頁是相對第一輪起始點變臟的內存頁，包括相對第一輪傳輸點未變臟的內存頁。這就會產生一種現象，即一個內存頁在起始點和傳輸點之間被更改時，盡管相對于起始點來說是變臟的，但是相對于傳輸點來說是沒有變臟的，對于這樣的內存頁，混合內存拷貝方式在后拷貝階段是要傳輸的。但實際上這樣的內存頁是不需要傳輸的，因為該內存頁在傳輸點以后沒有被更改，換句話說只有在傳輸點和結束點之間發(fā)生變化的內存頁才真正需要傳輸(圖3)。

圖3 起始點，結束點和傳輸點位置

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

圖4 第二輪三種內存頁面

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

圖5 第二輪三種頁面關系

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

圖6 起始點、結束點和定位點位置

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

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

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

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

圖7 段長選擇

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

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

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

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

在實際的運算中應當使an是大于零的整數，同時使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)，因為當(Sn-St)=(2n+1)時，Sn= (n+1)2這與已知n等于Sn的平方根后取整是相互矛盾的，n不可能等于n+1。所以根據(Sn-St)的取值范圍，B只能取值0或1或2，而且C小于整數n。當B=2時，C只能取0。當B=0時，C不能為0，如果為0實際上就是上述第一種情況了?？傊擟不等于0時，說明在等差數列的基礎上增加一個元素C而已。再把臨時變量C按其值的大小順序插入等差數列a1，a2，…,an中。以上就是等差劃分的計算公式。內存經過這樣的等差劃分成段以后，內存變臟的情況就可以在每個定位點被截取。

3.2 等差劃分整體流程

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

圖8 變臟次數與延遲時間

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

對<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。

從所做的數量積計算結果來看：應該避免延遲時間和變臟次數兩個要素當中大的數值相遇，從而減少內存頁傳輸后再次變臟的機會。

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

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

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

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

圖9 整體流程

3.3 等差劃分整體算法

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

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

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

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

4 試驗及分析

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

4.1 試驗環(huán)境

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

4.2 工作負載

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

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

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

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

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

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

測試中虛擬機被分配了512MB內存，并配置了一個VCPU，同時虛擬機在源端運行時的相關工作負載參數也被測試出來，具體如表2所示。

表2 各負載參數

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

4.3 工作負載測試

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

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

圖10 后拷貝方式傳輸內存頁數

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

圖11 同步內存位圖時間

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

圖12 總遷移時間

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

圖13 不同任務完成時間

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

4.4 不同內存測試

實際使用的虛擬機，內存大小是不盡相同的，為此增加了256MB，1024MB和2048MB的內存進行測試。以觀察基于等差劃分的方法在不同內存中的表現。并選用了Dbench場景作為工作負載。圖14～圖16給出了試驗結果。

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

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

圖14 后拷貝方式內存頁數

圖15 同步內存位圖時間

圖16 總遷移時間

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

5 結 論

虛擬機實時遷移技術是虛擬化領域的研究熱點之一。本文對虛擬機實時遷移中的混合內存方式進行了改進，在同步整個內存頁階段，按照等差數列的形式對整個內存頁劃分了不同的段，提出了基于等差劃分的虛擬機實時遷移技術。同時為了配合等差劃分這種技術，又安排了計數排序的預處理階段，和分批次同步變臟的內存頁位圖技術。試驗結果表明，在不同工作負載的情況下，基于等差劃分的虛擬機實時遷移技術可以減少后拷貝階段傳輸的內存頁的數量，同時帶動總遷移時間和同步位圖時間的減小。與混合內存方式相比，最好的情況下可以使總遷移時間減少5%上下，同時使同步位圖時間減少31%左右，使后拷貝階段傳輸的內存頁減少58%?；诘炔顒澐值奶摂M機實時遷移技術適用于不同的內存，對于不同內存下的同一負載，總遷移時間，同步內存位圖時間和第二輪傳輸的內存頁數目都有所改進。后續(xù)工作中，將著重研究多虛擬機實時遷移中存在的問題，因為在某些環(huá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] 陳陽，懷進鵬，胡春明. 基于內存混合復制方式的虛擬機在線遷移機制. 計算機學報，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

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

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

2015-10-20)

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