指纹碰撞规避、去重及恢复方法、存储介质和去重系统

摘要

本发明公开了一种指纹碰撞规避、去重及恢复方法、存储介质和去重系统，属于计算机存储领域。本发明提出的广域网数据去重方法，根据现有的网络状况及硬件设备，采用数据去重技术对数据流进行去重处理，以非常小的代价消除重复数据，以确保冗余数据不会重复发送，该方法有效减少了不必要的带宽浪费，达到提高传输速率和带宽利用的效果。本发明将指纹计算分为两层，MD5层和SHA‑256层；对每个数据块计算其MD5值；若出现相同的MD5值，再计算两个数据块的SHA‑256值；进而通过SHA‑256算法计算出的数据块指纹来判定数据是否重复，进一步增加了广域网数据去重系统的可靠性。

说明书

技术领域

本发明属于计算机存储领域，更具体地，涉及指纹碰撞规避、去重及恢复方法、存储介质和去重系统。

背景技术

如今存储系统中的数据爆炸式增长，重复数据删除(Data Deduplication)作为一种节省存储空间和网络带宽的有效方式，引起了越来越多的重视。重复数据删除技术通过对存储的文件分裂成多个数据块，并且用唯一的安全哈希摘要(即指纹)来标识该数据块，然后通过匹配数据块指纹确定重复数据块，从而避免逐个字节比较重复的数据块。重复数据删除技术不仅降低了存储空间的开销，而且还减少了网络存储系统中的冗余数据的网络传输。相对于传统的字节级和字符串级的数据压缩技术，数据块级的重复数据删除技术具有可扩展性强和压缩吞吐率高等特点，所以在近几年被广泛地应用于商用的数据备份存储系统中。

随着信息化程度的不断提高，企业的分支机构之间的数据通信需求急剧增长，尤其近年来，随着数据量的增长，有限的广域网带宽已不能满足企业级用户的数据传输需求。针对WAN(Wide Area Network)带宽不足、时延过长等问题，在广域网数据传输中采用重复数据删除技术对传输数据进行优化，以减少带宽占用，提高数据传输效率。

但是随着重复数据删除技术的发展，重复数据删除技术也面临诸多的挑战。安全哈希摘要(即指纹)有一个众所周知的“生日悖论”，即两个不同的数据块计算得出相同的SHA-1指纹，也就是存在着哈希碰撞的问题。当前有大量的研究针对数据去重的分块算法及索引算法进行研究，但这些研究都针对冗余数据的去重进行优化。随着目前数据规模的增长，数据中心及企业级用户拥有的海量数据的情况下，发生哈希指纹碰撞的概率也越来越大。当前最优哈希指纹碰撞规避方案是山东大学的王小云教授等人提出的一种基于差分攻击、近似碰撞、多区块碰撞技术，通过降低哈希冲突碰撞的计算复杂度，然而，也因为其也只是基于大量的计算来实现碰撞的个例。而在真实的广域网数据优化系统中，出现的数据块指纹冲突碰撞的概率还是很高的。随着目前数据规模的增长，提出一个哈希指纹碰撞规避方案，来保证广域网数据去重系统中数据的可靠性是十分重要且有意义的。

发明内容

针对现有技术的缺陷和改进需求，本发明提供了指纹碰撞规避、去重及恢复方法、存储介质和去重系统，其目的在于利用在广域网数据传输中应用重复数据删除技术，在有限的计算资源(CPU)以及指纹检索性能(内存、硬盘)约束下，在保障数据传输安全性情况下，尽可能降低广域网数据传输带宽占用。同时利用抗冲突性更强的混合哈希指纹碰撞规避方法，在保障网络去重率的情况下，来避免发生哈希碰撞的情况，从而提升系统的可靠性。

为实现上述目的，按照本发明的第一方面，提供了一种混合哈希指纹碰撞规避方法，该方法包括：数据指纹库初始化为空，对于数据流分块后得到的每一个数据块进行以下处理：

(1)计算该数据块的MD指纹；

(2)查找数据指纹库中是否已经存在该MD指纹，若有，进入(3)，否则，进入(4)；

(3)计算该数据块的SHA值，若该数据块的SHA值在数据指纹库中已经存在，则数据指纹库中只存储该数据块引用，同时增加该数据块的引用计数；否则，则进入(4)；

(4)在数据指纹库中分配新的空间，存储该数据块，该数据块的引用计数初始化为1。

优选地，MD指纹为MD5指纹，SHA指纹为SHA-256指纹。

为实现上述目的，按照本发明的第二方面，提供了一种广域网数据去重方法，该方法包括以下步骤：

S1.接收到从局域网一侧发送来的数据流时，对数据流进行分块；

S2.计算各个分块的指纹，计算过程中采用如第一方面所述的方法进行指纹碰撞规避；

S3.将各个分块的指纹同数据指纹库中的指纹信息进行对比，将数据块替换为指纹信息。

为实现上述目的，按照本发明的第三方面，提供了一种广域网数据去重恢复方法，该方法包括以下步骤：

S4.接收到采用如第二方面所述的方法得到的编码数据流时，进行数据指纹库的同步；

S5.通过检索同步后的数据指纹库，将编码数据流中的指纹信息替换为原始数据块，完成数据流的去重恢复。

