朱 鑫，蒲 衛(wèi)，秦秀磊，張文博，鐘 華

（1.中國(guó)科學(xué)院軟件研究所 軟件工程技術(shù)研究開(kāi)發(fā)中心，北京100190；2.中國(guó)科學(xué)院研究生院，北京100190；3.解放軍衛(wèi)生信息中心，北京100842）

0 引 言

作為一種新的基于互聯(lián)網(wǎng)的IT服務(wù)增值、使用和交付模式，云計(jì)算自產(chǎn)生以來(lái)就得到工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注，目前正變成商業(yè)上的現(xiàn)實(shí)［1］。云計(jì)算環(huán)境下，為了解決傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)的性能瓶頸，分布式緩存技術(shù)得到廣泛應(yīng)用，為用戶(hù)提供高性能、高可用、可伸縮的數(shù)據(jù)緩存服務(wù)。從云計(jì)算三層服務(wù)模式（基礎(chǔ)設(shè)施即服務(wù)（IaaS）、平臺(tái)即服務(wù)（PaaS）、軟件即服務(wù)（SaaS））的角度劃分，分布式緩存位于PaaS層，提供應(yīng)用加速與平臺(tái)的狀態(tài)維護(hù)服務(wù)。

由于應(yīng)用數(shù)據(jù)訪問(wèn)的不均衡性，緩存系統(tǒng)中往往存在若干熱點(diǎn)數(shù)據(jù)分區(qū)，包含較多熱點(diǎn)數(shù)據(jù)分區(qū)的節(jié)點(diǎn)負(fù)載較高，易達(dá)到性能瓶頸，而應(yīng)用訪問(wèn)模式的時(shí)變性也會(huì)導(dǎo)致熱點(diǎn)數(shù)據(jù)分區(qū)的分布隨時(shí)間而變化［2］。因此緩存系統(tǒng)需要定期地執(zhí)行數(shù)據(jù)重均衡操作，以保障數(shù)據(jù)和負(fù)載在各節(jié)點(diǎn)間均衡分布，最大化資源利用率，提升系統(tǒng)性能。

數(shù)據(jù)遷移過(guò)程中，緩存系統(tǒng)的性能會(huì)下降。如根據(jù)淘寶Tair［3］的遷移數(shù)據(jù)訪問(wèn)機(jī)制，對(duì)某些訪問(wèn)請(qǐng)求需要增加一次服務(wù)器轉(zhuǎn)發(fā)操作，導(dǎo)致系統(tǒng)的平均響應(yīng)時(shí)間增加。因此在制定數(shù)據(jù)重均衡方案時(shí)，應(yīng)盡量縮短遷移時(shí)間。

當(dāng)前主流的云平臺(tái)均使用虛擬化技術(shù)來(lái)屏蔽底層硬件的差異性及實(shí)現(xiàn)資源的快速部署。如亞馬遜的EC2和微軟的 Windows Azure分別使用了基于Xen［4］和基于 Hyper－V的虛擬化技術(shù)。對(duì)于部署在云平臺(tái)中的緩存系統(tǒng)而言，節(jié)點(diǎn)間的數(shù)據(jù)遷移會(huì)受到以下兩方面環(huán)境上下文的影響：

（1）遷移節(jié)點(diǎn)的物理位置：遷出節(jié)點(diǎn)（數(shù)據(jù)分區(qū)從其遷出的緩存服務(wù)器節(jié)點(diǎn)）和遷入節(jié)點(diǎn)（數(shù)據(jù)分區(qū)遷入的緩存服務(wù)器節(jié)點(diǎn)）所在的VM可能位于同一臺(tái)物理機(jī)，也可能位于不同的物理機(jī)。兩種情況下數(shù)據(jù)遷移的物理路徑有顯著差別，因而遷移速度不同。

（2）VM間性能干擾：由于VM間存在性能干擾，無(wú)論是同一物理機(jī)內(nèi)還是跨物理機(jī)的數(shù)據(jù)遷移的速度都會(huì)隨著物理機(jī)上部署的VM數(shù)量和運(yùn)行狀態(tài)的變化而變化。

本文在基于Xen虛擬化技術(shù)搭建的VM集群上部署分布式緩存系統(tǒng)，研究環(huán)境上下文對(duì)分布式緩存數(shù)據(jù)重均衡的影響，提出了一種上下文感知的分布式緩存數(shù)據(jù)重均衡方法。該方法由兩部分組成：①遷移時(shí)間預(yù)測(cè)模型。根據(jù)VM狀態(tài)預(yù)測(cè)物理機(jī)內(nèi)和物理機(jī)間遷移一定數(shù)據(jù)量所需的數(shù)據(jù)遷移時(shí)間，為數(shù)據(jù)重均衡方案的制定提供依據(jù)。②上下文感知的數(shù)據(jù)重均衡算法?；趯?duì)緩存數(shù)據(jù)分區(qū)數(shù)據(jù)量和網(wǎng)絡(luò)流量的細(xì)粒度監(jiān)測(cè)，該算法同時(shí)考慮緩存數(shù)據(jù)量均衡，網(wǎng)絡(luò)流量均衡和遷移時(shí)間較短這3個(gè)優(yōu)化目標(biāo)，以制定有效的數(shù)據(jù)重均衡方案。使用Yahoo公司的云存儲(chǔ)服務(wù)測(cè)試基準(zhǔn)YCSB［5］對(duì)上述方法進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果表明，該方法能夠準(zhǔn)確預(yù)測(cè)遷移時(shí)間，上下文感知的數(shù)據(jù)重均衡算法與傳統(tǒng)數(shù)據(jù)重均衡算法相比，能夠提供較好的均衡效果及較短的遷移時(shí)間。

