一種低開(kāi)銷的并行重復(fù)數(shù)據(jù)刪除算法

江程　朱銳　張芳等

摘要：重復(fù)數(shù)據(jù)刪除是數(shù)據(jù)備份系統(tǒng)中的一種重要數(shù)據(jù)壓縮技術(shù)。隨著備份數(shù)據(jù)量的逐漸增多，對(duì)備份數(shù)據(jù)中重復(fù)數(shù)據(jù)塊進(jìn)行識(shí)別和刪除可大大減少數(shù)據(jù)備份系統(tǒng)中的存儲(chǔ)空間和數(shù)據(jù)傳輸帶寬，提高數(shù)據(jù)備份系統(tǒng)的效率。當(dāng)前，隨著多核和并行處理技術(shù)的發(fā)展，重刪技術(shù)并行實(shí)現(xiàn)已經(jīng)成為研究熱點(diǎn)。隨著并行規(guī)模的擴(kuò)大，在并行重刪技術(shù)中，多線程在并行數(shù)據(jù)塊索引查詢中的一致性開(kāi)銷成為影響并行查重性能的主要因素。為減少查詢線程間的一致性開(kāi)銷，結(jié)合目前主流的并行重刪技術(shù)，提出一種基于數(shù)據(jù)后綴的并行重刪算法。通過(guò)對(duì)實(shí)際數(shù)據(jù)集的測(cè)試，相對(duì)于傳統(tǒng)并行重刪算法，該方法能有效提高系統(tǒng)性能1.5～2倍。

關(guān)鍵詞：重復(fù)數(shù)據(jù)刪除；多線程；并行

DOIDOI：10.11907/rjdk.151486

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2015）008009604

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，各種重要數(shù)據(jù)正在以PB（千萬(wàn)億字節(jié)）的速度逐年增長(zhǎng)。重復(fù)數(shù)據(jù)刪除技術(shù)通過(guò)對(duì)存儲(chǔ)數(shù)據(jù)流中冗余數(shù)據(jù)的定位與消除實(shí)現(xiàn)存儲(chǔ)資源高效利用，使其在網(wǎng)絡(luò)存儲(chǔ)和備份系統(tǒng)中發(fā)揮著越來(lái)越重要的作用。在重復(fù)數(shù)據(jù)刪除系統(tǒng)中，存儲(chǔ)數(shù)據(jù)流首先被特定的數(shù)據(jù)分塊算法按照一定的哈希計(jì)算結(jié)果進(jìn)行分割，然后對(duì)分割后數(shù)據(jù)塊的內(nèi)容信息進(jìn)行相應(yīng)的哈希計(jì)算（以MD-5[1]和SHA-1[2]為主），將計(jì)算結(jié)果標(biāo)識(shí)每個(gè)數(shù)據(jù)塊的特定指紋信息。全局索引表保存著已存數(shù)據(jù)塊的相關(guān)元數(shù)據(jù)信息（包括數(shù)據(jù)塊的指紋信息、存儲(chǔ)地址信息等），通過(guò)對(duì)當(dāng)前數(shù)據(jù)塊指紋信息的查詢結(jié)果可以判斷當(dāng)前數(shù)據(jù)塊是否為重復(fù)數(shù)據(jù)塊。通過(guò)存儲(chǔ)數(shù)據(jù)流分塊和查重操作，重復(fù)數(shù)據(jù)刪除技術(shù)能夠有效地減少存儲(chǔ)數(shù)據(jù)流中的冗余數(shù)據(jù)，在實(shí)現(xiàn)存儲(chǔ)空間的高效利用的同時(shí)減少冗余數(shù)據(jù)所占用的網(wǎng)絡(luò)傳輸帶寬。

