一种基于rabin指纹与异或计算的重复数据检测方法

摘要

一种基于rabin指纹与异或计算的重复数据检测方法，计算当前数据块的rabin指纹值；查找当前数据块的rabin指纹值是否在数据库中存在，如果不存在，则判断当前数据块为新数据块；否则查找数据库中所有具有与当前数据块相同rabin指纹值的数据块并将其读出；将读出的数据块与当前数据块按照异或计算进行数据对比，如果所有数据块对比的异或结果为1，则当前数据块为新数据块，否则判断当前数据块为重复数据块。本发明能够显著降低新型非易失性存储器件中的指纹计算性能开销，并且能够消除传统重复数据检测方法存在的安全隐患。

权利要求

1.一种基于rabin指纹与异或计算的重复数据检测方法，其特征在于，包括以下步骤：

1)计算当前数据块的rabin指纹值；

2)查找当前数据块的rabin指纹值是否在数据库中存在，如果不存在，则判断当前数据块为新数据块；否则查找数据库中所有具有与当前数据块相同rabin指纹值的数据块并将其读出；

3)将读出的具有与当前数据块具有相同rabin指纹的数据块按照异或计算进行数据对比，如果所有数据块对比的异或结果为1，则当前数据块为新数据块，否则判断当前数据块为重复数据块。

2.根据权利要求1所述的一种基于rabin指纹与异或计算的重复数据检测方法，其特征在于，计算当前数据块rabin指纹值的具体步骤为：(1)在进行数据切分后，先一次读取48个字节到窗口中并计算rabin指纹值，同时，构造一个计数器并将其值初始化为0；

(2)根据rabin指纹值判断窗口是否形成边界点；如果没有形成边界点，进行步骤(3)；

否则跳到步骤(5)；

(3)如果计数器等于48，则将窗口的rabin指纹值暂存起来，并将计数器重新清零；

(4)将窗口滑动一个字节并为计数器加1，返回步骤(2)；

(5)计算最后一个窗口的rabin指纹值，如果此时计数器等于48，则将其rabin指纹值保存下来，如果计数器值不等于48，则修正窗口内容，再将已修正的窗口的rabin指纹值进行相加与模运算，得到当前数据块的rabin指纹值。

3.根据权利要求2所述的一种基于rabin指纹与异或计算的重复数据检测方法，其特征在于，根据基于内容分块算法，判断窗口是否形成边界点。

4.根据权利要求2或3所述的一种基于rabin指纹与异或计算的重复数据检测方法，其特征在于，判断当前窗口是否形成边界点的条件有两个：1)(rabin指纹值％掩码值＝＝掩码值-1)&&当前数据块长度>最小值；2)当前数据块长度>最大值。

5.根据权利要求4所述的一种基于rabin指纹与异或计算的重复数据检测方法，其特征在于，当掩码值取二进制值为11111111时，预期数据块长度为28＝256字节。

6.根据权利要求2所述的一种基于rabin指纹与异或计算的重复数据检测方法，其特征在于，修正窗口内容的具体过程为，首先计算需要驱逐的字节数量，公式为expel＝48-count，其中expel是需要驱逐的字节数量，count为当前计数器值，然后将窗口的前expel个字节逐出，从而得到正确的窗口w7。

说明书

一种基于rabin指纹与异或计算的重复数据检测方法

技术领域

[0001] 本发明属于存储系统重复数据删除领域，涉及一种面向新型非易失性存储器件的重复数据检测方法，具体涉及一种基于rabin指纹与异或计算的重复数据检测方法。

背景技术

[0002] 近年来，以PCM、STT-RAM和3DXpoint等为代表的非易失性存储器(NVM：non-volatile memory)得到了工业界与学术界越来越多的关注。NVM器件具有高带宽、低延迟的特性，读写性能可以媲美DRAM，并且能够像磁盘一样在断电后存储数据。目前，Intel基于3DXpoint技术的傲腾SSD已在市场上销售。相比传统flash介质，NVM对计算机系统结构带来的是颠覆性的改变。NVM可按字节寻址，并具有接近DRAM的读写性能，可作为内存使用，CPU能够直接访问持久化数据，无需再经过内存-外存的持久化I/O栈。

