一种低开销的并行重复数据删除算法

江程　朱锐　张芳等

摘要：重复数据删除是数据备份系统中的一种重要数据压缩技术。随着备份数据量的逐渐增多，对备份数据中重复数据块进行识别和删除可大大减少数据备份系统中的存储空间和数据传输带宽，提高数据备份系统的效率。当前，随着多核和并行处理技术的发展，重删技术并行实现已经成为研究热点。随着并行规模的扩大，在并行重删技术中，多线程在并行数据块索引查询中的一致性开销成为影响并行查重性能的主要因素。为减少查询线程间的一致性开销，结合目前主流的并行重删技术，提出一种基于数据后缀的并行重删算法。通过对实际数据集的测试，相对于传统并行重删算法，该方法能有效提高系统性能1.5～2倍。

关键词：重复数据删除；多线程；并行

DOIDOI：10.11907/rjdk.151486

中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2015）008009604

0 引言

随着互联网技术的不断发展，各种重要数据正在以PB（千万亿字节）的速度逐年增长。重复数据删除技术通过对存储数据流中冗余数据的定位与消除实现存储资源高效利用，使其在网络存储和备份系统中发挥着越来越重要的作用。在重复数据删除系统中，存储数据流首先被特定的数据分块算法按照一定的哈希计算结果进行分割，然后对分割后数据块的内容信息进行相应的哈希计算（以MD-5[1]和SHA-1[2]为主），将计算结果标识每个数据块的特定指纹信息。全局索引表保存着已存数据块的相关元数据信息（包括数据块的指纹信息、存储地址信息等），通过对当前数据块指纹信息的查询结果可以判断当前数据块是否为重复数据块。通过存储数据流分块和查重操作，重复数据删除技术能够有效地减少存储数据流中的冗余数据，在实现存储空间的高效利用的同时减少冗余数据所占用的网络传输带宽。

随着多核和并行优化技术的发展，传统重复数据删除技术的并行优化已经成为相关研究的热点之一。Al-Kiswany Samer等[3]提出的StoreGPU技术最先采用GPU实现重复数据删除技术中的并行数据分块和哈希计算方法。该方法采用基于GPU的重删计算加速的思想，通过大规模的并行线程将重删计算性能提高了3～5倍。夏文等[4]针对并行流水线，对基于语义的文件分块算法中的同步问题进行了相应改进，使得并行流水能够应用于基于语义的重删系统中。然而，由于全局数据块索引表的唯一性，在并行处理过程中，并行重删线程在访问全局索引表时所造成的一致性开销会给系统性能带来较大影响。本文针对以上问题，对已有算法进行改进，提出一种低开销的并行重复数据算法。

1 并行一致性开销

近年来，随着多核技术的不断发展，并行技术逐渐成为研究热点。如图1所示，重复数据删除的并行实现主要采用并行流水线的方式。每条流水线由数据分块、数据块哈希指纹计算、数据块指纹索引表去重处理以及数据块内容存储4个单独的处理单元组成，流水间并行执行各自的处理模块。通过多流水线间并行实现，能有效利用多核处理器在并行处理上的优势，使得重删系统的整体性能得到提高。同时，它还实现了数据块的指纹索引表查重处理并行。而在并行流水线中的数据块查重能在一定程度上掩盖单个线程的磁盘索引表I/O访问延迟。在并行数据块去重过程中，全局指纹索引表需要满足多线程并行查询和更新需求。然而，由于索引表中的数据块索引信息需要保证其唯一性的特点，因此多线程之间的并行查询需要设计一种有效的同步机制。随着并行度的增加，传统基于锁的同步机制将带来较大的同步开销。虽然一些优化的并行算法能够具有较低的同步代价（例如对于同步读操作的Read-Copy-Update，RCU算法[5]），但由于重复数据删除对数据唯一性的需求，此类方法并不适用于并行索引表查重和更新操作。

图1 并行流水线结构

为测试并行查重在不同并行规模和不同索引结构下基于轻量级锁的同步机制所带来的同步开销，笔者作了以下测试。在一台拥有4核2.6GHZ处理器的服务器中，将一个4G大小的共包含2 216 836个数据块的数据集（平均分块大小为4KB）用于一个RAM索引表的并行查重。索引表中桶标的规模（即细粒度互斥锁的数量）分别设置为16K、32K和64K。并行规模跨度从1个线程到256个线程，实行并行索引表查重。测试结果如图2所示，随着索引表中桶标的增长（从16K到64K），在相同并行规模下，系统性能随之增加。这种性能增加是由于同一桶标中访问冲突发生的概率随着桶标数的增加而减小，并且并行规模越大，桶标数增加对性能的影响越大。在同一索引表结构下，随着并行规模的增长，系统性能增长幅度逐渐减小，直至达到一个增长极限。相对于理想状态而言，如图2中的bucket-64和bucket-64-ideal，在不同并行规模下实际得到系统加速比往往要大大低于理想加速比，并且随着并行规模的扩大，加速比之差越来越大。造成这种现象的主要原因是基于细粒度互斥锁的同步机制所带来的同步开销，并行度越高所造成的同步开销将越大。通过以上实验能够得出，要提高并行索引表查重的整体性能，必须设计一种高效且具有低同步时延代价的同并行同步机制。

图2 不同并行规模下多种结构的索引表并行查重性能比较

2 并行查重优化方法

