NOVOTS KMS 词汇表 Glossary    联系我们 Contact Us
查询 Search  
   
按类别浏览 Browse by Category
NOVOTS KMS .: 工具软件 .: 重复数据删除过程中的数据自动分段

重复数据删除过程中的数据自动分段

这种重复数据删除的方法原理很简单。首先将输入的数据流进行分块处理,最简单的分块处理方法是固定长度数据块切分方法。分块完成之后,计算数据块的fingerprint值,然后检索系统中是否存在具有相同fingerprint的数据块。如果存在,那么丢弃输入的数据块,否则将该数据块存入系统中。根据原理,我们可以发现Fingerprint是重复数据删除的关键。首先,通过数据块获取fingerprint需要大量的计算工作,其会影响到数据存储过程中的吞吐量;其次,不同数据块可能存在相同fingerprint。在实际应用中,通常采用SHA1这种HASH算法实现fingerprint的计算,但是有可能会出现HASH冲突事件,如果不解决这种冲突,会对应用导致数据丢失的问题。再次,fingerprint计算完毕之后,还需要查找系统中是否存在相同fingerprint的数据块,对于大容量存储而言,这种查找十分耗费时间,如何实现快速查找是在线重复数据删除的关键。

重复数据删除在原理上理解是简单的,但是如何实现一个实际有效的系统还是有很多难点的。在这里首先谈一下如何实现数据块的自动切分。前面提到对于输入数据流最简单的办法是固定数据块切分。也就是按照固定窗口大小对输入数据流进行切分,这种切分方法实现简单,但是影响重复数据删除效率。在备份应用中,每周会进行一次全备份,一周之内每天会进行增量备份。那么在全备份的过程中,这一次的备份对于上一次而言只是局部很小的数据进行了修改,如果按照固定窗口大小进行切分,那么这一次分块之后的数据块和上一次是完全不一样的,但实际上,只有局部数据不一样。所以,固定块大小的分块方式无法很好的做到高效重复数据删除。

为了解决这个问题,需要采用内容识别的分块方式,这种分块方式就是可变块大小的分块算法。采用这种方法之后,如果这次的备份数据和上次相比只有少许改变,那么只有若干少许的数据块是不一样的,而绝大部分的数据块还是原来的切分方法,这样就可以做到高效数据删除了。

最常用的分块算法是移动窗口法。该算法的示意图如下图所示:

首先定义个数据块窗口,从数据流的起点开始计算窗口内的fingerprintA,然后对A值取模(A%MM是固定的特征值)得B,最后比较B和预期值CC是系统固定的一个值)是否相等,如果相等,那么就意味着找到了Anchor点,得到一个segment。如果不相等,那么移动窗口一个offset(这个offset也是固定的),继续下一个窗口fingerprint值的计算,重复上述过程,直到找个Anchor点为止。这就是内容识别自动分段的算法思想。上图是一个形象的描述,我们假设特征值是abcdef,就是要找stream中存在abcdef的点作为anchor点。如果采用这种算法,那么得到的segment size是不相同的,为了防止segment太大或过小,可以设定.maximum或者minimum值。另外,设置不同的特征值、offset和预期值会得到不同的分段结果。

当输入的数据流发生了变化之后,采用上述算法思想的分段方法还可以得到和前次类似的分段结果。

如上图所示,当在segment 0中增加了一些字符之后,移动窗口可能无法检测到原来那个anchor点了,但是,后面的分段结果还是可以找到的。在上述案例中,我觉得offset对检测结果有很大的影响。如果offset过小,那么计算工作量十分巨大,如果offset过大,那么分段结果不会十分理想。

数据流自动分段是重复数据删除的第一步,高效内容识别算法的研究、优化对重复数据删除效率影响很大。


这篇文章对你多有用?

用户评语

添加评语
当前还没有评语.


.: .: .: .: .:
[ 登陆 ]
北京护航科技有限公司 2006

Novots Technologies Limited