隨著多核和并行優(yōu)化技術(shù)的發(fā)展，傳統(tǒng)重復(fù)數(shù)據(jù)刪除技術(shù)的并行優(yōu)化已經(jīng)成為相關(guān)研究的熱點(diǎn)之一。Al-Kiswany Samer等[3]提出的StoreGPU技術(shù)最先采用GPU實(shí)現(xiàn)重復(fù)數(shù)據(jù)刪除技術(shù)中的并行數(shù)據(jù)分塊和哈希計(jì)算方法。該方法采用基于GPU的重刪計(jì)算加速的思想，通過(guò)大規(guī)模的并行線程將重刪計(jì)算性能提高了3～5倍。夏文等[4]針對(duì)并行流水線，對(duì)基于語(yǔ)義的文件分塊算法中的同步問(wèn)題進(jìn)行了相應(yīng)改進(jìn)，使得并行流水能夠應(yīng)用于基于語(yǔ)義的重刪系統(tǒng)中。然而，由于全局?jǐn)?shù)據(jù)塊索引表的唯一性，在并行處理過(guò)程中，并行重刪線程在訪問(wèn)全局索引表時(shí)所造成的一致性開(kāi)銷會(huì)給系統(tǒng)性能帶來(lái)較大影響。本文針對(duì)以上問(wèn)題，對(duì)已有算法進(jìn)行改進(jìn)，提出一種低開(kāi)銷的并行重復(fù)數(shù)據(jù)算法。

1 并行一致性開(kāi)銷

近年來(lái)，隨著多核技術(shù)的不斷發(fā)展，并行技術(shù)逐漸成為研究熱點(diǎn)。如圖1所示，重復(fù)數(shù)據(jù)刪除的并行實(shí)現(xiàn)主要采用并行流水線的方式。每條流水線由數(shù)據(jù)分塊、數(shù)據(jù)塊哈希指紋計(jì)算、數(shù)據(jù)塊指紋索引表去重處理以及數(shù)據(jù)塊內(nèi)容存儲(chǔ)4個(gè)單獨(dú)的處理單元組成，流水間并行執(zhí)行各自的處理模塊。通過(guò)多流水線間并行實(shí)現(xiàn)，能有效利用多核處理器在并行處理上的優(yōu)勢(shì)，使得重刪系統(tǒng)的整體性能得到提高。同時(shí)，它還實(shí)現(xiàn)了數(shù)據(jù)塊的指紋索引表查重處理并行。而在并行流水線中的數(shù)據(jù)塊查重能在一定程度上掩蓋單個(gè)線程的磁盤索引表I/O訪問(wèn)延遲。在并行數(shù)據(jù)塊去重過(guò)程中，全局指紋索引表需要滿足多線程并行查詢和更新需求。然而，由于索引表中的數(shù)據(jù)塊索引信息需要保證其唯一性的特點(diǎn)，因此多線程之間的并行查詢需要設(shè)計(jì)一種有效的同步機(jī)制。隨著并行度的增加，傳統(tǒng)基于鎖的同步機(jī)制將帶來(lái)較大的同步開(kāi)銷。雖然一些優(yōu)化的并行算法能夠具有較低的同步代價(jià)（例如對(duì)于同步讀操作的Read-Copy-Update，RCU算法[5]），但由于重復(fù)數(shù)據(jù)刪除對(duì)數(shù)據(jù)唯一性的需求，此類方法并不適用于并行索引表查重和更新操作。

圖1 并行流水線結(jié)構(gòu)

