張宏偉,李曉歡,李春海,姚榮彬,唐 欣

(桂林電子科技大學(xué) a.信息與通信學(xué)院; b.信息科技學(xué)院,廣西 桂林 541004)

0 概述

動態(tài)遷移技術(shù)是云計算虛擬化技術(shù)中的關(guān)鍵部分[1],其可將正在運行的虛擬機或容器從一臺物理機遷移至另一臺物理機,而服務(wù)程序沒有中斷或中斷時間極短。目前,主流的動態(tài)遷移技術(shù)有內(nèi)存預(yù)拷貝遷移[2]、內(nèi)存后拷貝遷移[3]、內(nèi)存混合復(fù)制遷移[4]和基于日志的跟蹤重現(xiàn)遷移[5]等。其中,預(yù)拷貝遷移是動態(tài)遷移中的主流技術(shù)。但是,現(xiàn)有預(yù)拷貝遷移算法中的迭代過程存在重復(fù)拷貝同一個內(nèi)存頁的情況,導(dǎo)致拷貝內(nèi)存頁數(shù)量增加以及總遷移時間延長。

基于內(nèi)存壓縮的預(yù)拷貝遷移優(yōu)化方法是解決上述問題的常見方案之一。文獻[6]使用游程編碼(RLE)壓縮技術(shù)來減少遷移期間傳輸?shù)捻撁鏀?shù),由于在遷移期間轉(zhuǎn)移的總遷移數(shù)據(jù)量減少,導(dǎo)致總遷移時間和停機時間縮短。文獻[7]通過delta應(yīng)用壓縮遷移過程中由源主機生成的臟頁,以提高遷移吞吐量并縮短停機時間,其有效減少了總遷移數(shù)據(jù)量和總遷移時間。此外,控制內(nèi)存臟頁產(chǎn)生速率的預(yù)拷貝遷移優(yōu)化方法同樣能取得較好的效果。文獻[8]提出了一種使用CPU調(diào)度來控制內(nèi)存臟頁率的方法,當(dāng)虛擬機內(nèi)存寫入速度較快時,虛擬機CPU處理速度將減慢,該方法通過降低臟內(nèi)存產(chǎn)生速率使臟頁率降低至可接受的值,其能夠縮短總遷移時間和停機時間,然而,通過犧牲計算能力來減少臟內(nèi)存會導(dǎo)致應(yīng)用程序性能下降,影響用戶體驗。雖然上述方法通過對內(nèi)存頁進行壓縮或降低內(nèi)存的臟頁產(chǎn)生速率來降低遷移總時間和總數(shù)據(jù)量,但仍未完全解決多次迭代重復(fù)拷貝臟內(nèi)存頁的問題。

為解決現(xiàn)有預(yù)拷貝遷移算法中存在的重復(fù)拷貝內(nèi)存頁問題,改變內(nèi)存?zhèn)鬏旐樞虻念A(yù)拷貝遷移優(yōu)化方法應(yīng)運而生。文獻[9]提出了一種動態(tài)調(diào)整內(nèi)存頁面?zhèn)鬏旐樞虻姆椒?其通過對頁面更新頻率進行采樣,優(yōu)先傳輸更新頻率較低的頁面,這種動態(tài)調(diào)整內(nèi)存頁傳輸順序的方法能有效降低內(nèi)存臟頁的重傳次數(shù)。文獻[10]提出了一種基于重用距離的預(yù)測方法,該方法采用重用距離的概念對頻繁更新的頁面進行跟蹤,在此基礎(chǔ)上,決策是否將該頁面保存到最后進行迭代,以減少相同頁面的重復(fù)傳輸次數(shù)。文獻[11]提出了一種快速的臟頁預(yù)測預(yù)拷貝方法,其對內(nèi)存頁狀態(tài)改變的概率進行測算,并推遲狀態(tài)頻繁變化頁面的傳輸,達到優(yōu)化虛擬機實時遷移的目的。文獻[12]通過動態(tài)指數(shù)平滑法來預(yù)測下一輪的臟頁,有效地減少了遷移數(shù)據(jù)總量和總時間。文獻[13]針對內(nèi)存預(yù)拷貝過程中內(nèi)存頁反復(fù)重傳的特征,考慮時間相關(guān)性,引入馬爾科夫預(yù)測模型,改進現(xiàn)有的內(nèi)存動態(tài)遷移機制,其利用臟頁的歷史操作訪問情況預(yù)測下一輪迭代被修改的概率,且只傳輸預(yù)測概率較低的內(nèi)存頁。然而,上述方法在計算臟頁概率時都只考慮時間相關(guān)性,沒有考慮到內(nèi)存之間的空間相關(guān)性。文獻[14]利用時間相關(guān)性計算頁面臟頁率,優(yōu)先發(fā)送臟頁率低的內(nèi)存頁,同時考慮到空間相關(guān)性,認為相鄰內(nèi)存頁或相鄰內(nèi)存頁的鄰居內(nèi)存頁也是臟頁,然后提高該相鄰內(nèi)存頁的臟頁率,但是,這種判斷相鄰內(nèi)存頁是否變臟的方式并不能完全準(zhǔn)確地反映內(nèi)存的空間相關(guān)性。

