刘靖宇，杨雷，赵秀平，李娟，武优西

（河北工业大学计算机科学与软件学院，天津 300401）

DeduBS：一种基于Hash匹配的数据消重远程备份系统

刘靖宇，杨雷，赵秀平，李娟，武优西

（河北工业大学计算机科学与软件学院，天津 300401）

数据备份规模的不断增大，网络带宽成为了远程数据备份系统的瓶颈．针对这个问题，本文提出了一种基于Hash匹配的数据消重远程备份系统：DeduBS系统．DeduBS系统通过数据消重，避免了在数据备份过程中传输重复数据，有效地提高了网络传输效率．DeduBS系统在源节点和目标节点建立Hash库存储数据块的Hash值，数据传输前通过比对Hash值判断其是否为重复数据，只传输重复数据的Hash值和非重复数据，对于重复数据接收端通过Hash库恢复数据．实验数据表明，DeduBS系统可以减少网络传输的数据量，在降低成本、节省能耗的同时，提高数据备份的效率．

备份；数据消重；Hash值；网络传输

数据备份系统，也称为容灾系统或灾难恢复系统，指通过特定的数据备份恢复机制，能够在因灾难发生而导致数据丢失时，仍然能够最大限度地保障提供正常应用服务的计算机信息系统，即通过在异地建立和维护一个备份存储系统，利用地理上的分离来保证系统和数据对灾难性事件的抵御能力，是数据保持高可用性的最后一道防线[1]．

按照数据备份恢复功能实现的距离远近，数据备份系统可以分为远程数据备份恢复系统和本地数据备份恢复系统．本地数据备份恢复系统仅对人为操作失误、软件错误等有效，无法应对自然灾害，如火灾、地震，甚至恐怖袭击，因此对于数据依赖程度较高的场合，即使使用了本地数据备份恢复系统，仍然需要进行远程数据备份．

远程数据备份是数据容灾的一种重要手段，通过将本地数据复制到异地来保证数据的安全，本地存储系统称为源节点，远程存储系统称为目标节点．远程数据备份面临的一个主要问题是网络带宽的限制．通过光纤网络可以很好的解决网络带宽问题，但是，远程数据备份通常部署在不同建筑里，甚至两个不同的城市，使用光纤网络极大的提高了远程数据备份的成本．普通IP网络虽然成本很低，但是随着数据量的飞速增长，普通IP网络的带宽很难满足备份系统的要求，往往会因为网络延迟或阻塞造成数据丢失，网络成为了远程数据备份的瓶颈．

因此，需要深入研究如何提高普通网络的带宽效果，在不增加成本的情况下，满足系统要求．

研究表明[2]，在存储系统中，往往存在着大量的重复数据，最高可达数据总量的800%，在双机热备系统中，无论是主-从方式还是双主机方式，都需要保证两个节点间的数据一致性，因此不能直接利用重复数据删除技术删除冗余数据，而备份这些重复数据会造成严重的网络资源浪费．为解决远程数据备份系统中的网络瓶颈，本文提出1种利用数据去重技术避免重复数据传输的远程数据备份系统（Remote Data Backup System Based on Data Deduplicaion for Eliminating Duplicate Transmission，DeduBS）．

1 研究现状

随着信息技术的发展，数据信息在社会生活的各个方面都扮演者至关重要的角色，数据信息的安全性也日益重要．

RAID通过设置冗余来提高数据的安全性，但是RAID只能处理因硬件故障引起的数据丢失．一般情况下，RAID只能容忍1到2个磁盘同时出现故障．对于因操作错误、病毒和自然灾害等因素引起的数据丢失，RAID就无能为力了．因此除RAID外，大量数据保护技术得到广泛应用，其中主要有写前拷贝（copy-onwrite）、软件快照技术（snapshot）[3]、镜像技术[4]、连续数据保护[5]（continuous data protection，CDP）等．