為測(cè)試并行查重在不同并行規(guī)模和不同索引結(jié)構(gòu)下基于輕量級(jí)鎖的同步機(jī)制所帶來(lái)的同步開(kāi)銷，筆者作了以下測(cè)試。在一臺(tái)擁有4核2.6GHZ處理器的服務(wù)器中，將一個(gè)4G大小的共包含2 216 836個(gè)數(shù)據(jù)塊的數(shù)據(jù)集（平均分塊大小為4KB）用于一個(gè)RAM索引表的并行查重。索引表中桶標(biāo)的規(guī)模（即細(xì)粒度互斥鎖的數(shù)量）分別設(shè)置為16K、32K和64K。并行規(guī)模跨度從1個(gè)線程到256個(gè)線程，實(shí)行并行索引表查重。測(cè)試結(jié)果如圖2所示，隨著索引表中桶標(biāo)的增長(zhǎng)（從16K到64K），在相同并行規(guī)模下，系統(tǒng)性能隨之增加。這種性能增加是由于同一桶標(biāo)中訪問(wèn)沖突發(fā)生的概率隨著桶標(biāo)數(shù)的增加而減小，并且并行規(guī)模越大，桶標(biāo)數(shù)增加對(duì)性能的影響越大。在同一索引表結(jié)構(gòu)下，隨著并行規(guī)模的增長(zhǎng)，系統(tǒng)性能增長(zhǎng)幅度逐漸減小，直至達(dá)到一個(gè)增長(zhǎng)極限。相對(duì)于理想狀態(tài)而言，如圖2中的bucket-64和bucket-64-ideal，在不同并行規(guī)模下實(shí)際得到系統(tǒng)加速比往往要大大低于理想加速比，并且隨著并行規(guī)模的擴(kuò)大，加速比之差越來(lái)越大。造成這種現(xiàn)象的主要原因是基于細(xì)粒度互斥鎖的同步機(jī)制所帶來(lái)的同步開(kāi)銷，并行度越高所造成的同步開(kāi)銷將越大。通過(guò)以上實(shí)驗(yàn)?zāi)軌虻贸?，要提高并行索引表查重的整體性能，必須設(shè)計(jì)一種高效且具有低同步時(shí)延代價(jià)的同并行同步機(jī)制。

圖2 不同并行規(guī)模下多種結(jié)構(gòu)的索引表并行查重性能比較

2 并行查重優(yōu)化方法

為了解決以上并行索引查重所帶來(lái)的一致性開(kāi)銷，筆者提出一種優(yōu)化的并行查重方法。該方法主要思想來(lái)源于HYDRAstor[6]中所采用的一種基于數(shù)據(jù)塊指紋固定長(zhǎng)度前綴的存儲(chǔ)節(jié)點(diǎn)負(fù)載平衡算法。通過(guò)數(shù)據(jù)指紋的固定長(zhǎng)度前綴，不僅能使分布式存儲(chǔ)系統(tǒng)中各個(gè)存儲(chǔ)節(jié)點(diǎn)間達(dá)到一種負(fù)載平衡，同時(shí)能保證各存儲(chǔ)節(jié)點(diǎn)間的數(shù)據(jù)各不相同，從而實(shí)現(xiàn)各存儲(chǔ)節(jié)點(diǎn)間的并行重刪。

基于數(shù)據(jù)指紋固定前綴的思想，筆者提出一種并行索引表的結(jié)構(gòu)。如圖3所示，該結(jié)構(gòu)按照數(shù)據(jù)塊的指紋后綴將索引表分成不同的索引子表，每個(gè)索引子表對(duì)應(yīng)一個(gè)查重線程。數(shù)據(jù)塊在進(jìn)行索引表查重處理前，會(huì)根據(jù)其指紋后綴的不同分別進(jìn)入不同的后綴處理隊(duì)列中（Surfix Queue，SFQ），每個(gè)后綴處理隊(duì)列對(duì)應(yīng)于不同的查重處理線程。每個(gè)查重處理線程分別從相應(yīng)處理隊(duì)列中提取數(shù)據(jù)塊，在其對(duì)應(yīng)的后綴子表中進(jìn)行數(shù)據(jù)的查重和更新操作。由于數(shù)據(jù)后綴的不同，每個(gè)處理線程選擇的后綴索引子表也分別不同，這樣就保證了并行索引表中各個(gè)查重線程間的一致性，從而避免了各線程在索引表查重時(shí)所帶來(lái)的同步開(kāi)銷。同時(shí)，該并行索引結(jié)構(gòu)同樣能保持查重?cái)?shù)據(jù)塊的局部性特性。例如，當(dāng)存在3個(gè)并行查重線程時(shí)，存儲(chǔ)數(shù)據(jù)塊（q0，w2，e1，r1，t2，y1，a0，s0，d1，f2）將按照其后綴劃分為3個(gè)子序列（q0，a0，s0），（w2，t2，f2）和（e1，r1，y1，d1）。而每個(gè)子序列仍然保持了他們?cè)谠蛄兄械捻樞?，因此在后續(xù)緩存處理中能夠有效利用其局部性原理。

