一种相同数据块的自适应识别方法

摘要

本发明提出了一种相同数据块的自适应识别方法，包括：初始采样比率值，数据块字节，数据块内容，采样数据块中的内容，并对其进行混杂操作，得出其哈希值。根据哈希值，进行哈希表或者查找树的查询操作，找出有相同的哈希值的数据块，然后进行全内容比较，进一步确认相同性。如果最终确认两者其实不相同，那么这两个数据块构成一次哈希冲撞。每一个时间段统计这段时间以内的哈希冲撞率，并根据此冲撞率自适应调整采样值HS。由于采样率越低，哈希计算越快，本发明够在一批数据集上自适应到达一个最优化的采样值，进而到达一个最快的相同数据识别速度。本发明提出的算法可以大幅度提升去冗系统在寻找冗余数据时候的效率。

权利要求

1.一种相同数据块的自适应识别方法，其特征在于，包括以下步骤：步骤1，初始化用以哈希值查找的数据结构HStruct，初始化采样比率值HS，

0≤HS≤100%，分别初始化扫描计数器的值I，成功计数器的值S和冲撞计数器的值F为

0，并选定一个大小固定的数据块DATA，数据块DATA的大小为SIZE字节；

步骤2，从数据块DATA中采样出一定字节数的数据，采样字节数为HS×SIZE个；

步骤3，对所采样出的数据进行混杂操作，得出一个整型值大小的哈希值H；

步骤4，在查找数据结构HStruct中查找哈希值H，如果找到另一个数据块DTMP的哈希值与哈希值H相等，则返回数据块DTMP，进行步骤5，否则将数据块DATA以哈希值H为键值，插入查找数据结构HStruct，并转至步骤12；

步骤5，比较数据块DATA与数据块DTMP的内容，如果两者内容完全相同，则进行步骤

6，否则进行步骤7；

步骤6，记录一次成功的相同数据块识别操作，即令成功计数器的值S=S+1，并将二元组<数据块DATA，数据块DTMP>作为结果输出，跳至步骤8；

步骤7，记录一次哈希冲撞的操作，即冲撞计数器的值F=F+1，进行步骤8；

步骤8，扫描计数器的值I加1，如果I小于设定阈值N，转至步骤12，否则进行步骤9；

步骤9，计算扫描计数器从0～N范围时间内的哈希冲撞率C=F/(F+S)并计算判别函数J(C,HS)，其中，HS为当前的采样比率，如果判别结果大于0，则增大采样比率值，如果结果小于0，则减少采样比率值，否则采样比率值不变；

所述判别函数J(C,HS)是使得B-W逐渐趋向近似极大值的判定函数，其中，W为一次扫描周期中由于哈希冲撞而浪费的时间，W=M×C×N，其中M是一次比较数据块所需要的时间；

B为一次扫描周期中，采用当前的采样比率值HS比采用100%的采样比率所节省的时间：B=T×(1-C)×(1-HS)×N，其中T为假设HS=100%时步骤3所需要的时间；

步骤10，如果上步骤中采样比率值发生改变，令变化后的采样比率值为HSNEW，根据采样比率值HSNEW对查找数据结构HStruct中已有数据块进行混杂操作，得到更新后的哈希值，混杂操作的采样字节数为|HS-HSNEW|×SIZE个；

步骤11，扫描计数器的值I，成功计数器的值S和冲撞计数器的值F分别置0，并标记为本扫描周期的结束和下一个扫描周期的开始；

步骤12，选择下一个数据块作为数据块DATA，返回步骤2，直到所有数据块遍历结束。

2.根据权利要求1所述的一种相同数据块的自适应识别方法，其特征在于，所述查找数据结构Hstruct为数组、哈希表或者查找树中的任意一种。

3.根据权利要求1所述的一种相同数据块的自适应识别方法，其特征在于，所述混杂操作为任意二元整形运算任意组合而成。

说明书

一种相同数据块的自适应识别方法

技术领域

[0001] 本发明涉及一种计算机中相同数据块的比较识别方法，特别是一种基于哈希函数的相同数据块的自适应识别方法

背景技术

[0002] 用Hash（哈希）函数识别相同的数据块是一种常见的技术，被普遍应用于信息系统的各个领域，比如通常运用于服务器磁盘存储的去冗系统（Deduplication System）会通过Hash磁盘块内容的方式，来找到相同内容的冗余磁盘数据块，并进行消除，从而达到提高磁盘存储效率的效果。一般来说，Hash函数会将数据块的内容映射到一个整型值上，然后通过整型值的比较，可以加速寻找相同的数据块的过程。已有的用以此用途的基于哈希的方法，一般都会将数据块的全部内容或者固定部分的内容作为算法的输入，不会自动根据所运算的数据集合的特征做算法的输入内容数量的自动选取，因此在很多场合没有办法将算法的性能达到最优化。

