王麗芳, 張志珂, 蔣澤軍, 蔡小斌, 彭成章

(1.西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院, 陜西 西安 710072; 2.國家電網(wǎng) 河南省電力公司, 河南 鄭州 450052)

人類每年產(chǎn)生的數(shù)據(jù)量以指數(shù)級別的速度快速增長。云存儲供應(yīng)商、第3方備份服務(wù)和社交網(wǎng)絡(luò)等會產(chǎn)生大量數(shù)據(jù)[1]。例如，著名的社交網(wǎng)絡(luò)Facebook每天存儲8 300萬張照片，大約是200TB至400TB數(shù)據(jù)[2]。并且，由于越來越多的用戶使用這些服務(wù)，所產(chǎn)生的數(shù)據(jù)量也迅速增加。這些企業(yè)所存儲的數(shù)據(jù)是它們所提供服務(wù)的關(guān)鍵基礎(chǔ)。數(shù)據(jù)丟失會嚴(yán)重降低服務(wù)質(zhì)量，從而降低企業(yè)的利潤。為了避免數(shù)據(jù)丟失，數(shù)據(jù)中心必須在幾年的備份周期內(nèi)定期備份所有數(shù)據(jù)(通常是每周一次全備份)，并且保證在需要時(shí)能提供數(shù)據(jù)，另外，一些法律也規(guī)定數(shù)據(jù)中心必須定期備份所有數(shù)據(jù)[3]。

重復(fù)數(shù)據(jù)刪除技術(shù)能夠從已經(jīng)存儲的數(shù)據(jù)中找到重復(fù)的數(shù)據(jù)，不存儲重復(fù)的數(shù)據(jù)，只存儲新數(shù)據(jù)。因此，重復(fù)數(shù)據(jù)刪除技術(shù)可以大量縮減存儲使用量，使基于磁盤的數(shù)據(jù)備份成本與磁帶相當(dāng)甚至更低。這就使基于磁盤的重復(fù)數(shù)據(jù)刪除技術(shù)越來越流行，逐漸替代基于磁帶的數(shù)據(jù)備份技術(shù)[4-8]。單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除的容量是有限的，目前最先進(jìn)的重復(fù)數(shù)據(jù)刪除可以存儲幾十PB(petabyte)的數(shù)據(jù)[3]。然而，數(shù)據(jù)中心的備份需求已經(jīng)超過單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除的容量[1]。并且，隨著越來越多的企業(yè)把自己的存儲外包給云環(huán)境，數(shù)據(jù)中心的數(shù)據(jù)備份數(shù)量會繼續(xù)增長。

重復(fù)數(shù)據(jù)刪除集群可以滿足數(shù)據(jù)中心越來越大的數(shù)據(jù)備份需求[3,9-11]。重復(fù)數(shù)據(jù)刪除集群的關(guān)鍵問題是如何把數(shù)據(jù)合理分配到各個(gè)重復(fù)數(shù)據(jù)刪除節(jié)點(diǎn)上，即數(shù)據(jù)路由策略。重復(fù)數(shù)據(jù)刪除集群的數(shù)據(jù)路由策略的目標(biāo)是：①保證較高的重復(fù)數(shù)據(jù)刪除率；②保證各個(gè)重復(fù)數(shù)據(jù)刪除節(jié)點(diǎn)的負(fù)載平衡。重復(fù)數(shù)據(jù)刪除率是待存儲的數(shù)據(jù)量與存儲使用量的比值，用于評估重復(fù)數(shù)據(jù)刪除的存儲利用率。已有的重復(fù)數(shù)據(jù)刪除集群的數(shù)據(jù)路由策略使用文件或者數(shù)據(jù)段的所有數(shù)據(jù)塊簽名中最小的數(shù)據(jù)塊簽名計(jì)算目標(biāo)節(jié)點(diǎn)[3,9]，稱作MCS(minimum chunk signature)路由策略。對于包括幾個(gè)節(jié)點(diǎn)的小規(guī)模重復(fù)數(shù)據(jù)刪除集群，這種方法可以保證較高的重復(fù)數(shù)據(jù)刪除率。但是，當(dāng)重復(fù)數(shù)據(jù)刪除集群的規(guī)模較大時(shí)，這種方法的重復(fù)數(shù)據(jù)刪除率急劇下降，遠(yuǎn)遠(yuǎn)低于單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除[3]。