数据备份系统有3种备份方式：完全备份，增量备份和差量备份[6]．完全备份（FullBackup）是指对整个系统或用户指定的所有文件数据进行一次全面的备份．其优点是数据恢复简单，不足之处是备份过程较长，而且会产生大量冗余数据，浪费存储空间．增量备份（IncrementalBackup）只备份相对于上一次备份操作创建或者更新过的数据，节省了磁带空间并且缩短了备份时间，但是数据恢复时操作复杂，而且每次备份对前一次备份数据的依存度大，导致增量备份的可靠性很差．差分备份（DifferentialBackup）只备份上一次完全备份后新产生和更新的数据．差分备份有效避免了前两种方法的缺点而保留了其优点，应用比较广泛．

数据存储惊人的增长速度意味着数据中心需要海量的存储空间，为了缓解存储系统的空间增长问题，缩减数据占用空间，节省网络带宽资源，降低成本，重复数据删除技术大量应用于存储备份和归档系统中[7-8]．

重复数据删除的目的在于节省存储空间和网络带宽资源，可以通过数据缩减率（Data Elimination Ratio，DER）来衡量重复数据删除的效果，数据缩减率是指重复数据删除之前的数据量（ByteIn）与经过重复数据删除之后的数据量（ByteOut）之比[9]，公式表示为

重复数据删除可以实现在文件层次上，也可以实现在块层次上，甚至实现在位层次上．为达到更高的数据缩减率，需要寻找恰当的数据划分策略和划分粒度．常采用的划分策略包括：全文件划分、静态划分、基于内容分块、基于应用分块[10-11]和Delta编码．

应用在备份领域的重复数据删除技术主要由两类：基于目标数据和基于源数据．基于目标数据的重复数据删除，是数据在经过网络传输后进行重复数据删除，便于实现并且可以获得较高的数据缩减率；而基于源数据的重复数据删除，则是在数据备份前进行重复数据的删除工作，能够节省网络带宽，但数据缩减率不高．

2 基于数据消重的远程备份系统

针对远程数据备份系统的网络瓶颈，本文提出一种利用数据去重技术避免重复数据传输的远程数据备份系统（RemoteDataBackupSystemBasedonDataDeduplicaionforEliminating DuplicateTransmission，DeduBS），系统结构如图1所示．

图1中，源节点和目标节点通过普通IP网络互连，源节点和目标节点结构对称，数据备份时采用基于Hash值的数据消重算法，可以大量减少网络传输的数据量．

DeduBS系统中数据分为2部分：一部分是由用户或应用程序产生的正常数据，存储在大规模存储系统里，通常是由磁盘组成的磁盘阵列；另一部分是数据的Hash值，存储在SSD固态盘中．

DeduBS系统采用块级数据消重算法，在Hash库中为每个数据块创建1个Hash值．划分数据块大小可采用不同的粒度．粒度划分越细，数据消重率越高，消重效果越明显，但是服务器计算量也越大，会加重CPU负载；粒度划分越粗，虽然服务器计算量减少，但是消重效果也会显著降低．在实际应用中，可根据系统环境调整数据块划分粒度．

Hash值所占空间很小，但访问比较频繁，因此Hash库存储在随机读写性能高的固态盘中．

数据块的大小可以根据系统环境和不同应用设为4 kB、8 kB、16 kB等不同大小．当数据块以4 kB大小划分时，采用MD5算法计算的Hash值编码为16个字节，所占存储空间仅占原始数据的1/256．

存储系统中的每个数据块都有1个Hash值存放在Hash库中，Hash库结构如图2所示．

图1 DeduBS系统结构图Fig.1DeduBS Architecture

DeduBS系统属于热备份，目的在于对数据实现实时备份，使源节点和目标节点的数据同步更新，保持一致性．当源节点接收到1个数据块（目标块）的写请求后，将数据写入到目标块，并计算数据块的Hash值，对比Hash库中的Hash值．

如果Hash库中没有相匹配的Hash值，源节点将数据通过网络传送到目标节点，目标节点接收数据并将其写入存储系统．

