陸志剛 , 徐繼偉 , 黃 濤

1(中國科學(xué)院 軟件研究所 軟件工程技術(shù)中心,北京 100190)2(計(jì)算機(jī)科學(xué)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院 軟件研究所),北京 100190)3(中國科學(xué)院大學(xué),北京 100190)

容器(container)技術(shù)已經(jīng)成為一種被廣泛認(rèn)可的服務(wù)器資源共享技術(shù)[1].與虛擬機(jī)相比,容器具有輕量級(jí)的特點(diǎn),其快速啟動(dòng)、低系統(tǒng)資源消耗等優(yōu)點(diǎn)使容器技術(shù)在彈性云平臺(tái)和自動(dòng)運(yùn)維系統(tǒng)方面有著很好的應(yīng)用前景.國內(nèi)外主流云平臺(tái)(如亞馬遜AWS、阿里云等)都相繼開始支持Docker 容器部署,各大、中、小型企業(yè)數(shù)據(jù)中心也正致力于采用Docker 容器進(jìn)行應(yīng)用部署.Docker 容器將應(yīng)用封裝到鏡像(image)中,通過運(yùn)行鏡像創(chuàng)建應(yīng)用實(shí)例.由于鏡像在鏡像庫(repository)中集中存儲(chǔ),將鏡像從集中存儲(chǔ)加載到本地的過程需要耗費(fèi)大量的時(shí)間,這將導(dǎo)致鏡像實(shí)例創(chuàng)建時(shí)間由毫秒級(jí)延遲為分鐘級(jí),嚴(yán)重制約了應(yīng)用在面對(duì)突發(fā)高負(fù)載時(shí)的處理能力,影響應(yīng)用服務(wù)質(zhì)量.雖然Docker 鏡像采用了分層加載的機(jī)制,但是由于受到應(yīng)用版本多樣性等因素影響,在不同應(yīng)用版本鏡像之間依然存在重復(fù)存儲(chǔ)和重復(fù)加載的現(xiàn)象.復(fù)用已加載的數(shù)據(jù)可以有效提高鏡像加載速度,對(duì)提高應(yīng)用的彈性擴(kuò)展能力具有重要意義.

重復(fù)數(shù)據(jù)查找技術(shù)是數(shù)據(jù)去冗余中的一種常用技術(shù),廣泛應(yīng)用于數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)遷移中[2,3],其核心思想是基于內(nèi)容尋址進(jìn)行數(shù)據(jù)分片復(fù)用.將數(shù)據(jù)去冗余技術(shù)應(yīng)用到容器鏡像存儲(chǔ)和加載過程,可以有效提高容器鏡像存儲(chǔ)設(shè)備利用率、提高容器鏡像加載速度.充分利用舊版本鏡像中的相同數(shù)據(jù),可以有效提高新版本鏡像的加載速度.

本文分析了Docker 容器鏡像分層存儲(chǔ)和加載機(jī)制,提出了一種基于分片復(fù)用的容器鏡像加載方法.方法通過增加元數(shù)據(jù)信息實(shí)現(xiàn)對(duì)鏡像數(shù)據(jù)的有效組織,使已有鏡像數(shù)據(jù)具有可復(fù)用性,從而達(dá)到提高鏡像加載效率的目的.本文的貢獻(xiàn)如下:

(1) 首次提出了多版本容器鏡像加載過程中存在數(shù)據(jù)重復(fù)加載問題,并對(duì)其產(chǎn)生原因進(jìn)行分析,指出原生加載策略存在的不足;

(2) 提出一種基于重復(fù)數(shù)據(jù)刪除技術(shù)的鏡像數(shù)據(jù)分片復(fù)用方法,有效復(fù)用不同版本容器鏡像的相同數(shù)據(jù),降低鏡像加載過程中的網(wǎng)絡(luò)傳輸數(shù)據(jù)量,提高鏡像加載效率;

(3) 分析鏡像加載策略,針對(duì)不同場景下的鏡像加載需求,自動(dòng)選擇最優(yōu)的鏡像加載策略,減少不必要的操作開銷;

(4) 采用模擬實(shí)驗(yàn),通過設(shè)置不同實(shí)驗(yàn)參數(shù)進(jìn)行多組實(shí)驗(yàn),驗(yàn)證本文提出方法的有效性.

本文第1 節(jié)介紹本文的研究背景和研究動(dòng)機(jī),主要介紹Docker 容器和鏡像的組成結(jié)構(gòu),分析Docker 鏡像加載過程中存在的問題.第2 節(jié)提出一種基于重復(fù)數(shù)據(jù)刪除技術(shù)的鏡像加載方法,減少鏡像加載過程中的網(wǎng)絡(luò)傳輸.第3 節(jié)通過實(shí)驗(yàn)驗(yàn)證本文提出方法的有效性和可行性.第4 節(jié)系統(tǒng)地總結(jié)和分析對(duì)比相關(guān)工作.第5 節(jié)對(duì)本文工作進(jìn)行總結(jié).

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

1.1 Docker容器及鏡像

容器是一種進(jìn)程級(jí)虛擬化方案,容器鏡像用于容器的數(shù)據(jù)存儲(chǔ)并可以被實(shí)例化為容器實(shí)例.容器實(shí)例在運(yùn)行過程中會(huì)復(fù)用主機(jī)的操作系統(tǒng)內(nèi)核,因此,容器鏡像只負(fù)責(zé)封裝操作系統(tǒng)庫文件、中間件、應(yīng)用及其配置等內(nèi)容.為了提高存儲(chǔ)和加載效率,Docker 鏡像由一組只讀的文件層組成,每個(gè)文件層均為一個(gè)單獨(dú)的文件系統(tǒng).在鏡像實(shí)例化過程中,不同文件層按順序疊加組成了容器實(shí)例的根文件系統(tǒng)[4].如圖1 所示,以Ubuntu 17.04 容器鏡像為例,該鏡像包含5 個(gè)不同的文件層,每層所包含內(nèi)容為該層文件與上層文件的差異.Docker 鏡像在實(shí)例化時(shí),所有的鏡像文件層設(shè)為只讀層,在鏡像文件層上面添加一個(gè)可讀寫的層,該層通常被稱為容器層.容器實(shí)例運(yùn)行過程中,所有的文件系統(tǒng)修改操作(如寫文件、修改文件、刪除文件等)均發(fā)生在容器層.