本文提出一種基于路徑的重復(fù)數(shù)據(jù)刪除集群的數(shù)據(jù)路由策略，稱作DRSD(data routing strategy based on directories)。文件的路徑是一種文件系統(tǒng)語義，指的是文件系統(tǒng)路徑。在連續(xù)的數(shù)據(jù)備份版本中，數(shù)據(jù)的目錄結(jié)構(gòu)通常是穩(wěn)定的，那么具有相同目錄名稱的文件集很有可能包含一些相同的數(shù)據(jù)。用文件的路徑輔助數(shù)據(jù)路由可以把相關(guān)的或者相似的數(shù)據(jù)分配到同一個(gè)節(jié)點(diǎn)上，從而提高重復(fù)數(shù)據(jù)刪除率。文章使用文件路徑設(shè)計(jì)了一種數(shù)據(jù)路由策略。構(gòu)建一個(gè)路徑路由索引保存路徑相關(guān)的路由信息。當(dāng)需要路由數(shù)據(jù)時(shí)，先查詢路徑路由索引是否存在改路徑的路由信息，如果存在，就直接使用該路由信息路由數(shù)據(jù)到目標(biāo)節(jié)點(diǎn)；如果不存在，就使用文件的最小塊簽名計(jì)算目標(biāo)節(jié)點(diǎn)。

收集了一個(gè)來自真實(shí)世界的數(shù)據(jù)集，包含564個(gè)版本的Linux源代碼檔案。用它來評估提出的重復(fù)數(shù)據(jù)刪除集群的數(shù)據(jù)路由策略DRSD。實(shí)驗(yàn)結(jié)果表明，對于各種不同的節(jié)點(diǎn)數(shù)量，DRSD的重復(fù)數(shù)據(jù)刪除率都明顯高于MCS，并且接近單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除。當(dāng)節(jié)點(diǎn)數(shù)量是64時(shí)，DRSD的重復(fù)數(shù)據(jù)刪除率比MCS高35%。此外，當(dāng)節(jié)點(diǎn)數(shù)量小于8時(shí)，DRSD的數(shù)據(jù)傾斜率與MCS幾乎相同。

1 設(shè) 計(jì)

1.1 架 構(gòu)

圖1描述了重復(fù)數(shù)據(jù)刪除集群的架構(gòu)。備份服務(wù)器負(fù)責(zé)對數(shù)據(jù)的分塊工作，這種方式可以節(jié)約重復(fù)數(shù)據(jù)刪除服務(wù)器的計(jì)算資源。但是，這不是必需的，也可以由重復(fù)數(shù)據(jù)刪除集群的存儲節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)分塊工作。備份服務(wù)器首先把數(shù)據(jù)和分塊結(jié)果發(fā)送到主節(jié)點(diǎn)。

主節(jié)點(diǎn)分配數(shù)據(jù)至重復(fù)數(shù)據(jù)刪除集群中的目標(biāo)節(jié)點(diǎn)。目標(biāo)節(jié)點(diǎn)是通過數(shù)據(jù)路由算法計(jì)算得到的，例如DRSD或者M(jìn)CS。主節(jié)點(diǎn)同時(shí)也把數(shù)據(jù)的分塊結(jié)果發(fā)送至目標(biāo)節(jié)點(diǎn)。這個(gè)架構(gòu)只有一個(gè)主節(jié)點(diǎn)。采用這種設(shè)計(jì)的原因是數(shù)據(jù)路由策略不需要大量的計(jì)算資源，一個(gè)節(jié)點(diǎn)能夠滿足需要。

然后，存儲節(jié)點(diǎn)對數(shù)據(jù)做重復(fù)數(shù)據(jù)刪除工作，找到重復(fù)的數(shù)據(jù)。每個(gè)存儲節(jié)點(diǎn)獨(dú)立工作。這意味著一個(gè)存儲節(jié)點(diǎn)只能找到存儲在自己上的重復(fù)數(shù)據(jù)。最后，存儲節(jié)點(diǎn)把文件的元數(shù)據(jù)返回給主節(jié)點(diǎn)。文件的元數(shù)據(jù)包括用于讀取文件所必要的信息，例如，文件數(shù)據(jù)塊的簽名，文件數(shù)據(jù)塊的地址等。