[0003] 举例说明，假设一个数据集合有若干个数据块，而这些数据块的内容彼此差异很大：任意两个数据块，在相同位置上，没有一对字节是相同的，那么，实际上，只需要Hash这个两个数据块当中的相同位置的任意两个字节即可，如果Hash它们的全部内容则会浪费时间。

发明内容

[0004] 发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供一种相同数据块的自适应识别方法,提高系统在识别相同数据块时候的速度和效率。

[0005] 为了解决上述技术问题，本发明公开了一种相同数据块的自适应识别方法，包括以下步骤：

[0006] 步骤1，初始化用以哈希值查找的数据结构HStruct（可以是数组、哈希表或者查找树中的任意一种），初始化采样比率值HS，0≤HS≤100%，分别初始化扫描计数器I，成功计数器S和冲撞计数器F为0（定义第一个扫描周期的开始），并选定一个大小固定的数据块DATA，数据块DATA的为SIZE字节；

[0007] 步骤2，从数据块DATA中采样出一定字节数的数据，采样字节数为HS×SIZE个；

[0008] 步骤3，对所采样出的数据进行混杂操作，混杂操作为任意二元整形运算任意组合而成，得出一个整型值大小的哈希值H；

[0009] 步骤4，在查找数据结构HStruct中查找哈希值H，如果找到另一个数据块DTMP的哈希值值与哈希值H相等，则返回数据块DTMP，进行步骤5，否则将数据块DATA以哈希值H为键值，插入查找数据结构HStruct，并转至步骤12；数据块DATA与数据块DTMP位于同一存储空间中，分别代表任意两个数据块，DATA和DTMP只是对数据块命名的形式区分，并不指向数据块的具体内容。

[0010] 步骤5，比较数据块DATA与数据块DTMP的内容，如果两者内容完全相同，则进行步骤6，否则进行步骤7；

[0011] 步骤6，记录一次成功的相同数据块识别操作（即成功计数器的值S=S+1），并将二元组<数据块DATA，数据块DTMP>作为结果输出，跳至步骤8；

[0012] 步骤7，记录一次哈希冲撞的操作（即冲撞计数器的值F=F+1），进行步骤8；

[0013] 步骤8，扫描计数器I加1，如果I小于设定阈值N（N一般大于3，小于整个数据块集合数量的一半），转至步骤12，否则进行步骤9；

[0014] 步骤9，计算扫描计数器从0增长到N这整个过程中的哈希冲撞率C=F/(F+S)并计算判别函数J(C,HS)，如果判别结果大于0，则增大采样比率值，如果结果小于0，则减少采样比率值，否则采样比率值不变；假设定义B为此次扫描周期中，由于采样比率HS小于100%，而比采样全部数据块内容所节省的时间即B=T×(1-C)×(1-HS)×N，其中T为HS=100%时，步骤3所需要时间。定义W为此次扫描周期中由于哈希冲撞而浪费的时间，即W=M×C×N，其中M是一次比较数据块所需要的时间，则判别函数J(C,HS)是使得B-W逐渐趋向近似极大值的判定函数。其一个典型的形式可以为：其中B’和W’分别是上个扫描周期中节省和浪
费的时间,初始值都为0。

[0015] 步骤10，如果上步骤中采样比率值发生改变，令变化后的采样比率值为HSNEW，根据采样比率值HSNEW对查找数据结构HStruct中已有数据块进行混杂操作，得到更新后的哈希值，混杂操作的采样字节数为|HS-HSNEW|×SIZE个；

[0016] 步骤11，扫描计数器I置，成功计数器的值S和冲撞计数器的值F分别置0，并定义本扫描周期的结束和下一个扫描周期的开始；

[0017] 步骤12，选择下一个数据块作为数据块DATA，返回步骤2，直到所有数据块遍历结束。

[0018] 有益效果：本发明适用于快速识别相同内容的数据块，其主要有益效果体现在：

[0019] 1)能够自动适应数据集合的差异特征，如果一个数据集合数据块之间彼此差异很大，那么本发明的方法能很快将采样率调整到一个很小的值，而如果数据集合中数据块之间彼此相似性很高，那么本发明的方法又可以将采样率自动调高。避免了背景方法中只用某种哈希方法难以适应不同场景的劣势。