Docker 容器和Docker 鏡像的最大區(qū)別,就在于最上層的這個(gè)可讀寫的文件層.當(dāng)容器刪除時(shí),最上層的容器層會(huì)隨之刪除,而鏡像文件層則不受影響.由于每個(gè)容器有不同的容器層并且對(duì)于容器的修改都存儲(chǔ)于相應(yīng)的容器層當(dāng)中,多個(gè)容器可以通過共享的方式訪問相同的鏡像文件層,同時(shí)具有自己的數(shù)據(jù)狀態(tài).Docker 存儲(chǔ)驅(qū)動(dòng)采用寫時(shí)復(fù)制(copy-on-write)技術(shù)實(shí)現(xiàn)上述功能.Docker 容器通過特定的操作可以轉(zhuǎn)化為新的鏡像,即:將可寫的容器層設(shè)為鏡像的最上層,并將其狀態(tài)置為只讀狀態(tài).

由此可見,鏡像和容器的相互轉(zhuǎn)化關(guān)系是,容器可以直接轉(zhuǎn)化為鏡像,而鏡像不能直接轉(zhuǎn)化為容器,只能通過在最上層添加一個(gè)可讀寫文件層實(shí)例化為容器.

Fig.1 Docker container layers圖1 Docker 容器文件層

1.2 鏡像存儲(chǔ)與加載過程中存在的問題

在分布式環(huán)境中,同一鏡像對(duì)應(yīng)的容器實(shí)例會(huì)運(yùn)行在不同的主機(jī)上,Docker 采用服務(wù)器/客戶端的模式來存儲(chǔ)和分發(fā)鏡像.用戶一般采用Docker 鏡像庫(docker registry)來集中存儲(chǔ)鏡像.Docker 鏡像庫是Docker 生態(tài)系統(tǒng)中的重要組件,是一個(gè)存儲(chǔ)和內(nèi)容分發(fā)系統(tǒng),存儲(chǔ)已命名的鏡像和用不同tag 標(biāo)記的可用版本.

鏡像加載是指鏡像從鏡像庫加載到運(yùn)行主機(jī)的過程.由于Docker 鏡像具有分層的特性,且每層均以該層哈希值命名,在加載過程中,只需加載對(duì)應(yīng)哈希值不存在的文件層.Docker 鏡像加載過程可分為以下幾步:1.客戶端將鏡像名稱和版本號(hào)發(fā)送到相應(yīng)的鏡像庫服務(wù)器;2.服務(wù)器根據(jù)名稱和版本號(hào)查找對(duì)應(yīng)的鏡像,并將組成該鏡像的不同文件層的相關(guān)信息(如哈希值)返回客戶端;3.客戶端根據(jù)服務(wù)器返回的文件層信息,在本地查找相同文件層;4.如果客戶端在本地沒有找到某文件層,則向服務(wù)器發(fā)送加載該文件層請(qǐng)求;5.服務(wù)器端通過網(wǎng)絡(luò)將步驟4 中請(qǐng)求的文件層發(fā)送到客戶端;6.客戶端根據(jù)步驟2 中返回的信息將各文件層組織為鏡像.因此,Docker 鏡像加載本身是一種文件層去冗余的加載過程.圖2 所示為Vote App 從1.0.0 版本升級(jí)為1.1.0 版本過程,其中,L1～L4 文件層均沒有發(fā)生變化,而L5 文件層發(fā)生變化.

Fig.2 Docker image update diagram圖2 Docker 鏡像升級(jí)示意圖

按照鏡像加載策略,在升級(jí)過程中,L1～L4 文件層不需要重新加載,而L5 文件層需要全部重新加載.L5 文件層數(shù)據(jù)量大小約占整個(gè)鏡像的47%,而兩個(gè)版本的數(shù)據(jù)改變量不到1%.于是,我們可以得出一個(gè)結(jié)論:雖然當(dāng)前的鏡像加載方式采用了去冗余加載的策略,但是在特定的情況下,仍然需要加載大量冗余數(shù)據(jù).主要原因是:當(dāng)前去冗余加載是以文件層為粒度進(jìn)行去冗余,而更細(xì)粒度的數(shù)據(jù)情況改變無法獲得.Docker 設(shè)計(jì)者的本意是鼓勵(lì)用戶盡量將應(yīng)用微服務(wù)化,減少每個(gè)Docker 容器數(shù)據(jù)量,然而在實(shí)際使用過程中,大量應(yīng)用開發(fā)者仍按照舊有思路開發(fā)應(yīng)用,使應(yīng)用對(duì)應(yīng)的鏡像文件層數(shù)據(jù)量不斷變大.近年來,隨著DevOps 技術(shù)的不斷發(fā)展和進(jìn)步,應(yīng)用開發(fā)速度和升級(jí)頻率逐漸加快,每天10 次的應(yīng)用發(fā)布頻率已成為很多互聯(lián)網(wǎng)公司的標(biāo)準(zhǔn)配置.因此,在基于Docker 的應(yīng)用部署架構(gòu)中,減少應(yīng)用更新時(shí)的網(wǎng)絡(luò)數(shù)據(jù)傳輸量可以加快應(yīng)用更新速度、提高服務(wù)質(zhì)量.

綜上可知,Docker 鏡像升級(jí)過程中可能存在大量數(shù)據(jù)重復(fù)加載的問題,解決這個(gè)問題對(duì)提升服務(wù)質(zhì)量具有重要意義.

2 基于重復(fù)數(shù)據(jù)刪除技術(shù)的鏡像數(shù)據(jù)分片復(fù)用加載方法

