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

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

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