圖1 重復(fù)數(shù)據(jù)刪除集群架構(gòu)

1.2 基于文件路徑的數(shù)據(jù)路由策略

重復(fù)數(shù)據(jù)刪除集群的關(guān)鍵問題是如何合理地把數(shù)據(jù)分配至各個(gè)存儲節(jié)點(diǎn)。重復(fù)數(shù)據(jù)刪除集群的數(shù)據(jù)路由策略負(fù)責(zé)這項(xiàng)工作。數(shù)據(jù)路由算法的目標(biāo)包括保證重復(fù)數(shù)據(jù)刪除集群的高重復(fù)數(shù)據(jù)刪除率和較好的負(fù)載平衡。

重復(fù)數(shù)據(jù)刪除集群的數(shù)據(jù)路由策略主要分為2類。第一類是有狀態(tài)數(shù)據(jù)路由策略。對于每個(gè)文件或者數(shù)據(jù)段，有狀態(tài)路由策略首先向重復(fù)數(shù)據(jù)刪除集群中的每個(gè)節(jié)點(diǎn)發(fā)送詢問請求，詢問每個(gè)節(jié)點(diǎn)能在這個(gè)文件或者數(shù)據(jù)段中找到的重復(fù)數(shù)據(jù)的數(shù)量。在此之后，有狀態(tài)路由策略再確定哪個(gè)節(jié)點(diǎn)存儲這個(gè)文件或者數(shù)據(jù)段需要最少的存儲空間，再把數(shù)據(jù)存儲在那個(gè)節(jié)點(diǎn)。

另外一種數(shù)據(jù)路由策略是無狀態(tài)數(shù)據(jù)路由策略。它做數(shù)據(jù)路由時(shí)，只依賴于數(shù)據(jù)本身，而不需要其他信息。例如，MCS僅僅需要文件或者數(shù)據(jù)段的最小數(shù)據(jù)塊ID確定把數(shù)據(jù)存儲在哪個(gè)節(jié)點(diǎn)。

與無狀態(tài)路由策略相比，有狀態(tài)路由策略可以提供更好的重復(fù)數(shù)據(jù)刪除率，但是卻需要較多的計(jì)算開銷，因此，它的速度較慢。重復(fù)數(shù)據(jù)刪除集群需要在較短的備份窗口內(nèi)存儲大量的備份數(shù)據(jù)，需要高吞吐量。因此，無狀態(tài)路由策略更適合于重復(fù)數(shù)據(jù)刪除集群。

為了改進(jìn)重復(fù)數(shù)據(jù)刪除集群的重復(fù)數(shù)據(jù)刪除率，最好能夠把相似的數(shù)據(jù)或者文件存儲在同一個(gè)節(jié)點(diǎn)上。文件的路徑是一種文件系統(tǒng)語義，指的是文件系統(tǒng)路徑。在連續(xù)的數(shù)據(jù)備份版本中，數(shù)據(jù)的目錄結(jié)構(gòu)通常是穩(wěn)定的，備份版本中具有相同目錄名稱的目錄很可能對應(yīng)同一個(gè)原始目錄，那么具有相同目錄名稱的文件集很有可能包含一些相同的數(shù)據(jù)。可以利用文件的路徑為重復(fù)數(shù)據(jù)刪除集群設(shè)計(jì)一種數(shù)據(jù)路由策略。

本文提出一種基于路徑的重復(fù)數(shù)據(jù)刪除集群的數(shù)據(jù)路由策略，稱作DRSD(data routing strategy based on directories)。DRSD構(gòu)建一個(gè)路徑路由索引保存路徑相關(guān)的路由信息。當(dāng)需要路由數(shù)據(jù)時(shí)，先查詢路徑路由索引是否存在改路徑的路由信息，如果存在，就直接使用該路由信息數(shù)據(jù)到目標(biāo)節(jié)點(diǎn)；如果不存在，就使用文件的最小塊簽名計(jì)算目標(biāo)節(jié)點(diǎn)。

