一種基于文件相似性分簇的重復(fù)數(shù)據(jù)消除模型

一種基于文件相似性分簇的重復(fù)數(shù)據(jù)消除模型

0重復(fù)數(shù)據(jù)消除近年來，隨著各種新興網(wǎng)絡(luò)應(yīng)用的快速發(fā)展，電子數(shù)據(jù)產(chǎn)量顯著增加：2007年新增電子數(shù)據(jù)總量為281eb，2011年新增數(shù)據(jù)總量超過10倍。與此同時(shí),對(duì)存儲(chǔ)服務(wù)精細(xì)化和即時(shí)性的要求也不斷提高。這使得基于云存儲(chǔ)的備份應(yīng)用成為信息存儲(chǔ)領(lǐng)域的熱點(diǎn)。重復(fù)數(shù)據(jù)消除技術(shù)是云存儲(chǔ)應(yīng)用中一種重要的存儲(chǔ)優(yōu)化技術(shù),利用數(shù)據(jù)對(duì)象之間的信息冗余,可以獲得遠(yuǎn)高于傳統(tǒng)壓縮方法及增量備份方法的空間利用率。該技術(shù)將數(shù)據(jù)對(duì)象劃分為連續(xù)的、互不交疊的分塊,計(jì)算每個(gè)分塊的哈希值作為其唯一標(biāo)志符,并將其存入到分塊索引表中。數(shù)據(jù)對(duì)象被表示成各分塊標(biāo)志符按順序連接在一起的哈希鏈,并以分塊為單位進(jìn)行存儲(chǔ)。每當(dāng)寫入新數(shù)據(jù)對(duì)象時(shí),用該數(shù)據(jù)對(duì)象的各分塊標(biāo)志符在索引表中進(jìn)行分塊存在性查詢,并只存儲(chǔ)那些新的分塊及其標(biāo)志符。由于重復(fù)的數(shù)據(jù)分塊不再多次存儲(chǔ)和傳送,因此可以大幅度減小存儲(chǔ)空間占用量和遠(yuǎn)程傳送時(shí)的流量負(fù)載。根據(jù)重復(fù)數(shù)據(jù)消除是在備份數(shù)據(jù)寫入磁盤之前進(jìn)行還是寫入磁盤之后進(jìn)行,可以分為在線和離線兩種方式。在線方式的優(yōu)點(diǎn)是不需要額外的磁盤空間來緩存待處理的數(shù)據(jù),但在線重復(fù)數(shù)據(jù)消除在大規(guī)模應(yīng)用環(huán)境下如果不能有效解決磁盤瓶頸問題,會(huì)嚴(yán)重降低重復(fù)數(shù)據(jù)消除系統(tǒng)的吞吐量?，F(xiàn)有解決該問題的方法主要有bloomfilters、localitypreservedcaching(LPC)和sparseindexing,其中前兩種方法被綜合應(yīng)用在datadomain系統(tǒng)中,以提高系統(tǒng)的吞吐量。但datadomain和sparseindexing都要求數(shù)據(jù)具有很強(qiáng)的局部性才能獲得好的性能。而在云存儲(chǔ)備份應(yīng)用中,數(shù)據(jù)常常缺乏局部性,這種情況下,現(xiàn)有方法的吞吐量或重復(fù)數(shù)據(jù)消除性能會(huì)嚴(yán)重降低。為了提高重復(fù)數(shù)據(jù)消除系統(tǒng)的并行性,從而獲得更高的整體吞吐量,常采用DHT方法對(duì)分塊索引分片,并將分片分布到多個(gè)存儲(chǔ)節(jié)點(diǎn)上。但該方法中,一個(gè)數(shù)據(jù)對(duì)象的重復(fù)數(shù)據(jù)消除操作通常會(huì)涉及到多個(gè)節(jié)點(diǎn),各節(jié)點(diǎn)不能實(shí)現(xiàn)自治管理。為解決現(xiàn)有方法存在的問題,提出一種基于文件相似性分簇的重復(fù)數(shù)據(jù)消除模型(FCDM)。為后文敘述方便,提供縮略語對(duì)照表如表1所示。1問題描述1.1存儲(chǔ)機(jī)制chunkid傳統(tǒng)的重復(fù)數(shù)據(jù)消除系統(tǒng)中,為了實(shí)現(xiàn)快速的CEQ,所有非重復(fù)的chunk都對(duì)應(yīng)HTID中一條記錄,這種結(jié)構(gòu)稱為平面型的HTID。隨著數(shù)據(jù)規(guī)模的增大,平面型HTID的大小迅速增加,使得HTID不能全部裝入內(nèi)存,需要分頁到磁盤上保存。由于哈希函數(shù)的特性,chunkID可以看做是隨機(jī)均勻分布的,因此傳統(tǒng)方法無法有效緩存,這就導(dǎo)致幾乎每次CEQ都會(huì)引發(fā)磁盤訪問,嚴(yán)重降低了吞吐量。Datadomain用LPC技術(shù)成批地存儲(chǔ)和預(yù)取那些可能會(huì)被一起訪問概率很高的chunkID,并用bloomfilters技術(shù)快速判斷新chunk。Sparseindexing將chunk融合為更大的分段,量級(jí)為10MB左右,重復(fù)chunk的檢測(cè)在分段一級(jí)完成,檢索源僅為挑選出的與待處理分段相似程度很高的少量分段。在具有顯著局部性特征的傳統(tǒng)備份負(fù)載下,這兩種方法能夠有效提高系統(tǒng)吞吐量。1.2備份負(fù)載的特性傳統(tǒng)的備份負(fù)載通常是每天/每周將包含很多文件的目錄樹鏈接為較大的備份映像文件,因此傳統(tǒng)備份負(fù)載是由數(shù)據(jù)流組成的,其特點(diǎn)是組成備份負(fù)載的數(shù)據(jù)對(duì)象較大,通常為GB級(jí)。由于同一目錄下的文件在鄰近的備份版本之間變動(dòng)很小,并且?guī)缀跏且韵嗤捻樞虺霈F(xiàn)的,因此鄰近的備份數(shù)據(jù)流之間有大段的重復(fù)數(shù)據(jù)。換而言之,如果本次備份數(shù)據(jù)流中A、B、C三個(gè)文件的chunk是按照該順序出現(xiàn)的,那么在下一次備份數(shù)據(jù)流中如果A的chunk出現(xiàn)了,隨之出現(xiàn)B和C的chunk的概率非常高。傳統(tǒng)備份負(fù)載的這一特性稱為數(shù)據(jù)的局部性。由于對(duì)服務(wù)精細(xì)化和即時(shí)性要求的提高,在很多基于云存儲(chǔ)的備份應(yīng)用中,備份負(fù)載不再是由大的數(shù)據(jù)流組成,而是由細(xì)粒度的文件組成,這些較小的數(shù)據(jù)對(duì)象來自于分散的源,并且到達(dá)的順序完全是隨機(jī)的。例如多個(gè)用戶隨機(jī)提交的以文件為單位的備份和恢復(fù)請(qǐng)求;連續(xù)數(shù)據(jù)保護(hù)應(yīng)用(CDP)中,任何文件一旦發(fā)生改變,就立即要備份。這樣,在一段時(shí)間內(nèi)到達(dá)的文件之間幾乎是沒有局部性可言的。由于datadomain和sparseindexing均依賴于數(shù)據(jù)的局部性,因此在缺乏局部性的、基于細(xì)粒度數(shù)據(jù)對(duì)象的非傳統(tǒng)備份負(fù)載下,現(xiàn)有方法的吞吐量或重復(fù)數(shù)據(jù)消除性能會(huì)嚴(yán)重降低。2算法及其算法針對(duì)以上問題,本文提出FCDM模型及其算法。FCDM是基于文件的相似性對(duì)chunk進(jìn)行分簇和管理的,下面先對(duì)文件的相似性及其判斷方法進(jìn)行說明。2.1基于內(nèi)容分塊的特征提取算法假設(shè)H為特征提取函數(shù),H(fi)為用H從文件fi中提取的特征集合,根據(jù)Jaccard集合相似度測(cè)量指標(biāo),將文件的相似度規(guī)約為其特征集的相似度,定義文件fi和fj的相似度sim(fi,fj)如下:定義1sim(fi,fj)=|H(fi)∩H(fj)||H(fi)∪H(fj)|(1)(fi,fj)=|Η(fi)∩Η(fj)||Η(fi)∪Η(fj)|(1)有多種提取文件特征的方法。本文提出一種在Forman方法基礎(chǔ)上改進(jìn)的基于內(nèi)容分塊的特征提取算法,其基本思想是:如果兩個(gè)文件有大于平均分塊長(zhǎng)度的部分是相同的,那么這兩個(gè)文件至少有一個(gè)分塊相同的概率很高。該算法是基于min-wiseindependence置換族的,其定義如下:定義2設(shè)Sn是n元集合[n]上所有置換組成的n元對(duì)稱群。稱置換族F?Sn滿足min-wiseindependence條件是指:對(duì)任意X={x1,x2,…,xm}?[n]和任意xi∈X,從集合F中隨機(jī)、均勻地選取函數(shù)h,計(jì)算H(X)={h(x1),h(x2),…,h(xm)},則有下式成立:Pr(min(H(X))=h(xi))=1|X|(2)Ρr(min(Η(X))=h(xi))=1|X|(2)換而言之,X中的所有元素在h的作用下都有相等的概率成為H(X)中的最小元。在實(shí)際應(yīng)用中,完全滿足min-wiseindependence條件的哈希函數(shù)很難實(shí)現(xiàn),通常使用近似滿足min-wiseindependence條件的。本文提出的文件特征提取算法的主要過程為:a)用基于內(nèi)容的分塊算法TTTD將fi劃分為連續(xù)、互不交疊的分塊,記為fi={c1,c2,…,cn}。b)用哈希函數(shù)h計(jì)算各分塊的chunkID,得到特征集合H(fi)={h(c1),h(c2),…,h(cn)},其中h是近似滿足min-wiseindependence條件的。2.2brpod相似度判斷對(duì)于任意給定的fi,要從文件集合F中找出與其最相似的文件,最簡(jiǎn)單和直觀的方法是將fi與?fj∈F逐一按照定義1計(jì)算sim(fi,fj)(fi,fj),并從中找出最大值。但這種方法是不可擴(kuò)展的,隨著應(yīng)用規(guī)模的擴(kuò)大,其計(jì)算開銷過大導(dǎo)致不可實(shí)施。本文設(shè)計(jì)了如下快速判斷文件相似性的方法:a)選取H(fi)中最小的元素作為fi的代表chunkID,記為rid(fi)=min(H(fi))。b)如果rid(fi)=rid(fj),則認(rèn)為文件fi和fj的相似度很高。Broder定理保證了上述相似性判斷方法的正確性,該定理如下:定理1兩集合S1和S2,H(Si)={h(xk)|?xk∈Si},h是滿足min-wiseindependence條件的哈希函數(shù),min(Si)代表集合Si中的最小元,則Pr(min(H(S1))=min(H(S2)))=|S1∩S2||S1∪S2|(3)Ρr(min(Η(S1))=min(Η(S2)))=|S1∩S2||S1∪S2|(3)證明參見文獻(xiàn)。Broder定理說明當(dāng)h滿足min-wiseindependence條件時(shí),集合S1和S2的最小哈希元相等的概率與這兩個(gè)集合的Jaccard相似度指標(biāo)相等。結(jié)合該定理和定義1可得到如下推論:推論1sim(fi,fj)=Pr(rid(fi)=rid(fj))(4)因此如果兩個(gè)文件fi和fj的相似度很高,則它們的代表chunkID相同的概率也非常高。3基于相似性集群的重復(fù)數(shù)據(jù)解決方案在上述文件相似性快速判斷算法的基礎(chǔ)上,設(shè)計(jì)了如下所述的分層索引結(jié)構(gòu)并構(gòu)建了基于文件相似性分簇的重復(fù)數(shù)據(jù)消除模型。3.1創(chuàng)建文件的ridi為了解決磁盤瓶頸問題,將傳統(tǒng)平面型HTID縱向分為兩層:代表chunkID索引(RIDI)和分簇chunkID索引(CIDI)。其結(jié)構(gòu)如圖1所示。每個(gè)文件對(duì)應(yīng)RIDI中的一條記錄,該記錄保存了文件的rid、創(chuàng)建該記錄的文件的fid和指向CIDI中對(duì)應(yīng)chunkID簇的指針。CIDI將chunkID按其所屬文件的rid分成多個(gè)簇,每個(gè)簇中保存了具有相同rid的文件的全部非重復(fù)chunkID,以及各chunkID對(duì)應(yīng)的分塊大小和存儲(chǔ)地址等元數(shù)據(jù)信息。由于每個(gè)文件只提取一個(gè)rid,故RIDI較小,駐留在內(nèi)存;CIDI中存放了所有非重復(fù)分塊的元數(shù)據(jù),故CIDI較大,駐留在磁盤。3.2基于集群的chunkid搜索3.2.1文件fi的讀取向系統(tǒng)寫入一個(gè)文件fi的主要過程如下:a)計(jì)算rid(fi)和fid(fi),并用rid(fi)為條件檢索RIDI,如果返回rid域與rid(fi)相同的記錄,轉(zhuǎn)到b),否則轉(zhuǎn)到d)。b)如果fid(fi)與返回記錄的fid域相同,說明fi所有的chunk都是重復(fù)的,轉(zhuǎn)到e),否則轉(zhuǎn)到c)。c)從CIDI中將cluster(rid(fi))(以下簡(jiǎn)寫為cluster(fi))讀入內(nèi)存,然后用fi的所有chunkID在cluster(fi)中進(jìn)行CEQ,僅將新的chunkID及其元數(shù)據(jù)添加到cluster(fi)中;當(dāng)fi的所有chunkID都處理完后,為該文件生成哈希鏈HS(fi),將fi的新chunk數(shù)據(jù)、HS(fi)和更新后的cluster(fi)寫入磁盤,轉(zhuǎn)到e)。d)為fi創(chuàng)建一條新的RIDI記錄和一個(gè)新的cluster(fi),并將該RIDI記錄的指針指向該cluster(fi);然后將fi的所有非重復(fù)的chunkID及其元數(shù)據(jù)添加到cluster(fi)中;當(dāng)fi的所有chunkID都處理完后,為該文件生成哈希鏈HS(fi),將fi的全部非重復(fù)的chunk數(shù)據(jù)、HS(fi)和新的cluster(fi)寫入磁盤,轉(zhuǎn)到e)。e)文件fi的寫入過程結(jié)束。從系統(tǒng)讀出文件fi的過程相對(duì)比較簡(jiǎn)單:a)從磁盤上讀出HS(fi),并從中提取rid(fi)。b)用rid(fi)查詢RIDI,并根據(jù)查詢返回記錄的指針將對(duì)應(yīng)的cluster(fi)調(diào)入內(nèi)存。c)用組成HS(fi)的各chunkID查詢cluster(fi),得到組成fi的各chunk的地址和大小等信息,然后根據(jù)這些信息將對(duì)應(yīng)的chunk從磁盤讀出、組裝后得到fi。從以上文件的讀寫流程可以看出,系統(tǒng)中chunkID的存儲(chǔ)和檢索都是基于分簇完成的。3.2.2引入大量的chunkid基于分簇對(duì)chunkID進(jìn)行管理的優(yōu)點(diǎn)主要有:a)極大地減少了磁盤訪問次數(shù)。分簇管理方法的磁盤訪問次數(shù)與數(shù)據(jù)規(guī)模、數(shù)據(jù)是否具有局部性無關(guān),每個(gè)文件讀寫過程中,只需要在讀入對(duì)應(yīng)分簇時(shí)訪問磁盤一次,即可完成該文件全部chunkID的相關(guān)檢索,因此磁盤訪問的開銷被組成該文件的全部chunk攤銷了;而傳統(tǒng)檢索方法由于chunkID值的隨機(jī)分布,無法有效緩存而導(dǎo)致在數(shù)據(jù)規(guī)模較大時(shí),幾乎每一次chunkID的查詢就需要進(jìn)行一次磁盤訪問。b)有效提高了對(duì)內(nèi)存的利用率。由于RIDI只保存代表chunkID,因此遠(yuǎn)遠(yuǎn)小于傳統(tǒng)的平面型HTID,可以全部裝入內(nèi)存,大大提高了檢索和更新的速度;而傳統(tǒng)平面型HTID由于非常龐大,不能全部裝入內(nèi)存,再加上無法有效緩存,因此即使為其分配較大的內(nèi)存空間,仍需要在內(nèi)存和磁盤之間頻繁地進(jìn)行頁面的換入換出,對(duì)內(nèi)存的利用率非常低。c)保持了重復(fù)數(shù)據(jù)消除率。由于對(duì)每個(gè)文件,只選擇一個(gè)cluster作為其重復(fù)chunkID的檢索源,因此分簇管理方法允許系統(tǒng)中存在少量的重復(fù)chunk。換而言之,對(duì)某個(gè)chunkID,如果選中的cluster中沒有與之相同的,但其他cluster中有與之相同的chunkID,則其對(duì)應(yīng)的chunk會(huì)被認(rèn)為是新的。但由于chunkID是依據(jù)其所屬文件之間的相似性來分簇的,因此當(dāng)新來一個(gè)文件時(shí),Broder定理保證了選中的cluster是與其相似度很高的那些文件的chunkID的集合,故重復(fù)chunk的正確檢出概率是非常高的。綜上所述,分簇管理方法通過引入少量的重復(fù)chunk,可以大大提高內(nèi)存利用率和減少磁盤訪問,從而大幅度提高系統(tǒng)的吞吐量。與傳統(tǒng)的聚類方法不同,本文提出的分簇方法是無狀態(tài)的,在分簇時(shí)僅需要根據(jù)文件自身的內(nèi)容,而不需要了解已有分簇的額外信息。3.3重復(fù)數(shù)據(jù)的排除模型3.3.1sdd用戶各類節(jié)點(diǎn)云存儲(chǔ)應(yīng)用環(huán)境下的FCDM總體架構(gòu)如圖2所示。與傳統(tǒng)的基于數(shù)據(jù)流的備份負(fù)載不同,FCDM處理的是來自多個(gè)用戶節(jié)點(diǎn)的備份文件匯集成的文件序列,其特點(diǎn)是文件相對(duì)較小,文件到達(dá)的順序完全是隨機(jī)的,局部性特征非常弱。存儲(chǔ)節(jié)點(diǎn)(SD)是FCDM中最基本的工作單元,它是具有計(jì)算和存儲(chǔ)能力的獨(dú)立工作單元,其內(nèi)存和磁盤分別用于存儲(chǔ)RIDI和CIDI。單個(gè)SD的結(jié)構(gòu)如圖2虛線框內(nèi)部分所示。3.3.2sdridi的遷移在大規(guī)模應(yīng)用環(huán)境下,為了進(jìn)一步提高系統(tǒng)的整體吞吐量,需要將數(shù)據(jù)分布到多個(gè)SD上并行處理,因此FCDM除了縱向?qū)hunkID索引分為兩層外,還將雙層的chunkID索引進(jìn)行橫向分片,并根據(jù)一定的算法將每一分片分布到某一SD上,該過程稱為分片路由(PRT),如圖3所示。設(shè)系統(tǒng)中有K個(gè)SD(編號(hào)為1～K),PRT過程如下:a)對(duì)?ridi∈RIDI,計(jì)算SD(ridi)=ridimodK。b)將ridi對(duì)應(yīng)的記錄保存到編號(hào)為SD(ridi)的節(jié)點(diǎn)的RIDI中。c)將該記錄對(duì)應(yīng)的分簇cluster(ridi)保存到節(jié)點(diǎn)SD(ridi)的磁盤CIDI區(qū)中,并將該分簇對(duì)應(yīng)的分塊數(shù)據(jù)chunk(ridi)和文件哈希鏈HS(ridi)也分別保存到節(jié)點(diǎn)SD(ridi)磁盤上的chunk數(shù)據(jù)區(qū)和HS區(qū)。當(dāng)在系統(tǒng)中新增或者去掉SD,使得SD的數(shù)量變?yōu)榱薑′,此時(shí)需要重新進(jìn)行PRT。為了保證各SD的獨(dú)立和自治,采取如下遷移策略:a)對(duì)?ridi∈RIDI,計(jì)算SD′(ridi)=ridimodK′。b)將ridi對(duì)應(yīng)的記錄從節(jié)點(diǎn)SD(ridi)遷移到節(jié)點(diǎn)SD′(ridi)。c)將該記錄對(duì)應(yīng)的分簇cluster(ridi)、分簇對(duì)應(yīng)的分塊數(shù)據(jù)chunk(ridi)和文件哈希鏈HS(ridi)也一起遷移到節(jié)點(diǎn)SD′(ridi)。3.3.3發(fā)展性節(jié)點(diǎn)sdc和sdd的關(guān)聯(lián)FCDM處理備份負(fù)載的主要工作流程如下:a)FCDM服務(wù)器集群接收來自多個(gè)用戶的備份文件序列f1,f2,…,fi,…。對(duì)每一個(gè)文件fi,根據(jù)當(dāng)前各存儲(chǔ)節(jié)點(diǎn)的負(fù)載情況,將其分配到某一節(jié)點(diǎn)SDc。b)節(jié)點(diǎn)SDc對(duì)fi進(jìn)行分塊和特征提取,得到rid(fi),然后計(jì)算SDd=rid(fi)modK,并將fi分配到編號(hào)為SDd的節(jié)點(diǎn)進(jìn)行重復(fù)數(shù)據(jù)消除,該過程稱為文件路由(FRT)。SDc和SDd很可能是不相同的節(jié)點(diǎn),即fi很有可能是在一個(gè)節(jié)點(diǎn)進(jìn)行分塊而在另一個(gè)節(jié)點(diǎn)進(jìn)行重復(fù)數(shù)據(jù)消除。c)由于PRT和FRT算法的一致性,保證了包含cluster(fi)的分片也在SDd上,即SDd掌握了所需的全部元數(shù)據(jù)信息,可以獨(dú)立完成fi的重復(fù)數(shù)據(jù)消除。d)將fi的所有非重復(fù)的chunk數(shù)據(jù)和HS(fi)也保存在節(jié)點(diǎn)SDd上。3.3.4fcdm模型算法的特點(diǎn)從上述內(nèi)容可知,FCDM的分片方法主要具有以下特點(diǎn):a)PRT和FRT算法都是無狀態(tài)的,這意味著系統(tǒng)在決定將分片或文件路由到哪一個(gè)節(jié)點(diǎn)時(shí),不需要任何關(guān)于現(xiàn)有節(jié)點(diǎn)數(shù)據(jù)的額外信息,因此算法簡(jiǎn)單,路由效率高。b)各個(gè)節(jié)點(diǎn)是相互獨(dú)立和自治的,任何一個(gè)文件的所有相關(guān)數(shù)據(jù),包括chunkID索引、chunk數(shù)據(jù)以及HS都是保存在同一個(gè)節(jié)點(diǎn)上的,這極大地簡(jiǎn)化了文件的管理。例如某一文件的恢復(fù)、刪除、完整性校驗(yàn)、文件加密等不需要多個(gè)節(jié)點(diǎn)共同參與。c)遷移策略保證了各節(jié)點(diǎn)的獨(dú)立性和自治性,遷移前后不會(huì)在新舊節(jié)點(diǎn)之間產(chǎn)生任何數(shù)據(jù)的依賴關(guān)系,因此當(dāng)節(jié)點(diǎn)環(huán)境發(fā)生了變化,重新分布數(shù)據(jù)的過程中不會(huì)造成節(jié)點(diǎn)之間的依賴關(guān)系。d)一個(gè)文件的數(shù)據(jù)不被分割到多個(gè)節(jié)點(diǎn)保存,也提高了可靠性,因?yàn)槿绻粋€(gè)文件的數(shù)據(jù)被分割到多個(gè)節(jié)點(diǎn)保存,那么其中任何一個(gè)節(jié)點(diǎn)的失效都會(huì)導(dǎo)致該文件的失效。在分布式環(huán)境中,傳統(tǒng)的提高系統(tǒng)并行性的方法是采用DHT對(duì)HTID進(jìn)行橫向分片。例如對(duì)每一個(gè)chunkIDi,計(jì)算SDDHT(IDi)=chunkIDimodK,然后將該chunkID對(duì)應(yīng)的索引記錄保存到節(jié)點(diǎn)SDDHT(IDi)上。從上述FCDM模型及其算法的特點(diǎn)可知,FCDM相對(duì)于DHT主要具有以下優(yōu)點(diǎn):a)并行性更高。使用DHT方法時(shí),由于chunkID值的隨機(jī)性,在對(duì)一個(gè)文件重復(fù)數(shù)據(jù)消除的過程中,需要向多個(gè)節(jié)點(diǎn)發(fā)出CEQ請(qǐng)求,在最壞的情況下,甚至需要向全部的節(jié)點(diǎn)發(fā)出CEQ請(qǐng)求;而FCDM中,一個(gè)文件的所有CEQ請(qǐng)求僅需在一個(gè)節(jié)點(diǎn)就可完成,因此在節(jié)點(diǎn)數(shù)相同的情況下,FCDM可同時(shí)處理更多的文件。b)更加簡(jiǎn)單和便于擴(kuò)展。DHT方法中,同一個(gè)文件的chunkID索引和chunk數(shù)據(jù)是分布在多個(gè)節(jié)點(diǎn)上的,各個(gè)節(jié)點(diǎn)不是獨(dú)立的,不能自治地管理數(shù)據(jù);而FCDM中同一個(gè)文件的chunkID索引和chunk數(shù)據(jù)是存放在單個(gè)節(jié)點(diǎn)上的,各個(gè)節(jié)點(diǎn)自治地管理數(shù)據(jù),文件管理更加簡(jiǎn)單,系統(tǒng)的可擴(kuò)展性也更強(qiáng)。c)資源占用更少。DHT方法通過將chunkID索引分布到多個(gè)節(jié)點(diǎn),使得更多的chunkID索引能夠被裝入內(nèi)存,從而提高系統(tǒng)整體的吞吐量,但是DHT方法并不能減少內(nèi)存占用總量;而FCDM由于只需要將chunkID的很小一部分子集裝入內(nèi)存,因此大大減小了內(nèi)存占用總量。換而言之,在維持相同吞吐量的情況下,FCDM所需要的節(jié)點(diǎn)數(shù)更少。4實(shí)驗(yàn)與分析4.1文件的大小與特點(diǎn)為考察FCDM在非傳統(tǒng)備份負(fù)載下的性能,本文從某臺(tái)文件備份服務(wù)器采集了20個(gè)不同用戶連續(xù)兩個(gè)月的備份文件作為實(shí)驗(yàn)數(shù)據(jù)集。采集的文件總數(shù)約為8.79×106個(gè),總大小約為2TB(2071.30GB),文件的平均大小約為247KB,這些文件在數(shù)據(jù)集中按照到達(dá)備份服務(wù)器的時(shí)間先后排序。相對(duì)于傳統(tǒng)基于大數(shù)據(jù)流的備份負(fù)載,該數(shù)據(jù)集的特點(diǎn)是數(shù)據(jù)對(duì)象較小,在一段時(shí)間窗口內(nèi)的數(shù)據(jù)對(duì)象之間幾乎沒有局部性可言。FCDM基于網(wǎng)絡(luò)與數(shù)據(jù)安全四川省重點(diǎn)實(shí)驗(yàn)室的SAN網(wǎng)絡(luò)搭建,用IBMSystemx3850X5作為系統(tǒng)的服務(wù)器,用十臺(tái)清華同方PC機(jī)作為存儲(chǔ)節(jié)點(diǎn)。4.2結(jié)果4.2.1使用數(shù)據(jù)通訊數(shù)據(jù)壓縮比(數(shù)據(jù)原始大小/消除重復(fù)數(shù)據(jù)后的大小)用來衡量重復(fù)數(shù)據(jù)消除性能。實(shí)驗(yàn)比較了現(xiàn)有主流方法和FCDM的壓縮比,如表2所示。各方法的存儲(chǔ)空間占用量隨著文件總數(shù)量增加的變化趨勢(shì)如圖4所示。從表2和圖4中可以看出:a)由于datadomain系統(tǒng)采用的是平面型的HTID,因此能夠檢測(cè)出所有重復(fù)的chunk,具有最優(yōu)的重復(fù)數(shù)據(jù)消除性能。b)Sparseindexing和FCDM由于使用全部索引的子集作為檢索源,因此都不能檢測(cè)出全部重復(fù)分塊。c)Sparseindexing能夠選出較優(yōu)子集作為檢索源的前提條件是備份負(fù)載是基于流的并且具有很顯著的局部性,因此對(duì)基于細(xì)粒度文件的、缺乏局部性的備份負(fù)載而言,其重復(fù)數(shù)據(jù)消除性能會(huì)嚴(yán)重降低。d)FCDM由于在選擇檢索源時(shí)不依賴數(shù)據(jù)對(duì)象的粒度及局部性,因此能夠獲得接近最優(yōu)的重復(fù)數(shù)據(jù)消除性能,比最優(yōu)情況下僅多占用了20.69GB的存儲(chǔ)空間,僅為備份負(fù)載整體大小的1%。4.2.2tb級(jí)數(shù)據(jù)規(guī)模對(duì)實(shí)驗(yàn)結(jié)果的預(yù)測(cè)根據(jù)應(yīng)用環(huán)境的復(fù)雜程度和具體實(shí)現(xiàn)的不同,內(nèi)存中每條索引的存儲(chǔ)開銷也不同。本實(shí)驗(yàn)中,設(shè)內(nèi)存中每條索引的存儲(chǔ)開銷為200Byte。實(shí)驗(yàn)比較了幾種方法的內(nèi)存總需求量,如圖5所示。其中圖5(a)是實(shí)驗(yàn)所用的TB級(jí)數(shù)據(jù)規(guī)模得到的結(jié)果;圖5(b)是根據(jù)TB級(jí)實(shí)驗(yàn)結(jié)果,假設(shè)在文件平均大小、平均分塊大小、壓縮比等環(huán)境變量相同的情況下,預(yù)測(cè)的當(dāng)數(shù)據(jù)量為1PB時(shí),幾種方法的內(nèi)存總需求量?？梢钥闯?a)Sparseindexing和FCDM由于僅在內(nèi)存中維護(hù)全部索引的一個(gè)很小的子集,因此內(nèi)存總需求量遠(yuǎn)遠(yuǎn)低于datadomain的平面型chunkID索引。b)FCDM的內(nèi)存總需求量是三種方法中最低的,當(dāng)數(shù)據(jù)規(guī)模達(dá)到PB級(jí)別時(shí),僅為datadomain的1.86%,為sparseindexing的44.45%。這意味著在相同條件下,如果要將索引全部裝入內(nèi)存,FCDM所需要的存儲(chǔ)節(jié)點(diǎn)總數(shù)遠(yuǎn)少于其他兩種方法。4.2.3fcd的平均咀嚼和總咀嚼圖6是datadomain采用DHT分片,文件在重復(fù)數(shù)據(jù)消除過程中所需查詢節(jié)點(diǎn)數(shù)的情況。可以看出:a)當(dāng)存儲(chǔ)節(jié)點(diǎn)數(shù)K=4時(shí),有57.46%的文件在重復(fù)數(shù)據(jù)消除過程中需要查詢1個(gè)以上的節(jié)點(diǎn);有27.02%的文件需要查詢?nèi)抗?jié)點(diǎn)。這稱為DHT方法的多節(jié)點(diǎn)依賴問題。b)隨著存儲(chǔ)節(jié)點(diǎn)數(shù)的增加,多節(jié)點(diǎn)依賴問題更加顯著。當(dāng)K=10時(shí),有86.75%的文件需要查詢1個(gè)以上的節(jié)點(diǎn);有23.15%的文件需要查詢?nèi)抗?jié)點(diǎn)。由于FCDM中,每個(gè)文件重復(fù)數(shù)據(jù)消除所需的全部信息都保存在某一個(gè)節(jié)點(diǎn)上,各個(gè)節(jié)點(diǎn)自治管理,處理每一個(gè)文件都僅需要查詢1個(gè)節(jié)點(diǎn)。換而言之,在其他條件相同的情況下,FCDM能夠同時(shí)處理的文件數(shù)量比基于DHT分片的系統(tǒng)更多,這有利于提高系統(tǒng)整體吞吐量。實(shí)驗(yàn)比較了索引不分片(K=1)和分片(K=2～10)的情況下,幾種方法的總寫入吞吐量,如圖7所示。其中datadomain和sparseindexing采用DHT進(jìn)行分片,datadomain采用了bloomfilter和LPC技術(shù)提高吞吐量。為便于比較,圖中各吞吐量均以K=10時(shí),FCDM的吞吐量為單位進(jìn)行了歸一化?？梢钥闯?a)當(dāng)K=1時(shí),datadomain的吞吐量遠(yuǎn)遠(yuǎn)低于其他兩種方法,僅為FCDM的13%。這是因?yàn)閎loomfilter只能快速準(zhǔn)確斷言某個(gè)chunkID的不存在,而對(duì)存在性的斷言仍然需要查詢HTID,因此bloomfilter對(duì)吞吐量的提高作用非常有限。而datadomain的平面型HTID非常龐大,只有很小一部分能夠裝入內(nèi)存,因此對(duì)于缺乏局部性的備份負(fù)載,LPC不能有效緩存chunkID,這使得LPC的命中率非常低,系統(tǒng)需要頻繁地在內(nèi)存和磁盤之間交換索引頁面。b)當(dāng)K=1時(shí),FCDM由于大幅度減少了隨機(jī)磁盤I/O的數(shù)量,因此相對(duì)于datadomain有效提高了吞吐量;FCDM每個(gè)文件僅需要提取一個(gè)rid,并且其選取檢索源的流程比sparseindexing更加簡(jiǎn)化,因此其吞吐量高于sparseindexing。c)當(dāng)K>1時(shí),隨著節(jié)點(diǎn)數(shù)量的