一种基于源端数据重删的数据备份和恢复系统设计与实现

王兴虎,何安元

(1.南京航空航天大学计算机科学与技术学院,江苏 南京 211106) (2.南京航空航天大学信息化技术中心,江苏 南京 211106)

近年来,信息技术的快速发展和传统行业的信息化转型加快导致了数据量的飞速增长. 数据占用了越来越多的存储空间,企业的数据管理和存储成本逐年上升,大量的存储花费与严峻的数据安全问题给传统企业带来了巨大的经济压力. 文献[1]研究报告表明,47%的企业主管担心企业的预算被用于不必要的存储,42%的主管担心高昂的存储成本. 文献[2]研究表明,日常存储的业务数据中存在60%的冗余业务数据,冗余数据的存在造成了存储资源的浪费. 为了解决数据冗余问题,重复数据删除技术[3-4]成为了近年来的研究热点. 重复数据删除技术可以有效地删除数据存储中的冗余数据,确保数据存储中同样的数据信息只有一份,大大减少了备份时间和存储空间,在备份、归档和数据容灾恢复方面[5]应用广泛. 当前在国际上比较知名的数据备份与恢复产品有基于源端数据的EMC Avaram,基于目标端的Data Domain、IBM的Diligent以及Commvault的Simpana.

重复删除技术会消耗系统大量的计算资源,为了有效提高重删系统的性能,学者提出了一些有效的解决办法:如避免重删系统中的磁盘瓶颈技术[6]以及基于相似的搜索技术[7]、基于集群的增量压缩技术[8]. Sun等[9]设计了基于分布式系统的重删方案,即解决NP-Hard问题. 设计新的文件分区算法,通过增量来记录有效访问,Chu等[10]使用分块技术减少了相同块的重复对比,提出了Dis-Dedup的分配策略;Xue Yua等[11]在多域架构的基础上提出了云存储中的重删技术EPCDD. 在综合参考现有技术的基础上,本文设计和实现了基于源端数据重删技术的数据备份与恢复系统,通过在客户端建立预处理并行计算模块和在服务端建立高效的缓存模型,有效地提高整体备份效率.

1 备份与恢复系统结构

根据文件系统执行源端重复数据删除的存储节点位置的不同,目前主要有源端重复数据删除技术和目标端重复数据删除技术. 源端重复数据删除直接在文件系统内实现,少部分的数据通过网络传输;目标端重复数据删除中的所有数据需要通过网络传输到远端存储节点进行重删操作,它会占用大量网络带宽. 在现有重删技术中,基于源端数据重删技术的数据备份具体过程为:根据分块算法对数据流进行分块,然后对分好的块计算哈希(Hash)指纹[12],即对每个数据块生成检索指纹,用来标识其唯一性;把指纹发送服务端进行比对,在已存在的数据库指纹索引表中查找确认,确定数据块是否已经存在备份设备中,根据比对的结果把新数据发送到服务端保存起来,已有的数据就不再发送,以达到节省带宽并节省存储的目的. 在基于源端数据重删的技术中,由于客户端的分块、计算指纹需要大量时间,服务端存放数据时,指纹离散高,频繁操作数据块耗时大,从而整体流程耗时较高. 为了减少耗时,本文提出一个基于源端数据重删的备份与恢复系统,系统的结构如图1所示.

该数据备份与恢复系统包含客户端与服务端两部分,客户端主要包括数据流预处理、数据分块、计算指纹与索引信息建立,其中预处理模块可将输入数据流提前分段并存储,便于之后的并行计算. 服务端包括布隆过滤器(Bloom filter)[13-14]、多级缓存模型、数据库与容器(Container). 布隆过滤器与多级缓存模型负责存储容器,对比客户端传来的指纹,便于减少访问数据库的频率. 容器负责存储数据块与索引信息,提高缓存工作的效率. 服务端负责指纹对比、数据块的存储与检索功能.

客户端与服务端之间通过SAN网络传输数据块、索引信息与指纹. 在备份过程中客户端将指纹发送至服务端进行对比,依据对比结果将没有指纹的数据块与索引信息送至服务端备份,服务端将接收到的数据块与指纹按位置依次存放在容器中. 恢复数据时,客户端通过读取索引文件把索引信息发至服务端,服务端依据索引信息找到数据块返回到客户端.