文件路徑指的是文件的整個(gè)文件系統(tǒng)路徑，是由一些文件系統(tǒng)目錄名組成的，包括從根目錄至文件所在的目錄。用戶常見的一種操作是把某個(gè)目錄移動到另外一個(gè)目錄，或者修改某個(gè)目錄的名字。這種操作會改變文件目錄的父目錄，卻不會改變這個(gè)目錄的子目錄。這就意味著，在不同的備份版本內(nèi)，被移動或者修改的目錄的所有子目錄中的所有文件的部分父目錄是保持不變的。因此，DRSD使用與文件最接近的部分父目錄路由數(shù)據(jù)，而不使用文件的整個(gè)目錄。

圖2 數(shù)據(jù)路由算法(MCS和DRSD)

圖2給出了DRSD數(shù)據(jù)路由算法的細(xì)節(jié)。為了便于比較，圖2也包括了MCS數(shù)據(jù)路由算法。在算法中，directoryName指的是文件的整個(gè)路徑，包括從根目錄至文件所在的目錄。directoryDepth表示目錄深度，指的是從文件所在的目錄開始向上的目錄層次。getSubDirectory函數(shù)的功能是從文件的目錄名中獲得特定目錄深度的子目錄名。例如，文件d.txt的文件目錄是'/a/b/c/d.txt'，那么文件d.txt的目錄深度為2的子目錄名是"/b/c"，類似的，文件d.txt的目錄深度為3的子目錄名是"/a/b/c"。

2 評 估

本節(jié)比較DRSD、已有的MCS和單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除。收集了一個(gè)真實(shí)世界的數(shù)據(jù)集，并構(gòu)建了一個(gè)仿真器比較它們。首先詳細(xì)描述了仿真器。然后，描述了評估標(biāo)準(zhǔn)。最后，描述并分析了實(shí)驗(yàn)結(jié)果，包括存儲空間使用情況和負(fù)載均衡情況。

2.1 數(shù)據(jù)集

為了驗(yàn)證文章提出的算法，收集了一個(gè)真實(shí)世界的數(shù)據(jù)集。這個(gè)數(shù)據(jù)集是Linux源代碼檔案，稱作Linux。它包括Linux1.2.0至Linux2.5.75之間的所有源代碼檔案，共計(jì)564個(gè)備份版本。Linux數(shù)據(jù)集的大部分文件時(shí)小文件，一般是幾十KB。Linux代表了主要包括小文件的、高冗余的數(shù)據(jù)集。表1給出了Linux的詳細(xì)數(shù)據(jù)。

表1 數(shù)據(jù)集

2.2 評估標(biāo)準(zhǔn)

重復(fù)數(shù)據(jù)刪除集群的評估標(biāo)準(zhǔn)如下所示：

1)重復(fù)數(shù)據(jù)刪除率：數(shù)據(jù)集的原始尺寸與消除重復(fù)數(shù)據(jù)后存儲空間使用量的比值。

2)數(shù)據(jù)傾斜率：重復(fù)數(shù)據(jù)刪除集群中存儲使用量最大節(jié)點(diǎn)的存儲使用量與所有節(jié)點(diǎn)的平均存儲使用量的比值。它用于測量重復(fù)數(shù)據(jù)刪除集群的負(fù)載均衡情況。

2.3 仿真器

為了評估DRSD，構(gòu)建了一個(gè)仿真器，用于仿真重復(fù)數(shù)據(jù)刪除集群。重復(fù)數(shù)據(jù)刪除集群包括許多存儲節(jié)點(diǎn)。仿真器也包括一個(gè)主節(jié)點(diǎn)，負(fù)責(zé)把數(shù)據(jù)分配到各個(gè)存儲節(jié)點(diǎn)。仿真器包括分塊器。

