張揚(yáng)-cmd-基于頁(yè)面訪問(wèn)特性分類(lèi)內(nèi)存去冗余

可以降低服務(wù)器內(nèi)存配置需求。CBPS最廣泛的一種實(shí)現(xiàn)，KSM(KernelSamepage稱(chēng)CMD，在降低無(wú)用比較帶來(lái)的開(kāi)銷(xiāo)的同時(shí)，更加高效地檢測(cè)頁(yè)面共享機(jī)會(huì)。主要的創(chuàng)新點(diǎn)在于，基于特性，內(nèi)存頁(yè)被分成不同的分類(lèi)。在CMD中，全局比較樹(shù)被分% 描D.4.2[管理]：主存；D.4.8[性能]：測(cè)關(guān)于這項(xiàng)工作的個(gè)人或課堂應(yīng)用的部分或全部的數(shù)字或硬拷貝的權(quán)限已經(jīng)被保護(hù)沒(méi)有費(fèi)用需要提供，副本不會(huì)被制作或分發(fā)來(lái)取得利益或者是商業(yè)優(yōu)勢(shì)，副本要遵守本通知以及第一頁(yè)上所有的引證。擁有本作品組件的的他人而非AM應(yīng)該收到尊敬。指明相關(guān)人員的概述是允許的。以其他方式復(fù)制或重新發(fā)布，發(fā)布到服務(wù)器上或者重新分配到列表上，需要事先特定的權(quán)限或者/以及費(fèi)用。VEE‘14，2014312號(hào)，鹽湖城，猶他州，2014ACM 978-1-4503-2764-0/14/03....1 簡(jiǎn)部署在單臺(tái)物理服務(wù)器上，并且它們?cè)谔摂M化技術(shù)[16,25]下獨(dú)立地運(yùn)行。虛擬化技術(shù)可認(rèn)為是讓宿主服務(wù)器部署虛擬機(jī)的主要瓶頸之一。內(nèi)存去冗余技術(shù)是一種可以用于機(jī)會(huì)。比如，DifferenceEngine[17]，報(bào)告多虛擬機(jī)內(nèi)容節(jié)50%VMware[29]報(bào)告內(nèi)存節(jié)省約40%。這些相同頁(yè)面可以共享于同一個(gè)物理頁(yè)面上1,則冗余的內(nèi)存頁(yè)面就可以被超管理器回收備用。因此，CBPS可以高效地降低虛擬機(jī)內(nèi)存占用，并提高了宿主服務(wù)器部署虛無(wú)用比較(futilecomparison)，即通過(guò)頁(yè)內(nèi)容比較后（包括穩(wěn)定樹(shù)和不穩(wěn)定樹(shù)）也沒(méi)有找于CMD中，基于頁(yè)面問(wèn)次數(shù)，子頁(yè)面的寫(xiě)分布，然后僅僅在屬于該分類(lèi)的局部比較樹(shù)中進(jìn)行查找和比我們通過(guò)一個(gè)基于硬件的內(nèi)存系統(tǒng)來(lái)監(jiān)視內(nèi)存寫(xiě)特性。該系統(tǒng)使用細(xì)，依據(jù)。此外，硬件輔助頁(yè)面監(jiān)視器引入的開(kāi)銷(xiāo)可以忽略不計(jì)，因而，CMD的實(shí)現(xiàn)KSMKSM整個(gè)運(yùn)行時(shí)間的相當(dāng)一部分（約44）并且，無(wú)用比較占據(jù)了頁(yè)面比較開(kāi)銷(xiāo)的絕大部分（約83。CMD輕量級(jí)的基于分類(lèi)的內(nèi)存去冗余方法。在CMD中，依據(jù)頁(yè)面特性，我們?cè)谖覀儗?shí)際的實(shí)驗(yàn)系統(tǒng)中實(shí)現(xiàn)了CMDKSM相比，CMD可以高效地檢測(cè)到頁(yè)面共享機(jī)會(huì)（超過(guò)98%），同時(shí)減少了頁(yè)面比較次數(shù)（約685%，無(wú)用比較率也平均降低了約12.15%。2 2.1KernelSamepageKSM（KernelSamepageMerging）[6]CBPS的實(shí)現(xiàn)，檢測(cè)并共享具有相同內(nèi)容的頁(yè)面到一個(gè)副本。近來(lái)，KSM被是實(shí)現(xiàn)為一個(gè)內(nèi)核線程，周期性的掃KSM頁(yè)面（或相同頁(yè)面KSM頁(yè)面。這是通過(guò)修改冗余頁(yè)面的頁(yè)表映射到KSM頁(yè)上以回收冗余頁(yè)面的原始空間來(lái)實(shí)現(xiàn)的。冗余頁(yè)面通過(guò)寫(xiě)時(shí)(CoW)機(jī)制實(shí)現(xiàn)COW陷入的頁(yè)錯(cuò)誤。超管理器通過(guò)分配一個(gè)新的頁(yè)框分配給請(qǐng)求虛擬近來(lái)，KSM為物理服務(wù)器全部?jī)?nèi)存頁(yè)僅僅兩棵全局比較樹(shù)，如圖1：穩(wěn)定KSM頁(yè)面。否則它在不穩(wěn)定樹(shù)中進(jìn)一步就會(huì)入到不穩(wěn)定樹(shù)中（作為一個(gè)葉結(jié)點(diǎn)。在每一次完整的掃描后，不穩(wěn)定樹(shù)將會(huì)KSM沒(méi)CPU開(kāi)銷(xiāo)相對(duì)來(lái)KSM中，內(nèi)核線程以一種分批逐批次的方式對(duì)頁(yè)面進(jìn)行掃描：所有的候選頁(yè)面首先被分成頁(yè)面數(shù)量相同的多個(gè)批次。掃描完一個(gè)批次的頁(yè)面后，KSM線程面，不會(huì)在不穩(wěn)定樹(shù)中搜索。計(jì)算校驗(yàn)和也給系統(tǒng)帶來(lái)了一些CPU開(kāi)銷(xiāo)（如圖2所2.1KernelSamepage1KSM置請(qǐng)參考第四部分。在KSM中，有兩個(gè)參數(shù)控制著影響KSM共享效率和運(yùn)行開(kāi)銷(xiāo)的掃描速度：pages_to_scansleep_millisecs，分別代表在休眠前每批次掃描的頁(yè)面數(shù)量和KSM下一個(gè)批次頁(yè)面掃描前休眠的毫秒數(shù)。我們采用sleep_millisecs的默認(rèn)值20ms，pages_to_scan從100（默認(rèn)值，C0）到3200（C5）變化。對(duì)于我們8GB內(nèi)存的實(shí)驗(yàn)系統(tǒng)，對(duì)應(yīng)的完成一次完整掃描的時(shí)間分別在400秒到12.5秒。2KSM運(yùn)行時(shí)開(kāi)銷(xiāo)分解和CPU共有四臺(tái)虛擬機(jī)部署在物理服務(wù)器上，隨著每批次頁(yè)面掃描數(shù)量從100（C0）變化320（C5KS鎖著每批次掃描頁(yè)面數(shù)量的增加，CPU占用率也相應(yīng)地增加，C18.52%，C3C5，24.13%53.09%。CPU開(kāi)銷(xiāo)的增長(zhǎng)將會(huì)降低虛擬機(jī)的性能，盡管其可以發(fā)現(xiàn)頁(yè)面共享機(jī)會(huì)（3所示。KSM運(yùn)行時(shí)開(kāi)銷(xiāo)可以被分為三個(gè)部分：頁(yè)面校驗(yàn)和面在全局穩(wěn)定樹(shù)和全局不穩(wěn)定樹(shù)中進(jìn)行頁(yè)面比較所花的時(shí)間；其他開(kāi)銷(xiāo)代表著KSM其一個(gè)共享頁(yè)面被修改時(shí)移除寫(xiě)時(shí)等。可以看出，頁(yè)面校驗(yàn)和開(kāi)銷(xiāo)和頁(yè)面比較開(kāi)銷(xiāo)的比例基本保持不變（在相同掃描速度下保持不變。頁(yè)面比較開(kāi)銷(xiāo)約占KSM運(yùn)行時(shí)的44%，頁(yè)面校驗(yàn)和開(kāi)銷(xiāo)約占22%，其他約占34%。3，變而改變。可以看出，隨著掃描速度的加快，KSM可以檢測(cè)到的頁(yè)面共享機(jī)會(huì)，因?yàn)樗梢詸z測(cè)到的短生命周期的頁(yè)面共享。規(guī)范化到C0，C1可以檢測(cè)1.63倍的頁(yè)面共享機(jī)會(huì)，C22.08倍，C32.088倍。也可以看出，在我們四個(gè)虛擬機(jī)的實(shí)驗(yàn)400C2速度已經(jīng)足夠快，可以檢測(cè)到幾乎全部潛在的頁(yè)面共享機(jī)會(huì)因此的后續(xù)部分如果沒(méi)有特別我們采用C2作為我們默認(rèn)的KSM配，4KSM線程周期性的掃描和比較頁(yè)面，總的頁(yè)面比較次數(shù)線性地增長(zhǎng)。也Futile_Rate=Futile_PC_Num/ Futile_PC_Num表示無(wú)用比較(沒(méi)有找到可共享頁(yè)面)的次數(shù)，Total_PC_Num表示一由于近來(lái)KSM通過(guò)在兩棵全局樹(shù)中進(jìn)行頁(yè)面比較，同時(shí)并沒(méi)有考慮到頁(yè)面特性，44%3 中介紹一個(gè)用于監(jiān)視頁(yè)面特性的輕量級(jí)的硬件輔助方法，最后，在3.3節(jié)，我們會(huì)概對(duì)于頁(yè)面分類(lèi)有如下兩個(gè)要求：（1）很有可能具有相同內(nèi)容的頁(yè)面應(yīng)該被分為同一5KSM5展示了名為CMD的基于頁(yè)面分類(lèi)的內(nèi)存去冗余方法。在CMD中，有一個(gè)內(nèi)存監(jiān)視器以捕獲所有的頁(yè)面，尤其是寫(xiě)，因?yàn)閷?xiě)會(huì)修改頁(yè)面內(nèi)容并影響頁(yè)面共享機(jī)會(huì)。內(nèi)存監(jiān)視器為每一個(gè)內(nèi)存頁(yè)頁(yè)面特性：一旦一個(gè)對(duì)頁(yè)面的寫(xiě)獲，將會(huì)更新該頁(yè)的內(nèi)存特性（如寫(xiě)次數(shù)?；陧?yè)面特性，頁(yè)面是說(shuō)，上一輪掃描中所捕獲的頁(yè)面特性將會(huì)用于指導(dǎo)本輪掃描的頁(yè)面分類(lèi)。并且內(nèi)存監(jiān)視器在本輪也會(huì)繼續(xù)監(jiān)視特性，并用于下一輪掃描6KSM本輪的掃描中，根據(jù)頁(yè)面特性進(jìn)行更新。頁(yè)面監(jiān)視7HMTT在本文中，我們采用了一個(gè)基于硬件的名為HMTT[7]軟硬件混合的內(nèi)存追蹤監(jiān)此也能夠檢測(cè)到DDR3命令總線上的所有內(nèi)存事務(wù)信號(hào)（發(fā)給插在HMTT上的DRAM設(shè)斷DDR3協(xié)議，這樣HMTT就可以以緩存塊為粒度（由于處理器在上一級(jí)緩存未命中的時(shí)候DRAM內(nèi)存）捕獲真實(shí)系統(tǒng)的所有內(nèi)存蹤跡。我們也在HMTT實(shí)現(xiàn)了一個(gè)PCIe接口以將內(nèi)存蹤跡發(fā)送到另一臺(tái)擁有高帶寬的機(jī)器上，因而，HMTT能夠支持長(zhǎng)時(shí)間（比如小時(shí)級(jí)別）地監(jiān)視負(fù)載。的實(shí)現(xiàn)細(xì)節(jié)，請(qǐng)HMTT的主頁(yè)， 8KSM在本工作中，我們沒(méi)有必要獲得特別詳細(xì)的頁(yè)面蹤跡，相反，我們只需要頁(yè)面的寫(xiě)特性，比如寫(xiě)次數(shù)，子頁(yè)面的寫(xiě)分布等。因此我們可以通過(guò)HMTT板上的SDRAM緩沖直接頁(yè)面的特性。當(dāng)監(jiān)測(cè)到一個(gè)寫(xiě)，它首先從請(qǐng)求的地（pfn，在HMTT上實(shí)現(xiàn)了一個(gè)千兆以太網(wǎng)接口，并且，頁(yè)面信息將會(huì)周期性的通過(guò)以太網(wǎng)接口發(fā)送到實(shí)驗(yàn)服務(wù)器（KSM掃描周期。在軟件方面，我們也在周期性的獲得頁(yè)面特性反饋，這個(gè)反饋信息會(huì)用于頁(yè)面分類(lèi)。因?yàn)镠MTT采用硬件技術(shù)，頁(yè)面特性給物理服務(wù)器引入了幾乎可以忽略的開(kāi)銷(xiāo)。此外，HMTT可以細(xì)粒度（比如緩存塊）地捕獲頁(yè)面，因此我們可以獲得更加詳細(xì)和細(xì)粒頁(yè)面分8GB88B1GB的頁(yè)面0，1GB2GB1，依此類(lèi)推。CMD_Address能CMD_PageCount：內(nèi)存監(jiān)視器在每次掃描中為每個(gè)頁(yè)面捕獲頁(yè)面寫(xiě)次數(shù)，問(wèn)次數(shù)在0到8的被放到分類(lèi)0中，寫(xiě)次數(shù)在8到16的放到分類(lèi)1中，依此類(lèi)推。CMD_PageCount考慮一個(gè)完整的頁(yè)面的特性，因此，它可以提高頁(yè)面分類(lèi)的精確性并檢測(cè)到的頁(yè)面共享機(jī)會(huì)。CMD_Subpage_Distribution:每個(gè)頁(yè)面被分成多個(gè)子頁(yè)面（比如4個(gè)1KB頁(yè)面，該頁(yè)的分類(lèi)就是（0,1,1,0,0,0,0,1。按照細(xì)粒度的子頁(yè)面訪問(wèn)特性，CMD_Subpage_Distribution更有可能把具有相同內(nèi)容的頁(yè)面歸位一類(lèi)，因此可以4 EPT2.00GHzE55043級(jí)緩存，L132KB大小，L2級(jí)韓物理內(nèi)存為一個(gè)雙列DDR3800MHz的內(nèi)存，共8GB。宿主服務(wù)器跑的是內(nèi)核版本為3.6.0CentOS6.2Linux3.6.10KSMCMD。我們使用libpcap[5]從HMTT板的以太網(wǎng)口獲得存有頁(yè)面特性返回的以太網(wǎng)數(shù)據(jù)包。我們使CPU2GB464位Linux2.6.32-279CentOS6.3。我們選擇了如下三個(gè)基準(zhǔn)在客戶(hù)機(jī)中進(jìn)內(nèi)核編譯Linux3.6.10虛擬機(jī)中以24個(gè)并發(fā)請(qǐng)求來(lái)測(cè)試一個(gè)本地。在單線程，oltp-table-size為 CMD的配置參數(shù)設(shè)定如下4。對(duì)于CMD_Address，8GB物理內(nèi)存分成8個(gè)64作為頁(yè)面寫(xiě)閾值，并且由于我們采用16個(gè)頁(yè)面分類(lèi)，所有次數(shù)超過(guò)1024的都將被歸為最后一個(gè)分類(lèi)。至于CMD_Subpage_Distribution，我們采用4子頁(yè)面分布（每個(gè)子頁(yè)面1KB），分為16個(gè)分類(lèi)。為了獲得頁(yè)面分類(lèi)如子頁(yè)面臟位位圖，我們采用16作為每個(gè)子頁(yè)面寫(xiě)次數(shù)的閾值，也就是說(shuō)，當(dāng)一個(gè)子頁(yè)面寫(xiě)次數(shù)達(dá)到16，該子頁(yè)面的臟位設(shè)置為1，否則設(shè)置為0.5 104看出，在內(nèi)核編譯負(fù)載下，KSM能夠檢測(cè)到絕大多數(shù)頁(yè)面共享機(jī)會(huì)（1.02E6共享頁(yè)面。然而，由于使用兩棵全局比較樹(shù)來(lái)頁(yè)面信息，候選頁(yè)面需要與大量的無(wú)關(guān)頁(yè)7.25E5度的頁(yè)面特性（每一輪中頁(yè)面的寫(xiě)次數(shù)）以指導(dǎo)頁(yè)面分類(lèi)。盡管它可以達(dá)到更1.00E6CMD_PageCountCMD_Subpage方式相同。然CMD_Addr表現(xiàn)較差，它僅5對(duì)于10（C）所MySQL負(fù)載們可以看出，CMD_AddrCMD_PageCount檢測(cè)到幾乎相同的頁(yè)面共享機(jī)會(huì)（約3.54E5，約為KSM（約3.87E5）的91.5%。值得注意的是，CMD_Subpage甚至可以檢測(cè)到的頁(yè)面共享機(jī)會(huì)（約4.69E5約為KSM1.21被?？赡艿脑蚴?，在MySQL負(fù)載中，存在短生命周期的頁(yè)面共享機(jī)會(huì)。然而KSM沒(méi)有能夠檢測(cè)到它們，因?yàn)閷?duì)于每個(gè)候選頁(yè)，它需要花更長(zhǎng)的比較時(shí)間，這會(huì)導(dǎo)CMD_Subpage檢測(cè)到，因?yàn)樵诰植繕?shù)種的比較更加快114圖11展示了4臺(tái)虛擬機(jī)在不同負(fù)載下的頁(yè)面比較次數(shù)。如圖11（a）所示，對(duì)于內(nèi)CMD_Addr擁有最少的頁(yè)面比較次數(shù)，僅為KSM56.8%，因?yàn)镃MD_Addr的頁(yè)面分類(lèi)最為均衡（按照地址劃分。CMD_PageCountCMD_Subpage的頁(yè)面比較次數(shù)幾乎相同KSM73.3%CMD_Addr相比，盡CMD_Subpage1.08倍的頁(yè)面比更加高效得檢測(cè)到頁(yè)面共享（如圖10所示。如圖11（b）所示，對(duì)于Apache負(fù)載，KSM仍然擁有最多的頁(yè)面比較次數(shù)，CMD_Addr最少，約為CMD_Subpage是一種最好的權(quán)衡。圖12展示了4臺(tái)虛擬機(jī)下無(wú)用比較減少率，以KSM為基線。我們可以看出，這三分別減少了大概4.77%，6.35%和12.15%。CMD_Subpage方法在MySQL負(fù)載下最大減少量約為13.62%結(jié)果表明了基于細(xì)粒度子頁(yè)面分布特性的CMD_Subpage方法的準(zhǔn)圖13展示了不同方法下KSM線程的平均CPU占用率。我們通過(guò)top命令以一CPUKSMCMD方法（將全局樹(shù)分離成多個(gè)局部樹(shù)）均能減少CPU的占用率。對(duì)于內(nèi)核編譯負(fù)載，KSM的CPU24.98%CddrCDPagCoun19.45%19.65%CMDCPU運(yùn)行時(shí)開(kāi)銷(xiāo)。而Apache負(fù)載，KSM的CPU占用率約為38.12%CMD_Addr，分別減少到18.86%，21.28%和20.05%。圖13不同方法下KSM線程的平均CPU占用6 的有效的方法，內(nèi)存去冗余已經(jīng)吸引了關(guān)于它的諸多研究。Disco虛擬機(jī)器VMWareESX服務(wù)器上實(shí)現(xiàn)[29]，并且不要求客戶(hù)機(jī)操作系統(tǒng)的輔助并透明地工作在CBPS已經(jīng)在工業(yè)界和學(xué)術(shù)界成為了應(yīng)用最為廣泛的頁(yè)面共享技術(shù)。Klosteretal.[20]設(shè)計(jì)并Xen超管理器中實(shí)現(xiàn)了基于內(nèi)容的頁(yè)面共享。他們發(fā)現(xiàn)，在虛KSM（KernelSamepageMerging）[6]是一種基于掃描的用于檢測(cè)頁(yè)面共享機(jī)會(huì)的機(jī)制。KSM實(shí)現(xiàn)為一個(gè)內(nèi)核線程，周期性的掃描客戶(hù)機(jī)內(nèi)存頁(yè)面以檢測(cè)相同頁(yè)面（業(yè)余頁(yè)面內(nèi)容比較。Changetal.[12]KSM在不同負(fù)載下的效率實(shí)施了經(jīng)驗(yàn)性的研究。KSMIO50%的內(nèi)CPU密集型應(yīng)用，KSM會(huì)因?yàn)闊o(wú)用頁(yè)面比較而導(dǎo)致更CPU占用。Rachamallaetal[24]研究了不同配置KSM性能CPU占用之間的權(quán)Guptaetal，提出DifferenceEngine[17]，率先支持子頁(yè)面共享，這里面，一個(gè)完可以節(jié)省90%內(nèi)存，即使運(yùn)行不同的應(yīng)用，也能達(dá)65%。Woodetal.[30]提出了KSM++[21]采用了一種基于宿主I/O特性以使得內(nèi)存掃描進(jìn)程更加高效并利用短生命較早地利用共享機(jī)會(huì)。XLH在宿主機(jī)文件系統(tǒng)層生成頁(yè)面提示，使之較早地進(jìn)入合并階段。因而XLH能夠獲得短生命周期的合并機(jī)會(huì)。然而XLH只能工作在密集文件的虛擬機(jī)，并且仍然采用有兩棵全局樹(shù)的KSM以全部?jī)?nèi)存。Chiangetal[14]，提出了一種通用內(nèi)存去冗余引擎，利用客戶(hù)機(jī)操作系統(tǒng)的空閑內(nèi)存池信息，并且把這些內(nèi)存Storisystem[23]通過(guò)在磁盤(pán)的時(shí)候監(jiān)視內(nèi)存相同區(qū)域以實(shí)現(xiàn)，它能夠高效地找到短生命周期的頁(yè)面共享機(jī)會(huì)，然而他要求對(duì)客戶(hù)機(jī)操作系統(tǒng)進(jìn)行修改。Sharmaetal[27]將KSM的頁(yè)面去冗余擴(kuò)展到頁(yè)面緩存，他們提出了Singleton以定位雙緩存的問(wèn)題，并為宿主機(jī)和客戶(hù)機(jī)頁(yè)面緩存級(jí)別上實(shí)現(xiàn)了一個(gè)獨(dú)占緩存。Jimetal[19]提出了一種Dengetal[15]也提出了一種類(lèi)似的基于用戶(hù)分組的共享機(jī)制以為同一個(gè)宿主機(jī)的不同用戶(hù)提供和可信度。以上的兩種研究都沒(méi)有將無(wú)用比較的開(kāi)銷(xiāo)考慮進(jìn)來(lái)。Shaetal提SmartKSM[26]KSM中，基于頁(yè)面類(lèi)型和進(jìn)程方面將內(nèi)存占用分成不同的集合。Sindelaretal[28]提出了一種圖模型的設(shè)計(jì)以捕獲虛擬機(jī)之間的頁(yè)面共享機(jī)會(huì)。他們也發(fā)Dinda[31]研究，在大規(guī)模虛擬化并行系統(tǒng)中，虛擬機(jī)之間和虛擬機(jī)內(nèi)部的內(nèi)存共享IBM活