该体系结构中,客户端利用数据流分段并对每段数据并发执行分块和指纹计算,服务端用独立线程进行存储数据,并借助布隆过滤器与多级缓存模型,有效缩短时间,提高备份效率.

2 客户端设计

客户端包含预处理模块、数据分块、指纹计算与索引信息建立、缓存. 在备份过程中客户端主要实现重删功能,将新增数据块发送至服务端,并更新数据写入结果. 在恢复过程中,客户端通过读取索引文件中对应数据块的索引信息发送至服务端并将服务端发送来的数据块放在缓存中,重复整个流程直到恢复所有对应的数据块.

2.1 预处理模块

预处理模块主要是先通过对数据流进行分段得到多个数据段,再并行处理多个数据段,对每个数据段进行分块,并计算每个数据块的指纹.

(1)数据流分段

将待备份的文件以数据流的方式传输到客户端,客户端对数据流可以根据需求设定分段大小,例如以20MB为标准对数据流分段,即每个数据段为20MB,尾段可能不满20MB. 分段的目的是为了方便之后的并行计算.

(2)并行处理

为了实现对多个数据段进行并行处理,在客户端建立一个预处理环形队列,此预处理环形队列用来存储数据段. 将数据段存入预处理环形队列的具体存放过程为:若预处理环形队列中有空间存放传进来的数据段,则将此数据段按顺序存放在预处理环形队列的相应位置;若预处理环形队列中没有足够的空间存放,则等待预处理环形队列中存放的数据段处理完、释放空间后再把传入的数据段存入.

预处理环形队列中每个元素即是一个数据段,每个数据段有各自独立的线程,对队列中所存放的数据段进行并行处理,队列长度可以根据客户端的CPU并行计算能力进行配置,并行处理多个数据段可充分利用CPU的性能,提高指纹计算的整体性能.

2.2 数据分块

数据分块是数据重删的关键技术,一般来说对数据流的分块技术主要有:定长分块[15]技术(Fix-sized partition,FSP)、变长分块[16]技术(Content-defined chunking,CDC)、滑动块切分[17]技术. 在FSP技术中,提供一个预先定义好的块,然后所有文件依据定义好的块的大小进行划分,通过哈希算法给划分后的数据块一个指纹值,再将指纹值与存储中的块指纹值对比,删除相同的值. FSP技术能够有效减少数据占用的存储空间,降低通过网络传输的数据量,但是处理插入与删除问题效率很低. CDC技术通过计算窗口Rabin指纹[18],将文件划分成长度不同的块,再根据文件内容进行块的划分. CDC算法流程如图2所示.

从数据流头开始,滑动窗口中的数据流根据Rabin算法分成若干数据块,图2中垂直虚线是块的边界,当数据块的长度大于预设的最大数据块或者滑动窗口中的rabin指纹值满足了预设要求时,把此时窗口位置作为块的边界. 然后划分出的每个块用hash函数(MD5[19],SHA-1[20])计算指纹值并与已经存储的数据块对比,如果出现相同的指纹值,就删除代表的数据块,否则存储新的数据块. 滑动窗口大小固定,每次向后滑动一个字节,直到达到预定要求为止. CDC算法可以有效地提高重删率,重删率越高,节省的磁盘空间越大. 缺点是变长分块计算相对定长分块相对耗时,并且正常变长分块对于数据流都是顺序分块,因为每个数据块的长度不固定,在不破坏每一块的情况下无法从多个位置用不同的线程去分块. 滑块分块技术结合了固定分块与可变分块技术的优点. 首先固定块的大小,用校验函数(Checksum)计算分块后数据块的弱校验值. 弱校验值匹配先前的值,如果匹配不成功则滑动数据块,如果匹配成功则进一步采用SHA-1算法对块进行哈希计算得到强校验值,若强校验值匹配成功,则认定该数据块重复;若不匹配则继续滑动数据块.