[0003] 重复数据删除作为存储系统中的成熟数据精简技术，目前已经在存储系统中广泛应用。然而，传统重复数据删除方法在NVM存储系统中面临着新的挑战。研究者已经指出传统的重复数据删除方法在基于NVM的存储系统中存在着严重的性能退化。研究指出，在磁盘存储系统中，指纹计算仅占到总执行时间的21％。而在NVM存储系统中占到了44％。不同于传统基于磁盘存储系统中I/O操作是主要的性能瓶颈，在NVM存储系统中，指纹计算成为了新的系统性能瓶颈。因此，研究新型重复数据检测方法，消除传统SHA-1/MD5计算造成的性能开销成为了亟需解决的问题。

发明内容

[0004] 本发明的目的在于针对由新型非易失性存储器件构成的存储系统中指纹计算成为了新的性能瓶颈，提出一种基于rabin指纹与异或计算的重复数据检测方法，该方法避免了传统重复数据删除方法计算MD5/SHA-1这类强哈希算法造成的严重性能开销，能够显著减少重复数据删除中指纹计算时间。

[0005] 为达到上述目的，本发明采用的技术方案如下：

[0006] 一种基于rabin指纹与异或计算的重复数据检测方法，包括以下步骤：

[0007] 1)计算当前数据块的rabin指纹值；

[0008] 2)查找当前数据块的rabin指纹值是否在数据库中存在，如果不存在，则判断当前数据块为新数据块；否则查找数据库中所有具有与当前数据块相同rabin指纹值的数据块并将其读出；

[0009] 3)将读出的具有与当前数据块具有相同rabin指纹的数据块按照异或计算进行数据对比，如果所有数据块对比的异或结果为1，则当前数据块为新数据块，否则判断当前数据块为重复数据块。

[0010] 本发明进一步的改进在于，计算数据块rabin指纹值的具体步骤为：

[0011] (1)在进行数据切分后，先一次读取48个字节到滑动窗口中并计算rabin指纹值，同时，构造一个计数器并将其值初始化为0；

[0012] (2)根据rabin指纹值判断当前窗口是否形成边界点；如果没有形成边界点，进行步骤(3)；否则跳到步骤(5)；

[0013] (3)如果计数器等于48，则将当前窗口的rabin指纹值暂存起来，并将计数器重新清零；

[0014] (4)将窗口滑动一个字节并为计数器加1，返回步骤(2)；

[0015] (5)计算最后一个窗口的rabin指纹值，如果此时计数器等于48，则将其rabin指纹值保存下来，若果计数器值不等于48，则修正窗口内容，再将已修正的窗口的rabin指纹值进行相加与模运算，得到当前分块的rabin指纹值。

[0016] 本发明进一步的改进在于，根据基于内容分块算法，判断窗口是否形成边界点。

[0017] 本发明进一步的改进在于，判断窗口是否边界点的条件有两个：1)(rabin指纹值％掩码值＝＝掩码值-1)&&块长度>最小值；2)块长度>最大值。

[0018] 本发明进一步的改进在于，当掩码值取二进制值为11111111时，预期分块长度为28＝256字节。

[0019] 本发明进一步的改进在于，修正窗口内容的具体过程为，首先计算需要驱逐的字节数量，公式为expel＝48-count，其中expel是需要驱逐的字节数量，count为当前计算器值，然后将当前窗口的前expel个字节逐出，从而得到正确的窗口w7。

[0020] 与现有技术相比，本发明具有的有益效果：

[0021] 1)本发明的核心思想是利用rabin指纹和异或计算替代MD5/SHA-1指纹计算，减少数据计算量，从而加速重复数据检测过程。

[0022] 2)对于输入的数据流，利用基于内容分块过程中形成的窗口raibn指纹值计算数据块的rabin指纹值，减少计算量。

[0023] 3)本发明的重复数据检测不完全依赖于指纹值，能够提高存储系统数据安全性。由于两个不同的数据块存在极小的概率产生相同的MD5/SHA1/Rabin指纹值，因此，完全依赖指纹值检测数据块是否重复存在一定的安全隐患。本发明的方法同时采用指纹值与异或计算相补充的重复数据检测方法，消除了传统方法的安全隐患。

