基于文件路徑的重復(fù)數(shù)據(jù)刪除集群的數(shù)據(jù)路由策略

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

(1.西北工業(yè)大學(xué) 計算機學(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ù)丟失會嚴重降低服務(wù)質(zhì)量，從而降低企業(yè)的利潤。為了避免數(shù)據(jù)丟失，數(shù)據(jù)中心必須在幾年的備份周期內(nèi)定期備份所有數(shù)據(jù)(通常是每周一次全備份)，并且保證在需要時能提供數(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ù)備份成本與磁帶相當甚至更低。這就使基于磁盤的重復(fù)數(shù)據(jù)刪除技術(shù)越來越流行，逐漸替代基于磁帶的數(shù)據(jù)備份技術(shù)[4-8]。單節(jié)點重復(fù)數(shù)據(jù)刪除的容量是有限的，目前最先進的重復(fù)數(shù)據(jù)刪除可以存儲幾十PB(petabyte)的數(shù)據(jù)[3]。然而，數(shù)據(jù)中心的備份需求已經(jīng)超過單節(jié)點重復(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ù)合理分配到各個重復(fù)數(shù)據(jù)刪除節(jié)點上，即數(shù)據(jù)路由策略。重復(fù)數(shù)據(jù)刪除集群的數(shù)據(jù)路由策略的目標是：①保證較高的重復(fù)數(shù)據(jù)刪除率；②保證各個重復(fù)數(shù)據(jù)刪除節(jié)點的負載平衡。重復(fù)數(shù)據(jù)刪除率是待存儲的數(shù)據(jù)量與存儲使用量的比值，用于評估重復(fù)數(shù)據(jù)刪除的存儲利用率。已有的重復(fù)數(shù)據(jù)刪除集群的數(shù)據(jù)路由策略使用文件或者數(shù)據(jù)段的所有數(shù)據(jù)塊簽名中最小的數(shù)據(jù)塊簽名計算目標節(jié)點[3,9]，稱作MCS(minimum chunk signature)路由策略。對于包括幾個節(jié)點的小規(guī)模重復(fù)數(shù)據(jù)刪除集群，這種方法可以保證較高的重復(fù)數(shù)據(jù)刪除率。但是，當重復(fù)數(shù)據(jù)刪除集群的規(guī)模較大時，這種方法的重復(fù)數(shù)據(jù)刪除率急劇下降，遠遠低于單節(jié)點重復(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ù)分配到同一個節(jié)點上，從而提高重復(fù)數(shù)據(jù)刪除率。文章使用文件路徑設(shè)計了一種數(shù)據(jù)路由策略。構(gòu)建一個路徑路由索引保存路徑相關(guān)的路由信息。當需要路由數(shù)據(jù)時，先查詢路徑路由索引是否存在改路徑的路由信息，如果存在，就直接使用該路由信息路由數(shù)據(jù)到目標節(jié)點；如果不存在，就使用文件的最小塊簽名計算目標節(jié)點。

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

1 設(shè) 計

1.1 架 構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2給出了DRSD數(shù)據(jù)路由算法的細節(jié)。為了便于比較，圖2也包括了MCS數(shù)據(jù)路由算法。在算法中，directoryName指的是文件的整個路徑，包括從根目錄至文件所在的目錄。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é)點重復(fù)數(shù)據(jù)刪除。收集了一個真實世界的數(shù)據(jù)集，并構(gòu)建了一個仿真器比較它們。首先詳細描述了仿真器。然后，描述了評估標準。最后，描述并分析了實驗結(jié)果，包括存儲空間使用情況和負載均衡情況。

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

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

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

2.2 評估標準

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

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

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

2.3 仿真器

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

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

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

仿真器的第3個部分是分塊器。它逐個處理文件，輸出分塊結(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é)點數(shù)量，比較了DRSD、MCS和單節(jié)點重復(fù)數(shù)據(jù)刪除。圖3給出了比較結(jié)果。對于重復(fù)數(shù)據(jù)刪除集群的各種不同的節(jié)點數(shù)量(包括2，4，8，16，32，64，128，256，512，1 024)，測量了算法的重復(fù)數(shù)據(jù)刪除率。在圖3中，Single node表示單節(jié)點重復(fù)數(shù)據(jù)刪除；DRSD(2)表示DRSD并且路徑深度是2。

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

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

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

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

2.5 負載均衡

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

圖4 負載均衡比較

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

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

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

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

3 結(jié) 論

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

參考文獻：

[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