研究表明[16],当数据量较大时,CDC算法具有较好的表现,故在本系统中采用CDC分块. 由于数据流通过预处理模块已经分段存储在环形队列中,因此本系统在采用CDC分块的同时实现了在不破坏每一块的情况下从多个位置用不同线程分块.

2.3 指纹计算与索引信息

数据指纹用来唯一标识数据块的特征,一般选择抗冲突加密Hash值作为特征,目前MD5、SHA1和Rabin是应用最广泛的HASH算法,具有计算速度快、节省存储空间的优势,本文采用Rabin算法.

(1)指纹计算

Rabin算法是基于对系数为Z2的不可约多项式进行模运算的算法. 令S=[a1,a2,…,an],S为二进制字符串,S(t)是与字符串S关联的n-1项多项式,多项式系数为Z2,有

S(t)=a1tn-1+a2tn-2+…+an-1t+an.

(1)

令P(t)=btk+b2tk-1+…+bkt+bk+1为Z2的k阶不可约多项式,在确定P的形式后,可将Rabin指纹计算的形式定义为

r(t)=S(t)modp(t),

(2)

定义连续字符串[X1X2,…,Xω,Xω+1,Xω+2,…],其中每个字符串为8位的二进制字符. 使用宽度大小为ω的滑动窗口. 假设窗口中字符起点为Xi,由多项式Xi(t)表示. 整个连续字符串[X1X2,…,Xω,Xω+1,Xω+2,…]在窗口中的Rabin指纹值为

(3)

其中每一ri对应1个块. 块由Bi表示,i=1,2,…,n. 则数据块Bi的指纹值f(Bi)为

f(Bi)=Hash(Bi).

(4)

(2)索引信息

索引信息由按顺序记录每个数据块的起始位置、长度和指纹信息组成,供数据恢复时查找.

2.4 缓存

在数据恢复过程中,根据索引信息整理好需要从服务端获取数据块的指纹,在客户端建立一个16MB的缓存,用于缓存数据,缓存的大小可以根据具体情况确定,这么做的目的是为了防止每次读取较小的数据时客户端频繁地向服务端要数据,从而在一定程度上减少访问数据库的频率.

3 服务端设计

服务端主要有布隆过滤器、多级缓存模型、数据库与容器,在数据备份过程中服务端负责接收客户端传来的指纹与数据库中存储的指纹进行比对,并存储客户端传来的数据块与索引信息. 在数据恢复过程中,服务端根据客户端发来的索引信息查找相应数据块,并将数据块按照索引顺序拼接起来返回给客户端.

3.1 布隆过滤器

布隆过滤器本质上为概率型数据结构,具有高速查询与插入的特点. 使用布隆过滤器的目的是快速过滤不存在的指纹,数据块的指纹在使用Hash算法计算时会在布隆过滤器中留下一个标记,如果一个指纹经过hash算法计算后在布隆过滤器中没有找到对应的标记,则说明该指纹是一个新的指纹,对应的数据块也是一个新的数据块,如果指纹经过hash算法计算后在布隆过滤器中能找到对应的标记,则说明该指纹可能已经存在,需要经过后面的指纹比对过程继续确认.

在布隆过滤器中,存在假阳性的情况,即待索引的指纹虽然不在集合中,但经过k个Hash函数映射后布隆过滤器所对应的位置可能为1,从而误认为该指纹已经在集合里了. 布隆过滤器中把发生假阳性的可能性称为假阳性概率(False positive probability),简称为误判率(Error rate). 误判率由以下公式计算得出,即

fBF=(1-(1-1/m)kn)k≈(1-e-kn/m)k.

(5)

集合的指纹个数为n、位向量长度为m和Hash函数的个数为k.

假设m和n已知,此时令q=k·ln(1-(1-1/m)kn),则fBF=eq,而且fBF和q极值点相同,再令p=(1-1/m)kn,则可推导出

(6)

在本系统中,采用分段型布隆过滤器(Segemented Bloom filter),分段型布隆过滤器的k个哈希函数分别映射到k个长度为m/k的不相交的位段,将布隆过滤器的查询复杂度达到O(1),假阳性概率为

f′BF=(1-(1-k/m)n)k≈(1-e-kn/m)k.