图2 Hash库结构Fig.2Hash Repository

当本次写请求中某个数据块或某几个数据块的Hash值在Hash库中找到匹配项后，说明在存储系统中已经存储了相同内容的数据块，可判定该数据块为重复数据．由于源节点和目标节点的数据同步，因此，目标节点中也存在着和该数据块内容相同的数据．这时，源节点不再将此数据块传送给目标节点，而是只传送数据块的Hash值．因为Hash值的大小相对于数据块来说要小很多，所以传送Hash值所需的网络带宽和时间要比传送数据块要少很多，可以充分节省网络资源．

例如，源节点接收到一个写请求，将数据块A写入到存储系统，相应的，数据块A应通过网络传输到目标节点．源节点在与目标节点建立连接后通过以下步骤完成写操作和数据传输：

1）将数据块A写入到目标块；

2）计算数据块A的Hash值；

3）将数据块A的Hash值与Hash库对比；

4）如果没有匹配项，直接将数据块A通过网络传送给目标节点；

5）如果发现Hash库有相匹配的Hash值，源节点将数据块A的Hash值传送给目标节点；

6）数据块A的Hash值写入Hash库．

目标节点通过以下步骤完成写操作：

1）判断接收的内容为数据还是数据的Hash值；

2）如果接收的为数据，直接将数据写入存储系统；

3）计算数据块的Hash值并写入Hash库；

4）如果接收的为Hash值，跟据Hash值在Hash库中查找匹配项；

5）根据Hash库中查找到的相匹配的Hash值，确定数据块所在位置，假设为数据块B；

6）将数据块B复制到数据块A的存储空间；

7）将数据块A的Hash值写入Hash库；

8）向源节点发送“完成”信号．

传送过程中，为区分数据和数据的Hash值，在传送的数据包中加入标识符，如图3所示．如果传送的是数据，将标识符清“0”，如果传送的是数据的Hash值，将标识符置“1”．

当写入数据块为重复数据时，DeduBS系统只传输数据的Hash值，节约了网络带宽，系统性能得到了极大的提升．例如，数据块的划分粒度为4KB，写1个大小为8MB的文件，文件被分成了2048个数据块．假设其中50%的数据块为重复数据，则DeduBS系统需要向目标节点传送1024个数据块和1024个数据块的Hash值，相当于传送4MB的数据和4KB的Hash值，实际传送数据量远远低于原数据8 MB．

图3 DeduBS系统数据传输格式Fig.3DeduBS Network Package

3 数据恢复

当源节点出现故障后，需要从目标节点将数据复制到源节点，进行数据恢复．这时，由于目标节点和源节点的数据一致性被破坏，无法直接使用第3节中方法传送数据．数据恢复时，需要在目标节点创建1个临时Hash库．在目标节点向源节点传送数据块的同时，将数据块的Hash值写入临时Hash库．从传送第2个数据块开始，将数据块的Hash值与临时Hash库中的Hash值对比，查找匹配项．目标节点在与源节点建立后通过以下步骤完成数据传输：

1）创建临时Hash库；

2）读取第1个数据块，将数据块通过网络传送到源节点；并将该数据块的Hash值写入临时Hash库；

3）读取下一个数据块的Hash值，在临时Hash库中查找匹配值；

4）如果存在匹配项，将Hash值传送到源节点；

5）如果没有匹配项，直接将数据块传送到源节点；

6）更新临时Hash库；

7）判断数据是否传送完，如传送未完成，转到步骤3）继续执行；

8）传送完成，结束数据恢复．

源节点首先需要修复失效设备故障，然后同目标节点建立连接进行数据恢复，源节点通过以下步骤接收数据：

1）判断接收的内容为数据，还是数据的Hash值；

2）如果接收的是数据，直接将数据写入存储设备；

3）计算接收数据的Hash值并更新Hash库；

4）如果接受的是Hash值，跟据Hash值在Hash库中查找匹配项；

