张宗华，屈　英，叶志佳，牛新征

1)国家电网公司北京电力医院信息通讯部，北京 100073；2)电子科技大学计算机科学与工程学院，四川成都 611731



基于多特征匹配和Bloom filter的重复数据删除算法

张宗华1，屈英2，叶志佳2，牛新征2

1)国家电网公司北京电力医院信息通讯部，北京 100073；2)电子科技大学计算机科学与工程学院，四川成都 611731

针对EB(extreme binning)算法重复数据删除率低，磁盘I/O开销大的缺陷，提出基于多特征匹配和Bloom filter的重复数据删除算法DBMB(deduplication based on multi-feature matching and Bloom filter). 将小文件聚合为局部性文件单元，作为一个整体进行去重处理，采用最大、最小以及中间数据块ID的多重相似性特征进行匹配，并基于Bloom filter优化磁盘数据块的查找和匹配过程. 结果表明，DBMB算法能有效提升重复数据删除率，降低算法执行时间，同时减少处理小文件的内存开销，性能提升显著.

计算技术；重复数据删除；多特征匹配；布隆过滤器；EB算法；磁盘优化

重复数据删除(deduplication)是一种能有效优化存储空间、提高存储效率的技术，目前被广泛应用于数据备份和归档系统中. 在基于数据块的重复数据删除技术中，索引的内存占用量和运行效率是影响系统性能的关键. EB(extreme binning)是Bhagwat等[1]提出的一种可扩展的数据块级去重技术，能较好地缓解内存占用问题. EB算法基于数据流的相似性，通过建立和维护文件的代表块(representative chunk)指纹索引，并将文件主体在磁盘中以指纹容器(bin)保存. 由于EB算法只在内存中保存文件的代表块ID，且对于每个文件的备份至多只需访问一次磁盘，有效减小了内……