本文的研究工作基于中科院軟件所自主研發(fā)的分布式緩存系統(tǒng)OnceDC［6］進(jìn)行。OnceDC采用類(lèi)似亞馬遜Dynamo［7］的分區(qū)機(jī)制，數(shù)據(jù)被存儲(chǔ)在分區(qū)中，單個(gè)緩存服務(wù)器節(jié)點(diǎn)（簡(jiǎn)稱(chēng)緩存節(jié)點(diǎn)）可包含多個(gè)分區(qū)。此外OnceDC采用緩存客戶(hù)端主動(dòng)路由及緩存集群管理器集中管理的方式。

1 研究動(dòng)機(jī)

1.1 Xen的I／O模型

在基于Xen的虛擬化體系結(jié)構(gòu)中，每個(gè)客戶(hù)操作系統(tǒng)都運(yùn)行在一個(gè)虛擬域（domain）中。其中，dom0是特權(quán)域，擁有原生設(shè)備驅(qū)動(dòng)，具有直接訪問(wèn)I／O設(shè)備的特權(quán)，并通過(guò)和Xen虛擬機(jī)控制器（virtual machine monitor，VMM）的交互來(lái)控制和管理其它的虛擬域（稱(chēng)為domU）。dom0向domU提供I／O設(shè)備模型和平臺(tái)，domU訪問(wèn)IO資源均需經(jīng)過(guò)dom0進(jìn)行。如圖1所示。

圖1中，假設(shè)dom1（準(zhǔn)確的講是對(duì)應(yīng)的VM，下同）需要和dom2進(jìn)行網(wǎng)絡(luò)通信，那么，他們之間發(fā)送的網(wǎng)絡(luò)包會(huì)通過(guò)dom0傳遞，但不會(huì)經(jīng)過(guò)物理網(wǎng)卡。而如果dom1要和另一臺(tái)物理機(jī)上的某個(gè)VM通信，網(wǎng)絡(luò)包會(huì)經(jīng)過(guò)兩臺(tái)物理機(jī)的dom0，同時(shí)會(huì)經(jīng)過(guò)兩臺(tái)物理機(jī)的網(wǎng)卡。由于物理機(jī)內(nèi)和物理機(jī)間VM通信均會(huì)經(jīng)過(guò)dom0，因此一臺(tái)物理機(jī)上有多個(gè)VM同時(shí)進(jìn)行網(wǎng)絡(luò)I／O操作時(shí)會(huì)發(fā)生性能干擾。

圖1 Xen的I／O模型

1.2 虛擬化環(huán)境上下文對(duì)遷移時(shí)間的影響

1.2.1 實(shí)驗(yàn)方案

為了研究Xen虛擬化環(huán)境下遷移節(jié)點(diǎn)所處的物理位置以及VM間性能干擾對(duì)數(shù)據(jù)遷移產(chǎn)生的影響，我們基于YCSB生成客戶(hù)端負(fù)載，然后在不同環(huán)境上下文條件下遷移數(shù)據(jù)，尋找遷移時(shí)間的變化規(guī)律。實(shí)驗(yàn)基于的軟硬件環(huán)境與3.1節(jié)一致。在每個(gè)VM上部署1個(gè)OnceDC緩存服務(wù)器節(jié)點(diǎn)。變化部署的VM數(shù)量時(shí)，通過(guò)改變YCSB實(shí)例的個(gè)數(shù)，保證每個(gè)緩存節(jié)點(diǎn)承擔(dān)的負(fù)載不變。執(zhí)行一條遷移命令將定量數(shù)據(jù)從一個(gè)緩存節(jié)點(diǎn)遷移到另一個(gè)緩存節(jié)點(diǎn)，統(tǒng)計(jì)遷移時(shí)間。

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

圖2給出了遷出節(jié)點(diǎn)與遷入節(jié)點(diǎn)所在VM位于同一個(gè)物理機(jī)和不同物理機(jī)這兩種情況下分別遷移50M，100M，200M，300M數(shù)據(jù)所用的時(shí)間?？梢钥吹娇缥锢頇C(jī)間的遷移相比同一物理機(jī)內(nèi)的遷移，需要消耗更多的時(shí)間，并且隨著遷移數(shù)據(jù)量的增加，兩者之間的差距也在增大。

圖2 緩存節(jié)點(diǎn)物理位置對(duì)遷移時(shí)間的影響

圖3對(duì)比了部署不同數(shù)量VM的情況下，位于同一物理機(jī)內(nèi)的兩個(gè)緩存節(jié)點(diǎn)間分別遷移50M，100M，200M，300M數(shù)據(jù)所用的時(shí)間。對(duì)于每種遷移數(shù)據(jù)大小的一組數(shù)據(jù)，均以?xún)H部署兩個(gè)VM時(shí)的遷移時(shí)間為基準(zhǔn)標(biāo)準(zhǔn)化。由圖3可知，同一物理機(jī)內(nèi)的兩個(gè)緩存節(jié)點(diǎn)間遷移數(shù)據(jù)時(shí)，VM間的性能干擾使遷移時(shí)間最多增加了近2倍（遷移50M數(shù)據(jù)時(shí)）。

圖3 VM間性能干擾對(duì)遷移時(shí)間的影響（物理機(jī)內(nèi)遷移）

圖4對(duì)比了部署不同數(shù)量VM的情況下，位于不同物理機(jī)的兩個(gè)緩存節(jié)點(diǎn)間分別遷移50M，100M，200M，300M數(shù)據(jù)所用的時(shí)間。VM＝（x，y）表示遷出節(jié)點(diǎn)和遷入節(jié)點(diǎn)所在的物理機(jī)中分別部署了x與y個(gè)VM。對(duì)于每種遷移數(shù)據(jù)大小的一組數(shù)據(jù)，均以VM＝（1，1）時(shí)的遷移時(shí)間為基準(zhǔn)標(biāo)準(zhǔn)化。由圖4可知，物理機(jī)間遷移數(shù)據(jù)時(shí)，VM間的性能干擾對(duì)遷移時(shí)間的影響更為顯著，遷移時(shí)間最多增加了3倍。

