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

1、一種低開銷的并行重復數(shù)據(jù)刪除算法DOIDO：I10.11907/rjdk.1514860引言隨著互聯(lián)網(wǎng)技術的不斷發(fā)展，各種重要數(shù)據(jù)正在以PB（千萬億字節(jié)）的速度逐年增長。重復數(shù)據(jù)刪除技術通過對存儲數(shù)據(jù)流中冗余數(shù)據(jù)的定位與消除實現(xiàn)存儲資源高效利用，使其在網(wǎng)絡存儲和備份系統(tǒng)中發(fā)揮著越來越重要的作用。在重復數(shù)據(jù)刪除系統(tǒng)中，存儲數(shù)據(jù)流首先被特定的數(shù)據(jù)分塊算法按照一定的哈希計算結果進行分割，然后對分割后數(shù)據(jù)塊的內(nèi)容信息進行相應的哈希計算（以MD-51和SHA-12為主），將計算結果標識每個數(shù)據(jù)塊的特定指紋信息。全局索引表保存著已存數(shù)據(jù)塊的相關元數(shù)據(jù)信息（包括數(shù)據(jù)塊的指紋信息、存儲地址信息等），通過對當前

2、數(shù)據(jù)塊指紋信息的查詢結果可以判斷當前數(shù)據(jù)塊是否為重復數(shù)據(jù)塊。通過存儲數(shù)據(jù)流分塊和查重操作，重復數(shù)據(jù)刪除技術能夠有效地減少存儲數(shù)據(jù)流中的冗余數(shù)據(jù)，在實現(xiàn)存儲空間的高效利用的同時減少冗余數(shù)據(jù)所占用的網(wǎng)絡傳輸帶寬。隨著多核和并行優(yōu)化技術的發(fā)展，傳統(tǒng)重復數(shù)據(jù)刪除技術的并行優(yōu)化已經(jīng)成為相關研究的熱點之一。Al-KiswanySamer等3提出的StoreGPU技術最先采用GP度現(xiàn)重復數(shù)據(jù)刪除技術中的并行數(shù)據(jù)分塊和哈希計算方法。該方法采用基于GPUW重刪計算加速的思想，通過大規(guī)模的并行線程將重刪計算性能提高了35倍。夏文等4針對并行流水線，對基于語義的文件分塊算法中的同步問題進行了相應改進，使得并行流水能

3、夠應用于基于語義的重刪系統(tǒng)中。然而，由于全局數(shù)據(jù)塊索引表的唯一性，在并行處理過程中，并行重刪線程在訪問全局索引表時所造成的一致性開銷會給系統(tǒng)性能帶來較大影響。本文針對以上問題，對已有算法進行改進，提出一種低開銷的并行重復數(shù)據(jù)算法。1并行一致性開銷近年來，隨著多核技術的不斷發(fā)展，并行技術逐漸成為研究熱點。如圖1所示，重復數(shù)據(jù)刪除的并行實現(xiàn)主要采用并行流水線的方式。每條流水線由數(shù)據(jù)分塊、數(shù)據(jù)塊哈希指紋計算、數(shù)據(jù)塊指紋索引表去重處理以及數(shù)據(jù)塊內(nèi)容存儲4個單獨的處理單元組成，流水間并行執(zhí)行各自的處理模塊。通過多流水線間并行實現(xiàn)，能有效利用多核處理器在并行處理上的優(yōu)勢，使得重刪系統(tǒng)的整體性能得到提高。同

4、時，它還實現(xiàn)了數(shù)據(jù)塊的指紋索引表查重處理并行。而在并行流水線中的數(shù)據(jù)塊查重能在一定程度上掩蓋單個線程的磁盤索引表I/O訪問延遲。在并行數(shù)據(jù)塊去重過程中，全局指紋索引表需要滿足多線程并行查詢和更新需求。然而，由于索引表中的數(shù)據(jù)塊索引信息需要保證其唯一性的特點，因此多線程之間的并行查詢需要設計一種有效的同步機制。隨著并行度的增加，傳統(tǒng)基于鎖的同步機制將帶來較大的同步開銷。雖然一些優(yōu)化的并行算法能夠具有較低的同步代價（例如對于同步讀操作的Read-Copy-Update,RCUM法5）,但由于重復數(shù)據(jù)刪除對數(shù)據(jù)唯一性的需求，此類方法并不適用于并行索引表查重和更新操作。圖1并行流水線結構為測試并行查重