本文提出一種基于內(nèi)存關(guān)聯(lián)分析的預(yù)拷貝遷移策略,通過統(tǒng)計臟頁率來預(yù)測下一輪內(nèi)存頁變臟的概率,停止傳輸變臟概率高的內(nèi)存頁。在此基礎(chǔ)上,基于內(nèi)存的空間相關(guān)性,設(shè)計一種內(nèi)存關(guān)聯(lián)(Memory_cor)算法以計算內(nèi)存頁之間的強關(guān)聯(lián)規(guī)則,取消傳輸臟頁率高的內(nèi)存頁及其強關(guān)聯(lián)內(nèi)存頁,從而避免內(nèi)存臟頁反復(fù)傳輸?shù)默F(xiàn)象,縮短總遷移時間。

1 基于內(nèi)存關(guān)聯(lián)分析的預(yù)拷貝遷移策略

1.1 高頻臟頁計算

內(nèi)存的時間相關(guān)性是指:如果某個內(nèi)存頁在一定時間段內(nèi)重復(fù)改變,則該內(nèi)存頁不久之后很有可能再次被改變[15]。基于內(nèi)存關(guān)聯(lián)分析的預(yù)拷貝遷移策略利用內(nèi)存的時間相關(guān)性原理對內(nèi)存頁下一輪變臟概率進行預(yù)測。通過統(tǒng)計最近N輪的內(nèi)存變臟情況來計算臟頁率,利用臟頁率的大小對內(nèi)存下一輪變臟概率進行預(yù)測[16]。本文將臟頁率過高的內(nèi)存頁定義為高頻臟頁,對于高頻臟頁,本輪迭代將不傳輸,以抑制內(nèi)存頁反復(fù)傳輸?shù)默F(xiàn)象。臟頁率dp定義為:

1.2 高頻臟頁強關(guān)聯(lián)內(nèi)存頁計算

通過統(tǒng)計內(nèi)存修改的歷史數(shù)據(jù)來預(yù)測內(nèi)存頁下一輪迭代變臟概率的方法,只能在時間相關(guān)性上對內(nèi)存變臟的可能性進行分析。本文基于內(nèi)存關(guān)聯(lián)分析的預(yù)拷貝遷移策略在預(yù)測內(nèi)存頁變臟概率的基礎(chǔ)上,結(jié)合內(nèi)存頁的空間相關(guān)性原理,統(tǒng)計內(nèi)存修改的歷史數(shù)據(jù),并提出Memory_cor算法用于分析內(nèi)存頁之間的關(guān)聯(lián)性,從而減少內(nèi)存頁反復(fù)傳輸?shù)默F(xiàn)象。

內(nèi)存的空間相關(guān)性是指:在一輪迭代的時間內(nèi),2個內(nèi)存頁均被修改這一事件在預(yù)設(shè)的程度上呈現(xiàn)關(guān)聯(lián)關(guān)系,如內(nèi)存頁Mn的修改記錄為01010111(1表示被修改,0表示未修改),內(nèi)存頁Mm的修改記錄為01010101,2個內(nèi)存頁的修改記錄極其相似,則兩者之間可能存在空間相關(guān)性,這2個內(nèi)存頁有可能為強關(guān)聯(lián)內(nèi)存頁[17]。