綜上可見(jiàn)，遷移節(jié)點(diǎn)所處物理位置和VM間的性能干擾對(duì)緩存系統(tǒng)的數(shù)據(jù)遷移具有無(wú)法忽略的影響，因此在制定數(shù)據(jù)遷移計(jì)劃時(shí)需要考慮該因素。

1.3 XenMon工具數(shù)據(jù)分析

1.3.1 實(shí)驗(yàn)方案

基于XenMon［8］工具對(duì)性能干擾因素進(jìn)行深入分析。XenMon是由惠普實(shí)驗(yàn)室開(kāi)發(fā)的一款應(yīng)用于Xen平臺(tái)的性能監(jiān)測(cè)工具。其底層使用xentrace和xenbaked收集數(shù)據(jù)，前端使用Python編寫(xiě)的xenmon提供界面展示。變化物理機(jī)上緩存節(jié)點(diǎn)（VM）的部署數(shù)量，分別在物理機(jī)內(nèi)和物理機(jī)間遷移100M數(shù)據(jù)，使用XenMon監(jiān)測(cè)遷移過(guò)程中Xen平臺(tái)的性能。其它實(shí)驗(yàn)設(shè)計(jì)與1.2節(jié)一致。

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

圖5給出了在物理機(jī)內(nèi)遷移時(shí)，遷出節(jié)點(diǎn)所在domain（dom1）部分性能指標(biāo)隨VM數(shù)量的變化情況。各監(jiān)測(cè)指標(biāo)均以部署2個(gè)VM時(shí)的測(cè)量值為基準(zhǔn)標(biāo)準(zhǔn)化。隨著VM數(shù)量的增加，VM對(duì)網(wǎng)絡(luò)資源的競(jìng)爭(zhēng)越來(lái)越激烈，因而dom1在I／O等待隊(duì)列的時(shí)間逐漸增長(zhǎng)（blocked（%）＿dom1）；系統(tǒng)中運(yùn)行隊(duì)列的長(zhǎng)度得以降低，處于可運(yùn)行狀態(tài)（runnable）的VM獲得時(shí)間片相對(duì)容易，導(dǎo)致等待時(shí)間逐步降低（waited（%）＿dom1）；I／O阻塞越來(lái)越多，導(dǎo)致消耗的CPU資源降低（cpu（%）＿dom1），同時(shí)每秒執(zhí)行次數(shù)降低（ex／s＿dom1）。

圖6給出了在物理機(jī)間遷移時(shí)，遷出節(jié)點(diǎn)所在domain（dom1）及其所在物理機(jī)的dom0部分性能指標(biāo)隨VM數(shù)量的變化情況。各監(jiān)測(cè)指標(biāo)以VM＝（1，1）時(shí)的測(cè)量值為基準(zhǔn)標(biāo)準(zhǔn)化。隨著VM數(shù)量的增加，各VM間I／O競(jìng)爭(zhēng)越來(lái)越激烈，因而dom0進(jìn)入阻塞狀態(tài)及I／O切換的次數(shù)增加（Block＿dom0與Switch＿dom0），內(nèi)存頁(yè)映射次數(shù)增加（PageMap＿dom0）；系統(tǒng)中運(yùn)行隊(duì)列的長(zhǎng)度得以降低，遷出節(jié)點(diǎn)所在VM處于可運(yùn)行狀態(tài)（runnable）時(shí)獲得時(shí)間片相對(duì)容易，導(dǎo)致每次執(zhí)行的等待時(shí)間降低（Waited／ex＿dom1）。

圖6 XenMon監(jiān)測(cè)指標(biāo)隨VM數(shù)量的變化（物理機(jī)間遷移）

可見(jiàn)，XenMon的監(jiān)測(cè)數(shù)據(jù)反映了VM間性能干擾的程度。

2 上下文感知的分布式緩存數(shù)據(jù)重均衡方法

由上文可知，①遷移節(jié)點(diǎn)所處的物理位置以及VM間性能干擾對(duì)分布式緩存的數(shù)據(jù)遷移具有無(wú)法忽略的影響。②XenMon收集的監(jiān)控?cái)?shù)據(jù)指標(biāo)較好的反映了Xen虛擬化環(huán)境下VM間的性能干擾。③數(shù)據(jù)重均衡過(guò)程的一個(gè)重要的優(yōu)化目標(biāo)是盡可能的減少數(shù)據(jù)遷移時(shí)間。因此本章首先基于統(tǒng)計(jì)學(xué)習(xí)方法建立虛擬化環(huán)境下XenMon收集的底層監(jiān)測(cè)數(shù)據(jù)與遷移時(shí)間之間的映射關(guān)系，即遷移時(shí)間預(yù)測(cè)模型；然后以該模型為基礎(chǔ)，提出一種基于細(xì)粒度資源監(jiān)測(cè)的上下文感知的數(shù)據(jù)重均衡算法，從而改善虛擬化環(huán)境下緩存系統(tǒng)的性能。

2.1 遷移時(shí)間預(yù)測(cè)模型

2.1.1 模型目標(biāo)

我們的目標(biāo)是建立XenMon監(jiān)測(cè)數(shù)據(jù)，遷移數(shù)據(jù)量與遷移時(shí)間的映射關(guān)系。具體來(lái)說(shuō)，希望建立如下函數(shù)