5、在不同并行規(guī)模和不同索引結構下基于輕量級鎖的同步機制所帶來的同步開銷，筆者作了以下測試。在一臺擁有4核2.6GHZ處理器的服務器中，將一個4G大小的共包含2216836個數(shù)據(jù)塊的數(shù)據(jù)集（平均分塊大小為4KB）用于一個RAMK引表的并行查重。索引表中桶標的規(guī)模（即細粒度互斥鎖的數(shù)量）分別設置為16K、32K和64K。并行規(guī)卞K跨度從1個線程到256個線程，實行并行索引表查重。測試結果如圖2所示，隨著索引表中桶標的增長（從16K到64K）,在相同并行規(guī)模下，系統(tǒng)性能隨之增加。這種性能增加是由于同一桶標中訪問沖突發(fā)生的概率隨著桶標數(shù)的增加而減小，并且并行規(guī)模越大，桶標數(shù)增加對性能的影響越大。在同一索

6、引表結構下，隨著并行規(guī)模的增長，系統(tǒng)性能增長幅度逐漸減小，直至達到一個增長極限。相對于理想狀態(tài)而言，如圖2中的bucket-64和bucket-64-ideal，在不同并行規(guī)模下實際得到系統(tǒng)加速比往往要大大低于理想加速比，并且隨著并行規(guī)模的擴大，加速比之差越來越大。造成這種現(xiàn)象的主要原因是基于細粒度互斥鎖的同步機制所帶來的同步開銷，并行度越高所造成的同步開銷將越大。通過以上實驗能夠得出，要提高并行索引表查重的整體性能，必須設計一種高效且具有低同步時延代價的同并行同步機制。圖2不同并行規(guī)模下多種結構的索引表并行查重性能比較2并行查重優(yōu)化方法為了解決以上并行索引查重所帶來的一致性開銷，筆者提出一種

7、優(yōu)化的并行查重方法。該方法主要思想來源于HYDRAstor6中所采用的一種基于數(shù)據(jù)塊指紋固定長度前綴的存儲節(jié)點負載平衡算法。通過數(shù)據(jù)指紋的固定長度前綴，不僅能使分布式存儲系統(tǒng)中各個存儲節(jié)點間達到一種負載平衡，同時能保證各存儲節(jié)點間的數(shù)據(jù)各不相同，從而實現(xiàn)各存儲節(jié)點間的并行重刪?；跀?shù)據(jù)指紋固定前綴的思想，筆者提出一種并行索引表的結構。如圖3所示，該結構按照數(shù)據(jù)塊的指紋后綴將索引表分成不同的索引子表，每個索引子表對應一個查重線程。數(shù)據(jù)塊在進行索引表查重處理前，會根據(jù)其指紋后綴的不同分別進入不同的后綴處理隊列中（SurfixQueue,SFQ,每個后綴處理隊列對應于不同的查重處理線程。每個查重處理

8、線程分別從相應處理隊列中提取數(shù)據(jù)塊，在其對應的后綴子表中進行數(shù)據(jù)的查重和更新操作。由于數(shù)據(jù)后綴的不同，每個處理線程選擇的后綴索引子表也分別不同，這樣就保證了并行索引表中各個查重線程間的一致性，從而避免了各線程在索引表查重時所帶來的同步開銷。同時，該并行索引結構同樣能保持查重數(shù)據(jù)塊的局部性特性。例如，當存在3個并行查重線程時，存儲數(shù)據(jù)塊（q0，w2，e1，r1，t2，y1，a0，s0，d1，f2）將按照其后綴劃分為3個子序列（q0，a0，50） ,（w2,t2,f2）和（el,門，y1,di）。而每個子序列仍然保持了他們在原序列中的順序，因此在后續(xù)緩存處理中能夠有效利用其局部性原理。圖3并行索引