本文Memory_cor算法對關(guān)聯(lián)分析中最基礎(chǔ)的Apriori算法[18]進行優(yōu)化和改進,使其適用于時延敏感的內(nèi)存關(guān)聯(lián)分析場景[19],其基本思想是計算變臟概率大的高頻臟頁的強關(guān)聯(lián)內(nèi)存頁。算法主要步驟為:

1)以所有內(nèi)存頁修改記錄為輸入,計算內(nèi)存頁修改次數(shù)的頻繁2-項集。

2)以內(nèi)存頁修改次數(shù)的頻繁2-項集為輸入,計算高頻臟頁的強關(guān)聯(lián)內(nèi)存頁。

Memory_cor算法用強關(guān)聯(lián)規(guī)則記錄所求強關(guān)聯(lián)內(nèi)存頁,強關(guān)聯(lián)規(guī)則的格式如下:

{Mn}=>{Mm}

其中,Mn和Mm分別表示第n號內(nèi)存頁和第m號內(nèi)存頁。強關(guān)聯(lián)規(guī)則表示Mn與Mm存在空間相關(guān)性,如果內(nèi)存頁Mn變臟概率大則Mm也有很大概率變臟。

基于內(nèi)存關(guān)聯(lián)分析的預(yù)拷貝遷移策略最大的時間開銷來源于計算高頻臟頁的強關(guān)聯(lián)規(guī)則,為使策略的優(yōu)化達到理想效果,強關(guān)聯(lián)規(guī)則的計算時間應(yīng)滿足:

TCalcn

其中,TCalc為計算單個高頻臟頁強關(guān)聯(lián)規(guī)則的時間開銷,n為高頻臟頁的數(shù)量,TTra為從源主機傳輸單個內(nèi)存頁至目的主機消耗的平均時間,m為強關(guān)聯(lián)內(nèi)存頁的數(shù)量。計算強關(guān)聯(lián)規(guī)則的時間開銷必須小于傳輸篩除的強關(guān)聯(lián)內(nèi)存頁的時間開銷,本文策略才能取得時間優(yōu)化的效果。通過分析可以發(fā)現(xiàn),TTra由網(wǎng)絡(luò)傳輸速率決定,而n和m由負載情況決定,TCalc則由Memory_cor算法決定。由于Memory_cor算法只計算Apriori算法中的頻繁2-項集,大幅降低了頻繁項集的數(shù)量,減少了計算單個高頻臟頁強關(guān)聯(lián)規(guī)則的時間開銷TCalc,從而提高了優(yōu)化策略的效率。Memory_cor算法偽代碼描述如下:

算法1Memory_cor算法

輸入二階頻繁項集L2,臟頁表danger_table0

輸出加入強關(guān)聯(lián)規(guī)則后的臟頁表danger_table

1.for all memory m∈danger_table0 do

2./*找出L2中所有包含內(nèi)存頁m的項集*/

3.Ct= findfreitem(m,L2);

4.if Ct≠φ then

5./*對所有包含m的項集,計算{m}=>{t-m}置信度*/

6.for all itemsets t∈Ctdo

7.confidence=support(t)/support(m);

8.if confidence≥minconfidence then

9./*將該強關(guān)聯(lián)規(guī)則加入danger_table*/

10.write({m}=>{t-m}) to danger_table;

11.end if

12.end for

13.end if

14.end for

依照Memory_cor算法,首先利用內(nèi)存頁歷史修改記錄計算修改次數(shù)的頻繁2-項集,對于本輪臟頁表中的每一個高頻臟頁,判斷是否存在包含該臟頁的頻繁2-項集,若不存在,則判斷下一個;若存在,則計算該頻繁2-項集中此高頻臟頁與其他內(nèi)存頁之間的置信度,置信度大于等于最小置信度閾值表示該高頻臟頁與其他內(nèi)存頁之間存在強關(guān)聯(lián)關(guān)系,記錄此強關(guān)聯(lián)規(guī)則和強關(guān)聯(lián)內(nèi)存頁,一直遍歷本輪臟頁表直至為空。

