(转)重复数据删除算法的考虑和关键问题

从原理上来讲,重复数据删除很简单,通常通过SHA1算法(一种HASH算法)得出每个数据块的fingerprint(HASH值),然后查找系统中是否存在具有相同HASH值的数据块。

如果存在,那么说明有重复数据;否则,表明不存在重复数据。

采用HASH算法的时候,唯一需要注意的是如何避免HASH碰撞。

有些设计会采用读数据校验的方法;

有些设计会采用双重HASH( SHA1 + SHA3 ) 的方式,降低碰撞概率。不同的设计会导致不同的吞吐量和延迟特征。从算法的角度来看,基于HASH算法的重复数据删除本身没有太多的问题,关键的问题在于如何提高查找效率。因为数据都在磁盘上,如何进行磁盘级的数据查找,这是一个严峻的挑战。

第一种是基于散列(hash)的方法,Data Domain、飞康、昆腾的DXi系列设备都是采用SHA-1, MD-5 等类似的算法将这些进行备份的数据流断成块并且为每个数据块生成一个散列(hash)。如果新数据块的散列(hash)与备份设备上散列索引中的一个散列匹配,表明该数据已经被备份,设备只更新它的表,以说明在这个新位置上也存在该数据。

基于散列(hash)的方法存在内置的可扩展性问题。为了快速识别一个数据块是否已经被备份,这种基于散列(hash)的方法会在内存中拥有散列(hash)索引。当被备份的数据块数量增加时,该索引也随之增长。一旦索引增长超过了设备在内存中保存它所支持的容量,性能会急速下降,同时磁盘搜索会比内存搜索更慢。因此,目前大部分基于散列(hash)的系统都是独立的,可以保持存储数据所需的内存量与磁盘空间量的平衡,这样,散列(hash)表就永远不会变得太大。

==============================================================================

MD5 + SHA1