仿真器的第1個(gè)部分是主節(jié)點(diǎn)。它運(yùn)行數(shù)據(jù)路由算法，負(fù)責(zé)把文件分發(fā)至重復(fù)數(shù)據(jù)刪除集群的各個(gè)存儲節(jié)點(diǎn)。實(shí)現(xiàn)了2個(gè)數(shù)據(jù)路由算法，DRSD和MCS。數(shù)據(jù)路由算法逐個(gè)處理文件。它把文件的分塊結(jié)果作為輸入，然后確定目標(biāo)節(jié)點(diǎn)，再把文件和分塊結(jié)果發(fā)送至目標(biāo)節(jié)點(diǎn)。

仿真器的第2個(gè)部分是存儲節(jié)點(diǎn)。重復(fù)數(shù)據(jù)刪除集群包括一定數(shù)量的存儲節(jié)點(diǎn)。存儲節(jié)點(diǎn)負(fù)責(zé)重復(fù)數(shù)據(jù)刪除工作。這與單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除是一樣的。存儲節(jié)點(diǎn)維護(hù)一個(gè)數(shù)據(jù)塊索引，包括所有已經(jīng)存儲的數(shù)據(jù)塊的簽名。當(dāng)處理1個(gè)文件時(shí)，它首先在數(shù)據(jù)塊索引中搜索文件的每個(gè)數(shù)據(jù)塊簽名或者ID。如果數(shù)據(jù)塊ID存在于數(shù)據(jù)塊索引中，那么，這個(gè)數(shù)據(jù)塊ID對應(yīng)的數(shù)據(jù)塊就是重復(fù)的。否則，這個(gè)數(shù)據(jù)塊就是新數(shù)據(jù)塊。存儲節(jié)點(diǎn)然后構(gòu)造文件的元數(shù)據(jù)。存儲節(jié)點(diǎn)采用最優(yōu)重復(fù)數(shù)據(jù)刪除，即把整個(gè)數(shù)據(jù)塊索引都放在內(nèi)存中。

仿真器的第3個(gè)部分是分塊器。它逐個(gè)處理文件，輸出分塊結(jié)果到分塊結(jié)果文件中。分塊器首先從磁盤讀出文件，然后對它分塊。使用TTTD分塊算法[12]，設(shè)置平均數(shù)據(jù)塊尺寸為4 kB。

2.4 存儲空間使用量

存儲空間使用量對于重復(fù)數(shù)據(jù)刪除系統(tǒng)是非常重要的。存儲空間使用量決定了磁盤使用量。由于備份數(shù)據(jù)通常都是海量的，那么磁盤是備份系統(tǒng)的主要成本。因此，存儲使用量決定了重復(fù)數(shù)據(jù)刪除系統(tǒng)的成本。重復(fù)數(shù)據(jù)刪除率一般用于測量重復(fù)數(shù)據(jù)刪除系統(tǒng)的存儲使用量。

對于重復(fù)數(shù)據(jù)刪除集群的不同的節(jié)點(diǎn)數(shù)量，比較了DRSD、MCS和單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除。圖3給出了比較結(jié)果。對于重復(fù)數(shù)據(jù)刪除集群的各種不同的節(jié)點(diǎn)數(shù)量(包括2，4，8，16，32，64，128，256，512，1 024)，測量了算法的重復(fù)數(shù)據(jù)刪除率。在圖3中，Single node表示單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除；DRSD(2)表示DRSD并且路徑深度是2。

如圖3所示，單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除具有最好的重復(fù)數(shù)據(jù)刪除率。因?yàn)槭撬械臄?shù)據(jù)都存儲在同一個(gè)節(jié)點(diǎn)上，可以找到所有的重復(fù)數(shù)據(jù)塊。而對于DRSS和MCS，數(shù)據(jù)分布在許多節(jié)點(diǎn)上。每個(gè)節(jié)點(diǎn)獨(dú)立工作，這意味著每個(gè)節(jié)點(diǎn)只在自己上存儲的數(shù)據(jù)中查找重復(fù)數(shù)據(jù)，而不查找其他節(jié)點(diǎn)上存儲的數(shù)據(jù)。因此，DRSS和MCS的重復(fù)數(shù)據(jù)刪除率小于單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除。