1.3 預(yù)拷貝遷移策略實現(xiàn)

基于內(nèi)存關(guān)聯(lián)分析的預(yù)拷貝遷移策略的基本思想是計算變臟概率大的高頻臟頁及其強關(guān)聯(lián)內(nèi)存頁,在本輪迭代不傳輸高頻臟頁及其對應(yīng)的強關(guān)聯(lián)內(nèi)存頁。為實現(xiàn)該策略,本文定義7個內(nèi)存頁表類型,如表1所示。

表1 內(nèi)存頁表類型Table 1 Types of memory page tables

基于內(nèi)存關(guān)聯(lián)分析的預(yù)拷貝遷移策略實現(xiàn)步驟如圖1所示,其中,Mx表示第x號內(nèi)存頁,1表示內(nèi)存頁變臟,0表示內(nèi)存頁未變臟,強關(guān)聯(lián)規(guī)則使用{Mn}=>{Mm}格式。

圖1 內(nèi)存遷移優(yōu)化策略框架

內(nèi)存遷移優(yōu)化策略具體步驟如下:

步驟1在預(yù)拷貝遷移階段每一輪迭代開始前,先更新一輪迭代時間內(nèi)的內(nèi)存訪問狀況,將每一輪的內(nèi)存臟頁記錄在history_table中。

步驟2判斷本輪迭代為第幾輪迭代傳輸,若為前3輪迭代傳輸,則按原有遷移策略執(zhí)行,跳過以下步驟,第4輪開始執(zhí)行本文的拷貝優(yōu)化策略。

步驟3更新dirty_table0,將dirty_table0復(fù)制至send_table,同時使用history_table結(jié)合dirty_table0計算出本輪臟頁的臟頁率,生成dirty_table。

步驟4對dirty_table進行篩選,將臟頁率大于判定閾值dmax的內(nèi)存頁放入danger_table0中,這些內(nèi)存頁被判定為高頻臟頁。

步驟5使用Memory_cor算法計算danger_table0中危險內(nèi)存頁的強關(guān)聯(lián)規(guī)則,將強關(guān)聯(lián)規(guī)則對應(yīng)的內(nèi)存頁寫入danger_table0中,生成danger_table。

步驟6融合danger_table中的強關(guān)聯(lián)規(guī)則,將danger_table中的高頻臟頁及其強關(guān)聯(lián)內(nèi)存頁均放入skip_table中。

步驟7更新dirty_table0并將新出現(xiàn)的臟頁添加到內(nèi)存頁表skip_table中。

步驟8比較send_table和skip_table,取消傳輸同時出現(xiàn)在2個表中的臟頁,傳輸send_table中剩余的頁,清空skip_table與send_table。

步驟9本輪迭代結(jié)束,判斷是否滿足停機拷貝條件,若滿足,則開始停機拷貝;若不滿足,則轉(zhuǎn)入下一輪迭代。

2 實驗結(jié)果與分析

2.1 實驗環(huán)境搭建

基于內(nèi)存關(guān)聯(lián)分析的預(yù)拷貝遷移策略實驗環(huán)境[20]如圖2所示,主機Host A和Host B均裝有Xubuntu14.04和Xen4.3.0,為驗證本文預(yù)拷貝遷移優(yōu)化策略的性能,主機A配置現(xiàn)有的Xen動態(tài)遷移策略,主機B配置基于內(nèi)存關(guān)聯(lián)分析的預(yù)拷貝遷移優(yōu)化策略,主機之間使用千兆以太網(wǎng)交換機連接,NFS服務(wù)器為主機提供NFS服務(wù)?；谔摂M化平臺創(chuàng)建內(nèi)存分別為256 MB、512 MB、1 024 MB、2 048 MB的Xen虛擬機,對不同內(nèi)存大小的虛擬機進行來回遷移并對比總遷移時間、停機時間,對每個數(shù)據(jù)均測量20次取平均值。通過對比現(xiàn)有遷移策略和本文預(yù)拷貝遷移策略在不同負載下的總遷移時間、停機時間,以驗證本文策略的性能優(yōu)勢。