本文的工作目標(biāo)是:通過復(fù)用重復(fù)數(shù)據(jù)來降低鏡像加載過程時(shí)間消耗,提高鏡像加載效率.為達(dá)到這個(gè)目的,我們首先需要發(fā)現(xiàn)并識(shí)別鏡像中的重復(fù)數(shù)據(jù).重復(fù)數(shù)據(jù)識(shí)別可包括數(shù)據(jù)塊級(jí)重復(fù)數(shù)據(jù)識(shí)別[5]和文件級(jí)重復(fù)數(shù)據(jù)識(shí)別[6],其主要區(qū)別在于:數(shù)據(jù)塊級(jí)重復(fù)數(shù)據(jù)識(shí)別需要對(duì)數(shù)據(jù)進(jìn)行細(xì)粒度切分后再進(jìn)行比較,而文件級(jí)重復(fù)數(shù)據(jù)識(shí)別則直接對(duì)文件進(jìn)行比較.因而數(shù)據(jù)塊級(jí)重復(fù)數(shù)據(jù)識(shí)別更加適用于數(shù)據(jù)流和少量變化頻繁的大文件,而文件級(jí)重復(fù)數(shù)據(jù)識(shí)別則適用于小文件或變化較少的大文件.容器鏡像加載過程中鏡像文件層以一個(gè)整體進(jìn)行流式傳輸,因此本文中采用數(shù)據(jù)塊級(jí)重復(fù)數(shù)據(jù)識(shí)別方法.重復(fù)數(shù)據(jù)識(shí)別方法原理見公式(1).

已知存在數(shù)據(jù)塊哈希值集合S,對(duì)于任意數(shù)據(jù)塊b,其哈希值h=H(b),則有:

其中,輸出結(jié)果1 代表數(shù)據(jù)塊為重復(fù)數(shù)據(jù);輸出結(jié)果0 代表數(shù)據(jù)塊為非重復(fù)數(shù)據(jù)塊.此時(shí),則有:

下面,我們將具體介紹方法細(xì)節(jié).

2.1 邊界匹配數(shù)據(jù)塊切分

如圖3(a)所示:由于存在對(duì)文件層數(shù)據(jù)的插入、修改、刪除等操作,會(huì)導(dǎo)致邊界漂移問題的出現(xiàn)[7],固定長度分塊算法無法滿足準(zhǔn)確切分冗余數(shù)據(jù)塊的需求.為此,我們需要一種能夠有效識(shí)別數(shù)據(jù)塊邊界的可變長度數(shù)據(jù)塊切分方法,如圖3(b)所示.為實(shí)現(xiàn)上述目標(biāo),我們首先采用一種與邊界相關(guān)的指紋算法計(jì)算滑動(dòng)窗口內(nèi)數(shù)據(jù)指紋,再通過特定條件加以遴選,確定邊界符合條件的數(shù)據(jù)塊.

Fig.3 Data chunking diagram圖3 數(shù)據(jù)塊切分示意圖

本文中我們采用Rabin 指紋算法[8].Rabin 指紋算法是一種邊界相關(guān)的指紋算法,其實(shí)現(xiàn)如下:給定n位的數(shù)據(jù)m0,m1,…,mn-1,我們將其視作在有限域上度為n-1 的多項(xiàng)式:

選擇一個(gè)度為k的不可約多項(xiàng)式p(x),數(shù)據(jù)指紋通過公式(3)計(jì)算:

給定整數(shù)m,n,若滿足公式(4),則視為滿足邊界條件:

基于邊界匹配的數(shù)據(jù)塊切分方法如圖4 所示.我們假定滑動(dòng)大小為W,移動(dòng)步長為s,最大數(shù)據(jù)塊大小為M.從位置0 開始,通過公式(4)判斷滑動(dòng)窗口內(nèi)數(shù)據(jù)[0,W]是否滿足邊界條件:若滿足,則將進(jìn)行切分;若不滿足,則按步長移動(dòng)滑動(dòng)窗口至新位置ns,直至滑動(dòng)窗口內(nèi)數(shù)據(jù)滿足邊界條件,則將[0,ns]數(shù)據(jù)和[ns,ns+W]數(shù)據(jù)分別切分為數(shù)據(jù)塊.移動(dòng)步長超過最大數(shù)據(jù)塊大小M,則將[0,M]數(shù)據(jù)切分為數(shù)據(jù)塊,并將位置M重置為起始位置0.

Fig.4 Boundary matching based chunking method diagram圖4 基于邊界匹配的數(shù)據(jù)塊切分方法示意圖

2.2 B-樹數(shù)據(jù)指紋搜索

我們通過比較數(shù)據(jù)塊指紋是否相同,來判斷數(shù)據(jù)塊是否為重復(fù)數(shù)據(jù).由于Rabin 指紋算法散列值的空間較小,容易產(chǎn)生哈希沖突,為避免哈希沖突,我們使用SHA-1 算法重新計(jì)算每個(gè)數(shù)據(jù)塊的指紋,并將該數(shù)據(jù)塊對(duì)應(yīng)指紋存儲(chǔ)到指紋庫中.容器鏡像切分后將產(chǎn)生大量數(shù)據(jù)指紋,以數(shù)據(jù)塊平均大小為4KB 計(jì)算,1TB 鏡像數(shù)據(jù)切分后,將產(chǎn)生2.7×108條數(shù)據(jù).在數(shù)據(jù)條目多的情況下,散列表將出現(xiàn)大量哈希沖突,嚴(yán)重影響搜索效率.因此,我們選擇搜索復(fù)雜度為O[log2N]的B-樹結(jié)構(gòu)進(jìn)行存儲(chǔ).另外,散列表的一般利用率約為50%,由于指紋庫數(shù)據(jù)量較大,會(huì)浪費(fèi)大量的存儲(chǔ)空間.

B-樹是平衡多路查找樹.樹節(jié)點(diǎn)結(jié)構(gòu)設(shè)計(jì)如圖5 所示,節(jié)點(diǎn)記錄了數(shù)據(jù)塊對(duì)應(yīng)的SHA-1 值、數(shù)據(jù)塊存儲(chǔ)的物理地址(physical address)、數(shù)據(jù)塊相對(duì)于物理地址的偏移量(offset)和數(shù)據(jù)塊長度等信息(length).其中,SHA-1值作為節(jié)點(diǎn)的關(guān)鍵字(key),用于數(shù)據(jù)指紋的查找和比對(duì).一棵m階的B-樹中,每個(gè)結(jié)點(diǎn)最多含有m個(gè)子節(jié)點(diǎn)(m≥2),除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外,其他每個(gè)結(jié)點(diǎn)至少有[m-2]個(gè)孩子,每個(gè)非葉子結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息和n+1 個(gè)指針信息:(n,P0,P1,K1,…,Pn,Kn).其中,([m/2]-1)≤n≤(m-1);Ki(i=1,…,n)為關(guān)鍵字,且滿足Ki～1＜Ki;Pi為指向子樹指針,且指針Pi～1指向子樹所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki,大于Ki～1.