(7)

尽管f′BF稍大于fBF,由于m与n较大,误差可忽略不计.

3.2 多级缓存模型

多级缓存模型由一级缓存与二级缓存组成. 一级缓存用于同步的更新命中的容器,布隆过滤器中能找到的指纹,需要在指纹比对的后续流程继续确认是否真的存在,如果在一级缓存和二级缓存中都没有找到对应的指纹记录,并且在数据库的指纹表中找到该指纹,那么通过数据库中的记录找到该指纹存放的容器,把容器中的所有指纹更新到一级缓存中. 二级缓存的作用是在一级缓存更新找到容器的同时,找到该容器id临近的下一个容器,找到把容器id对应的容器,并把该容器内指纹更新到二级缓存中. 布隆过滤器与多级缓存模型一同组成高效缓存模型,如图3所示.

在高效缓存模型中,每个指纹对比流程为:约定指纹存在则标记为1(对于标记为1的说明数据块已经在服务端有了,客户端不需要再发送),不存在标记为0. 首先去布隆过滤器里查找,若没有此指纹则标记为0,流程结束,若有此指纹(根据布隆过滤器特性上面已经说明,布隆过滤器中能查到的指纹不一定存在,需要走后面的流程继续确认)则去一级缓存中查找,一级缓存中若有则标记为1,流程结束,若没有则进一步去二级缓存中查找,二级缓存中若有则标记为1,流程结束,二级缓存中若还没有则去数据库中查找,数据库中若还没有,则标记为0,流程结束,若有则标记为1,并把该指纹对应的容器同步更新到一级缓存中,下一个容器异步的更新到二级缓存中.

3.3 容器

采用基于流的块排列技术(Stream-Informed Segment Layout,SISL),SISL技术主要特点是面对同一个数据流,将新数据块存放在一起,块描述符也存放在一起,即数据块在磁盘的物理空间上尽可能地连续存储,并且其对应的指纹也连续存储. 本系统服务端通过设立容器实现SISL技术. 服务端先把客户端传来的数据块放到缓存队列,然后顺序放到容器中,这样就能保证临近数据存放的位置也是临近的,以容器为单位的缓存能大大提高缓存的命中率,降低访问数据库的次数,这样在指纹比对和恢复数据时都能有比较高的效率. 容器是一段数据组合的概念,其固定大小为4MB的一段数据. 它的数据组织结构是前24KB存放指纹及数据块的起始位置和长度信息,从4MB-24KB的位置开始存放数据块. 一个容器一般可以放800个左右的数据块,由于数据块的长度不固定,因此这个数量也不固定.

当服务端接收到数据块与索引信息时,将每块数据存储至容器的步骤如下:

(1)服务端将传过来的新数据块放到容器中,数据块按照容器中存放数据块的位置依次存放,数据块的指纹按照容器中存放指纹的位置依次存放,并在数据库中记录该指纹对应的容器id;

(2)容器写满后把容器放到文件中,并在数据库中记录该容器对应的文件id. 然后创建新的容器,过程为:清空当前容器中的数据(当前容器中的数据已经保存在文件中了),容器id加1,并将容器的信息记录到数据库中.

(3)文件放在磁盘上并在数据库中记录文件对应的磁盘位置. 这样就可以根据数据库中的指纹记录一层层地找到对应的数据块.

系统中每个文件最大为1 GB,一个数据文件放满了,才会生成一个新的文件存放容器,一个文件可以放256个容器. 文件放满容器后会创建新的文件,并把文件的信息记录到数据库中.

4 数据备份与恢复流程

本数据备份与恢复系统克服现有技术中的不足,提供一种基于源端数据重删的数据备份与恢复方法,解决了现有备份与恢复技术中数据的重删效率低、计算指纹耗时长、频繁操作数据库耗时的问题. 下面分别介绍数据的备份流程与数据的恢复流程.

4.1 数据备份流程

数据备份流程如图4所示.

(1)在客户端,对数据流进行分段得到多个数据段;

(2)并行处理多个数据段,对每个数据段进行分块,并计算每个数据块的指纹;

(3)顺序将指纹发送服务端进行对比,并将对比结果返回至客户端;