5）根据Hash库中查找到相匹配的Hash值，确定数据块所在位置；

6）复制数据块；

7）更新Hash库；

8）向目标节点发送“完成”信号．

需要说明的是，无论是在数据备份过程中，还是在数据恢复过程，为保证数据传输效率，数据发送后并不等待对方应答信号，而是直接发送下一个数据块，只是在一定时间后没有收到应答信号，再重新发送该数据块．另外，在双机热备系统中，无论是主-从方式还是双主机方式，都需要保证两个节点间的数据一致性．因此，尽管DeduBS系统中的数据消重技术与传统的重复数据删除技术在原理和方式上类似，但是DeduBS系统的目的并不是利用重复数据删除技术减少数据存储量，而是通过数据传输过程中的消重减少网络数据的传送量，在提高网络利用率的同时，仍能保证两个节点间的数据一致性．

4 系统测试

测试平台由2台服务器组成，存储系统为Linuxkernel2.6.35.32，2台服务器配置相同，分别作为源节点和目标节点，服务器CPU为IntelXeon（R）X3220，内存4GB；SeagateST3500630AS硬盘，容量500GB；Crucial CT128M4SSD2固态盘，容量128 GB；网络带宽4 Mbps．

Hash值计算采用MD5算法，Hash库占用2 GB的存储空间．随着存储容量的增大，Hash所占空间也会随之增大，128 GB固态盘可以存放约32 TB数据的Hash值．

数据缩减率测试结果如图4所示．

由图4可知，当数据块划分越小时，数据缩减率越高，反之，数据块划分越大，数据缩减率就越低．数据块划分大小为4 KB时，50 G、100 G和200 G数据中，数据缩减率分别为13%、19%和27%；数据块划分大小为8KB时，数据缩减率分别为8%、11%和17%；数据块划分大小为16 KB时，数据缩减率分别为4%、7%和11%．可见，随着数据量的最大，重复率越来越高，在大规模数据存储系统中，数据缩减率最高能达到60%以上．

图5为数据传输时间测试结果．

与图4中的实验结果相符，当数据块划分粒度细时，由于数据缩减率高，因此数据传输时间较短，数据块大小为4 KB、8KB和16KB时，传输50GB数据分别需要36.8h、41.4 h和41.2h，传输100GB数据分别需要76.5h、80.1h和80h，传输50GB数据分别需要137.3h、149.4h和153.1h．以数据块大小为4KB的传输时间为标准，数据块增大后，数据传输速率比理论计算值要稍低一些，这是因为网络传输大数据块要比传输小数据块的效率要高．

通过实验结果可以看出，当数据量增大时，重复数据率也随之增加，对于远程数据备份系统来说，传输这些重复数据会浪费大量网络资源和能耗．DeduBS系统利用基于Hash值的数据去重技术，避免了传输重复数据，提高了远程数据备份系统的效率，节省网络资源和运行成本．

图4 DeduBS系统数据缩减率Fig.4DeduBS Data Reduction Rate

图5 DeduBS系统数据备份时间Fig.5DeduBS Data Backup Time

5 小结

本文针对远程数据备份系统的网络瓶颈问题，提出了一种利用数据消重避免重复数据传输的远程备份系统：DeduBS系统，实现了基于普通IP网络的远程数据实时备份．在源节点和目标节点建立Hash库，存储所有数据的Hash值．当源节点数据更新后，需要向目标节点传递更新数据，通过计算数据的Hash值，比对Hash库，如果存在与之相匹配的Hash值，则说明在源节点和目标节点均已存在与更新数据相同的数据块．这时，只需向目标节点传送数据的Hash值即可，而不是传输数据本身．目标节点接收到数据的Hash值，在本地Hash库中找到匹配项，通过Hash值可以找到存储在本地的相同数据，直接从本地复制数据到目的数据块即可．在大规模存储系统中，存在着大量的重复数据，因此，利用数据去重技术实现远程数据备份，可以提高网络利用率，节省网络资源．同时，由于传输的数据量减少，也降低了系统能耗．