Fig.5 Information of B-tree node圖5 B-樹節(jié)點(diǎn)信息

由于指紋數(shù)據(jù)量大,無法全部加載到內(nèi)存中,降低指紋搜索復(fù)雜度可以有效減少磁盤I/O,提高搜索效率.我們?nèi)〉脭?shù)據(jù)塊指紋之后,在基于B-樹的指紋庫中進(jìn)行搜索,其搜索過程等價(jià)于在指紋全集中做一次二分查找.查找過程中,如果指紋存在,則該數(shù)據(jù)塊為重復(fù)數(shù)據(jù)塊,可不用重復(fù)加載;如果指紋不存在,則該數(shù)據(jù)塊為非重復(fù)數(shù)據(jù)塊,需要進(jìn)行加載.

2.3 策略決策

對(duì)鏡像數(shù)據(jù)進(jìn)行分片處理,可以降低重復(fù)數(shù)據(jù)加載.但同時(shí),由于增加了一些額外的系統(tǒng)開銷(如數(shù)據(jù)塊切分、指紋計(jì)算、指紋搜索等),這在一定程度上可能會(huì)影響系統(tǒng)效率[9].考慮兩種極端情況:一是當(dāng)重復(fù)數(shù)據(jù)為0的情況,系統(tǒng)非但沒有達(dá)到減少數(shù)據(jù)加載量的目的,還白白增加了額外系統(tǒng)開銷;二是當(dāng)重復(fù)數(shù)據(jù)為100%的情況下,額外系統(tǒng)開銷沒有發(fā)生變化,而網(wǎng)絡(luò)數(shù)據(jù)傳輸量則減少為0.大多數(shù)時(shí)候系統(tǒng)處于這兩種極端情況之間,因此我們需要在基于重復(fù)數(shù)據(jù)刪除技術(shù)的鏡像數(shù)據(jù)分片復(fù)用加載方法和原生鏡像加載方法之間做權(quán)衡.

我們就利用決策樹對(duì)鏡像加載方法進(jìn)行選擇.容器鏡像集中存儲(chǔ)在容器庫(repository)中,宿主機(jī)發(fā)送鏡像加載請(qǐng)求后,鏡像庫服務(wù)器根據(jù)請(qǐng)求內(nèi)容進(jìn)行反饋.為應(yīng)用本文提出的方法,我們對(duì)傳統(tǒng)的鏡像加載流程進(jìn)行改造,如圖6 所示.在宿主機(jī)和鏡像庫服務(wù)器上分別放置一個(gè)Agent 用于監(jiān)測和計(jì)算系統(tǒng)當(dāng)前各資源使用狀態(tài)和鏡像情況等信息,用于作為決策樹判斷的依據(jù).發(fā)起請(qǐng)求時(shí),宿主機(jī)將Agent 收集到的信息一并發(fā)送至鏡像庫服務(wù)器,鏡像庫服務(wù)器將宿主機(jī)發(fā)送來的信息和本機(jī)Agent 上收集的信息發(fā)送給決策樹,由決策樹判定采用何種加載方法.確定之后,系統(tǒng)將根據(jù)所確定的方法傳輸相應(yīng)的數(shù)據(jù)到宿主機(jī),宿主機(jī)根據(jù)接收到的數(shù)據(jù)類型重組鏡像,從而完成整個(gè)加載流程.

Fig.6 Decision tree based image load diagram圖6 基于決策樹的鏡像加載示意圖

決策樹構(gòu)建需要選擇對(duì)加載過程產(chǎn)生影響的因子作為特征值,我們從以下幾個(gè)方面選取.

1)數(shù)據(jù)方面.數(shù)據(jù)方面影響因子包括數(shù)據(jù)大小(S)和去冗余率(r),鏡像加載過程中的網(wǎng)絡(luò)傳輸數(shù)據(jù)量可以根據(jù)以上兩個(gè)因子計(jì)算得出;

2)網(wǎng)絡(luò)方面.鏡像通過網(wǎng)絡(luò)從鏡像庫加載到宿主機(jī),因此選取網(wǎng)絡(luò)傳輸速度(ns)作為決策樹特征值;

3)磁盤方面.鏡像庫磁盤讀取速度(R)和宿主機(jī)端磁盤寫速度(W)影響鏡像數(shù)據(jù)加載過程,因此選擇這兩個(gè)屬性作為特征值;

4)內(nèi)存方面.鏡像傳輸和B-樹查找都是內(nèi)存密集型運(yùn)算,我們使用可用內(nèi)存大小(Ma)和指紋庫數(shù)據(jù)大小(A)之間的比值作為決策樹特征值;

5)CPU 方面.CPU 在數(shù)據(jù)塊指紋計(jì)算方面發(fā)揮重要作用,直接影響加載效率,因此選擇CPU 利用率、payload 和real-time 這3 個(gè)指標(biāo)作為特征值;

6)其他方面.在分布式系統(tǒng)中,系統(tǒng)負(fù)載經(jīng)常發(fā)生變化,因此我們需要加以考慮.由于系統(tǒng)負(fù)載難以刻畫,而系統(tǒng)負(fù)載通常隨時(shí)間變化產(chǎn)生周期性變化,因此我們采用時(shí)間(t)作為特征值.

假設(shè)訓(xùn)練決策樹的樣本數(shù)據(jù)集為D,決策樹的輸出有兩種,分別為基于重復(fù)數(shù)據(jù)刪除的鏡像加載和原生鏡像加載方法.在構(gòu)建決策樹時(shí),選擇某個(gè)特征值作為樹的節(jié)點(diǎn).根據(jù)信息論,計(jì)算出該數(shù)據(jù)中的信息熵:

其中,Pi表示類別為i樣本數(shù)量占所有樣本的比例.在特征A作用下的信息熵計(jì)算公式如下:

其中,k表示樣本D分為k個(gè)部分.數(shù)據(jù)集D在特征A的作用下信息熵減少的值為信息增益,計(jì)算公式如下:

利用訓(xùn)練樣本數(shù)據(jù)集,根據(jù)上述公式即可構(gòu)建決策樹.

2.4 方法開銷

我們?cè)谠椒ǖ幕A(chǔ)上增加了數(shù)據(jù)塊級(jí)別重復(fù)數(shù)據(jù)刪除方法和基于決策樹的策略決策方法,因此相比原生方法會(huì)產(chǎn)生額外的開銷.本節(jié)我們分別分析兩種方法對(duì)系統(tǒng)性能產(chǎn)生的影響.

數(shù)據(jù)塊級(jí)別重復(fù)數(shù)據(jù)刪除方法主要由3 個(gè)子任務(wù)構(gòu)成.

1)數(shù)據(jù)分塊及指紋計(jì)算.將鏡像劃分為不同數(shù)據(jù)塊并計(jì)算數(shù)據(jù)塊指紋.該操作為CPU 敏感型操作,在服務(wù)器和客戶端分別執(zhí)行;

2)數(shù)據(jù)塊指紋查找.在指紋庫中查找數(shù)據(jù)塊指紋及數(shù)據(jù)塊存儲(chǔ)地址,用于判斷該數(shù)據(jù)塊是否已存在和確定數(shù)據(jù)塊的讀取位置.該操作為內(nèi)存敏感型操作,在服務(wù)器和客戶端分別執(zhí)行.由于服務(wù)器端指紋庫遠(yuǎn)大于客戶端指紋庫,因此資源消耗更多;

3)網(wǎng)絡(luò)傳輸.將數(shù)據(jù)從服務(wù)器發(fā)送到客戶端,該操作為網(wǎng)絡(luò)敏感型操作.由于只需要發(fā)送發(fā)生變化的數(shù)據(jù)塊,相比鏡像整體傳輸網(wǎng)絡(luò)資源占用會(huì)變小.

從以上分析中可以看出:采用數(shù)據(jù)塊級(jí)別重復(fù)數(shù)據(jù)刪除方法進(jìn)行鏡像加載,在降低網(wǎng)絡(luò)負(fù)擔(dān)的同時(shí)增加了額外的操作.本文中,我們主要關(guān)注任務(wù)的完成時(shí)間,所以我們從任務(wù)時(shí)間成本出發(fā),提出了基于決策樹的策略決策方法,用于對(duì)特定的鏡像選擇合適的加載策略.

基于決策樹的策略決策方法的建模過程為離線操作,其開銷不在本文討論范圍內(nèi)之內(nèi).在運(yùn)行過程中,其主要開銷應(yīng)為Agent 對(duì)系統(tǒng)資源使用狀態(tài)監(jiān)測,然而資源監(jiān)控是數(shù)據(jù)中心運(yùn)維的一項(xiàng)重要功能,系統(tǒng)只需要調(diào)用運(yùn)維監(jiān)控系統(tǒng)的數(shù)據(jù)即可完成數(shù)據(jù)指標(biāo)采集.在結(jié)果計(jì)算過程中,決策時(shí)間為毫秒級(jí),在本文中,我們視為可以忽略.

3 實(shí)驗(yàn)驗(yàn)證

我們?cè)贒ocker 1.9.1 版本和Docker Register V2 版本上實(shí)現(xiàn)了基于重復(fù)數(shù)據(jù)刪除技術(shù)的鏡像數(shù)據(jù)分片復(fù)用加載方法,本節(jié)我們通過實(shí)驗(yàn)驗(yàn)證方法的有效性和穩(wěn)定性.

3.1 實(shí)驗(yàn)設(shè)置

通過實(shí)驗(yàn),我們首先驗(yàn)證邊界匹配數(shù)據(jù)塊切分方法去冗余的有效性,然后將基于重復(fù)數(shù)據(jù)刪除技術(shù)的鏡像加載方法與原生鏡像加載方法進(jìn)行對(duì)比,最后驗(yàn)證數(shù)據(jù)規(guī)模不斷擴(kuò)大情況下方法的穩(wěn)定性.

實(shí)驗(yàn)中,我們采用5 臺(tái)刀片服務(wù)器作為實(shí)驗(yàn)設(shè)備,每臺(tái)服務(wù)器擁有兩顆Intel Xeno E5645 CPU,600GB 硬盤和32GB 內(nèi)存.其中,4 臺(tái)作為宿主機(jī),一臺(tái)作為鏡像庫服務(wù)器.鏡像庫存儲(chǔ)采用10TB 空間的存儲(chǔ)集群.所有設(shè)備通過千兆網(wǎng)絡(luò)設(shè)備進(jìn)行連接.

我們從OnceCloud[10]云平臺(tái)中選取大小不同(100MB～500MB)的10 種不同類型的鏡像,并通過模擬升級(jí)的方式進(jìn)行獨(dú)立演化.針對(duì)每個(gè)鏡像我們模擬了100 個(gè)升級(jí)版本,版本間數(shù)據(jù)變化率設(shè)置為0.1%～10%,其中,新增數(shù)據(jù)和修改數(shù)據(jù)比例為1:1.實(shí)驗(yàn)中所涉及的數(shù)據(jù)變化率和重復(fù)數(shù)據(jù)率,均指鏡像最上層文件發(fā)生的數(shù)據(jù)變化.實(shí)驗(yàn)用總數(shù)據(jù)量約為200GB.數(shù)據(jù)塊切分時(shí),滑動(dòng)窗口大小設(shè)為4KB,移動(dòng)步長設(shè)為512B,最大數(shù)據(jù)塊大小為8KB.宿主機(jī)上采用Device Mapper 作為Docker 存儲(chǔ)驅(qū)動(dòng).

3.2 重復(fù)數(shù)據(jù)識(shí)別率