附图说明

[0024] 图1为本发明的原理图；

[0025] 图2为本发明计算rabin指纹的示意图；其中，(a)为预期窗口分布情况，(b)为窗口滑动到最后一个字节的实际情况，(c)为修正后的窗口情况。

具体实施方式

[0026] 下面结合附图对本发明做进一步详细描述：

[0027] 参见图1，本发明的基于rabin指纹与异或计算的重复数据检测方法，包括以下步骤：

[0028] 1)计算当前数据块的rabin指纹值，具体由以下步骤得到；

[0029] (1)在开始进行数据切分后，先一次读取48个字节到滑动窗口中并通过公式(1)计算rabin指纹值。同时，构造一个计数器并将其值初始化为0。

[0030] f(A)＝A(t)mod P(t)  (1)

[0031] 其中，f(A)为rabin指纹值，

[0032] (2)根据rabin指纹值判断当前窗口是否形成边界点，根据重复数据删除系统经典的基于内容分块算法，判断窗口是否形成边界点的条件有两个：

[0033] 1)(rabin指纹值％掩码值＝＝掩码值-1)&&块长度>最小值，掩码值决定了预期分块的长度，例如当掩码值取二进制值为11111111时，预期分块长度为28＝256字节；

[0034] 2)块长度>最大值，当分块大小大于预定的最大值时，强制将当前窗口形成边界点。如果没有形成边界点，进行步骤(3)；否则跳到步骤(5)。

[0035] (3)如果计数器等于48，则将当前窗口的rabin指纹值暂存起来，并将计数器重新清零。

[0036] (4)将窗口滑动一个字节并为计数器加1，返回步骤(2)。

[0037] (5)形成边界点后，要计算最后一个窗口w7的rabin指纹值，如图2所示。如果此时计数器正好等于48，则可以直接将其rabin指纹值保存下来，但是大多数情况下，计数器值不会等于48。此时的窗口与w7窗口并不相等，包含与w6窗口重叠的部分，因此需要修正窗口内容。修正方法为：首先计算需要驱逐的字节数量，公式为expel＝48-count，其中expel是需要驱逐的字节数量，count为当前计算器值。之后，将当前窗口的前expel个字节逐出，从而得到正确的w7窗口。最后，根据公式(2)，得到当前数据块的rabin指纹值。

[0038]

[0039] 其中，A为数据流，Wi为当前窗口数据，P为不可约多项式。

[0040] 因此，将基于内容分块算法(CDC算法)在分块过程中形成的所有窗口rabin指纹值临时保存下来，当边界点被检测到后，计算所有已滑动窗口的rabin指纹值之和并做模运算得到当前数据块的rabin指纹值。

[0041] 2)查找当前数据块的rabin指纹值是否在数据库中存在，如果不存在，则判断当前数据块为新数据块；否则查找数据库中所有具有与当前数据块相同rabin指纹值的数据块并将其读出。

[0042] 3)将存储系统已存在，读出的具有与当前数据块具有相同rabin指纹的数据块按照异或计算进行数据对比，如果所有数据块对比的异或结果为1，则当前数据块为新数据块，否则判断当前数据块为重复数据块。

[0043] 本发明具有以下优点：

[0044] 1)本发明的核心思想是利用rabin指纹和异或计算替代MD5/SHA-1指纹计算，减少数据计算量，从而加速重复数据检测过程。

[0045] 2)本发明的重复数据检测不完全依赖于指纹值，能够提高存储系统数据安全性。由于两个不同的数据块存在极小的概率产生相同的MD5/SHA1/Rabin指纹值，因此，完全依赖指纹值检测数据块是否重复存在一定的安全隐患。尤其我国王小云院士提出产生MD5/SHA-1的冲突方法后，恶意用户即使使用一台普通配置的计算机就能在半小时内产生指纹值冲突，当恶意用户将伪造数据块上传到存储系统后，所有具有与该指纹值相同的正常数据块都会被判断为重复而丢弃，造成用户数据丢失。而本发明的方法同时采用指纹值与异或计算相补充的重复数据检测方法，消除了传统方法的安全隐患。