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

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

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

0 概述

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

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

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

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

1.1 高頻臟頁計(jì)算

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

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

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

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

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

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

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

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

{Mn}=>{Mm}

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

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

TCalcn

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

算法1Memory_cor算法

輸入二階頻繁項(xiàng)集L2,臟頁表danger_table0

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

1.for all memory m∈danger_table0 do

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

3.Ct= findfreitem(m,L2);

4.if Ct≠φ then

5./*對(duì)所有包含m的項(xiàng)集,計(jì)算{m}=>{t-m}置信度*/

6.for all itemsets t∈Ctdo

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

8.if confidence≥minconfidence then

9./*將該強(qiáng)關(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)存頁歷史修改記錄計(jì)算修改次數(shù)的頻繁2-項(xiàng)集,對(duì)于本輪臟頁表中的每一個(gè)高頻臟頁,判斷是否存在包含該臟頁的頻繁2-項(xiàng)集,若不存在,則判斷下一個(gè);若存在,則計(jì)算該頻繁2-項(xiàng)集中此高頻臟頁與其他內(nèi)存頁之間的置信度,置信度大于等于最小置信度閾值表示該高頻臟頁與其他內(nèi)存頁之間存在強(qiáng)關(guān)聯(lián)關(guān)系,記錄此強(qiáng)關(guān)聯(lián)規(guī)則和強(qiáng)關(guān)聯(lián)內(nèi)存頁,一直遍歷本輪臟頁表直至為空。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)環(huán)境搭建

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

圖2 實(shí)驗(yàn)環(huán)境

2.2 結(jié)果分析

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

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

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

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

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

圖3 空載場(chǎng)景下2種策略的總遷移時(shí)間與停機(jī)時(shí)間對(duì)比

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

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

圖4 中負(fù)載場(chǎng)景下2種策略的總遷移時(shí)間與停機(jī)時(shí)間對(duì)比

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

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

圖5 高負(fù)載場(chǎng)景下2種策略的總遷移時(shí)間與停機(jī)時(shí)間對(duì)比

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