pi（1＜＝i＜＝m），qi（1＜＝i＜＝n）分別為物理機(jī)內(nèi)和物理機(jī)間遷移時(shí)間預(yù)測(cè)模型選取的監(jiān)測(cè)指標(biāo)。M＿Size表示遷移數(shù)據(jù)量，y表示遷移時(shí)間。

2.1.2 監(jiān)測(cè)指標(biāo)的選取

XenMon包含的監(jiān)測(cè)指標(biāo)較多，在分析了各指標(biāo)的意義后，我們選擇關(guān)注如表1所示的監(jiān)測(cè)指標(biāo)。

表1 XenMon監(jiān)測(cè)指標(biāo)的選取

表1中包含的各監(jiān)測(cè)指標(biāo)的含義說(shuō)明如下：

·CPU（%）：domU使用cpu的時(shí)間占對(duì)應(yīng)統(tǒng)計(jì)間隔的百分比。

·Blocked（%）：domU由于等待I／O事件發(fā)生而阻塞的時(shí)間占對(duì)應(yīng)統(tǒng)計(jì)間隔的百分比。

·Waited（%）：domU處于可運(yùn)行狀態(tài)，等待被調(diào)度的時(shí)間占對(duì)應(yīng)統(tǒng)計(jì)間隔的百分比。

·Waited／ex：domU平均每次被調(diào)度運(yùn)行需要等待被調(diào)度的時(shí)間。

·Ex／s：domU每秒被調(diào)度運(yùn)行的次數(shù)。

·Wake：統(tǒng)計(jì)間隔內(nèi)dom0被喚醒的次數(shù)。

·Block：統(tǒng)計(jì)間隔內(nèi)dom0等待I／O事件發(fā)生所用的時(shí)間。

·Switch：統(tǒng)計(jì)間隔內(nèi)系統(tǒng)中發(fā)生的domU切換次數(shù)。

·PageMap：統(tǒng)計(jì)間隔內(nèi)發(fā)生的頁(yè)映射次數(shù)。

2.1.3 數(shù)據(jù)預(yù)處理

為了減少監(jiān)測(cè)指標(biāo)數(shù)量級(jí)間的差異對(duì)建模過(guò)程產(chǎn)生的影響，我們對(duì)收集到的監(jiān)測(cè)數(shù)據(jù)進(jìn)行Z標(biāo)準(zhǔn)化（Z－standardization）處理，如式（4）所示

式中：μ、σ——所有樣本的均值、方差，X——樣本值，X＊——標(biāo)準(zhǔn)化后的值。

2.1.4 線性模型

我們基于回歸分析的方法構(gòu)建線性預(yù)測(cè)模型，函數(shù)關(guān)系式如式（5）、式（6）所示。物理機(jī)內(nèi)數(shù)據(jù)遷移

式中：αi，βi，δi，μ——回歸系數(shù)，c1——常量。

物理機(jī)間數(shù)據(jù)遷移

式中：αi，δi，βi，χi，μ——回歸系數(shù)，c2——常量。

在構(gòu)建線性模型的過(guò)程中，我們采用了兩種方法：主成分分析法和逐步回歸法。

（1）主成分分析法

主成分分析（principal components analysis，PCA）也稱(chēng)為主分量分析，是一種對(duì)高維變量進(jìn)行綜合與降維的統(tǒng)計(jì)分析方法。我們先使用主成分分析從原變量中提取出若干具有最佳解釋能力的新綜合變量（也稱(chēng)成分），這些綜合變量由原變量線性組合得到，可以反映初始變量的大部分信息，如式（7）所示。然后將上述成分作為回歸變量進(jìn)行最小二乘回歸分析得到最終的模型。我們稱(chēng)這種方法建立的線性模型為PCA－LM。

（2）逐步回歸法

在線性回歸模型中，若干變量或全部變量的樣本觀測(cè)值之間可能存在某種線性關(guān)系，這種現(xiàn)象即多重共線性，該現(xiàn)象會(huì)降低模型估計(jì)的精度。逐步回歸（stepwise regression）是一種常用的消除多重共線性、選取 “最優(yōu)”回歸方程的方法。其做法是逐個(gè)引入自變量，引入的條件是該自變量經(jīng)F檢驗(yàn)（F－test）是顯著的，每引入一個(gè)變量后，對(duì)已選入的變量進(jìn)行逐個(gè)檢驗(yàn)，如果原來(lái)引入的變量由于后面變量的引入而變得不再顯著，那么就將其剔除。引入一個(gè)變量或從回歸方程中剔除一個(gè)變量，為逐步回歸的一步，每一步都要進(jìn)行F檢驗(yàn)，以確保每次引入新變量之前回歸方程中只包含顯著的變量。這個(gè)過(guò)程反復(fù)進(jìn)行，直到既沒(méi)有不顯著的變量選入回歸方程，也沒(méi)有顯著變量從回歸方程中剔除為止。我們首先使用逐步回歸方法消除冗余指標(biāo)，然后基于最小二乘法求解模型。將使用這種方法建立的線性模型稱(chēng)作Stepwise－LM。

2.1.5 非線性模型（nonlinear models）

我們首先采用主成分分析法對(duì)監(jiān)測(cè)指標(biāo)進(jìn)行降維處理，然后構(gòu)建一個(gè)面向主成分的完全二次多項(xiàng)式函數(shù)，如式（8）所示

式中：ai，bij、di——回歸系數(shù)，c——常量，F(xiàn)i（1≤i≤m）為主成分。在構(gòu)建該函數(shù)時(shí)，采用高斯－牛頓（Gaussi－Newton）法進(jìn)行最小二乘擬合。將這種方法建立的非線性模型簡(jiǎn)稱(chēng)為PCA－NLM。