实验数据表明，随着备份数据集的增大，DeduBS系统的传输数据量较原始数据明显减少，传输时间缩短，是一种基于普通IP网络、高效、节能的远程数据备份系统．

[1]杨天明．网络备份中重复数据删除技术研究[D]．武汉：华中科技大学，2010．

[2]Brain Babineau，Jonh Mcknight．Digital archiving：end-user surevey and market forecast[EB/OL]．http：//www.esg-global.com/default/assets/ File/ESG%20Research%20Report%20Digital%20Archive%20Market%20Forecast%20Abstract.pdf，[2013-2-25]．

[3]Yang Jing，Cao Qiang，Li Xu，et al．ST-CDP：Snapshots in TRAP for continuous data protection[J]．IEEE Transactions on Computers，2012，61（6）：753-766．

[4]YangQing，XiaoWeijun，RenJin．TRAP-array：adiskarrayarchitectureprovidingtimelyrecoverytoanypoint-in-time[J]．ComputerArchitecture News，2006，34（2）：289-300．

[5]LiuJingning，YangTianming，LiZuoheng，etal．TSPSCDP：atime-stampcontinuous dataprotectionapproachbasedonpipelinestrategy．Japan-China Joint Workshop on Frontier of Computer Science and Technology[C]//Nagasahi：IEEE 2008：96-102．

[6]Qian Cunhua，Huang Yingyan，Zhao Xufeng，et al．Optimal backup interval for a database system with full and periodicincremental backup[J]．Journal of Computers，2010，5（4）：557-564．

[7]敖莉，舒继武，李明强．重复数据删除技术[J]．软件学报，2010（5）：916-929．

[8]付印金，肖侬，刘芳．重复数据删除关键技术研究进展[J]．计算机研究与发展，2012（1）：12-20．

[9]杨义先，姚文斌，陈钊．信息系统灾备技术综论[J]．北京邮电大学学报，2012，4（30）：1-6．

[10]MuthitacharoenA，ChenB，Mazieres D．A low-bandwidth network file system[J]．ACM SIGOPS OperatingSystems Review，2002，35（5）：174-187．

[11]Liu C，Lu Y，Shi C，et al．ADMAD：Application-driven metadata aware de-duplication archival storage system．The Fifth IEEE International Workshop on Storage Network Architecture and Parallel I/Os（SNAPI）[C]//Baltimore，MD：IEEE，2008：29-35．

[责任编辑 田丰夏红梅]

DeduBS:a duplicate eliminating remote backup system based on hash matching

LIU Jingyu，YANG Lei，ZHAO Xiuping，LI Juan，WU Youxi

(School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China)

With data increasing,network bandwidth has become a bottleneck in remote data backup system.A new duplicate eliminating remotebackup systemisproposedbasedonHash matching:DeduBS.DeduBS improvestheefficiency of network transmission by deduplication.In DeduBS,a Hash library is established in both the source node and the destination node to store alldata blocks Hash value.Before being transferred,the data will bejudged whetherit is duplication or not by its Hash value.Only the non-duplicate and the Hash value of duplicate are transferred in DeduBS.Experiment shows thatthe DeduBS can transfer less data and save the cost and energy of backup system,thus improving network utilization.

backup;duplicate eliminating;Hash;network transmission

TP309.3

A

1007-2373(2015)04-0032-06

10.14081/j.cnki.hgdxb.2015.04.007

2014-09-05

河北省教育厅青年基金（QN2014192）；河北省自然科学基金（F2013202138）；河北省教育厅重点项目（ZH2012038）

刘靖宇（1976-），男（汉族），讲师，博士．通讯作者：武优西（1974-），男（汉族），教授，博士．

数字出版日期：2015-06-17

数字出版网址：http://www.cnki.net/kcms/detail/13.1208.T.20150617.1536.003.html