7 結(jié)在本文中，我們首先對(duì)KSM運(yùn)行時(shí)進(jìn)行了詳細(xì)的分析，并且我們發(fā)現(xiàn)存在大量的KSM線程依據(jù)兩棵大的全局比較樹(shù)進(jìn)行掃描。接下來(lái)我們提出了CMDCMD中，頁(yè)面依據(jù)訪本文的所有作者為審稿人的建設(shè)性意見(jiàn)向其致謝。本作部分地收到了國(guó)家科學(xué)基金（NSFC編號(hào), 計(jì)劃編號(hào)2011CB302502，中國(guó)重點(diǎn)研究發(fā)展計(jì)劃，編號(hào)XDA 及研究計(jì)劃YBCB 。YungangBao部分地受到了CCF-In英特爾青年教師 .Kvm-kernelbasedvirtualmachine.Linux2632-linuxkernelnewbies.Sysbench:asystemperformancebenark.Tcpdumpandlibpcap.A.Arcangeli,I.Eidus,andC.Wright.Increasingmemorydensitybyusingksm.InProceedingsoftheLinuxSymposium(OLS’09),pages19–28,2009.Y.Bao,M.Chen,Y.Ruan,L.Liu,J.Fan,Q.Yuan,B.Song,andJ.Xu.Hmtt:aplatformindependentfull-systemmemorytracemonitoringsystem.InProceedingsofthe2008ACMSIGMETRICSinternationalconferenceonMeasure-75mentandmodelingofcomputersystems,SIGMETRICS’08,pages229–240,2008.S.Barker,T.Wood,P.Shenoy,andR.Sitaraman.Anempiricalstudyofmemorysharinginvirtualmachines.InProceedingsofthe2012USENIXconferenceonAnnualTechnicalConference,USENIXATC’12,pages273–284,2012.F.Bellard.Qemu,afastandportabledynamictranslator.InProceedingsoftheannualconferenceonUSENIXAnnualTechnicalConference,ATEC’05,pages41–46,2005.E.Bugnion,S.Devine,K.il,andM.Rosenblum.Disco:runningcommodityoperatingsystemsonscalablemultiprocessors.ACMTrans.Comput.Syst.,15(4):412–447,Nov.1997.R.Ceron,R.Folco,B.Leitao,andH.Tsubamoto.Powersystemsmemorydeduplication.InIBMRedbooks,2012./ C.-R.Chang,J.-J.Wu,andP.Liu.Anempiricalstudyonmemorysharingofvirtualmachinesforserverconsolidation.InParallelandDistributedProcessingwithApplications(ISPA),2011IEEE9thInternationalSymposiumon,pages244–249,2011.L.Chen,Z.Cui,Y.Bao,M.Chen,Y.Huang,andG.Tan.Alightweighthybridhardware/softwareapproachforobjectrelativememoryprofiling.InPerformanceysisofSystemsandSoftware(ISPASS),2012IEEEInternationalSymposiumon,pages46–57,J.-H.Chiang,H.-L.Li,andT.-c.Chiueh.Introspection-basedmemoryde-duplicationandmigration.InProceedingsofthe9thACMSIGPLAN/SIGOPSinternationalconferenceonVirtualexecutionenvironments,VEE’13,pages51–62,2013.Y.Deng,C.Hu,T.Wo,B.Li,andL.Cui.Amemorydeduplicationapproachbasedongroupinvirtualizedenvironments.InProceedingsofthe2013IEEESeventhInternationalSymposiumonService-OrientedSystemEngineering,SOSE’13,pages367–372.R.P.Goldberg.Surveyofvirtualmachineresearch.Computer,7(9):34–45,Sept.D.Gupta,S.Lee,M.Vrable,S.Savage,A.C.Snoeren,G.Varghese,G.M.Voelker,A.Vahdat.Differenceengine:harnessingmemoryredundancyinvirtualmachines.In8thUSENIXSymposiumonOperatingSystemsDesignandImplementation,OSDI’08,pages309–322,Y.Huang,Z.Cui,L.Chen,W.Zhang,Y.Bao,andM.Chen.Halock:hardware-assistedlockcontentiondetectioninmultithreadedapplications.InProceedingsofthe21stinternationalconferenceonParallelarchitecturesandcompilationtechniques,PACT’12,pages253–262,2012.S.Kim,H.Kim,andJ.Lee.Group-basedmemorydeduplicationforvirtualizedclouds.In6thWorkshoponVirtualizationinHigh-PerformanceCloudComputing,VHPC2011,pages387–397,2011.J.F.Kloster,J.Kristensen,andA.Mejlholm.Determiningtheuseofintershareablepagesusingkernelintrospection.InTech.rep.,AalborgUniversity,.K.Miller,F.Franz,T.Groeninger,M.Rittinghaus,M.Hillenbrand,andF.Bellosa.Ksm++:Usingi/o-basedhintstomakememory-deduplicationscannersmoreefficient.InProceedingsoftheASPLOSWorkshoponRuntimeEnvironments,Systems,Layeringand .K.Miller,F.Franz,M.Rittinghaus,M.Hillenbrand,andF.Bellosa.Xlh:Moreeffectivememorydeduplicationscannersthroughcross-layerhints.InProceedingsofthe2013USENIXconferenceonAnnualTechnicalConference,USENIXATC’13,pages279–290,G.Mi?′os,D.G.Murray,S.Hand,andM.A.Fetterman.Satori:enlightenedpagesharing.InProceedingsofthe2009conferenceonUSENIXAnnualtechnicalconference,USENIX’09,pages1–14,2009.S.Rachamalla,D.Mishra,andP.Kulkarni.Allpagesharingisequal,butsomesharingis .M.RosenblumandT.Garfinkel.Virtualmachinemonitors:currenttechnologyandfutureputer,38(5):39–47,2005.[26]S.Sha,J.Li,N.Li,W.Ju,L.Cui,andB.Li.Smartksm:Avmm-basedmemoryscannerforvirtualmachines. P.SharmaandP.Kulkarni.Singleton:system-widepagededuplicationinvirtualenvironments.InProceedingsofthe21stinternationalsymposiumonHigh-PerformanceParallelandDistributedComputing,HPDC’12,pages15–26,2012.M.Sindelar,R.K.Sitaraman,andP.Shenoy.Sharing-awarealgorithmsforvirtualmachinecolocation.InProceedingsofthe23rdACMsymposiumonParallelisminalgorithmsandarchitectures,SPAA’11,pages367–378,2011.C.A.Waldspurger.Memoryresourcemanagementinvmwareesxserver.SIGOPSOper.Syst.Rev.,36(SI):181–194,Dec.2002.T.Wood,G.Tarasuk-Levin,P.Shenoy,P.Desnoyers,E.Cecchet,andM.D.Corner.Memorybuddies:exploitingpagesharingforsmartcolocationinvirtualizeddatacenters.InProceedingsofthe2009ACMSIGPLAN/SIGOPSinternationalconferenceonVirtualexecutionenvironments,VEE’09,pages31–40,2009.L.XiaandP.A.Dinda.Acasefortrackingandexploitinginter-nodeandintra-memorycontentsharinginvirtualizedlarge-scaleparallelsystems.InProceedingsofthe6thinternationalworkshoponVirtualizationTechnologiesinDistributedComputingDate,VTDC’12,pages11–18,2012.X.Yang,C.Ye,andQ.Lin.Evaluationandenhancementtomemorysharingandswap on_and_Enhancement_to_Memory_Sharing_and_SwapCMD:Classification-basedMemoryDeduplicationthroughPageAccessCharacteristicsLichengChen?§,ZhipengWei?§,ZehanCui?§,MingyuChen?,HaiyangPan?§,Yungang{chenlicheng,weizhipeng,cuizehan,cmy,panhaiyang,Limitedmainmemorysizeisconsideredasoneofthemajorbottlenecksinvirtualizationenvironments.Content-BasedPageSharing(CBPS)isanefficientmemorydeduplicationtechniquetoreduceservermemoryrequirements,inwhichpageswithsamecontentaredetectedandsharedintoasin-glecopy.AsthewidelyusedimplementationofCBPS,Ker-nelSamepageMerging(KSM)maintainsthewholemem-orypagesintotwoglobalcomparisontrees(astabletreeandanunstabletree).Todetectpagesharingopportunities,eachcandidatepageneedstobecomparedwithpagesalreadyinthesetwolargeglobaltrees.Howeversincethevastmajor-ityofpageshavedifferentcontentwithit,itwillresultinmassivefutilepagecomparisonsandthusheavyoverhead.Inthispaper,weproposealightweightpageClassification-basedMemoryDeduplicationapproachnamedCMDtore-ducefutilepagecomparisonoverheadmeanwhiletodetectpagesharingopportunitiesefficiently.ThemaininnovationofCMDisthatpagesaregroupedintodifferentclassifica-tionsbasedonpageaccesscharacteristics.Pageswithsimi-laraccesscharacteristicsaresuggestedtohavehigherpossi-bilitywithsamecontent,thustheyaregroupedintothesameclassification.InCMD,thelargeglobalcomparisontreesaredividedintomultiplesmalltreeswithdedicatedlocalonesineachpageclassification.Pagecomparisonsareperformedjustinthesameclassification,andpagesfromdifferentclas-sificationsarenevercompared(sincetheyprobablyresultinfutilecomparisons).TheexperimentalresultsshowthatCMDcanefficientlyreducepagecomparisons(byabout68.5%)meanwhiledetectnearlythesame(bymorethan98%)orevenmorepagesharingopportunities.Permissiontomakedigitalorhardcopiesofallorpartofthisworkfor alorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.CopyrightsforcomponentsofthisworkownedbyothersthanACMmustbehonored. ingwithcreditispermitted.Tocopyotherwise,orrepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.Requestpermissionsfrompermissions@.VEE’14,March1–2,2014,SaltLakeCity,Utah,USA.Copyrightc2014ACM978-1-4503-2764-0/14/03...$15.00..

CategoriesandSubjectDescriptorsD.4.2[StorageMan-agement]:MainMemory;D.4.8[Performance]:Measure-MemoryDeduplication;PageClassification;PageAccessCharacteristicsCloudcomputing esincreasinglypopularandcom-petitivebothinindustryandacademia.Incloudcomputing,multiplevirtualmachines(VMs)canbecollocatedonasin-glephysicalserver,andtheycanoperateindependentlywithvirtualizationtechnology[16,25],whichispromisingtoprovideflexibleallocation,migrationofservices,andbetterresources(suchasprocessor,mainmemory)aremanagedbyasoftwarelayercalledhypervisor(orVirtualMachineMon-itor,VMM),andtheprimarygoalofahypervisoristopro-videefficientresourcesharingamongmultipleco-runningvirtualmachines.However,asthenumberofVMscollocatedonaphysi-calserverkeepsincreasing(e.g.itcancollocateupto8vir-tualmachinesonaphysicalcoreindesktopcloudenviron-ment),meanwhilewiththeincreasingsizeofworkingsetofapplicationsrunninginavirtualmachine,virtualizationhasHowever,sincetheincreasingspeedofmainmemorycapac-ityfallsbehindwiththedemand,thelimitedmainmemorysizehasbeenconsideredasoneofthemajorbottleneckstoconsolidatemorenumberofguestVMsonahostingserver[17,22].Memorydeduplicationisanefficienttechniquetoalleviatethememorycapacitybottleneck,whichdetectsandreducespageduplicationtosavememory.Alargevolumeofpriorworkhasshownthattherearegreatopportunitiesinmemorydeduplicaion,e.g.DifferenceEngine[17]reportedabsolutememorysavingsof50%acrossVMs,andVMware[29]reportedabout40%memoryContentBasedPageSharing(CBPS)isoneofthemostwidelyusedmemorydeduplicationtechniquestoimprovememoryefficiency,sinceCBPScanbeperformedtranspar-entlyinthehypervisorlayeranditdoesn’trequireanymod-ificationtoguestoperatingsystems(OS).InCBPS,amem-oryscannerisadoptedtoscanmemorypagesofguestVMsperiodicallyandtodetectallidenticalpagesthathavesamecontent,theseidenticalpagescanthenbesharedintoasin-glephysicalpage1,andtheredundantmemorypagescanbereclaimedandfreebacktothehypervisor.ThusCBPScanefficientlyreducethememoryfootprintofguestVMsandprovidegoodopportunitytoincreasethenumberofVMscollocatedonahostserver.Inthispaper,wemainlyfocusonKernelSamepageMerging(KSM)[6],whichisawidely-usedimplementationofCBPS,andithasbeenintegratedintotheLinuxkernelarchive[3].InKSM,therearetwoglobalred-blackcompar-isontreesforthewholememorypagesofahostingserver,treecontainsalreadysharedpageswithwrite-protected,andtheunstabletreecontainsonlypagesthatarenotsharedyet(withoutwrite-protected).Ineachscanround,eachcandi-datepageneedstobecomparedwithpagesalreadyinthesetwolargeglobaltreestodetectpagesharingopportunities.Wedefinethetermfutilecomparisonasthepagecontentcomparisonofacandidatepagewithotherpages(bothinthestabletreeandunstabletree),whichfailstofindanypagewiththesamecontent.SinceKSMonlymaintainstwoglobalcomparisontreesforthewholememorypages,eachglobaltreewillcontainalargenumberofnodes(orpages),e.g.1Mnodes(4KBpage)for4GBmemory.Foreachcan-didatepage,itneedstobecomparedwithalargenumberofuncorrelatedpagesintheglobaltrees,thusitwillresultinmassivefutilepagecomparisonsandheavyoverhead.Andasthepagescanperformsrepeatedly,thenumberoffutilepagecomparisonswillincreaseproportionally.Inthispaper,weproposealightweightpageClassification-basedMemoryDeduplicationapproachnamedCMDtore-ducefutilecomparisonoverheadmeanwhiletodetectpagesharingopportunitiesefficiently.InCMD,pagesaregroupedintodifferentclassificationsbasedonpageaccesscharac-teristics.Pageswithsimilaraccesscharacteristicsaresug-gestedtohavehigherpossibilitywithsamecontent,thustheyaregroupedintothesameclassification.Andthelargeglobalcomparisontreesaredividedintomultiplesmalltreesthattherearededicatedlocalcomparisontreesineachpageclassification.Foreachcandidatepage,itsclassificationisfirstlydeterminedbasedonitsaccesscharacteristics(e.g.writeaccesscount,writeaccessdistributionofsubs),andthenitissearchedandcomparedwithpagesonlyinthelocalcomparisontreesofitsclassification.Thuspagecomparisonsareperformedjustinthesameclassification,andpagesfromdifferentclassificationsarenevercompared,sincetheyprobablyresultinfutilecomparisons.Inthispa-per,wemainlyfocusonpagewriteaccess,whichwillmod-ifypagecontentandthusaffectpagesharingopportunities.1Withallidenticalguestphysicalpagespointingbacktothesamemachinephysicalpageinthehypervisor’spagetable.

Wemonitorwriteaccessofpageswithahardware-snoobasedmemorytracemonitoringsystem,whichisabletocaptureallmemorywritereferenceswithfinecache-blockgranularity,thuswecanusenotonlythecountofwriteaccessesforeachpage(coarsegranularity),butalsowriteaccessdistributionofsubs(finegranularity),whichwillbeabetterhintforpageclassification.Additionally,hardware-assistedpageaccessmonitorintroducesnegligibleoverhead,thusourimplementationofCMDislightweightandefficient.WeperformadetailedprofilingofKSM,wefindthatpagecontentcomparisonscontributeacertainportionofthewholeKSMrun-time(about44%).Andfutilecom-parisonscontributemostofthepagecomparisonover-head(about83%).Toreducefutilecomparisonoverheadmeanwhiletodetectpagesharingopportunitiesefficiently,wepro-posealightweightpageClassification-basedMemoryDeduplicationapproachnamedCMD.InCMD,pagesaregroupedintodifferentclassificationsbasedonpageaccesscharacteristics,thelargeglobalcomparisontreesaredividedintomultipletreeswithdedicatedlocalonesineachclassification.Pagecomparisonsareperformedjustinthesameclassification,andpagesfromdifferentclassificationsarenevercompared(sincetheyprobablyresultinfutilecomparisons).WeimplementtheCMDinourrealexperimentalsys-tem.Theexperimentalresultsshowthat,comparedwiththebaselineKSM,theCMDcanefficientlydetectpagesharingopportunities(bymorethan98%)meanwhilere-ducethenumberofpagecomparisons(byabout68.5%),andthefutilecomparisonrateisalsoreducedbyabout12.15%onaverage.Therestofthepaperisorganizedasfollows:Section2introducesthebackgroundandmotivation.Section3de-scribesthedesignandimplementationofpageclassificationbasedmemorydeduplication.Wedescribetheexperimen-talmethodologyinSection4anddemonstrateexperimentalresultsanddiscussioninSection5.Relatedworkandcon-clusionareinSection6andSection7respectively.BackgroundandKSM(KernelSamepageMerging)[6]isascanningbasedimplementationofCBPS,whichdetectsandsharespageswithsamecontentintoasinglecopy.NowadaysKSMisimplementedasakernelthread,whichperiodicallyscansmemorypagesofguestvirtualmachinesco-runningonahostingserver.Eachcandidatepageiscomparedcontentwithpagesalreadyinthecomparisontrees,andthenitisinsertedintotheglobaltreesbasedoncomparisonresult.Ifmultiplepageswithsamecontentaredetectedduringascanround,oneofthepagesisselectedastheKSMpage(oridenticalpage),thenotherduplicatepagesaremergedandsharedwiththesingleKSMpage,whichisimplementedbyreplacingthepagetableentriesofduplicatepagestomaptotheKSMpage,andtheoriginalspaceofduplicatepagesarereclaimedandsaved.DuplicatedPagesaresharedwithCopy-On-Write(COW)mechanism,whichmeansthatallpagetableentriesofduplicatepagesaremappedwithread-onlypermission.IfaVMattemptstowriteasharedpage,apagefaultnamedCOWfaultwillbetriggered.Thehypervisorhandlesthefaultbyallocatinganewpageframe

…………page……

leobalreeandmakingaprivatecopyofthepagefortherequestingVM,thentheVMwritesdatainthisnewprivatepage.Nowadays,KSMmaintainsonlytwoglobalred-blackcomparisontreesforthewholememorypagesofahostingserver,asshowninFigure1:thestabletreeandtheunstabletree.Nodesofthesetwoglobaltreesareindexeddirectlywiththecontentofpages(askeyofred-blacknodes).Thestabletreemaintainssearchstructureforsharedpages,whiletheunstabletreemaintainsonlypagesthatarenotyetshared.Ineachscanround,acandidatepageisfirstlycomparedwithpagesinthestabletree.IfthereisamatchwithanexistedKSMpage,thecandidatepagewillbemergedandsharedwiththismatchedKSMpage.Otherwise,itneedstobefurthersearchedintheunstabletree:Ifthereisamatchintheunstabletree,thematchedpagewillberemovedfromtheunstabletree,thenitwillbemergedwiththecandidatepageandmigratedintothestabletreewithwrite-protected;ifnomatchisfound,thecandidatepageisinsertedintotheunstabletree(asaleafnode).Ineachfullscanround,theunstabletreeneedstobereconstructed,whichmeansthatpagesintheunstabletreeneedtobere-insertedintotheunstabletreetogetthecorrectnodeposition.Thisisbecausethatpagesintheunstabletreearenotwrite-protected,andcontentofthesepagesmightbemodifiedduringthescanround.Astheincreasingcapacityofmainmemory,thesizeofthesetwoglobaltreesexpandsproportionally.SinceKSMdoesnottakeanypageaccesscharacteristicsintoaccount,foracandidatepage,itneedstobecomparedcontentwithalargenumberofuncorrelatedpageswhichwillinducemassivefutilecomparisons.ThereisatradeoffofcontrollingthepagescanspeedKSM.Fastscancandetectmorepagesharingopportuni-ties,especiallyforshort-livedsharing,howeveritwillinduceheavyCPUoverheadduetofrequentpagecontentcomparisons.Slowscan,ontheotherside,mightlosesomeshort-livedpagesharingopportunities,buttheCPUover-headisrelativelylightweight.InKSM,thekernelthreadscanspagesofVMsinabatch-by-batchmanner:allcandi-datepagesarefirstlyseparatedintobatcheswitheachbatchhavingthesamenumberofpages;afterscanningallpagesinabatch,theKSMthreadgoestosleepforaspecifiedtime;thenitcontinuestoscanpagesinthenextbatch.Thescan

Figure1.TheglobalstabletreeandglobalunstabletreeinKSM.Acandidatepageisfirstlysearchedandcomparedwithpagesinthestabletree.Ifnomatchisfound,itneedstobefurthersearchedandcomparedwithpagesintheunstablespeedcanbecontrolledbyconfiguringthenumberofpagesinabatch(itis100bydefault)andthesleeptimebetweenbatches(20msbydefault).Beforeapageissearchedintheunstabletree,thechecksumofitisre-calculatedandthencomparedwithitslastchecksum.Thechecksumservesasafilterofpagecomparisonsintheunstabletree:ifthecheck-sumremainsthesame,itisacandidatepage,andthepagecanbesearchedandcomparedwithpagesintheunstabletree;otherwise,itisconsideredasavolatilepageanditwillnotbesearchedintheunstabletree.ThecomputationofpagechecksumalsoinducessomeCPUoverheadtothesystem(asshowninFigure2).ProfilingofPagestoineachFullscanfigurationsinourexperimentalsystemwith8GBmemory(pleaserefertoSection4fordetailedsystemconfiguration).InKSM,therearetwoparametersthatcontrolscan-speedwhichcanaffectKSMsharingefficiencyandrun-timeover-head:pagestoscanandsleepmillisecs,whichrepresentsthenumberofpagestobescannedinabatchbeforetheKSMthreadgoestosleep,andhowmanymillisecondsoftimetheKSMthreadwillsleepbeforeturningtoscanpagesofthenextbatchofrespectively.Weadoptthedefaultvalueofsleepmillisecsas20msandvarypagestoscanfrom100(default,asC0)to3200(asC5).Forourexperimentalsys-temwith8GBphysicalmemory,thecorrespondingofafullRuntimeOverheadRuntimeOverhead

CPUCPU

x7##ofPageSharing543210

Figure2.KSMrun-timeoverheadbreakdownandtheCPUUtilizationoftheKSMthreadasthenumberofpagestobescannedinabatchvariedfrom100to3200withfourguestVMscollocatedonthehostserver.scantimeisvariedfrom400secondsto12.5secondsrespec-Figure2showstheKSMrun-timeoverheadbreakdownandtheCPUUtilizationoftheKSMthreadasthenumberofpagestobescannedinabatchvariedfrom100(C0)to3200(C5)withfourguestVMscollocatedonthehostserver.Wecanseethatasthenumberofpagesscannedinabatchin-creasing,theCPUutilizationincreasecorrespondingly,itisabout8.52%forC1,itincreaseupto24.13%forC3and53.09%forC5.TheinducedCPUoverheadwilldegradetheperformanceofVMs,althoughitcanfindmorepageshar-ingopportunities(asshown