2.1.6 模型的訓(xùn)練

我們使用迭代的方法完成模型的訓(xùn)練，選用的訓(xùn)練參數(shù)如表2所示。具體做法是首先選取參數(shù)的邊界值組合作為輸入，運(yùn)行實(shí)驗(yàn)并收集采樣數(shù)據(jù)，接下來(lái)隨機(jī)選取邊界之間的若干組值再次作為輸入收集訓(xùn)練數(shù)據(jù)。對(duì)訓(xùn)練得到的模型的預(yù)測(cè)錯(cuò)誤率進(jìn)行評(píng)估，如果高于設(shè)定的閾值（如30%），則進(jìn)一步將輸出值細(xì)分，判斷每個(gè)區(qū)間的覆蓋情況。如果沒(méi)有覆蓋，則增加能較好覆蓋這部分區(qū)間的訓(xùn)練數(shù)據(jù)。

表2 訓(xùn)練模型使用的輸入負(fù)載

2.2 上下文感知的數(shù)據(jù)重均衡算法

根據(jù)上一節(jié)得到的遷移時(shí)間預(yù)測(cè)模型，對(duì)于給定的上下文（遷入遷出節(jié)點(diǎn)的物理位置，相關(guān)domain的XenMon監(jiān)測(cè)數(shù)據(jù)），可以求得遷移指定數(shù)據(jù)量所需的遷移時(shí)間。為了改善數(shù)據(jù)重均衡的效果，同時(shí)降低遷移時(shí)間，本節(jié)基于上述模型提出一種上下文感知的數(shù)據(jù)重均衡算法（contextaware data rebalancing algorithm），簡(jiǎn)稱(chēng)CADR算法。

為方便描述，先給出如下定義：

定義1 緩存集群C中包含n個(gè)緩存節(jié)點(diǎn)，分別用S1，S2，……，Sn表示。size［Si］為Si上的分區(qū)個(gè)數(shù)，Si上的第j個(gè)數(shù)據(jù)分區(qū)用Sij表示。

定義2mem［Sij］，net［Sij］分別為Sij的數(shù)據(jù)量和網(wǎng)絡(luò)流量。mem［Si］和net［Si］分別為Si上各分區(qū)數(shù)據(jù)量與網(wǎng)絡(luò)流量之和，mem－cap［Si］，net－cap［Si］分別為Si的內(nèi)存限額和網(wǎng)絡(luò)流量限額。

定義3 分別用mem－rate［Si］和net－rate［Si］表示節(jié)點(diǎn)Si的內(nèi)存利用率和網(wǎng)絡(luò)利用率，mem－rate［Si］＝mem［Si］／mem－cap［Si］，net－rate［Si］＝net［Si］／netcap［Si］。定義節(jié)點(diǎn)Si的綜合利用率為內(nèi)存利用率和網(wǎng)絡(luò)利用率之乘積，用mn－rate［Si］表示。

約束1：為了減少遷移時(shí)間，我們?cè)O(shè)定單個(gè)緩存節(jié)點(diǎn)的遷移方向是固定的，即在一次數(shù)據(jù)重均衡過(guò)程中不會(huì)同時(shí)有數(shù)據(jù)分區(qū)的遷入和遷出。

CADR算法存在以下3個(gè)優(yōu)化目標(biāo)：①緩存節(jié)點(diǎn)的數(shù)據(jù)量均衡；②緩存節(jié)點(diǎn)的網(wǎng)絡(luò)流量均衡；③數(shù)據(jù)遷移所需時(shí)間盡可能短。

CADR算法偽代碼如圖7所示，說(shuō)明如下：

（1）1－2行，按照mn－rate將節(jié)點(diǎn)劃分進(jìn)遷出節(jié)點(diǎn)集合out－set及遷入節(jié)點(diǎn)集合in－set。ε為一個(gè)大于1的常數(shù)，變化ε可以調(diào)整算法最終的均衡度及遷移的數(shù)據(jù)量。

（2）第4行從out－set中選出mn－rate值最高的節(jié)點(diǎn)Sf作為當(dāng)前步的遷出節(jié)點(diǎn)。第5－8行從Sf中選出當(dāng)前步的遷移分區(qū)，使得遷出節(jié)點(diǎn)的內(nèi)存利用率和網(wǎng)絡(luò)利用率之比盡量接近緩存集群的平均值。

（3）第9－19行基于3.1節(jié)得到遷移時(shí)間預(yù)測(cè)模型，從in－set中選出一個(gè)節(jié)點(diǎn)St存放分區(qū)P，使得遷移時(shí)間最短。

（4）第20行將＜Sf，St，P＞加入遷移計(jì)劃中，第21－22行更新Sf，St相應(yīng)的統(tǒng)計(jì)量。

第9行比較耗時(shí)，設(shè)其平均時(shí)間復(fù)雜度為O（l），再設(shè)緩存集群中分區(qū)總數(shù)為m，緩存節(jié)點(diǎn)數(shù)為n，則CADR算法的整體復(fù)雜度為O（m（n（l）。遷移時(shí)間預(yù)測(cè)模型使用離線訓(xùn)練的方式得到，在線預(yù)測(cè)遷移時(shí)間時(shí)所需的Xen－Mon監(jiān)控?cái)?shù)據(jù)通過(guò)運(yùn)行在dom0上的agent收集并定期發(fā)送給緩存集群管理器。

CADR算法由緩存集群管理器觸發(fā)執(zhí)行。根據(jù)其返回結(jié)果能夠生成新的分區(qū)路由信息及遷移計(jì)劃。為了避免遷移流量過(guò)大影響緩存系統(tǒng)的持續(xù)可用性，可在遷出節(jié)點(diǎn)實(shí)施流量控制。此外，應(yīng)實(shí)現(xiàn)遷移數(shù)據(jù)訪問(wèn)協(xié)議以能持續(xù)訪問(wèn)遷移中的數(shù)據(jù)分區(qū)。這兩方面內(nèi)容在［6］中作了討論。

