注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

亮丽

一直想安静的过着安静的日子,安静的爱着爱我的人

 
 
 

日志

 
 
 
 

重复数据删除(Data de-duplication)技术(转)  

2011-10-10 09:56:34|  分类: 云存储 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       重复数据删除 是近年存储领域涌现出来的一门新兴技术,各大竞争厂商都生成其重复删除比可以达到 1:20 左右甚至更高,被专家誉为是一种“将会改写存储行业的经济规则”的技术。然而在实际和用户的接触中,大多数用户对该技术还存在许多疑问,诸如:“和增量备份有何区别”、“会不会造成数据损害”、“会不会影响备份性能”等等。所以,在这里我们就详细探讨一下重复数据删除的工作原理。

区别重复数据删除与增量备份

首先,“重复数据删除”和“增量备份”是完全不同的概念。“增量备份”是指只备份变化的文件;“重复数据删除”则是指只备份不重复的数据。举个简单的例子说明它们的区别:比如有一个文件型数据库 Access的文件 finance..mdb ,如果向该库中新插入了几笔记录,那么则意味着该文件发生了变动。当采用增量备份时会检查该文件的标志位,并将该文件整个重新备份;而如果使用“重复数据删除”技术,则只会备份新插入记录的数据。

从工作原理上讲,重复数据删除技术可以分为两大阵营,一种是基于哈希(Hash)算法的重复删除,一种是基于内容识别的重复删除。

基于哈希算法的重复数据删除

基于哈希算法的重复删除技术的代表厂商有昆腾、Data domain 、飞康等,其基本原理是利用SHA 、MD5 等算法将备份数据流切分成“块”,并且为每一块数据生成一组哈希码序列,不同厂商的技术可能对块大小的划分不同。

当备份新的数据时,将按照索引把新数据的哈希码和已存数据的哈希码进行比较,如果发现有相同的哈希码存在,则说明该数据块已经存在相同的实例,此时新备份的数据将被放弃而在相应的位置代之以指向原有实例的指针。

这种算法的优势在于算法简单,而缺点在于当磁盘容量不断增长时,数据块产生的哈希码表可能会超出内存的负载容量,这意味着进行哈希比对时需要去访问磁盘——这势必造成重复删除性能的迅速下降。

另外,哈希算法可能会产生哈希冲突——简单的讲就是不同的数据块产生了相同的索引,这会导致有用的数据被错误的丢弃,从而造成文件的损坏。当然,产生哈希冲突的概率是非常低的,以 128 位的 MD5 码为例,两个哈希码产生冲突的概率为 2E-128,假设一个阵列中存储了 N 个数据块的哈希码,那么其中包含冲突的概率可以按照(1/2)*(N/2e64)e2 进行计算,这意味着只有数据块的数量级达到 2E64 时才可能产生一个冲突。

基于内容识别的重复数据删除

基于内容识别的重复删除技术的代表厂商有 Sepaton、ExaGrid Systems 等,其基本原理是对记录的数据格式进行比对。在备份数据时,该技术会读取数据并从中提取出每组备份集以及备份集中数据对象的元数据,存入到内嵌文件系统的数据库内。当有新的数据进入时则对新的元数据与数据库中的元数据进行版本比对。

不同厂商技术的比对范围会有差别,有的只能在相同文件内进行比对,有的可以在整个阵列空间内进行比对。如果发现相同的元数据,接下来会对数据对象进行逐字节的比较,从而发现发生变化的数据——即使它们的元数据是形同的。如果数据对象确实是重复的,则删除该数据对象并代之以相应的指针。这种算法的优势在于可以避免哈希冲突,并可以利用元数据之间的联系更快的查找重复数据。

从上面两种技术的原理来看,用户完全没有必要担心数据损失问题,并且,各大厂商也采取了严格的措施来确保数据删除的准确性——以 Sepaton 的Delta Store 技术为例,在删除重复数据时首先会做一次模拟删除,从而生成一份删除后的数据视图,只有验证表明该视图确实可以准确的恢复原始数据后才进行真正的重复数据删除并回收磁盘空间。

另外还有一种分类方法是:根据处理的时间不同分为同步和异步的数据删除技术

联机重复数据删除技术(我觉得称之为同步方式更合适)
       当大量的备份数据流到达具备重复数据删除技术的备份设备时,首先驻留在内存里,重复数据删除引擎开始对先到的备份数据进行辨识,判断是否存在已保存过的数据块。 如果有,则写入一个指针来代替实际数据块的写入过程。如果没有,则写入该新数据块。任务结束。
       采用这种方式进行重复数据删除工作,可以显著降低I/O的开销,因为大部分工作是在RAM内完成的。只是在做哈希算法查找重复的数据块时产生了少量的磁盘操作(只有一家厂商声称他们的哈希查找也是在RAM内完成的)。
    某些重复数据删除产品还需要花费额外的时间,对于在原有数据块中初步已判断重复的数据块进行读操作,在字节级别确认匹配后才会舍弃。假设重复数据删除比为10:1,那么95%的处理时间只是对于重复的数据块进行一次写操作,用来更新哈希表就可以了,对于冗余的数据块丢弃即可而无需对磁盘进行其他任何写操作。剩余5%的时间用来将那些唯一的数据块写入磁盘并更新哈希表。

后期处理重复数据删除技术(我觉得称之为异步方式更合适)
       当备份服务器开始向备份设备传输备份数据流时,会将整个备份数据量作为一个整体来传送。 然后启动单独的进程开始读取已写入磁盘的数据块,开始重复数据删除处理过程(该过程通常由另外一个设备执行,访问备份数据已写入的磁盘),如读入的数据块和已存储的数据块重复了,则用指针替代该数据块,如果没有重复,则将该新数据块留在磁盘上,而无需任何其他操作。
       这种处理方式比联机处理方式显然需要更多的I/O操作。首先,后期处理方式要求进行所有备份数据块的写入操作。 然后,还需要对写入的所有数据块进行再读入操作,并与哈希表记录进行对比查找重复的数据块,这就需要额外的磁盘读操作。某些厂商的产品还要求进行再次的读操作来确认数据块在字节级别的重复。如果确认了重复的数据块,需要进行删除重复的数据块的写操作,另外还需要发起更新哈希表的写操作,该过程占用了整个处理过程95%的时间。余下5%的时间用来处理那些不匹配的数据块,同样需要对哈希表进行更新写操作。

 

转自:http://www.click2earth.com/post/26.html

  评论这张
 
阅读(340)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017