重复数据删除知识点大汇总
这篇文章主要讲的是重复数据的概念原理和重复数据删除技术的使用方法和重复数据删除知识点的大汇总。重复数据删除是一个很热门的存储技术哦！。希望本篇文章对你们有用，大家要认真看噢~
我相信所有人都会同意，数据存储正在以飞快地，甚至是令人震惊的速度在增长。这意味着为了不影响普通用户的正常使用，存储管理员们不得不加班加点地在幕后工作着。他们的鲜为人知的工作包括：配额管理，快照（snapshots)，数据备份，数据复制（replication），为灾难时数据恢复而做的数据备份，离线数据拷贝，已删除的用户数据的恢复，监测数据增长和数据使用率，以及其他为确保应用平稳运行所做的数以千计的工作（正如花样游泳，从水上看起来非常优雅美观，而在水下，运动员的腿和手臂不得不飞快地摆动。）我把存储专家与花样游泳运动员类比，可能会让两方面的人都不高兴（我得道歉）。现在让我们来看一下这项新技术是如何使得存储管理人员的工作轻松而又节约企业预算的。这项新技术叫做重复数据删除。虽然这是一项新技术，但通过我的介绍你会知道它其实也是已有技术的变形，虽然它对多数存储系统产生了巨大影响。闲话少说，让我们来看一下重复数据删除这项技术。
简介
重复数据删除，其实很简单，遇到重复数据时不是保存重复数据的备份，取而代之，增加一个指向第一份（并且是唯一一份）数据的索引。从上讲，它能减少存储数据所占用的空间。这会带来如下好处：节约IT经费（不需要为所需要的额外空间增加投资）减少备份数据，数据快照等的大小(节约经费，节约时间，等）较少电源压力（因为更少的硬盘，更少的磁带等）节约网络带宽（因为只需要更少的数据）节约时间，因为需要较少的存储空间，磁盘备份成为可能。它是一种目前主流且非常热门的存储技术，可对存储容量进行有效优化。它通过删除数据集中重复的数据，只保留其中一份，从而消除冗余数据。如下图所示。这种技术可以很大程度上减少对物理存储空间的需求，从而满足日益增长的数据存储需求。Dedupe技术可以带许多实际的利益，主要包括以下诸多方面：
(1) 满足ROI(投资回报率，Return On Investment)/TCO(总持有成本，Total Cost of Ownership)需求；
(2) 可以有效控制数据的急剧增长；
(3) 增加有效存储空间，提高存储效率；
(4) 节省存储总成本和管理成本；
(5) 节省数据传输的网络带宽；
(6) 节省空间、电力供应、冷却等运维成本。
上面这些好处也正是重复数据删除技术风靡当前的根本原因。又有谁会不喜欢节约经费，时间，网络带宽呢？但是像很多美好的东西一样，魔鬼存在于细节中。本文将会介绍重复数据删除方面的概念及存在的问题。重复数据删除绝不是新事物，事实上它只是数据压缩的衍生品。数据压缩在单文件范围内删除重复的数据，代之以指向第一份数据的索引。重复数据删除把这个概念进行如下扩展：单个文件范围内（跟数据压缩完全一致）
1.跨文件
2.跨应用
3.跨客户端
4.跨时间
重复数据删除与数据压缩的主要区别在于：假如你有两个完全相同的文件，数据压缩会对每个文件进行重复数据的排除并代之以指向第一份数据的索引；而重复数据排除则能分辨出两个文件完全相同，从而只保存第一个文件。而且，它还跟数据压缩一样，排除掉第一个文件里的重复数据，从而减小所存储数据的大小。
下面是个简单的重复数据删除的例子。
该例中一共有三个文件。第一个文件，document1.docx，是个大小为6MB的简单的word文档。第二个文件，document2.docx，是第一个文件的拷贝，只是文件名不同。最后那个文件，document_new.docx，在document1.docx基础了进行某些小的修改，其大小仍旧为6MB.设重复数据删除程序会把文件分割成6个部分（6在实际应用中可能太小，这儿只是为了说明用）。现在第一个文件有A,B,C,D,E和F六个部分。第二个文件既然是第一个文件的拷贝，所有有会被分成完全相同的六个部分。第三个文件相比前两个文件只有一部分发生了变化（标记为G)，其大小仍旧是6MB. 在不使用重复数据删除的情况下，备份这些文件需要18MB的空间，而是用重复数据删除技术的情况下，只需要备份第一个文件和第三个文件的G部分，大约只需要7MB.重复数据删除技术还有一个特性：备份后，A,B,C,D,E,F,G存储在一个列表中有时也称为索引）。当新的文件被备份到该同一系统时，A,B,C,D,E,F,G各部分分别会于新文件进行比较。这就是跨时间的数据重复删除。关于重复数据删除，“什么是重复数据删除？“之后的下一个问题通常是”它能带来多大程度的数据删除？” 这个问题的答案依赖于使用场合和重复数据删除技术的具体实现。据EMC的统计，经过一段的稳定运行后，重复数据排除率在20:1到50:1之间。
细节之魔
重复数据删除技术无论从哪一种角度看都不是一种标准技术，因此它的所有实现技术都是有专利权的。从而，每一种产品的实现都不一样。理解这些基本差异对于决定是否和何时要应用到你的环境非常重要。重复数据删除技术最典型的应用是在数据备份方面，但绝不仅限于备份。记住这一点，我们一起来看一下重复数据删除技术的实现方式。
事实上，应用在备份领域的重复数据删除技术主要由两类：基于目标数据和基于源数据。其实这两种类型的区别很简单：基于目标数据的重复数据删除，是在数据在经过网络传输后进行充数数据删除；而基于源数据的重复数据删除，则是在数据备份前进行重复数据的删除工作。这两者的区别对于理解重复数据删除的典型部署方式非常重要。基于目标数据的重复数据删除的情况下，重复数据删除的工作通常由类似虚拟带库的单元来完成。备份数据被传输到备份服务器之后，虚拟带库才做重复数据的删除工作。因此，数据在网络传输中并没有经过重复数据删除，这增大了需要传输的数据量。但有一个优点：它允许我们使用现有的备份工具和备份程序。还有一种情况：你通过广域网进行远程的数据备份。此时，网络带宽资源异常重要。如果你仍然想使用基于目标数据的重复删除，虚拟带库单元可以放置于备份服务器附近，以便在数据通过广域网传输之前首先进行重复数据删除。与基于目标数据的重复删除相反的是基于源数据的重复数据删除。此时，重复数据的删除工作需要由备份软件来完成。客户端的备份软件首先需要告诉服务器端的备份软件在数据传输之前先进行重复数据的删除。基本上客户端首先把数据分成块，然后传给备份软件，由备份软件来比较是否已经有相同的块。如果已经有相同的块，备份软件则增加一个指向已有数据块的索引。基于源数据的重复数据删除很大程度上降低了传输数据所使用的网络带宽，虽然增加了客户端和备份软件之间的通信。而且，由于重复数据删除由备份软件来完成，因此不需要额外的软件支持。但是，为了使用重复数据删除，你不得不放弃当前的备份工具而是用专门的支持重复数据删除的备份软件。直到现在，重复数据删除看上去很简单。的确，基本概念非常容易理解。但是，还有很多细节没有被提及。对于重复数据删除这项技术来说需要很多部件被开发，集成，和可靠性测试（毕竟，这关系到你的数据）。重复数据删除技术的公司的主要区别就在于这些实现。比如，重复数据删除技术的实现是基于源数据的还是基于目标数据的？承担重复数据删除工作的部件或软件的特性有何不同？重复数据删除在数据哪一层次上实现？数据块如何与已有数据数据进行比较的？等等。
在深入讨论重复数据删除的具体部署之前，先让我们来谈一下重复数据删除的算法。前面已经提到，重复数据删除可以实现在文件层次上，也可以实现在块层次上（块的定义依赖于具体的实现），甚至实现在位层次上。如果只是简单地把整个数据块与已有的数据进行比较并生成索引的话，效率非常低。为了提高效率，重复数据删除通常利用如MD5,SHA-1等算法对每个数据块生成唯一的一个Hash值。从而可以利用这个Hash值与存储在索引中的已有数据块的Hash值进行比较。但是，使用这些Hash算法的一个潜在问题，就是Hash值冲突。Hash值冲突类似错误的肯定。也就是说，两个不同的数据块产生出相同的Hash值。因而，由于数据块的Hash值已经存在于已有数据的索引中，因此该数据块可能不被备份，虽然事实上数据没有被存储。显然，由于本应该备份的数据没有被备份，会导致数据的损坏。对于这一点，重复数据删除公司一般都采用几种Hash算法或它们的组合，来确保只有真的是重复的数据才不会被再存储。另外，也有厂商使用元数据来辅助确认以防止出现Hash值冲突。详细解释这种Hash值冲突的发生概率需要一点数学知识。基本结论是Hash值冲突的发生概率是1/2^160.这是个非常非常非常小的概率。换句话说，如果你有95EB的数据（1EB=1000PB），你会有0.00000000000001110223024625156540423631668090820313%的机会发生Hash值冲突，导致你扔掉了本应该保存的数据。即使你有95EB的数据在给定的时间内几乎不可能发生。但是，永远不要说永远不。（毕竟，有人曾预言我们只需要640KB的内存。）
CDC(content-defined chunking)算法是一种变长分块算法，它应用数据指纹(如Rabin指纹)将文件分割成长度大小不等的分块策略。与定长分块算法不同，它是基于文件内容进行数据块切分的，因此数据块大小是可变化的。算法执行过程中，CDC使用一个固定大小(如48字节)的滑动窗口对文件数据计算数据指纹。如果指纹满足某个条件，如当它的值模特定的整数等于预先设定的数时，则把窗口位置作为块的边界。CDC算法可能会出现病态现象，即指纹条件不能满足，块边界不能确定，导致数据块过大。实现中可以对数据块的大小进行限定，设定上下限，解决这种问题。CDC算法对文件内容变化不敏感，插入或删除数据只会影响到检少的数据块，其余数据块不受影响。CDC算法也是有缺陷的，数据块大小的确定比较困难，粒度太细则开销太大，粒度过粗则dedup效果不佳。如何两者之间权衡折衷，这是一个难点。
Dedupe按照消重的粒度可以分为文件级和数据块级。文件级的dedupe技术也称为单一实例存储(SIS, Single Instance Store)，数据块级的重复数据删除其消重粒度更小，可以达到4-24KB之间。显然，数据块级的可以提供更高的数据消重率，因此目前主流的dedupe产品都是数据块级的。数据分块算法主要有三种，即定长切分(fixed-size partition)、CDC切分(content-defined chunking)和滑动块(sliding block)切分。定长分块算法采用预先义好的块大小对文件进行切分，并进行弱校验值和md5强校验值。弱校验值主要是为了提升差异编码的性能，先计算弱校验值并进行hash查找，如果发现则计算md5强校验值并作进一步hash查找。由于弱校验值计算量要比md5小很多，因此可以有效提高编码性能。定长分块算法的优点是简单、性能高，但它对数据插入和删除非常敏感，处理十分低效，不能根据内容变化作调整和优化。
滑动块(sliding block)算法结合了定长切分和CDC切分的优点，块大小固定。它对定长数据块先计算弱校验值，如果匹配则再计算md5强校验值，两者都匹配则认为是一个数据块边界。该数据块前面的数据碎片也是一个数据块，它是不定长的。如果滑动窗口移过一个块大小的距离仍无法匹配，则也认定为一个数据块边界。滑动块算法对插入和删除问题处理非常高效，并且能够检测到比CDC更多的冗余数据，它的不足是容易产生数据碎片。
指纹计算。数据指纹是数据块的本质特征，理想状态是每个唯一数据块具有唯一的数据指纹，不同的数据块具有不同的数据指纹。数据块本身往往较大，因此数据指纹的目标是期望以较小的数据表示(如16、32、64、128字节)来区别不同数据块。数据指纹通常是对数据块内容进行相关数学运算获得，从当前研究成果来看Hash函数比较接近与理想目标，比如MD5、SHA1、SHA-256、SHA-512、为one-Way、RabinHash等。另外，还有许多字符串Hash函数也可以用来计算数据块指纹。然而，遗憾的是这些指纹函数都存在碰撞问题，即不同数据块可能会产生相同的数据指纹。相对来说，MD5和SHA系列HASH函数具有非常低的碰撞发生概率，因此通常被采用作为指纹计算方法。其中，MD5和SHA1是128位的，SHA-X(X表示位数)具有更低的碰撞发生概率，但同时计算量也会大大增加。实际应用中，需要在性能和数据安全性方面作权衡。另外，还可以同时使用多种Hash算法来为数据块计算指纹。
实现要点
研发或应用Dedupe技术时应该考虑各种因素，因为这些因素会直接影响其性能和效果。
(1) What：对何种数据进行消重？
对时间数据还是空间数据进行消重，对全局数据还是局部数据进行消重？这是首先需要考虑的因素，这直接决定着Dedupe实现技术和数据消重率。随时间变化的数据，如周期性的备份、归档数据，比空间数据具有更高的消重率，Dedupe技术在备份归档领域中被广泛应用。不难想象，全局范围内的数据重复率比局部范围数据要高，会获得更高的数据消重率。
(2) When：何时进行消重？
数据消重时机分为两种情形：在线消重和离线消重。采用在线消重模式，数据写入存储系统同时执行消重，因此实际传输或写入的数据量较少，适合通过LAN或WAN进行数据处理的存储系统，如网络备份归档和异地容灾系统。由于它需要实时进行文件切分、数据指纹计算、Hash查找，对系统资料消耗大。离线消重模式，先将数据写入存储系统，然后利用适当的时间再进行消重处理。这种模式与前面一种刚好相反，它对系统资料消耗少，但写入了包含重复的数据，需要更多的额外存储空间来预先存储消重前数据。这种模式适合直连存储DAS和存储区域网络SAN存储架构，数据传输不占用网络带宽。另外，离线消重模式需要保证有足够的时间窗口来进行数据去重操作。总之，在何时进行消重，要根据实际存储应用场景来确定。
(3) Where：在何处进行消重？
数据消重可以在源端(Source)或者目标端(Target)进行。源端消重在数据源进行，传输的是已经消重后的数据，能够节省网络带宽，但会占用大量源端系统资源。目标端消重发生在目标端，数据在传输到目标端再进行消重，它不会占用源端系统资源，但占用大量网络带宽。目标端消重的优势在于它对应用程序透明，并具有良好的互操作性，不需要使用专门的API，现有应用软件不用作任何修改即可直接应用。
(4) How：如何进行消重？
重复数据删除技术包含许多技术实现细节，包括文件如何进行切分？数据块指纹如何计算？如何进行数据块检索？采用相同数据检测还是采用相似数据检测和差异编码技术？数据内容是否可以感知，是否需要对内容进行解析？这些都是Dedupe具体实现息息相关。本文主要研究相同数据检测技术，基于二进制文件进行消重处理，具有更广泛的适用性。
解决方案的选择是一种艺术，需要结合你的实际运用环境和运用过程来考虑。上面提到的视频里面介绍了基于基于源数据的重复删除和基于目的数的重复删除的基本差异而提出的一些基本准则。基于源数据的重复删除适用于网络带宽资源紧张的场合：比如，共享文件系统的备份（并非把整文件系统的数据重新备份），vmware存储，分支机构间（这种情况下可使用的网络带宽异常受限）。但是不要忘记：为了使用基于源数据的重复删除，你必须从现有的数据备份软件转换到支持重复数据删除的备份软件。而基于目的数据的重复删除则非常适用于SAN,LAN,数据库的场合。这是因为在LAN,SAN网络内移动数据非常容易，你也可以继续使用已有的备份程序或软件。
最后视频里说基于源数据的重复数据删除可以达到50：1的重复排除率，而基于目的数据的重复删除则只能达到20：1的重复删除率。两种技术的重复数据删除率的效果都很显著。而且，有很多讨论如何估计你能达到的最大重复数据删除率的文章。应该说20：1的压缩率是可以预见的。市场上已经有很多重复数据删除的产品。本文中的列表虽然不完全叶很难说没有一丝倾向性。但我还是给出一个提供重复数据删除产品的公司列表：
Exagrid
NEC HydraStor
Symantec Netbackup Puredisk
Data Domain (owned by EMC)
FalconStor
EMC Avamar
Sepaton
Commvault
Netapp （可以在他们公司的产品中使用重复数据删除）
Quantum
这些公司都会提供重复数据删除的解决方案。同时，也有一些中小公司提供重复数据删除的产品。
重复数据删除和开源
在开源世界里目前还没有几个（一个也没有？）重复数据删除的开源项目。但如果你使用基于目的数据的重复数据删除，因为你可以使用已有的备软件，而这个备份软件有可能是开源的。但是，还是建议你在使用之前先跟提供商确认他们是否在linux上做过测试。目前被发现的唯一的开源项目叫做LessFS.它是一个内建支持重复数据删除的FUSE文件系统。它仍让在开发初期，虽然已经展示了它的重复数据删除能力和内建的加密。
数据安全
这里的数据安全包含两个层面的含义：一是数据块碰撞，二是数据可用性。这两种安全性对用户来说都是至关重要的，必须事先考虑。
数据块指纹FP(FingerPrinter)通常使用Hash函数来计算获得，如MD5、SHA1、SHA-256、SHA-512等。从纯数学角度看，如果两个数据块指纹不同，则这两个数据块肯定不同。然而，如果两个数据块指纹相同，我们则不能断定这两个数据块是相同的。因为Hash函数会产生碰撞，山东大学的王小云教授所带领的团队已经找到快速产生碰撞的方法。但是，这种碰撞的概率是非常非常小的，小到甚至低于磁盘发生损坏的概率，因此通常近似认为：如果数据块指纹相同，则数据块相同。由于数据产生碰撞可能性的存在，Dedupe技术很少被用于关键数据存储的应用场合，一旦发生碰撞将产生巨大的经济损失。针对这种问题，目前主要有两种解决路径：
一是对数据指纹相同的块进行字节级完全比较，它的难点在于数据块原始数据有时难以方便获得，另外性能会产生一定损失。
二是最大可能降低碰撞产生的概率，即采用更优的Hash函数（如SHA-512, SHA-1024），或者采用两种以上hash算法组合方式，这显然会对性能造成影响。本人在”数据同步算法研究”中采用的是该种方法，为每个数据块计算两个指纹，一个类似Rsync算法中的弱校验值（Rsync滚动校验算法）和一个强校验值MD5。弱校验值计算消耗远小于MD5计算量，先计算目标数据块的弱校验值，如果与源数据块不同则不必再计算其MD5校验值，相同则计算MD5并作比较。这种方式以较小的性能代价极大地降低了碰撞产生的概率，而且通过优化，性能损失无几。
#p#分页标题#e#
Dedupe仅保存唯一的数据副本，如果该副本发生损坏将造成所有相关数据文件不可访问，数据可用性压力要高于不作Dedupe许多。数据可用性问题可以采用传统数据保护方法来解决，常用的方式包括数据冗余(RAID1,RAID5, RAID6)、本地备份与复制、远程备份与复制、纠错数据编码技术(如海明码、信息分散算法IDA)、分布式存储技术。这些技术均可以有效消除单点故障，从而提高数据可用性。当然，这需要付出一定代价，以空间换取安全性。
小结
这只是关于重复数据删除的简单介绍。而重复数据删除是现在存储业界最热门的技术。它承诺由于能够减少备份数据所需要的物理空间和传输数据所需要的带宽，因而可以为企业或组织节约IT花费。本文只是蜻蜓点水式的介绍了重复数据删除和它是否适用于你的IT环境。请多看看其他的文章–有很多关于重复数据删除的天花乱坠般的宣传。你需要就对你是否有用来做出自己的判断。如果你想试试开源项目，那么很不幸，并没有多少开源项目可供你选择。我唯一发现的就是集成了重复数据删除功能的基于FUSE的文件系统项目 — LessFS。它值得你去调查一下，虽然它也许只能用于你的二级存储。
今天的分享就到这了，也不知道对大家有用不，如果有用的话，那就点个赞吧！如果哪部分知识点欠缺，欢迎各位朋友进行补充哦~更多精彩的内容，就在课课家教育，还不赶紧行动？等着你们哟~