圖7 CADR算法

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

我們?cè)贠nceDC上實(shí)現(xiàn)了上下文感知的分布式緩存數(shù)據(jù)重均衡方法。本章通過(guò)實(shí)驗(yàn)證明該方法的有效性。

3.1 實(shí)驗(yàn)方案

實(shí)驗(yàn)環(huán)境拓?fù)浣Y(jié)構(gòu)圖如圖8所示。S1，S2，S3為三臺(tái)16核的刀片機(jī)，我們?cè)谒械镀瑱C(jī)上安裝了Xen虛擬化環(huán)境。在每個(gè)刀片上部署若干個(gè)VM，并在每個(gè)VM上部署一個(gè)緩存服務(wù)器節(jié)點(diǎn)。測(cè)試客戶(hù)端使用YCSB，且每個(gè)YCSB實(shí)例部署在4核的普通PC上。YCSB所在物理機(jī)和S1，S2，S3之間使用1Gbps的以太網(wǎng)連接。OnceDC的緩存集群管理器部署在一臺(tái)4核PC上。表3給出了實(shí)驗(yàn)環(huán)境配置。

圖8 實(shí)驗(yàn)環(huán)境拓?fù)浣Y(jié)構(gòu)

表3 實(shí)驗(yàn)環(huán)境配置

在兩次實(shí)驗(yàn)中，每個(gè)YCSB實(shí)例運(yùn)行500線程，讀寫(xiě)比設(shè)為4∶1，每條緩存數(shù)據(jù)的大小為4KB。

3.2 實(shí)驗(yàn)1：遷移時(shí)間預(yù)測(cè)模型的準(zhǔn)確度

對(duì)于2.1節(jié)使用3種方法分別創(chuàng)建的遷移時(shí)間預(yù)測(cè)模型PCA－LM、Stepwis－LM和PCA－NLM，通過(guò)實(shí)驗(yàn)測(cè)量預(yù)測(cè)錯(cuò)誤率的方法來(lái)評(píng)價(jià)其準(zhǔn)確度。預(yù)測(cè)錯(cuò)誤率定義為

3.2.1 物理機(jī)內(nèi)遷移

在S2和S3上分別部署8和10個(gè)VM（緩存節(jié)點(diǎn)）。部署6個(gè)YCSB實(shí)例產(chǎn)生負(fù)載，YCSB使用uniform負(fù)載模式。變化S1上部署的VM（緩存節(jié)點(diǎn)）的數(shù)目（4，6，8，10），對(duì)于這4種情況，通過(guò)緩存集群管理器發(fā)出將定量數(shù)據(jù)（50M，100M）從S1上的一個(gè)緩存節(jié)點(diǎn)遷移到另一個(gè)緩存節(jié)點(diǎn)的命令，統(tǒng)計(jì)遷移時(shí)間，同時(shí)收集VM性能數(shù)據(jù)，按照各模型計(jì)算預(yù)測(cè)的遷移時(shí)間。每組配置重復(fù)實(shí)驗(yàn)5次，分別計(jì)算預(yù)測(cè)錯(cuò)誤率，最后取平均值。這樣得到物理機(jī)內(nèi)遷移時(shí)3種模型的預(yù)測(cè)錯(cuò)誤率如圖9所示。

由圖9可知，在物理機(jī)內(nèi)遷移時(shí)，3種模型的預(yù)測(cè)錯(cuò)誤率差別比較大，如在VM＝4時(shí)，PCA－LM模型的錯(cuò)誤率超過(guò)30%，而Stepwise－LM模型的錯(cuò)誤率為10%左右。Stepwise－LM模型在各種配置下均具有較低的預(yù)測(cè)錯(cuò)誤率（低于13%）。

圖9 3種遷移時(shí)間預(yù)測(cè)模型的錯(cuò)誤率（物理機(jī)內(nèi)遷移）

3.2.2 物理機(jī)間遷移

在S3部署10個(gè)VM（緩存節(jié)點(diǎn)），部署6個(gè)YCSB實(shí)例來(lái)產(chǎn)生負(fù)載，YCSB使用uniform負(fù)載模式。變化S1，S2上部署的VM及緩存服務(wù)器的數(shù)目（（3，3），（5，3），（5，5），（3，7），（7，7））。對(duì)于這5種情況，通過(guò)緩存集群管理器發(fā)出將定量數(shù)據(jù)（50M，100M）從S1上的一個(gè)緩存節(jié)點(diǎn)遷移到S2上另一個(gè)緩存節(jié)點(diǎn)的命令，統(tǒng)計(jì)遷移時(shí)間，同時(shí)收集VM性能數(shù)據(jù)，按照各模型計(jì)算預(yù)測(cè)的遷移時(shí)間。每組配置重復(fù)實(shí)驗(yàn)5次，分別計(jì)算預(yù)測(cè)錯(cuò)誤率，最后取平均值。這樣得到物理機(jī)間遷移時(shí)3種模型的預(yù)測(cè)錯(cuò)誤率如圖10所示。

圖10 3種遷移時(shí)間預(yù)測(cè)模型的錯(cuò)誤率（物理機(jī)間遷移）

由圖10可知，在物理機(jī)間遷移時(shí)，3種模型的預(yù)測(cè)效果都比較理想。其中PCA－NLM模型具有最低的預(yù)測(cè)錯(cuò)誤率（低于10%）。

由本實(shí)驗(yàn)可知，遷移時(shí)間預(yù)測(cè)模型具有較高的準(zhǔn)確度。

