重复数据删除的数据区块切分方法与新增方法专利名称：重复数据删除的数据区块切分方法与新增方法技术领域：本发明公开了一种重复数据删除的处理方法特别有关于一种重复数据删除的数据区块切分方法与新增方法背景技术：重复数据删除是一种数据缩减技术，通常用于基于磁盘的备份系统，主要目的在于减少存储系统中使用的存储容量它的工作方式是在某个时间周期内查找不同文件中不同位置的重复可变大小数据块重复的数据块用指示符取代由于存储系统中总是充斥着大量的冗余数据为了解决这个问题，节省更多空间，“重复删除”技术便顺理成章地成了人们关注的焦点采用“重复删除”技术可以将存储的数据缩减为原来的1/20，从而让出更多的备份空间，不仅可以使存储系统上的备份数据保存更长的时间，而且还可以节约离线存储时所需的大量的带宽为能判断存除系统中数据区块是否重复，因此现有技术中以定长切分 (fixed-size partition)或内容定义切分(content-defined chunking,CDC)作为判断的依据定长切分算法采用预先定义好的数据区块110大小对输入文件100进行切分定长分块算法的优点是简单、性能高，但它对数据插入和删除非常敏感，处理十分低效，不能根据内容变化作调整和优化。
请参考图IA所示，其为现有技术的定长切分示意图内容定义切分算法是一种变长分块算法它应用指纹数据(如Rabin指纹)将文件分割成长度大小不等的分块策略与定长切分算法不同，内容定义切分算法是基于文件内容进行数据区块110切分的，因此数据区块110大小是可变化的在算法执行过程中，内容定义切分算法是使用一个固定大小(如48字节)的滑动窗口对文件数据计算数据指纹如果指纹满足特定条件(例如当值模特定的整数等于预先设定的数时)则把窗口位置作为数据区块110的边界但是内容定义切分算法可能会出现错误切分的情况换言之，当指纹条件不能满足，数据区块110的边界就不能确定，这样将导致数据区块110的容量过大请参考图IB所示，其为现有技术的内容定义切分示意图发明内容鉴于以上的问题，本发明的主要目的在于提供一种重复数据删除的数据区块切分方法，应用在文件备份程序中，用以将输入文件进行文件切割为多个数据区块为达上述目的，本发明所公开的重复数据删除的数据区块切分方法包括以下步骤载入输入文件；利用固定长度的滑动窗口在输入文件中循序移动，并记录滑动窗口于输入文件的起始位置，且同时记录当前滑动窗口位于输入文件的尾端位置，将起始位置与尾端位置间的长度定义为分块长度；根据滑动窗口对输入文件的固定长度的所涵盖范围进行指纹特征程序，用以产生指纹特征值；重复滑动窗口的移动，直至滑动窗口符合切分条件时，则停止滑动窗口的移动，再根据输入文件的分块长度产生相应的数据区块；依据滑动窗口在前一数据区块的尾端位置作为新的滑动窗口的起始位置，并重复执行产生数据区块的步骤，直至完成输入文件中的所有数据区块为止，且产生指纹特征值的索引文件。
其中，切分条件中更包括判断指纹特征值符合切分数值；若指纹特征符合切分数值，则停止滑动窗的滑动；若指纹特征不符合切分数值，则判断分块长度是否符合预设长度；若分块长度符合预设长度，则停止滑动窗口的滑动；若分块长度不符合预设长度，移动滑动窗口并重复判断切分条件透过上述的数据区块切分方法的处理后，本发明另提出一种应用上述切分方法的重复数据删除的数据区块新增方法为达上述目的，本发明所公开的一种重复数据删除的数据区块新增方法包括以下步骤载入新增过数据区块的该输入文件；对输入文件进行数据区块切分程序，产生多组数据区块；对每一数据区块进行哈希程序，计算每一数据区块所相应的哈希值；依序比对每一哈希值是否与这些指纹特征值相同；当哈希值与指纹特征值不相同时，则在索引文件中将哈希值插入前一相同数据区块的指纹特征值之后；重复比对哈希值与这些指纹特征值，直至完成所有的哈希值的比对为止本发明以不同的数据长度动态的产生不同大小数据区块，并且透过相应的新增方法将新的数据写入对应的数据区块后因此，本发明可以有效的降低数据的储存量，并且亦可对现有的数据做相应的新增有关本发明的特征与实作，配合附图作最佳实施例详细说明如下图IA为现有技术的定长切分示意图；图IB为现有技术的内容定义切分示意图；图2为本发明的切分运作流程示意图；图3为本发明的数据区块切分示意图；图4A为本发明的分块长度运作示意图；图4B为本发明的切分位置示意图；图5为本发明新增数据的运作流程示意图；图6A为本发明新增数据的数据区块分解示意图；图6B为本发明新增数据的数据区块分解示意图；图6C为本发明新增数据的数据区块分解示意图。
其中，附图标记输入文件100数据区块110输入文件310数据区块32O滑动窗口330具体实施例方式本发明应用于具有处理重复数据删除程序的计算机，例如个人电脑、笔记型电脑、服务器或应用在客户端与服务端架构中为能清楚本发明运作流程与实际数据区块的划分方式，还请同时参考图2与图3所示，其分别为本发明的切分运作流程示意图与数据区块切分示意图本发明包括以下步骤步骤S210 载入输入文件；步骤S220 利用固定长度的滑动窗口在输入文件中循序移动，并记录滑动窗口于输入文件的起始位置，且同时记录当前滑动窗口位于输入文件的尾端位置，将起始位置与尾端位置间的长度定义为分块长度；步骤S230 根据滑动窗口对输入文件的固定长度的所涵盖范围进行指纹特征程序，用以产生指纹特征值；步骤S240 重复滑动窗口的移动，直至滑动窗口符合切分条件时，则停止滑动窗口的移动，再根据输入文件的分块长度产生相应的数据区块；以及步骤S250 依据滑动窗口在前一数据区块的尾端位置作为新的滑动窗口的起始位置，并重复执行产生数据区块的步骤，直至完成输入文件中的所有数据区块为止，且产生指纹特征值的索引文件首先，将输入文件310载入相应的计算机装置中，而对欲进行切分的数据区块320 的分块长度定义为L (图3中左起第一个与第二个为已完成切分的数据区块320，而第三个为欲进行切分的数据区块320)，滑动窗口 330的长度为W(如图3所示中虚线框)。
接着， 滑动窗口 330的起始位置对齐于输入文件310的起始位置滑动窗口 330以固定长度的字节在输入文件310中循序地移动举例来说，若是滑动窗口 330每次以一个字节作为移动单位时，则滑动窗口 330会每次以一个字节在输入文件310中依序移动换言之，第一次的滑动窗口 330的起始位置与第二次滑动窗口 330相差一个字节若是以五个字节作为移动单位，则滑动窗口 330会每次移动五个字节的间隔在输入文件310中移动在滑动窗口 330移动的过程中，另外会记录滑动窗口 330位于输入文件310的尾端位置，在每次移动时会计算一个哈希值而起始位置与尾端位置间的长度就是为分块长度L本发明为避免滑动窗口 330无终止的滑动，所以以下列步骤作为分块长度决定依据，请参考图4A所示，其为本发明的分块长度运作示意图分块长度的决定包括以下步骤步骤S231 对指纹特征值进行模数处理，并判断处理结果是否符合第一切分数值；步骤S232 若指纹特征符合第一切分数值，则停止滑动窗口的滑动并进行切分；步骤S233 若指纹特征不符合第一切分数值，则判断指纹特征是否符合第二切分数值；步骤S234:若指纹特征不符合第二切分数值，则开始移动滑动窗口并跳至步骤 S236 ；步骤S235 若指纹特征符合第二切分数值，则记录滑动窗口在输入文件的当前位置；步骤S236 判断分块长度是否符合预设长度；步骤S237 若分块长度符合预设长度，则判断当前的指纹特征是否符合第二切分数值；步骤S239 若指纹特征不符合第二切分数值，则以预设长度进行切分；步骤S238 若指纹特征符合第二切分数值，则当前滑动窗口的位置作为切分的边界，并进行切分；以及步骤S240 若分块长度未符合预设长度，则继续移动滑动窗口。
在步骤S231中，对于每一次移动的过程中均会对滑动窗口 330所涵盖的部分输入文件310进行哈希处理，而哈希处理的种类可以是SHA-1、rolling哈希程序当滑动视窗每次移动时，将会产生相应部分的输入文件310的指纹特征值，请参考下式1所示Fingerprint (W) mod (D) =r ζ 1式1中的Fingerprint为哈希程序，W为滑动窗口 330的长度，D为一预设模数，r 为 Fingerprint (W)的余数在滑动视窗每次滑动时均会计算相应部分的输入文件310的指纹特征值接着， 在对指纹特征值进行模数计算，计算相应的余数值在本发明中将所产生的余数值与切分数值进行比对当余数值与切分数值相同时，则停止滑动窗口 330的滑动本发明中为避免滑动窗口 330无限制的滑动，所以分别设定至少两组的指纹特征值，根据第一指纹特征值rl与第二指纹特征值r2用以检测是否继续进行切分而第一特征值与第二特征值的设定除了可以透过统计的方式得到也可以藉由乱数生成或人为的方式所给定将每次滑动窗口 330滑动时所产生的指纹特征值和第一特征值比较如果两者相同，则分块成功如果不同，则继续使用指纹特征值和第二特征值进行比较。
如果指纹特征值和第二特征值相同，则记录当前滑动窗口 330的数据位置但此一数据位置并非一定是切分的边界接着，滑动窗口 330仍会继续移动至预设长度，并计算相应的指纹特征值假设在到达预设长度前仍未出现符合第一特征值或第二特征值的指纹特征值，则将会以预设长度为基准，对输入文件310进行切分若是在到达预设长度都没有符合第一特征值的位置时才去检查是否有过符合第二特征值的位置如果有则以符合第二特征值的位置分块如果没有才以预设长度的位置为边界分块就上述的切分处理过程中可能还会出现“在切分过程中一直没有符合第一特征值的位置，但存在符合第二特征值的位置P1”的情形(请参考图4B)但比较到位置Pl时，由于还没有达到预设长度的位置P2，不确定后面(位置Pl到位置P2之间)是否会有符合第一特征值的位置所以要继续将滑动窗口 330向后进行滑动，一直到达预设长度时认为确实没有符合第一特征值的位置，才再检查是否有过符合第二特征值的位置若有则以该位置为边界分块，若没有则以预设长度为边界分块举例来说，当切分数值rl为50，切分数值r2为70，预设长度为128Kbytes，并且假设滑动窗口 330在输入文件310中移动时产生下列余数值18、52、37、50、26、45、70与100。
当第一次所产生的余数值为18时，由于余数值18未符合上述两组切分数值且未达预设长度，所以将继续移动滑动窗口 330同理，余数值52与37未符合上述两组切分数值且未达预设长度，所以将继续移动滑动窗口 330当余数值为50时，由于未达预设长度所以暂先记录余数值50时的滑动窗口 330位于输入文件310的所在位置，并继续移动滑动窗口 330同理，余数值26、45未符合上述两组切分数值且未达预设长度，所以将继续移动滑动窗口 330当余数值为70时，由于未达预设长度所以暂先记录余数值70时的滑动窗口 330 位于输入文件310的所在位置，并继续移动滑动窗口 330假设余数值100时的分块长度等于预设长度由于余数值100不符合切分数值rl与r2，但分块长度以达预设长度，所以滑动窗口 330将不继续移动而且将滑动窗口 330回卷至余数值为70位于输入文件310相应位置，并将此一位置作为数据区块320切分的边界持续重复上述数据区块320的切分处理，直至完成输入文件310中的所有数据区块320为止，且产生指纹特征值的索引文件与元数据(meta-data)本发明除了上述的数据区块320的切分处理外，本发明并提出以下的数据区块 320的新增处理，藉以将新的数据加入现有的数据区块320中。
请参考图5所示，其为本发明新增数据的运作流程示意图本发明新增数据包括下列步骤步骤S510 载入新增文件；步骤S520 对新增文件进行数据区块切分程序，产生多组数。