9、表結構3 并行重刪系統(tǒng)整體架構并行查重系統(tǒng)整體架構如圖4所示，在數(shù)據(jù)傳輸?shù)椒掌髦?，客戶端首先完成存儲文件的分塊和指紋計算，然后將相應的數(shù)據(jù)塊及相關元數(shù)據(jù)（主要包括數(shù)據(jù)塊的指紋信息、文件相應的代表指紋及文件恢復字典）一起傳到存儲服務器端。存儲服務器將完成數(shù)據(jù)塊的查重及存儲工作。如圖4所示，數(shù)據(jù)處理流程至上而下由不同的處理線程分步完成。在數(shù)據(jù)處理過程中，數(shù)據(jù)塊及其相應的元數(shù)據(jù)根據(jù)不同的緩存算法被送入到不同的后綴隊列中。在基于局部性重刪算法中，根據(jù)數(shù)據(jù)塊指紋的后綴送入相應隊列，而在文件相似性重刪算法中，則根據(jù)數(shù)據(jù)塊所屬文件代表指紋的后綴送入相應隊列中。數(shù)據(jù)送入到隊列后，每個隊列對應的去重線程將從

10、隊列尾逐一取出相應數(shù)據(jù)塊信息，并在并行索引結構中進行去重和更新操作。為保持數(shù)據(jù)的局部性和相似性特征，對應于并行索引結構設計相應的并行緩存優(yōu)化并行線程的磁盤索引I/O。唯一的數(shù)據(jù)塊內(nèi)容將存儲在后端的存儲節(jié)點中，而相應的元數(shù)據(jù)信息將保存在服務器的本地磁盤中。4 算法性能評價并行查重的實驗原型運行在一臺基于Linux操作系統(tǒng)的服務器上。服務器硬件配置包括4核2.4GHzCPU6GB內(nèi)存及由15塊磁盤組成的總容量為3TB的磁盤陣列。因為并行查重主要測試數(shù)據(jù)指紋在索引表中的查重性能，因此測試數(shù)據(jù)集主要由數(shù)據(jù)塊指紋組成，分別收集于不同的三類數(shù)據(jù)集合中。測試數(shù)據(jù)集的名字分別為GROUINCREMENTLIN

11、UXGROU收集于本課題組多名研究生主機中的文檔全備份，INCREMENT集于多臺主機的增量備份文件信息，LINUX搜集于linux內(nèi)核多版本的內(nèi)核源碼中。在局部性原理數(shù)據(jù)去重方法以及文件相似性的數(shù)據(jù)去重方法的實現(xiàn)上，實驗原型分別借鑒了ChunkStash7和SiLo8的思想。為了詳細表示索引查重的吞吐量，本次試驗采用的是哈希指紋的數(shù)據(jù)集進行的并行索引表的查重能力測試，因此吞吐率采用每秒處理的數(shù)據(jù)塊指紋數(shù)表示：Throughput=Chunk_countsTime_parallel_dedup（1）其中，參數(shù)Time-parallel-dedup表示完成全部數(shù)據(jù)指紋查重所消耗的時間，Chunk

12、-counts表示所處理數(shù)據(jù)指紋的總數(shù)量。圖5顯示了基于相似性的重復數(shù)據(jù)刪除技術中采用并行優(yōu)化策略和采用傳統(tǒng)的細粒度鎖策略的查重吞吐量的比較。隨著并行度的提高，并行優(yōu)化查重方法最多能夠?qū)?個數(shù)據(jù)集的查重吞吐量提高34倍。相對于基于鎖機制的并行方法而言，該并行優(yōu)化方法平均能夠得到1.5倍的性能提升。圖5基于相似性重刪的并行優(yōu)化查重與傳統(tǒng)鎖機制并行方式的吞吐量比較6顯示了基于局部性的重復數(shù)據(jù)刪除技術中采用并行優(yōu)化策略和采用傳統(tǒng)的細粒度鎖策略的查重吞吐量的比較。隨著并行度的提高，并行優(yōu)化查重方法最多能夠?qū)?個數(shù)據(jù)集的查重吞吐量提高45倍。相對于基于鎖機制的并行方法而言，該并行優(yōu)化方法平均能夠得到1.3倍的性能提升。