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

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

0 概述

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

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

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

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

1 基于內存關聯分析的預拷貝遷移策略

1.1 高頻臟頁計算

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

1.2 高頻臟頁強關聯內存頁計算

通過統(tǒng)計內存修改的歷史數據來預測內存頁下一輪迭代變臟概率的方法,只能在時間相關性上對內存變臟的可能性進行分析。本文基于內存關聯分析的預拷貝遷移策略在預測內存頁變臟概率的基礎上,結合內存頁的空間相關性原理,統(tǒng)計內存修改的歷史數據,并提出Memory_cor算法用于分析內存頁之間的關聯性,從而減少內存頁反復傳輸的現象。

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

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

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

2)以內存頁修改次數的頻繁2-項集為輸入,計算高頻臟頁的強關聯內存頁。

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

{Mn}=>{Mm}

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

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

TCalcn

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

算法1Memory_cor算法

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

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

1.for all memory m∈danger_table0 do

2./*找出L2中所有包含內存頁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ī)則加入danger_table*/

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

11.end if

12.end for

13.end if

14.end for

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

1.3 預拷貝遷移策略實現

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

表1 內存頁表類型Table 1 Types of memory page tables

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

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

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

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

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

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

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

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

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

步驟7更新dirty_table0并將新出現的臟頁添加到內存頁表skip_table中。

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

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

2 實驗結果與分析

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

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

圖2 實驗環(huán)境

2.2 結果分析

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

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

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

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

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

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

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

圖4所示為中負載場景下2種策略的總遷移時間和停機時間對比,從圖4可以看出,相比現有Xen遷移策略,本文優(yōu)化策略在虛擬機內存大小為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%的停機時間。這是由于在中負載情況下,內存頁被頻繁改寫,優(yōu)化策略能夠有效抑制內存頁反復傳輸的現象,時間優(yōu)化效果較為明顯。

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

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

圖5所示為高負載場景下2種策略的總遷移時間和停機時間對比,從圖5可以看出,相比現有的Xen遷移策略,預拷貝遷移優(yōu)化策略在虛擬機內存大小為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%的停機時間。由于高負載下內存臟頁反復傳輸的問題嚴重,而優(yōu)化策略能夠大幅減少臟頁反復傳輸的現象,使預拷貝傳輸更快收斂,因此,其總遷移時間和停機時間更短。

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

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

3 結束語

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