[0020] 2)平均性能比背景已有方法大幅度提高。在自然产生的很多数据集合中，本发明[0021] 的方法能够自适应到一个小于100%的采样率上，因此预期在绝大部分数据集上会有普遍的性能提高。

附图说明

[0022] 下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/或其他方面的优点将会变得更加清楚。

[0023] 图1是本发明方法的流程图。

具体实施方式

[0024] 本发明公开了一种相同数据块的自适应识别方法，包括如下步骤：

[0025] 1.初始化用以Hash值查找的数据结构HStruct，初始化采样比率值HS（0≤HS≤100%）,分别初始化扫描计数器的值I，成功计数器的值S和冲撞计数器的值F为0（定义第一个扫描周期的开始），并选定一个大小固定为SIZE字节的数据块DATA。

[0026] 用以Hash（哈希）值查找的数据结构HStruct可以选择Hash表，或者查找树等可以用作快速查找的数据结构，如果选择查找树的话，常见可以使用红黑树或者AVL树等具有平衡结构的树结构。初始的采样比率值可以根据对所需运算的数据集合的预估计来定，如果数据集中的数据块彼此差异相对比较大，那么HS可以采用比较高的值（≥50%），反之，则应该选取较低值（≤50%）。由于是作相同数据块识别，显然数据集中的所有数据块都是固定大小，设为SIZE字节。

[0027] 2.从数据块DATA当中采样出HS×SIZE个字节的数据；

[0028] 在具体实施时，对数据块采样意味着从数据块当中读取HS×SIZE个字节的内容。采样的方式，同样也需根据数据块特征来定，如果预估计数据块当中的数据分布成随即分布，则可以按照采样率使用线性间隔的方式采样（例如读取第1、3、5、7…等字节）。如果预估计数据块当中的数据分布有固定规律，那么采样方式可以避开该分布规律以使得算法稳定。

[0029] 3.对所采样出的数据进行混杂操作，得出一个整型值大小的Hash值H；

[0030] 混杂操作可以由任何二元整形运算符组合而成，如加、减、乘、除、取余数、移位、异或等，而操作的单位可以是单个字节，也可以由采样字节组合而成的一定长度的整型值，如32位或者64位的整型值。混杂操作可以在采样的字节上进行若干次，将最后得出的结果，作为Hash值H。

[0031] 4.在查找数据结构HStruct中查找哈希值H，如果找到另一个数据块DTMP的Hash值与数据块DATA的哈希值相等，则返回数据块DTMP，继续下一步骤，否则将数据块DATA以哈希值H为键值，插入HStruct，并转至步骤12。

[0032] 在查找结构HStruct中查找哈希值H，查找的方式按照HStruct具体种类而进行。如果找到另一个数据块DTMP的Hash值与之相等，则返回B’，返回的方式是某种可以读取数据块DTMP的索引，比如指针或者数组下标等。如果没有找到相等Hash值的数据块，那么，数据块DATA以哈希值H为键值，插入HStruct（其中包含对HStruct做对应的调整），并转至步骤11。

[0033] 5.比较数据块DATA与数据块DTMP的内容，如果两者内容完全相同，则进行步骤[0034] 6，否则进行步骤7；

[0035] 数据块DAT1与数据块DTMP容比较可以采用类似memcmp等C语言函数，或自行用循环结构来实现。

[0036] 6.记录一次相同数据块识别成功的操作（即成功计数器的值S=S+1），并将二元组<数据块DATA，数据块DTMP>作为算法结果输出，跳至步骤8；

[0037] 如果相等则记录一次相同数据块识别成功的操作，记录的方式可以是增加某计数器的值,定义为S=S+1。如果相同数据块识别成功，该二元组<数据块DATA，数据块DTMP>作为算法结果输出；其他上层系统或者算法，如去冗系统（deduplication system），可以借助此输出来进行进一步的操作。

[0038] 7.则记录一次Hash冲撞的操作（即冲撞计数器的值F=F+1），进行步骤8；。

[0039] 如果数据块DATA与数据块DTMP的内容不相同，则记录一次Hash冲撞的操作；记录的方式是增加某计数器一个固定大小值，典型的可以定义冲撞计数器的值F=F+1。

[0040] 8.扫描计数器I加1，如果I小于某阈值N，转至步骤12，否则进行步骤9；

[0041] 在具体实施时，阈值N的确定，可以根据数据集合的特征来定，如果数据集合中数据块的分布相对比较均匀，那么，N值可以采用一个比较小的值，反之，则应该适当增大。N值总体的取值范围是3~M/2，其中M是整个数据集合中数据块的数量。