如圖3所示，對于不同的節(jié)點(diǎn)數(shù)量，路徑深度為1的DRSD的重復(fù)數(shù)據(jù)刪除率都非常接近單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除，并且遠(yuǎn)遠(yuǎn)優(yōu)于MCS。這表明DRSD能夠有效地把相似的文件分配至同一個(gè)節(jié)點(diǎn)。隨著節(jié)點(diǎn)數(shù)量的增加，DRSD和MCS的重復(fù)數(shù)據(jù)刪除率迅速下降。當(dāng)節(jié)點(diǎn)數(shù)量大于64時(shí)，其重復(fù)數(shù)據(jù)刪除率不再有明顯的降低。此時(shí)，DRSD(1)的重復(fù)數(shù)據(jù)刪除率比MCS高35%。

隨著路徑深度的增加，DRSD的性能逐漸降低。對于各種不同的節(jié)點(diǎn)數(shù)量，路徑深度為1和2的DRSD的重復(fù)數(shù)據(jù)刪除率都比MCS好一些，路徑深度為3和4的DRSD的重復(fù)數(shù)據(jù)刪除率都比MCS差。

圖3 重復(fù)數(shù)據(jù)刪除率比較

2.5 負(fù)載均衡

負(fù)載均衡對于重復(fù)數(shù)據(jù)刪除集群是很重要的。重復(fù)數(shù)據(jù)刪除集群的某個(gè)節(jié)點(diǎn)的存儲使用量不能太大，否則，這個(gè)節(jié)點(diǎn)會成為整個(gè)集群的性能瓶頸，惡化整個(gè)集群的性能。使用數(shù)據(jù)傾斜率測量重復(fù)數(shù)據(jù)刪除集群的負(fù)載均衡。數(shù)據(jù)傾斜率越高，說明負(fù)載均衡越差。數(shù)據(jù)遷移策略一般用于保證重復(fù)數(shù)據(jù)刪除集群各節(jié)點(diǎn)的負(fù)載均衡。但是，這不是本文的重點(diǎn)，本文主要研究不包括數(shù)據(jù)遷移的DRSD的原始數(shù)據(jù)傾斜率。實(shí)驗(yàn)不包括數(shù)據(jù)遷移策略。

圖4 負(fù)載均衡比較

對于各種不同節(jié)點(diǎn)數(shù)量，圖4比較了DRSD、MCS和單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除的數(shù)據(jù)傾斜率。Single node表示單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除；DRSD(2)表示DRSD并且路徑深度是2。

隨著節(jié)點(diǎn)數(shù)量的增加，DRSD和MCS的數(shù)據(jù)傾斜率也隨之增加。當(dāng)節(jié)點(diǎn)數(shù)量小于64時(shí)，DRSD和MCS的數(shù)據(jù)傾斜率緩慢增加。然而，當(dāng)節(jié)點(diǎn)數(shù)量大于64時(shí)，DRSD的數(shù)據(jù)傾斜率快速增加。當(dāng)節(jié)點(diǎn)數(shù)量小于8時(shí)，DRSD與MCS的數(shù)據(jù)傾斜率幾乎相同。當(dāng)節(jié)點(diǎn)數(shù)量是8時(shí)，DRSD(1)的重復(fù)數(shù)據(jù)刪除率比MCS高29%。

當(dāng)節(jié)點(diǎn)數(shù)量是大于32時(shí)，DRSD(1)的數(shù)據(jù)傾斜率明顯大于MCS。注意，這是不包括數(shù)據(jù)遷移策略的原始數(shù)據(jù)傾斜率。在將來的工作中，將研究如何改進(jìn)DRSD的數(shù)據(jù)傾斜率。

隨著路徑深度的增加，DRSD的數(shù)據(jù)傾斜率隨之降低。DRSD(3)和DRSD(4)具有幾乎相同的數(shù)據(jù)傾斜率。DRSD(1)和DRSD(2)的數(shù)據(jù)傾斜率則大于其它算法，并且隨著節(jié)點(diǎn)數(shù)量的增加，這種區(qū)別更加明顯。

3 結(jié) 論