圖3 并行索引表結(jié)構(gòu)

3 并行重刪系統(tǒng)整體架構(gòu)

并行查重系統(tǒng)整體架構(gòu)如圖4所示，在數(shù)據(jù)傳輸?shù)椒?wù)器之前，客戶端首先完成存儲(chǔ)文件的分塊和指紋計(jì)算，然后將相應(yīng)的數(shù)據(jù)塊及相關(guān)元數(shù)據(jù)（主要包括數(shù)據(jù)塊的指紋信息、文件相應(yīng)的代表指紋及文件恢復(fù)字典）一起傳到存儲(chǔ)服務(wù)器端。存儲(chǔ)服務(wù)器將完成數(shù)據(jù)塊的查重及存儲(chǔ)工作。

如圖4所示，數(shù)據(jù)處理流程至上而下由不同的處理線程分步完成。在數(shù)據(jù)處理過(guò)程中，數(shù)據(jù)塊及其相應(yīng)的元數(shù)據(jù)根據(jù)不同的緩存算法被送入到不同的后綴隊(duì)列中。在基于局部性重刪算法中，根據(jù)數(shù)據(jù)塊指紋的后綴送入相應(yīng)隊(duì)列，而在文件相似性重刪算法中，則根據(jù)數(shù)據(jù)塊所屬文件代表指紋的后綴送入相應(yīng)隊(duì)列中。數(shù)據(jù)送入到隊(duì)列后，每個(gè)隊(duì)列對(duì)應(yīng)的去重線程將從隊(duì)列尾逐一取出相應(yīng)數(shù)據(jù)塊信息，并在并行索引結(jié)構(gòu)中進(jìn)行去重和更新操作。為保持?jǐn)?shù)據(jù)的局部性和相似性特征，對(duì)應(yīng)于并行索引結(jié)構(gòu)設(shè)計(jì)相應(yīng)的并行緩存優(yōu)化并行線程的磁盤索引I/O。唯一的數(shù)據(jù)塊內(nèi)容將存儲(chǔ)在后端的存儲(chǔ)節(jié)點(diǎn)中，而相應(yīng)的元數(shù)據(jù)信息將保存在服務(wù)器的本地磁盤中。

4 算法性能評(píng)價(jià)

并行查重的實(shí)驗(yàn)原型運(yùn)行在一臺(tái)基于Linux操作系統(tǒng)的服務(wù)器上。服務(wù)器硬件配置包括4核2.4GHzCPU，6GB內(nèi)存及由15塊磁盤組成的總?cè)萘繛?TB的磁盤陣列。因?yàn)椴⑿胁橹刂饕獪y(cè)試數(shù)據(jù)指紋在索引表中的查重性能，因此測(cè)試數(shù)據(jù)集主要由數(shù)據(jù)塊指紋組成，分別收集于不同的三類數(shù)據(jù)集合中。測(cè)試數(shù)據(jù)集的名字分別為GROUP，INCREMENT和LINUX。GROUP收集于本課題組多名研究生主機(jī)中的文檔全備份，INCREMENT收集于多臺(tái)主機(jī)的增量備份文件信息，LINUX搜集于linux內(nèi)核多版本的內(nèi)核源碼中。在局部性原理數(shù)據(jù)去重方法以及文件相似性的數(shù)據(jù)去重方法的實(shí)現(xiàn)上，實(shí)驗(yàn)原型分別借鑒了ChunkStash [7]和SiLo[8]的思想。

為了詳細(xì)表示索引查重的吞吐量，本次試驗(yàn)采用的是哈希指紋的數(shù)據(jù)集進(jìn)行的并行索引表的查重能力測(cè)試，因此吞吐率采用每秒處理的數(shù)據(jù)塊指紋數(shù)表示：

Throughput=Chunk_countsTime_parallel_dedup（1）

其中，參數(shù)Time-parallel-dedup表示完成全部數(shù)據(jù)指紋查重所消耗的時(shí)間，Chunk-counts表示所處理數(shù)據(jù)指紋的總數(shù)量。

