Winnowing指纹串匹配的重复数据删除算法

Deduplication algorithm based on Winnowing fingerprint matching

针对可变长度分块(CDC)的重复数据删除算法的分块大小难以控制、指纹计算对比开销大、需要预先设置参数问题,提出Winnowing指纹串匹配的重复数据删除算法(DWFM)。首先,在数据分块前引入分块大小预测模型,较准确地根据应用场景计算出合适的分块大小;然后,在计算指纹时采用ASCII/Unicode编码方式作为数据块指纹;最后,在确定分块边界时,提出指纹串匹配的分块算法,不需要预先设置参数,使得指纹计算和对比开销减少。在多种数据集上的实验结果表明,相比固定长度分块(FSP)和CDC算法,DWFM在数据的重删率上提升10%左右,在指纹计算和对比开销方面减少了18%左右。因此,DWFM的分块大小和边界更加符合数据特性,减少了参数设置对重复数据删除算法性能的影响,在处理不同类型的数据时,可以有效地消除更多的重复数据。

There are some problems in big data that the chunking size of the deduplication algorithm for Content-Defined Chunking （CDC） is difficult to control, the expense of fingerprint calculation and comparison is high, and the parameter needs to be set in advance. Thus, a Deduplication algorithm based on Winnowing Fingerprint Matching （DWFM） was proposed. Firstly, the chunking size prediction model was introduced before chunking, which can accurately calculate proper chunking size according to the application scenario. Then, the ASCIl/Unicode was used as the data block fingerprint in the calculation of the fingerprint. Finally, when determining the block boundary, the proposed algorithm based on chunk fingerprint matching does not need to set the parameters in advance to reduce fingerprint calculation and contrast overhead. The experimental results on a variety of datasets show that DWFM is about 10% higher than FSP （ Fixed-Sized Partitioning） and CDC algorithms in deduplication rate, and about 18% in fingerprint computing and contrast overhead. As a result, the chunking size and boundaries of DWFM are more consistent with data characteristics, reducing the impact of parameter settings on the performance of deduplication algorithms, meanwhile, effectively eliminating more duplicate data when dealing with different types of data.