重復(fù)數(shù)據(jù)識(shí)別率是衡量數(shù)據(jù)塊切分方法有效性的重要指標(biāo),高重復(fù)數(shù)據(jù)識(shí)別率表示數(shù)據(jù)塊切分方法更加有效,在鏡像加載過程中可以更大限度減少網(wǎng)絡(luò)傳輸開銷.我們采用邊界匹配數(shù)據(jù)塊切分方法對(duì)實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行切分并查找重復(fù)數(shù)據(jù),以鏡像類型和數(shù)據(jù)變化率兩個(gè)維度對(duì)切分結(jié)果進(jìn)行統(tǒng)計(jì),統(tǒng)計(jì)結(jié)果分別如圖7 和圖8所示.

Fig.7 Real duplication rate vs.deduplication rate圖7 實(shí)際重復(fù)數(shù)據(jù)率與重復(fù)數(shù)據(jù)識(shí)別率對(duì)比

Fig.8 Relationship between real data change rate and recognition data change rate圖8 實(shí)際數(shù)據(jù)變化率與識(shí)別數(shù)據(jù)變化率對(duì)比

圖7 所示為按鏡像類型進(jìn)行統(tǒng)計(jì)的結(jié)果,其中,橫軸代表10 個(gè)不同類型的版本,縱軸代表冗余數(shù)據(jù)率.圖中黑色圖例(real rate)表示同種鏡像不同版本的真實(shí)重復(fù)數(shù)據(jù)率的平均值,白色圖例(dedup rate)表示通過數(shù)據(jù)塊切分后重復(fù)數(shù)據(jù)識(shí)別率的平均值.從圖中我們可以看出:真實(shí)重復(fù)數(shù)據(jù)率與重復(fù)數(shù)據(jù)識(shí)別率的最大相差11.4%(圖中第2 個(gè)鏡像),最小為5.3%(圖中第6 個(gè)鏡像),平均相差7.6%.這說明邊界匹配數(shù)據(jù)塊切分方法能夠很好的識(shí)別重復(fù)數(shù)據(jù),可以有效應(yīng)用于鏡像分片復(fù)用加載.

圖8 所示為按鏡像數(shù)據(jù)更新率進(jìn)行統(tǒng)計(jì)的結(jié)果,其中,橫軸表示真實(shí)數(shù)據(jù)變化率,recognition rate 圖例表示重復(fù)數(shù)據(jù)識(shí)別方法識(shí)別出的數(shù)據(jù)變化率,diff rate 圖例表示識(shí)別數(shù)據(jù)變化率與真實(shí)數(shù)據(jù)變化率之間的差值.從圖中我們可以看出:(1) 隨著數(shù)據(jù)變化率不斷增大,識(shí)別數(shù)據(jù)變化率也隨之增加,其識(shí)別數(shù)據(jù)變化率始終大于真實(shí)數(shù)據(jù)變化率,這是因?yàn)槲覀兯玫溺R像不存在內(nèi)部重復(fù)數(shù)據(jù)[11],且每次版本更新與之前,版本沒有相同的數(shù)據(jù)塊;(2) 隨著數(shù)據(jù)變化率不斷增大,識(shí)別數(shù)據(jù)變化率與真實(shí)數(shù)據(jù)變化率之間的差值也在不斷增大.但當(dāng)數(shù)據(jù)變化率增大到一定程度時(shí),該值變化趨于穩(wěn)定,其波動(dòng)范圍在6%～8%之間.實(shí)驗(yàn)結(jié)果表明:邊界匹配數(shù)據(jù)塊切分方法能在5.3%～11.4%誤差范圍內(nèi)識(shí)別重復(fù)數(shù)據(jù),且受到數(shù)據(jù)變化率的影響較小,證明方法具有較好的有效性和穩(wěn)定性.

3.3 加載效率

我們通過實(shí)際系統(tǒng)測試對(duì)比基于重復(fù)數(shù)據(jù)分片復(fù)用加載方法和原生加載方法的加載效率,實(shí)驗(yàn)結(jié)果以鏡像類型和數(shù)據(jù)變化率兩個(gè)維度進(jìn)行統(tǒng)計(jì),結(jié)果分別如圖9 和圖10 所示.我們將原生加載方法的加載速度作為基準(zhǔn),考察基于重復(fù)數(shù)據(jù)分片復(fù)用加載方法的加載速度與原生加載方法加載速度的比值,即方法的加速比,圖中用Speed Factor 表示.

Fig.9 Average speed factor of different image types圖9 不同類型鏡像平均加載比

Fig.10 Relationship between real data change rate and recognition data change rate圖10 實(shí)際數(shù)據(jù)變化率與識(shí)別數(shù)據(jù)變化率對(duì)比

圖9 所示為不同鏡像類型各版本的平均加速比,其中,橫軸代表10 個(gè)不同類型的版本,縱軸代表方法的加速比.從圖中我們可以看出:基于重復(fù)數(shù)據(jù)分片復(fù)用加載方法平均可以提高7X 左右的加載速度,最高平均可提高7.82X 的加載速度,最低平均可提高6.25X 的加載速度.

圖10 所示為不同鏡像更新率下方法的加速比,其中,橫軸代表不同的鏡像更新率,縱軸代表方法加速比.從圖中我們可以看出:當(dāng)鏡像更新率小于0.2%時(shí),方法可以達(dá)到300X～700X 的加速比;當(dāng)鏡像更新率在4%左右時(shí),方法可以達(dá)到10X 以上的加速比;當(dāng)鏡像更新率為10%時(shí),方法加速比約為5.8X.方法的加速比隨著鏡像更新率的不斷提高而逐漸減小.這是因?yàn)殓R像更新率越高,鏡像不同版本之間的重復(fù)數(shù)據(jù)越少,可復(fù)用的數(shù)據(jù)越少,鏡像加載時(shí)通過網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)就越多.

實(shí)驗(yàn)結(jié)果表明,基于重復(fù)數(shù)據(jù)分片復(fù)用加載方法可以有效提高鏡像加載效率.

3.4 指紋查找時(shí)間