[0042] 9.计算扫描计数器从0~N范围时间内的哈希冲撞率C=F/(F+S)并计算判别函数J(C,HS)，如果判别结果大于0，则增大采样比率值，如果结果小于0，则减少采样比率值，否则采样比率值不变；。

[0043] 如果Hash冲撞率越高，那么应该提高采样比率，反之应该降低采样比率。由于每次Hash冲撞可能带来额外的性能损耗，，冲撞率C越大，那么J(C,HS)的判别结果应该越容易导致采样率的提高。J(C,HS)同时需要考虑当前的采样率，相对于全内容的Hash计算（HS=100%），所节省的不必要数据读取时间。一个常见的用以评估在某个扫描周期内，采用某个小于100%的采样比率值比用100%的采样比率加速的效果，是计算节省时间和浪费时间之间的差，进而希望这个差值最大化。假设定义B为此次扫描周期中，由于采样比率HS小于100%，而比采样全部数据块内容所节省的时间即B=T×(1-C)×(1-HS)×N，其中T为HS=100%时，步骤3所需要时间。定义W为此次扫描周期中由于哈希冲撞而浪费的时间，即W=M×C×N，其中M是一次比较数据块所需要的时间，则判别函数J(C,HS)是使得B-W逐渐趋向近似极大值的判定函数。J(C,HS)一个典型的形式可以为：其中B’和W’分别是上个扫描周期中节省和浪
费的时间。如果判别函数J(C,HS)得出结果大于0，则增大采样比率值，如果结果小于0，则减少采样比率值。否则采样比率值不变。

[0044] 10.如果步骤8采样比率值更新为HSNEW，根据采样比率值HSNEW对查找数据结构HStruct中已有数据块进行混杂操作，得到更新后的哈希值，混杂操作的采样字节数为|HS-HSNEW|×SIZE个。

[0045] 如果步骤8采样比率值更新成HSNEW，那么下一个被选择的数据块的Hash值将基于HSNEW的采样比率，而原有的查找数据结构HStruct中作为键值的数据块的Hash值是基于旧的采样比率，因此，需要重新计算HStruct中已有数据块的新的Hash值，重新计算的方式与步骤3所采用的混杂操作相同，同时为减少计算时间，对于HStruct中已有数据块的Hash值的计算，在已有其旧Hash值的基础上，只需进一步采样|HS-HS'|×SIZE个字节的内容。

[0046] 11.扫描计数器的值I，成功计数器的值S和冲撞计数器的值F分别置0，并定义本扫描周期的结束和下一个扫描周期的开始；

[0047] 12.选择下一个数据块作为数据块DATA，返回步骤2，直到所有数据块遍历结束。；

[0048] 在具体实施时，下一个数据块DATA的选取，按照本算法输入的数据集合来定。

[0049] 作为本发明的一种应用，如果数据块DATA与数据块DTMP内容完全相同，则删除数据块DAT1，将其所占用的空间释放。此类需求可以广泛出现在存储系统，内存管理，数据备份等等很多场景，接下来实施例将具体阐述。

[0050] 实施例1

[0051] 本实施案例公开了一种相同数据块的自适应识别方法在一个静态图像监控系统存储优化上的应用。实施场景如下所述：

[0052] 一个静态图像监控系统每隔一小段时间对目标实施高分辨率的拍摄，拍摄结果以png格式进行存放。由于其拍摄目标很可能很长时间都不发生变化，也有可能短时间发生很大的变化，因此其存储的图片有很多相同，有少量不同。由于png格式本身已经是压缩格式，因此在保证图片质量不损失的情况下，采用传统的无损压缩技术很难进一步缩小存储空间。因此，系统优化策略打算通过某种方法快速鉴别大量完全相同的图像，进而减少实际存储的空间。

[0053] 在此场景下，本实施例的方法具体实施步骤为：

[0054] 步骤1，初始化用以哈希值查找的数据结构HStruct，本实施例采用红黑树作为实例。初始化采样比率值HS，由于考虑数据集合的特征，即大部分相同，少量有很大不同，HS初始值设为一个较小的值20%。分别初始化扫描计数器的值I，成功计数器的值S和冲撞计数器的值F为0（定义第一个扫描周期的开始），并选定其中一张图片P（由于是同镜头同分辨率拍摄，所有图片大小相同，本实施例假设为SIZE字节）；

[0055] 步骤2，从图片P中采样出一定字节数的数据，采样字节数为HS×SIZE个；

[0056] 步骤3，对所采样出的数据进行混杂操作，本实施例混杂操作使用二元运算为其中H是哈希值H，初始值为0，I是依次序的混杂过程中的采样数据中的某个整型值。计算结果得出最终的该图片采样的哈希值H；

