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

摘要

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

主权项

一种相同数据块的自适应识别方法，其特征在于，包括以下步骤：步骤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，直到所有数据块遍历结束。