在前面的實(shí)驗(yàn)中,我們假設(shè)內(nèi)存足夠大可以加載整個(gè)數(shù)據(jù)塊指紋庫,但在實(shí)際系統(tǒng)中,數(shù)據(jù)塊指紋庫會(huì)隨著鏡像的增多而不斷增大.我們采用SHA-1 散列值作為數(shù)據(jù)塊指紋,每個(gè)數(shù)據(jù)塊指紋大小為20B.按平均每個(gè)數(shù)據(jù)塊大小為4KB 計(jì)算,20GB 非重復(fù)數(shù)據(jù)對(duì)應(yīng)的指紋庫大小為100MB.我們通過實(shí)驗(yàn)的方式驗(yàn)證當(dāng)可用內(nèi)存大小超出指紋庫大小時(shí),指紋查找的效率.我們將可用內(nèi)存大小設(shè)置為100MB,數(shù)據(jù)塊指紋庫大小從100MB 遞增到500MB.我們選取一個(gè)大小為200MB 的容器鏡像的指紋序列(約為5 000 條指紋)進(jìn)行指紋搜索操作,記錄不同指紋庫大小時(shí)查詢操作所需要的時(shí)間.

實(shí)驗(yàn)結(jié)果如圖11 所示,其中,橫軸代表指紋庫大小,縱軸代表查詢操作所需要的時(shí)間.當(dāng)指紋庫大小為100MB,內(nèi)存剛好容納可以所有數(shù)據(jù)指紋時(shí),查詢操作所需要的時(shí)間為0.2s.隨著指紋庫逐漸增大,查詢操作所需要的時(shí)間也隨之增加.當(dāng)指紋庫大小為500MB 時(shí),查詢操作所需要的時(shí)間約為8s.實(shí)驗(yàn)結(jié)果表明:當(dāng)可用內(nèi)存大于指紋庫時(shí),指紋查找時(shí)間可用忽略不計(jì);但當(dāng)可用內(nèi)存小于指紋庫時(shí),指紋查找時(shí)間顯著增加,可能會(huì)影響方法的效率.若指紋查找時(shí)間超過分片復(fù)用加載方法所帶來的的時(shí)間收益時(shí),本文方法反而會(huì)使加載過程變慢.

Fig.11 Relationship between fingerprint repository size and search time圖11 指紋庫大小與查找時(shí)間的關(guān)系

3.5 策略決策比例

圖12 所示為實(shí)驗(yàn)過程中經(jīng)過策略決策后所采用的兩種加載方法所占的比例,其中,橫軸代表10 個(gè)不同類型的鏡像版本,縱軸代表兩種方法在經(jīng)過決策后所占在比例.圖中黑色圖例代表采用基于重復(fù)數(shù)據(jù)刪除技術(shù)加載方法所占的比例,白色圖例代表采用原生鏡像加載方法所占的比例.從圖中我們可以看出:本文提出的基于重復(fù)數(shù)據(jù)刪除技術(shù)的鏡像加載方法所占最小的比例約為86.2%,最大比例約為88.8%,平均比例約為87.8%;而原生鏡像加載方法所占最小比例約為11.2%,最大比例約為13.8%,平均比例約為12.2%.

Fig.12 Ratio of the two loading methods圖12 兩種加載方法所占比例

實(shí)驗(yàn)結(jié)果表明:本文提出的基于重復(fù)數(shù)據(jù)刪除技術(shù)的鏡像加載方法可以有效應(yīng)對(duì)多版本鏡像升級(jí)這一使用場景,提高升級(jí)版本鏡像的加載效率.

4 相關(guān)工作

如何提高Docker 鏡像加載效率,已成為一個(gè)熱點(diǎn)研究問題[12].為解決該問題,研究人員針對(duì)不同的場景提出了不同的解決方案.Wang 等人[13]針對(duì)大規(guī)模鏡像加載并發(fā)沖突問題,提出了基于P2P 的鏡像加載解決方案.Liang 等人[14]將P2P 加載方法和原生鏡像加載方法相結(jié)合,提出了一種混合鏡像加載方法.基于P2P 的鏡像加載方法充分利用了節(jié)點(diǎn)間的網(wǎng)絡(luò)帶寬,提高了鏡像加速效率.Du 等人[15]使用Ceph 作為共享存儲(chǔ),利用Ceph 提供的快照克隆等功能,來提高不同節(jié)點(diǎn)之間鏡像加載效率.以上方法提高了特定情況下的鏡像加載效率,但鏡像加載所需要的網(wǎng)絡(luò)數(shù)據(jù)傳輸總量沒有變化.Harter 等人[16]將共享存儲(chǔ)和重復(fù)數(shù)據(jù)刪除技術(shù)相結(jié)合,提出了Slacker平臺(tái).Slacker 基于共享的NFS 文件系統(tǒng),在所有節(jié)點(diǎn)和Registry 之間共享鏡像.這種懶加載方式可以大大提高鏡像加載效率,然而為了便于快照和克隆,Slacker 需要將Docker 鏡像扁平化為單獨(dú)一層,這與Docker 方便創(chuàng)建和更新鏡像的設(shè)計(jì)理念相沖突.本文僅針對(duì)鏡像升級(jí)這一特殊卻又廣泛存在的使用場景,提出利用重復(fù)數(shù)據(jù)刪除技術(shù)進(jìn)行鏡像加載,同時(shí)考慮到方法開銷與收益的平衡,又提出利用決策樹進(jìn)行方法選擇.與上述方法相比,本文方法在鏡像升級(jí)這一應(yīng)用場景下,可以有效降低網(wǎng)絡(luò)數(shù)據(jù)傳輸,提高鏡像加載效率.

重復(fù)數(shù)據(jù)刪除技術(shù)[17,18]本質(zhì)上是一種數(shù)據(jù)壓縮技術(shù),可以用于消除單個(gè)或多個(gè)數(shù)據(jù)文件中的重復(fù)數(shù)據(jù),保證相同的數(shù)據(jù)只存儲(chǔ)一份,以達(dá)到降低存儲(chǔ)空間和傳輸開銷的目的.按照去冗余數(shù)據(jù)單元粒度劃分,可以將去冗余方法分為文件級(jí)別去冗余[6]和數(shù)據(jù)塊級(jí)別去冗余[18]:文件級(jí)別去冗余首先計(jì)算文件的哈希值作為文件指紋,然后與指紋庫中的哈希值進(jìn)行比較判斷文件是否重復(fù);數(shù)據(jù)塊級(jí)別去冗余首先將數(shù)據(jù)切分粒度較小的數(shù)據(jù)塊,計(jì)算每個(gè)數(shù)據(jù)塊的哈希值,與指紋庫中的哈希值進(jìn)行比較,來判斷數(shù)據(jù)塊是否重復(fù).數(shù)據(jù)塊切分方法可以分為兩種:一種是固定長度切分方法[5,18,19],一種是可變長度切分方法[20-22].本文采用的是可變長度分塊方法.Policroniades 等人[23]對(duì)文件哈希、固定長度哈希和可變長度哈希算法進(jìn)行了比較,實(shí)驗(yàn)結(jié)果顯示,三者對(duì)相同大小數(shù)據(jù)進(jìn)行處理的時(shí)間分別為62s,71s 和340s.可見,可變長度切分去冗余將大大提高操作的時(shí)間復(fù)雜度.