[0057] 步骤4，在查找数据结构HStruct中查找哈希值H，如果找到另一个图片PNEW的采样哈希值与哈希值H相等，则返回图片PNEW，进行步骤5，否则将图片P以哈希值H为键值，插入查找数据结构HStruct，并转至步骤12；

[0058] 步骤5，比较图片P与图片PNEW的内容，如果两者内容完全相同，则进行步骤6，否则进行步骤7；

[0059] 步骤6，记录一次成功的相同数据块识别操作（即成功计数器的值S=S+1），并将二元组<图片P，图片PNEW>作为结果输出，在此基础上系统存储管理程序将图片P的文件索引指向图片PNEW，并删除冗余图片P，跳至步骤8；

[0060] 步骤7，记录一次哈希冲撞的操作（即冲撞计数器的值F=F+1），进行步骤8；

[0061] 步骤8，扫描计数器的值I加1，如果I小于设定阈值N，转至步骤12，否则进行步骤9。对于此实施案例，N取较小值10；

[0062] 步骤9，计算扫描计数器从0~N范围时间内的哈希冲撞率C=F/(F+S)并计算判别函数J(C,HS)，如果判别结果大于0，则增大采样比率值，如果结果小于0，则减少采样比率值，否则采样比率值不变；假设定义B为此次扫描周期中，由于采样比率HS小于100%，而比采样全部数据块内容所节省的时间即B=T×(1-C)×(1-HS)×N，其中T为HS=100%时，步骤3所需要时间。定义W为此次扫描周期中由于哈希冲撞而浪费的时间，即W=M×C×N，其中M是一次比较数据块所需要的时间，则判别函数J(C,HS)是使得B-W逐渐趋向近似极大值的判定函数。判别函数J(C,HS)具体为： 其中B’和W’分别是上个扫描周期中节省和浪费的时间。

[0063] 步骤10，如果上步骤中采样比率值发生改变，令变化后的采样比率值为HSNEW，根据采样比率值HSNEW对查找数据结构HStruct中已有数据块进行混杂操作 得到更新后的哈希值，混杂操作的采样字节数为|HS-HSNEW|×SIZE个；

[0064] 步骤11，扫描计数器的值I置，成功计数器的值S和冲撞计数器的值F分别置0，并标记为本扫描周期的结束和下一个扫描周期的开始；

[0065] 步骤12，选择下一个数据块作为图片P，返回步骤2，直到所有数据块遍历结束。

[0066] 本实施例与现有技术处理方法（比如用SuperFastHash整个哈希图片）相比，经过100次以上试验，在处理相同数据对象的情况下，整体处理速度提高了5倍，CPU平均占用下降了60%，处理准确度相同。

[0067] 实施例2

[0068] 本实施例公开了一种相同数据块的自适应识别方法在一个多用户文件备份系统上的应用。实施场景如下所述：

[0069] 一个用以多用户存储备份文件的系统，通常会有很多相同或者雷同的文件，典型的情况是一个工作组在共享一批文件，并且各自在不同的文件上有自己的修改，而每个人都是直接将自己的文件目录备份在网络共享的服务器上。该备份系统的优化策略希望能将相同的文件数据块融合到一起。

[0070] 在此场景下，本实施例与实施例1相比，不同之处在于：

[0071] 步骤1中，数据块的选择，为了提高可以融合的数据量，将所有输入的文件切块成小数据块，一个典型的大小为4KB。

[0072] 步骤1中，由于事先对文件数据块类似程度的无法预料，HS初始值设为一个折中的值，即50%，而让后面的步骤自动调整；

[0073] 步骤3和步骤10中，混杂操作使用二元运算为H=((H＞＞16)^H^(H＜＜17))+I；

[0074] 步骤4中，查找数据结构Hstruct采用哈希表结构；

[0075] 步骤8中，由于文件数据块数量可能比较庞大，因此采用的N值为所有文件数量。

[0076] 步骤9中，由于考虑到文件数据加载到内存需要额外的时间，判别函数J(C,HS)采用的公式为 其中Bi，Wi分别代表第前i个扫描周期中，对应的测算值。

[0077] 其余未说明的部分的处理步骤，与实施例1相同。

[0078] 本实施例与现有技术处理方法（比如用SHA-1哈希数据块）相比，经过100次以上试验，在处理相同数据对象的情况下，系统的整体速度提高10倍以上，CPU平均使用率下降85%。

[0079] 本发明提供了一种相同数据块的自适应识别方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。