为了解决以上并行索引查重所带来的一致性开销，笔者提出一种优化的并行查重方法。该方法主要思想来源于HYDRAstor[6]中所采用的一种基于数据块指纹固定长度前缀的存储节点负载平衡算法。通过数据指纹的固定长度前缀，不仅能使分布式存储系统中各个存储节点间达到一种负载平衡，同时能保证各存储节点间的数据各不相同，从而实现各存储节点间的并行重删。

基于数据指纹固定前缀的思想，笔者提出一种并行索引表的结构。如图3所示，该结构按照数据块的指纹后缀将索引表分成不同的索引子表，每个索引子表对应一个查重线程。数据块在进行索引表查重处理前，会根据其指纹后缀的不同分别进入不同的后缀处理队列中（Surfix Queue，SFQ），每个后缀处理队列对应于不同的查重处理线程。每个查重处理线程分别从相应处理队列中提取数据块，在其对应的后缀子表中进行数据的查重和更新操作。由于数据后缀的不同，每个处理线程选择的后缀索引子表也分别不同，这样就保证了并行索引表中各个查重线程间的一致性，从而避免了各线程在索引表查重时所带来的同步开销。同时，该并行索引结构同样能保持查重数据块的局部性特性。例如，当存在3个并行查重线程时，存储数据块（q0，w2，e1，r1，t2，y1，a0，s0，d1，f2）将按照其后缀划分为3个子序列（q0，a0，s0），（w2，t2，f2）和（e1，r1，y1，d1）。而每个子序列仍然保持了他们在原序列中的顺序，因此在后续缓存处理中能够有效利用其局部性原理。

图3 并行索引表结构

3 并行重删系统整体架构

并行查重系统整体架构如图4所示，在数据传输到服务器之前，客户端首先完成存储文件的分块和指纹计算，然后将相应的数据块及相关元数据（主要包括数据块的指纹信息、文件相应的代表指纹及文件恢复字典）一起传到存储服务器端。存储服务器将完成数据块的查重及存储工作。

如图4所示，数据处理流程至上而下由不同的处理线程分步完成。在数据处理过程中，数据块及其相应的元数据根据不同的缓存算法被送入到不同的后缀队列中。在基于局部性重删算法中，根据数据块指纹的后缀送入相应队列，而在文件相似性重删算法中，则根据数据块所属文件代表指纹的后缀送入相应队列中。数据送入到队列后，每个队列对应的去重线程将从队列尾逐一取出相应数据块信息，并在并行索引结构中进行去重和更新操作。为保持数据的局部性和相似性特征，对应于并行索引结构设计相应的并行缓存优化并行线程的磁盘索引I/O。唯一的数据块内容将存储在后端的存储节点中，而相应的元数据信息将保存在服务器的本地磁盘中。

4 算法性能评价

并行查重的实验原型运行在一台基于Linux操作系统的服务器上。服务器硬件配置包括4核2.4GHzCPU，6GB内存及由15块磁盘组成的总容量为3TB的磁盘阵列。因为并行查重主要测试数据指纹在索引表中的查重性能，因此测试数据集主要由数据块指纹组成，分别收集于不同的三类数据集合中。测试数据集的名字分别为GROUP，INCREMENT和LINUX。GROUP收集于本课题组多名研究生主机中的文档全备份，INCREMENT收集于多台主机的增量备份文件信息，LINUX搜集于linux内核多版本的内核源码中。在局部性原理数据去重方法以及文件相似性的数据去重方法的实现上，实验原型分别借鉴了ChunkStash [7]和SiLo[8]的思想。

为了详细表示索引查重的吞吐量，本次试验采用的是哈希指纹的数据集进行的并行索引表的查重能力测试，因此吞吐率采用每秒处理的数据块指纹数表示：

Throughput=Chunk_countsTime_parallel_dedup（1）

其中，参数Time-parallel-dedup表示完成全部数据指纹查重所消耗的时间，Chunk-counts表示所处理数据指纹的总数量。

图5显示了基于相似性的重复数据删除技术中采用并行优化策略和采用传统的细粒度锁策略的查重吞吐量的比较。随着并行度的提高，并行优化查重方法最多能够将3个数据集的查重吞吐量提高3～4倍。相对于基于锁机制的并行方法而言，该并行优化方法平均能够得到1.5倍的性能提升。

图5 基于相似性重删的并行优化查重与传统锁机制并行方式的吞吐量比较

图6显示了基于局部性的重复数据删除技术中采用并行优化策略和采用传统的细粒度锁策略的查重吞吐量的比较。随着并行度的提高，并行优化查重方法最多能够将3个数据集的查重吞吐量提高4～5倍。相对于基于锁机制的并行方法而言，该并行优化方法平均能够得到1.3倍的性能提升。

图6 基于局部性重删的并行优化查重与传统锁机制并行方式的吞吐量比较

5 结语

并行优化查重技术能够在局部性原理和相似性原理的重删方法中提升系统性能，从而减少索引表的磁盘I/O的影响。同时，并行优化计算能得到比锁机制的并行查重方法更好的效果。然而，系统整体性能的提升极限取决于硬件环境的支持，因此如何在特定硬件环境下，选择并行参数，如并行线程数、缓存大小等的最优设定值还有待进一步研究。

参考文献：

[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，FENG 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，FENG 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.

（责任编辑：陈福时）