重復(fù)數(shù)據(jù)刪除技術(shù)可以應(yīng)用于數(shù)據(jù)備份、數(shù)據(jù)遷移、文件系統(tǒng)管理等多種不同場景.Fu 等人提出的應(yīng)用感知的數(shù)據(jù)去冗余技術(shù)[24]應(yīng)用于云備份服務(wù)中,主要解決數(shù)據(jù)傳輸效率問題.該方法通過特定的索引機(jī)制,將全部索引劃分為若干相互獨(dú)立且具有典型應(yīng)用特性的組織形式,達(dá)到緩解索引查找瓶頸的目的.基于語義的源端重復(fù)數(shù)據(jù)刪除技術(shù)[25]主要用來解決備份中的數(shù)據(jù)量傳輸過高導(dǎo)致備份時(shí)間窗口長的問題,該方法通過混合重復(fù)數(shù)據(jù)刪除技術(shù)和語義層冗余數(shù)據(jù)消除技術(shù)來降低備份過程中的數(shù)據(jù)傳輸量.基于Hadoop 重復(fù)數(shù)據(jù)刪除方法[26,27]和基于固態(tài)硬盤的重復(fù)數(shù)據(jù)刪除方法[28]可以用于在特定應(yīng)用場景下加速重復(fù)數(shù)據(jù)刪除過程.Zhang 等人將重復(fù)數(shù)據(jù)刪除技術(shù)應(yīng)用到OpenStack 中,開發(fā)了虛擬機(jī)鏡像管理系統(tǒng)IM-dedup[29].該系統(tǒng)采用固定分塊的技術(shù)將虛擬機(jī)鏡像切分為大小相等的數(shù)據(jù)塊,通過使用指紋驗(yàn)證是否重復(fù)數(shù)據(jù)塊的方式,避免冗余數(shù)據(jù)塊通過網(wǎng)絡(luò)進(jìn)行重復(fù)傳輸;同時(shí),通過部署采用了去冗余技術(shù)的內(nèi)核態(tài)文件系統(tǒng)來降低存儲(chǔ)空間占用.Ng 等人開發(fā)了LiveFS 系統(tǒng)實(shí)現(xiàn)鏡像存儲(chǔ)的實(shí)時(shí)去冗余[30],降低磁盤存儲(chǔ)空間使用.分布式多層次選擇去冗余[31]系統(tǒng)在Inner-VM 去冗余階段實(shí)現(xiàn)虛擬機(jī)內(nèi)部數(shù)據(jù)塊級(jí)重復(fù)數(shù)據(jù)刪除,在Cross-VM 去冗余階段,針對(duì)不同類型的操作系統(tǒng)進(jìn)行分組,對(duì)分組內(nèi)的虛擬機(jī)鏡像進(jìn)行去冗余,因而可以利用較小的內(nèi)存空間完成指紋查找過程.Zhang 等人[32-34]將重復(fù)數(shù)據(jù)刪除技術(shù)應(yīng)用于虛擬機(jī)遷移過程中,通過數(shù)據(jù)指紋發(fā)現(xiàn)相同內(nèi)存頁,減少遷移內(nèi)存數(shù)據(jù)量.由于需要解決尖峰負(fù)載、即時(shí)失效、集群維護(hù)等問題,數(shù)據(jù)中心可能會(huì)面臨虛擬機(jī)組遷移(gang migration)的問題.不同宿主機(jī)內(nèi)存中可能存在大量相同的內(nèi)存頁,Deshprade 等人提出了集群范圍內(nèi)去冗余方案(GMGD)[35],方法通過一種冗余跟蹤機(jī)制對(duì)不同虛擬機(jī)中的相同內(nèi)存頁進(jìn)行跟蹤,利用一種分布式協(xié)調(diào)機(jī)制阻止相同的數(shù)據(jù)塊通過核心鏈路進(jìn)行重新發(fā)送.

5 總結(jié)

將重復(fù)數(shù)據(jù)刪除技術(shù)用于容器鏡像加載,可以提高容器鏡像加載速度.容器鏡像采用聯(lián)合文件系統(tǒng)技術(shù)實(shí)現(xiàn)了可以實(shí)現(xiàn)文件層級(jí)別的數(shù)據(jù)復(fù)用.由于以文件層為單位進(jìn)行劃分粒度較粗,無法實(shí)現(xiàn)對(duì)同一文件層內(nèi)部重復(fù)數(shù)據(jù)的復(fù)用.在鏡像版本升級(jí)時(shí),復(fù)用文件層內(nèi)部數(shù)據(jù)可以有效提高鏡像加載效率.我們提出一種基于重復(fù)數(shù)據(jù)刪除技術(shù)的鏡像數(shù)據(jù)分片復(fù)用加載方法提高原生容器鏡像加載過程,利用邊界匹配數(shù)據(jù)塊切分方法和B-樹搜索發(fā)現(xiàn)重復(fù)數(shù)據(jù)塊并加以復(fù)用.由于重復(fù)數(shù)據(jù)刪除技術(shù)需要一定的資源開銷,在實(shí)際使用中需要平衡方法的收益與開銷,以達(dá)到最優(yōu)效果.為此,我們利用決策樹選擇合適的加載方法.實(shí)驗(yàn)結(jié)果顯示:我們的方法穩(wěn)定有效,可以提高5.8X 以上的鏡像加載速度.在今后的工作中,我們將繼續(xù)優(yōu)化該方法,并在實(shí)際系統(tǒng)中檢驗(yàn)方法的穩(wěn)定性和有效性.