3.3 實(shí)驗(yàn)2：數(shù)據(jù)重均衡算法的有效性

OnceDC原有的數(shù)據(jù)重均衡算法，也以整個(gè)緩存集群的數(shù)據(jù)量和網(wǎng)絡(luò)流量均衡為目標(biāo)，不過(guò)其只對(duì)每個(gè)緩存節(jié)點(diǎn)具有的數(shù)據(jù)量和網(wǎng)絡(luò)流量進(jìn)行了監(jiān)測(cè)，因此在制定遷移計(jì)劃時(shí)將一個(gè)節(jié)點(diǎn)上的多個(gè)分區(qū)等同對(duì)待，忽略了各分區(qū)之間數(shù)據(jù)量和網(wǎng)絡(luò)流量的差異；同時(shí)它也沒(méi)有考慮虛擬化環(huán)境上下文對(duì)遷移時(shí)間的影響。我們稱(chēng)之為SPDR算法（simple partition based data rebalancing algorithm）。本節(jié)比較分別使用CADR算法和SPDR算法進(jìn)行數(shù)據(jù)重均衡的效果，以驗(yàn)證CADR算法的有效性。

實(shí)驗(yàn)時(shí)，在S1，S2，S3上分別部署12，8，10個(gè)VM及緩存服務(wù)器節(jié)點(diǎn)。使用6個(gè)YCSB實(shí)例來(lái)生成訪問(wèn)負(fù)載，YCSB按照表4所示的負(fù)載模式訪問(wèn)緩存集群。配置緩存集群每2分鐘執(zhí)行一次數(shù)據(jù)重均衡操作。分別配置SPDR算法和CADR算法進(jìn)行實(shí)驗(yàn)，結(jié)果如圖11所示。

表4 實(shí)驗(yàn)2YCSB的負(fù)載模式

圖11 SPDR算法與CADR算法比較

緩存集群初始時(shí)按照基于負(fù)載權(quán)重的分區(qū)機(jī)制在各緩存節(jié)點(diǎn)分配數(shù)據(jù)分區(qū)［6］。由于YCSB的負(fù)載模式是latest，導(dǎo)致各緩存節(jié)點(diǎn)存在數(shù)據(jù)量和網(wǎng)絡(luò)流量不均衡的現(xiàn)象，部分緩存節(jié)點(diǎn)cpu和網(wǎng)絡(luò)利用率接近100%，而某些節(jié)點(diǎn)的資源未得到充分使用。在120s，緩存系統(tǒng)第一次運(yùn)行數(shù)據(jù)重均衡算法，緩存系統(tǒng)進(jìn)入不穩(wěn)定（遷移）狀態(tài)。在重均衡過(guò)程中，由于訪問(wèn)遷移中的數(shù)據(jù)開(kāi)銷(xiāo)較大，緩存系統(tǒng)的平均響應(yīng)時(shí)間增大。在重均衡完成后，瓶頸緩存節(jié)點(diǎn)得到消除，因此系統(tǒng)的平均響應(yīng)時(shí)間與重均衡前相比變小。在180 s，YCSB的負(fù)載模式從latest變成zipfian。各緩存節(jié)點(diǎn)的負(fù)載分布再一次出現(xiàn)不均衡，平均響應(yīng)時(shí)間增大。240s時(shí)，第二次數(shù)據(jù)重均衡操作被觸發(fā)。與第一次類(lèi)似，在重均衡過(guò)程中，平均響應(yīng)時(shí)間增大，重均衡結(jié)束后平均響應(yīng)時(shí)間降到比重均衡前更小的水平。

與SPDR算法相比，CADR算法基于對(duì)每個(gè)分區(qū)的細(xì)粒度監(jiān)控，更好地實(shí)現(xiàn)了數(shù)據(jù)量和網(wǎng)絡(luò)流量的均衡，因此執(zhí)行完數(shù)據(jù)重均衡后平均響應(yīng)時(shí)間更低；同時(shí)在制定數(shù)據(jù)重均衡方案時(shí)考慮了虛擬機(jī)環(huán)境上下文的影響，優(yōu)先選取遷移時(shí)間較短的方案，因此系統(tǒng)的性能抖動(dòng)區(qū)間更小。

上述兩個(gè)實(shí)驗(yàn)表明，針對(duì)部署在虛擬化環(huán)境下的緩存系統(tǒng)而言，本文提出的遷移時(shí)間預(yù)測(cè)模型具有較高的準(zhǔn)確度；上下文感知的數(shù)據(jù)重均衡算法具有更好的均衡效果且遷移時(shí)間更短，能夠有效降低緩存系統(tǒng)的平均響應(yīng)時(shí)間，提高系統(tǒng)性能。

4 相關(guān)工作

Mei等人［9－10］針對(duì)虛擬化環(huán)境下VM間的性能干擾問(wèn)題進(jìn)行了研究。該研究工作表明，當(dāng)網(wǎng)絡(luò)I／O密集型或cpu密集型應(yīng)用部署在同一物理機(jī)時(shí)，應(yīng)用的性能會(huì)受到VM間性能干擾的影響。

現(xiàn)有工業(yè)界的分布式緩存系統(tǒng)如 Memcached，Terracotta EX，Oracle Coherence等大多不支持在運(yùn)行時(shí)動(dòng)態(tài)地進(jìn)行數(shù)據(jù)重均衡，無(wú)法適應(yīng)異構(gòu)集群環(huán)境及實(shí)際數(shù)據(jù)訪問(wèn)情況的多樣性。