为实现上述目的，按照本发明的第四方面，提供了一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如第一方面所述的混合哈希指纹碰撞规避方法。

为实现上述目的，按照本发明的第五方面，提供了一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如第二方面所述的广域网数据去重方法和如第四方面所述的广域网数据去重恢复方法。

为实现上述目的，按照本发明的第六方面，提供了一种广域网数据去重系统，所述系统包括：

数据流接收端、数据流发送端、路由器和至少两个包含如第五方面所述的计算机可读存储介质的交换机；

数据发送收端用于向一个交换机发送数据流；

数据流接收端用于从另一个交换机接收解码后的数据流；

两个交换机通过链路两侧的路由器接入广域网，分别进行数据去重和数据去重恢复。

总体而言，通过本发明所构思的以上技术方案，能够取得以下有益效果：

(1)本发明提出的广域网数据去重方法，根据现有的网络状况及硬件设备，采用数据去重技术对数据流进行去重处理，以非常小的代价消除重复数据，以确保冗余数据不会重复发送，该方法有效减少了不必要的带宽浪费，达到提高传输速率和带宽利用的目的。

(2)本发明将指纹分为两层，MD5层和SHA-256层；对每个数据块计算其MD5值；若出现相同的MD5值，再计算两个数据块的SHA-256值；进而通过SHA-256算法计算出的数据块指纹来判定数据是否重复，增加了广域网数据去重系统的可靠性。

附图说明

图1为本发明提供的一种广域网数据去重系统拓扑结构示意图；

图2为本发明提供的广域网数据去重过程示意图；

图3为本发明提供的一种混合哈希指纹碰撞规避方法流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

如图1所示，本发明所述的广域网数据去重系统，由两台PC作为数据流的接收端和发送端，广域网数据去重方法部署在两端的交换机上，分别起到对数据流进行编码和解码的作用，交换机通过链路两侧的路由器接入广域网。

如图2所示，本发明所述的广域网数据去重系统对TCP流进行数据去重操作，数据发送时，TCP透明代理模块将符合规则的TCP数据流截取下来，进行重组，当满足一定条件时，就将该数据段传输给数据去重模块进行处理，最终将处理过的新数据发送到广域网上。

在接收端，TCP透明代理检测数据流中的索引号，当发现有重复数据的索引值时则将其发送给去重模块进行还原，最终将还原后的数据送往目的端。

该广域网数据去重系统的工作机制如下：

(S1)当数据从局域网一侧发送过来时，依据其数据特征进行数据流分块处理；

本发明中对数据流的分块方式不局限，可以是现有分块方式的任一种，例如，定长分块算法(fixed-size chunking，FSC)、AE分块算法、MAXP分块算法、SampleByte分块算法等。

(S2)计算各个分块的指纹，指纹计算过程中执行混合哈希指纹碰撞规避方法；

(S3)同数据指纹库中的指纹信息进行对比，将数据块替换为指纹信息，在此处应用下述混合哈希指纹碰撞规避方法；

(S4)去重后的数据流传输到广域网另一侧的交换机，同时进行数据指纹库维护；

(S5)通过检索字典，将数据中的指纹信息替换为原始数据块，完成数据流的去重恢复。

如图3所示，所述混合哈希指纹碰撞规避方法包括以下步骤：

(T1)对数据流进行分块，得到多个数据块；

(T2)通过MD5算法计算每个数据块的数据块指纹；

(T3)查找数据指纹库中是否已经存在该MD5指纹，若有，则存在两个数据块相同或发生哈希碰撞的情况，进入(T4)；若不存在，则该数据块为非重复数据块，转入(T5)；

(T4)继续计算该数据块的SHA-256值，若该数据块的SHA-256值在数据指纹库中已经存在，则该数据块为重复数据块，只存储数据块引用，同时增加该数据块的引用计数；若该数据块的SHA-256值在数据指纹库中不存在，则该数据块为非重复数据块，分配新的空间，存储该数据块及相关数据，进入(T5)；

(T5)将计算结果存于数据块指纹属性中，执行(S4)操作。

本发明提出的混合指纹碰撞规避方法中，哈希指纹碰撞条件为：MD5层指纹相同且SHA-256层指纹冲突。在存储系统中，若总数据块个数为n，哈希算法生成的摘要长度为bbit，p为这些数据块指纹中至少产生一次哈希冲突的概率，则：

MD5生成摘要长度为128bit，SHA-256生成摘要长度为256bit。记数据去重模块分块后总数据块个数为N，SHA-256层数据块个数为N

显然S(N)＜M(N)，根据(1)式

由于SHA-256层数据量比数据去重模块数据量要小(或相等)，即N

p

由公式(5)知本文提出的混合哈希防碰撞方法碰撞概率小于单一的MD5指纹策略，也小于单一的SHA-256指纹策略。理论的碰撞概率如表1所示。

表1

本发明在根据当前交换机硬件条件来灵活的构建了一个广域网去重系统，其可充分利用当前有限的计算资源(CPU)以及指纹检索性能(内存、硬盘)约束下，在保障网络去重率情况下，尽可能提高网络去重吞吐量，并且在指纹计算阶段应用混合哈希指纹碰撞规避方法，提升了广域网去重系统的可靠性。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。