為了改進(jìn)重復(fù)數(shù)據(jù)刪除集群的重復(fù)數(shù)據(jù)刪除率，利用文件路徑提出了一種新穎的數(shù)據(jù)路由策略DRSD。構(gòu)建了一個(gè)仿真器，并用來自真實(shí)世界的數(shù)據(jù)集評估了DRSD。實(shí)驗(yàn)結(jié)果表明，對于各種不同的節(jié)點(diǎn)數(shù)量，DRSD的重復(fù)數(shù)據(jù)刪除率都明顯高于MCS，并且接近單節(jié)點(diǎn)重復(fù)數(shù)據(jù)刪除。當(dāng)節(jié)點(diǎn)數(shù)量是64時(shí)，DRSD的重復(fù)數(shù)據(jù)刪除率比MCS高35%。此外，當(dāng)節(jié)點(diǎn)數(shù)量小于8時(shí)，DRSD的數(shù)據(jù)傾斜率與MCS幾乎相同，即二者的負(fù)載均衡幾乎相同。

參考文獻(xiàn)：

[1] Gantz J F, Chute C, Manfrediz A, Minton S, Reinsel D, Schlichting W, Toncheva A . The Diverse and Exploding Digital Universe: An Updated Forecast of Worldwide Information Growth through 2011[R]. An IDC White Paper-Sponsored by EMC, 2008

[2] Stoica I. A Berkeley View of Big Data. https://amplab.cs.berkeley.edu/about/.

[3] Dong W, Douglis F, Li K, Patterson H, Reddy S, Shilane P. Tradeoffs in Scalable Data Routing for Deduplication Clusters[C]∥Proceedings of the 9th Conference on USENIX Conference on File and Storage Technologies. San Jose, CA, USA: USENIX Association, Berkeley, CA, USA, 2011: 15-17, 15-29

[4] You L, Pollack K, Long D. Deep Store: An Archival Storage System Architecture[C]∥Proceedings of the 21th International Conference on Data Engineering. Tokyo, Japan: IEEE Computer Society, Washington, DC, USA, 2005: 804-815

[5] Zhu B, Li K, Patterson H. Avoiding the Disk Bottleneck in the Data Domain Deduplication File System[C]∥Proceedings of the 6th Conference on USENIX Conference on File and Storage Technologies. San Jose, CA, USA: USENIX Association, Berkeley, CA, USA, 2008: 269-282

[6] Zhang Zhike, Bhagwat D, Litwin W, Long D, Schwarz S. Improved Deduplication through Parallel Binning[C]∥Performance Computing and Communications Conference (IPCCC), 2012 IEEE 31st International. IEEE, Washington, DC, USA, 2012: 130-141

[7] Zhang Zhike, Jiang Zejun, Liu Zhiqiang, et al. LHs: A Novel Method of Information Retrieval Avoiding an Index Using Linear Hashing with Key Groups in Deduplication[C]∥Proceedings of 2012 International Conference on Machine Learning and Cybernetics. Washington, DC: IEEE, 2012: 1312-1318

[8] Zhang Zhike, Jiang Zejun, Cai Xiaobin, Peng Chengzhang. A Novel Cache Prefetching Algorithm for Restoration Operations of Deduplication Systems[J]. Lecture Notes in Electrical Engineering, 2012, 219(4): 331-338

[9] Bhagwat D, Eshghi K, Long D, Lillibridge M. Extreme Binning: Scalable, Parallel Deduplication for Chunk-Based File Backup[C]∥Proceedings of the 17th Annual Meeting of the IEEE/ACM International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems. London, UK: IEEE Computer Society, Washington, DC, USA, 21-23 September 2009, 1-9

[10] Dubnicki C, Gryz L, Heldt L, Kaczmarczyk M, Kilian W, Strzelczak P, Szczepkowski J, Ungureanu C, Welnicki M. Hydrastor: A Scalable Secondary Storage[C]∥Proceedings of the 7th Conference on USENIX Conference on File and Storage Technologies. San Francisco, CA, USA: USENIX Association, Berkeley, CA, USA, 2009: 197-210

[11] Frey D, Kermarrec A, Kloudas K. Probabilistic Deduplication for Cluster-Based Storage Systems[C]∥Proceedings of the Third ACM Symposium on Cloud Computing. ACM, New York, NY, USA, 2012: 17

[12] Forman G, Eshghi K, Chiocchetti S. Finding Similar Files in Large Document Repositories. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Chicago, IL, USA: ACM, New York, NY, USA, 2005: 394-400