(4)客户端根据对比结果,将没有的数据块发送至服务端进行保存备份,服务端将数据块存放状态返回给客户端.

4.2 数据恢复流程

数据恢复流程如图5所示.

(1)客户端从索引文件中读取一段待恢复文件的索引,把索引信息发送到服务端.

(2)服务端根据索引信息找到数据块返回客户端,其具体步骤为:解析每个数据块的索引信息,根据索引信息中的指纹先到一级读缓存中查找,若找到则读取数据块,继续找下一数据块;若找不到则去二级读缓存中查找,若二级读缓存中能找到,读取数据块,继续找下一数据块,若找不到则去数据库中找,在数据库中根据指纹找到对应的容器,根据容器id找到对应的文件,从文件中读出对应的容器更新到一级读缓存中,并把对应容器的下个容器异步更新到二级读缓存中;将读到的每个数据块按照索引顺序拼接起来返回给客户端.

(3)循环执行以上两步直到获取文件所对应的所有数据块,恢复出完整的文件.

恢复过程中用到一级读缓存和二级读缓存和备份过程中用到一级缓存和二级缓存逻辑上类似,不同的地方在于在备份过程中用到的一级缓存和二级缓存只需要缓存指纹即可,而恢复过程中用到一级缓存和二级缓存除了缓存指纹还要缓存指纹对应的数据块. 恢复中用的缓存和备份中用的缓存是各自独立的.

5 系统仿真实验

本系统为基于源端的数据重删与备份系统,系统采用C/S架构,基于Java语言. 在系统仿真实验中,建立测试服务器与测试机进行多线程的备份与恢复测试,测试服务器配置如表1所示,测试机配置如表2所示.

表2 测试机的配置Table 2 Configuration of test machine

表1 测试服务器的配置Table 1 Configuration of test server

在Windows环境下,对同一个数据样本进行两次文件备份测试,数据样本由ghost的镜像文件与windows的系统目录文件组成,共13.2GB. 文件样本分别基于本系统的数据备份恢复产品与传统的数据备份恢复系统中测试,测试备份系统的数据备份速度与重删率,其中重删率为备份集实际大小与存储大小之间差值占实际大小的百分比,即系统在进行重删时删掉的重复数据所占百分比. 备份的实验结果如表3,4所示.

表4 现有的数据备份系统实验结果Table 4 Experimental result for the present date backup system

表3 本文数据备份系统实验结果Table 3 Experimental results for the proposed data backup system

表5 数据恢复结果
Table 5 Experimental results for data recovery

本文的数据备份恢复系统现有数据备份恢复系统恢复总时间3 min 45 s4 min 2 s备份集实际大小/GB13.213.2平均恢复速度/(Mb·s-1)60.0755.73

备份速度为源数据除以时间. 改进后的备份系统与现有备份系统的备份速度对比如图6所示.

由表中数据可以明显发现,与采用传统源端数据重删技术的现有产品相比,尽管双方在重删率上十分接近(这是由于在重删中当前主要采用CDC分块技术,故大家的重删率才会十分接近),但在备份速度方面无论是初次备份还是第2次备份,基于本系统的数据备份恢复产品对比现有的数据备份恢复产品在速度上有明显优势. 在数据恢复方面,实验结果如表5所示.由表5可见,该系统在进行数据恢复时也能保持较高的恢复速度.

6 结论

针对传统基于源端数据重删的数据备份与恢复技术中,因为重删导致耗时过长、服务端存放数据频繁操作数据库耗时所产生的问题,本文设计了一种改进后基于数据重删的数据备份与恢复的系统,对于重删耗时过长的问题,本文通过在客户端对数据流分段并存放至预处理环形队列,实现将重删功能块分布执行、减少重删的耗时,在服务端针对存储数据的耗时问题,设立布隆过滤与多级缓存模型进行指纹对比,减少访问数据库频率,并基于块排列技术,将数据与指纹存放在容器中,提高在对比指纹时指纹的命中率. 结果表明,相比于现有的基于源端数据重删的数据备份与恢复系统,本系统在数据备份与恢复方面具有良好的表现.