圖2 實驗環(huán)境

2.2 結(jié)果分析

本文在不同負載下的主機A與主機B之間進行Xen虛擬機遷移,進而比較現(xiàn)有Xen動態(tài)遷移策略和本文遷移優(yōu)化策略的性能,實驗選擇3種應(yīng)用場景:

1)空載場景:空載場景下Xen虛擬機內(nèi)除系統(tǒng)自帶服務(wù)外不運行其他應(yīng)用。

2)中負載場景:在創(chuàng)建的Xen虛擬機內(nèi)使用Apache_kafka自帶的生產(chǎn)者與消費者性能測試腳本,在生產(chǎn)者吞吐量為4 000 Byte/s、消費者吞吐量為1 000 Byte/s的條件下進行測試。

3)高負載場景:在創(chuàng)建的Xen虛擬機內(nèi)使用make工程管理器4個線程編譯Linux-4.14.103內(nèi)核包。

圖3所示為空載場景下2種策略的總遷移時間和停機時間對比,從圖3可以看出,在空載場景下,2種策略的總遷移時間和停機時間相差不大,這是由于空載場景下臟頁反復(fù)變臟概率低,總變臟內(nèi)存頁數(shù)量少,因此,本文遷移略的時間優(yōu)化效果較小。

圖3 空載場景下2種策略的總遷移時間與停機時間對比

Fig.3 Comparison of total migration time and downtime of two strategies under no load circumstance

圖4所示為中負載場景下2種策略的總遷移時間和停機時間對比,從圖4可以看出,相比現(xiàn)有Xen遷移策略,本文優(yōu)化策略在虛擬機內(nèi)存大小為256 MB、512 MB、1 024 MB、2 048 MB的條件下,分別減少了9.0%、8.2%、8.3%、7.9%的總遷移時間和6.6%、7.5%、6.9%、6.2%的停機時間。這是由于在中負載情況下,內(nèi)存頁被頻繁改寫,優(yōu)化策略能夠有效抑制內(nèi)存頁反復(fù)傳輸?shù)默F(xiàn)象,時間優(yōu)化效果較為明顯。

圖4 中負載場景下2種策略的總遷移時間與停機時間對比

Fig.4 Comparison of total migration time and downtime of two strategies under medium load circumstance

圖5所示為高負載場景下2種策略的總遷移時間和停機時間對比,從圖5可以看出,相比現(xiàn)有的Xen遷移策略,預(yù)拷貝遷移優(yōu)化策略在虛擬機內(nèi)存大小為256 MB、512 MB、1 024 MB、2 048 MB的條件下,分別減少了11.0%、10.7%、9.7%、7.7%的總遷移時間和4.2%、7.6%、10.4%、11.7%的停機時間。由于高負載下內(nèi)存臟頁反復(fù)傳輸?shù)膯栴}嚴重,而優(yōu)化策略能夠大幅減少臟頁反復(fù)傳輸?shù)默F(xiàn)象,使預(yù)拷貝傳輸更快收斂,因此,其總遷移時間和停機時間更短。

圖5 高負載場景下2種策略的總遷移時間與停機時間對比

Fig.5 Comparison of total migration time and downtime of two strategies under high load circumstance

3 結(jié)束語

本文提出一種基于內(nèi)存關(guān)聯(lián)分析的預(yù)拷貝遷移優(yōu)化策略。依據(jù)臟頁率對下一輪的內(nèi)存頁變臟概率進行預(yù)測,停止傳輸變臟概率大的高頻臟頁,同時融入空間相關(guān)性原理,利用Memory_cor算法計算高頻臟頁的強關(guān)聯(lián)頁面并取消傳輸。實驗結(jié)果表明,該策略在總遷移時間、停機時間和迭代輪數(shù)上優(yōu)于現(xiàn)有的Xen動態(tài)遷移策略,其能夠提高預(yù)拷貝遷移性能。下一步將針對內(nèi)存頁關(guān)聯(lián)性強的特定場景,對Memory_cor算法的參數(shù)進行優(yōu)化,使內(nèi)存頁強關(guān)聯(lián)規(guī)則的計算時間更短,效率更高。