美國(guó)東北大學(xué)的Kunkle［11］等人的研究工作在制定遷移計(jì)劃的同時(shí)考慮了遷移開(kāi)銷(xiāo)的優(yōu)化。作者定義了定值（constant）、線性（linear）、基于經(jīng)驗(yàn)的（empirical）和非線性（non－linear）等多種模型。遷移算法迭代地選取開(kāi)銷(xiāo)最小的分區(qū)遷移方案。該工作的不足是未考慮遷移時(shí)間的影響。

加州大學(xué)圣巴巴拉分校的Das等人［12－13］針對(duì)多承租場(chǎng)景下數(shù)據(jù)庫(kù)集群的數(shù)據(jù)遷移問(wèn)題，提出了一種輕量級(jí)的、基于迭代復(fù)制的數(shù)據(jù)遷移方法，目標(biāo)是盡可能降低遷移開(kāi)銷(xiāo)。作者同時(shí)給出了遷移過(guò)程中各種失效的處理及正確性證明。

Kari［14］將存儲(chǔ)系統(tǒng)的數(shù)據(jù)遷移問(wèn)題規(guī)約為圖著色（multi－edge coloring problem）問(wèn)題，目標(biāo)是在滿(mǎn)足各存儲(chǔ)節(jié)點(diǎn)傳輸約束的前提下，使數(shù)據(jù)遷移消耗的時(shí)間片最少，即使用的顏色數(shù)量最少。與本文關(guān)注數(shù)據(jù)重均衡方案的制定不同，該文關(guān)注的是數(shù)據(jù)重均衡方案制定好后，如何有效的制定遷移計(jì)劃，縮短全局遷移持續(xù)時(shí)間的問(wèn)題。

本文提出的上下文感知的分布式緩存數(shù)據(jù)重均衡方法面向云虛擬化環(huán)境，同時(shí)考慮數(shù)據(jù)量和網(wǎng)絡(luò)流量的均衡，并且盡可能的減少了遷移時(shí)間。

5 結(jié)束語(yǔ)

虛擬化環(huán)境中，遷移節(jié)點(diǎn)的物理位置及VM間性能干擾會(huì)對(duì)緩存數(shù)據(jù)遷移產(chǎn)生無(wú)法忽略的影響。本文提出一種遷移時(shí)間預(yù)測(cè)模型建模這種影響，在此基礎(chǔ)提出一種基于細(xì)粒度資源監(jiān)測(cè)的上下文感知的數(shù)據(jù)重均衡算法。實(shí)驗(yàn)結(jié)果表明，本文方法能夠準(zhǔn)確預(yù)測(cè)遷移時(shí)間，有效地均衡應(yīng)用變化的負(fù)載，同時(shí)降低遷移時(shí)間，從而改善緩存系統(tǒng)性能。

［1］Armbrust M.Above the clouds：A berkeley view of cloud computing［R］.Berkeley，California：EECS Department，University of California，2009：1－25.

［2］Zhang Gong，Chiu L，Liu Ling.Adaptive data migration in multi－tiered storage based cloud environment［C］／／Miami，F(xiàn)L：Proc of IEEE 3rd Int’l Conf on Cloud Computing，2010：148－155.

［3］Taobao tair［EB／OL］.［2012－03－12］.http：／／code.taobao.org／p／tair／wiki／aboutus／.

［4］Barham P，Dragovic B，F(xiàn)raser K，et al.Xen and the art of virtualization［C］／／New York，USA：Proc of ACM SOSP，2003.

［5］Cooper B，Silberstein A，Tam E，et al.Benchmarking cloud serving systems with YCSB［C］／／Indianapolis，Indiana，USA：Roceedings of the 1st ACM Symposium on Cloud Computing，2010：143－154.

［6］ZHU Xin，QIN Xiulei，WANG Lianhua，et al.Research on dynamic scaling of elastic distributed cache systems［J］.Frontiers of Computer Sciences and Technology，2012，6（2）：97－108（in Chinese）.［朱鑫，秦秀磊，王聯(lián)華，等.彈性分布式緩存動(dòng)態(tài)擴(kuò)展方法研究［J］.計(jì)算機(jī)科學(xué)與探索，2012，6（2）：97－108.］

［7］Hastorun D，Jampani M，Kakulapati G，et al.Dynamo：Amazon’s highly available key－value store［C］／／Washington State，USA：Proc of ACM Symp on Operating Systems Principles，2007：205－220.

［8］Gupta D，Gardner R，Cherkasova L.XenMon：QoS monitoring and performance profiling tool［R］.Hewlett－Packard Labs，Technical Report HPL－2005－187，2005.

［9］Mei Yiduo，Liu Ling，Pu Xing，et al.Performance measurements and analysis of network I／O applications in virtualized cloud［C］／／Miami，F(xiàn)L：CLOUD，2010.

［10］Pu Xing，Liu Ling，Mei Yiduo，et al.Understanding performance interference of I／O workload in virtualized cloud environments［C］／／Miami，F(xiàn)L：CLOUD，2010.

［11］Kunkle D，Schindler J.A load balancing framework for clustered storage systems［C］／／Berlin，Heidelberg：Proceedings of 15th International Conference on High Performance Computing，2008：57－72.

［12］Das S，Nishimura S，Agrawal D，et al.Albatross：Lightweight elasticity in shared storage databases for the cloud using live data migration［J］.Proceedings of the VLDB Endowment，2011，4（8）：494－505.

［13］Elmore AJ，Das S，Agrawal D，et al.Zephyr：Live migration in shared nothing databases for elastic cloud platforms［C］／／Athens，Greece：SIGMOD，2011：301－312.

［14］Kari C，Kim Y，Russell A.Data migration in heterogeneous storage systems［C］／／Minneapolis，MN：In Proceedings of The 31st Int’l Conference on Distributed Computing Systems，2011：143－150.