圖5顯示了基于相似性的重復(fù)數(shù)據(jù)刪除技術(shù)中采用并行優(yōu)化策略和采用傳統(tǒng)的細(xì)粒度鎖策略的查重吞吐量的比較。隨著并行度的提高，并行優(yōu)化查重方法最多能夠?qū)?個(gè)數(shù)據(jù)集的查重吞吐量提高3～4倍。相對(duì)于基于鎖機(jī)制的并行方法而言，該并行優(yōu)化方法平均能夠得到1.5倍的性能提升。

圖5 基于相似性重刪的并行優(yōu)化查重與傳統(tǒng)鎖機(jī)制并行方式的吞吐量比較

圖6顯示了基于局部性的重復(fù)數(shù)據(jù)刪除技術(shù)中采用并行優(yōu)化策略和采用傳統(tǒng)的細(xì)粒度鎖策略的查重吞吐量的比較。隨著并行度的提高，并行優(yōu)化查重方法最多能夠?qū)?個(gè)數(shù)據(jù)集的查重吞吐量提高4～5倍。相對(duì)于基于鎖機(jī)制的并行方法而言，該并行優(yōu)化方法平均能夠得到1.3倍的性能提升。

圖6 基于局部性重刪的并行優(yōu)化查重與傳統(tǒng)鎖機(jī)制并行方式的吞吐量比較

5 結(jié)語(yǔ)

并行優(yōu)化查重技術(shù)能夠在局部性原理和相似性原理的重刪方法中提升系統(tǒng)性能，從而減少索引表的磁盤I/O的影響。同時(shí)，并行優(yōu)化計(jì)算能得到比鎖機(jī)制的并行查重方法更好的效果。然而，系統(tǒng)整體性能的提升極限取決于硬件環(huán)境的支持，因此如何在特定硬件環(huán)境下，選擇并行參數(shù)，如并行線程數(shù)、緩存大小等的最優(yōu)設(shè)定值還有待進(jìn)一步研究。

參考文獻(xiàn)：

[1] RIVEST R.The MD5 messagedigest algorithm[M].IETF，1992.

[2] ALFRED J，MENEZES，PAUL C.VAN OORSCHOT，et al.Vanstone[M].Handbook of Applied Cryptography.CRC Press，1996.

[3] ALKISWANY SAMER，GHARAIBEH ABDULLAH，SANTOS-NETO ELIZU，et al."StoreGPU： exploiting graphics processing units to accelerate distributed storage systems"[C].In Proceedings of the 17th international symposium on High Performance Distributed Computing，165174，2008.

[4] W XIA H，JIANG，F(xiàn)ENG D，et al.Accelerating data deduplication by exploiting pipelining and parallelism with multicore or manycore processors [C].Proceedings of the 10th USENIX Conference on File and Storage Technologies （FAST12）.San Jose： USENIX Association，2012：12.

[5] TRIPLETT J，MCKENNEY E P，WALPOLE RESIZABLE J，et al.Concurrent hash tables via relativistic programming[C].Proceedings of the 2011 conference on USENIX Annual Technical conference （USENIX ATC11），Portland： USENIX Association，2011，157172.

[6] MUTHITACHAROEN A，CHEN B，MAZIERES D.A low bandwidth network file system[C].In Proceedings of the 18th ACM Symposium on Operating Systems Principles （SOSP01），Oct.2001.174–187.

[7] DEBNATH B，SENGUPTA S，LI J.ChunkStash：speeding up inline storage deduplication using flash memory[C].Proceedings of the 2010 conference on USENIX Annual Technical conference （USENIX ATC10），Boston： USENIX Association，2010：1616

[8] W XIA，JIANG H，F(xiàn)ENG D，et al.SiLo：a similaritylocality based nearexact deduplication scheme with low RAM overhead and high throughput[C].In Proceedings of the 2011 conference on USENIX Annual Technical conference （USENIX ATC11）.Portland： USENIX Association，2011：2638.

（責(zé)任編輯：陳福時(shí)）