重复数据删除

一：数据重删技术概述

1.源端去重 && 宿端去重

源端去重(Source Deduplication)首先在客户端计算待传输数据的指纹并通过与服务端进行指纹比对发现和消除重复内容,然后仅向服务端发送非重复数据内容 , 从而达到同时节约网络带宽和存储资源的目标。
宿端去重( Destination Deduplication)直接将客户端的数据传输到服务端,并在服务端内部检测和消除重复内容。两种部署方式都能够提高存储空间效率,其主要区别在于源端去重通过消耗客户端计算资源换取网络传输效率的提升。
也不见得在源端去重能够节省多大的网络开销啊～毕竟首先得与宿端进行通信，源端去重会将重删过程划分成好几个阶段。

2.当前去重方法突破性能瓶颈的主要技术手段包括(1)构造内存快速索引(布隆过滤器)、挖掘数据局部性(缓存)、利用数据相似性(extreme binning)和使用新型存储介质(chunkstash)。

3.重复数据删除技术主要分为两类:
(1)相同数据的检测技术和
相同数据主要包括相同文件及相同数据块两个层次. 完全文件检测(whole file detection,简称WFD)技术主要通过 hash 技术进行数据挖掘; 细粒度的相同数据块主要通过固定分块(fixed-sized partition,简称FSP)检测技术、可变分块(content-defined chunking, 简称CDC)检测技术、滑动块(sliding block)技术进行重复数据的查找与删除.
(2)相似数据的检测与编码技术
利用数据自身的相似性特点, 通过shingle 技术、bloom filter 技术和模式匹配技术挖掘出相同数据检测技术不能识别的重复数据; 对相似数据采用delta 技术进行编码并最小化压缩相似数据, 以进一步缩减存储空间和网络带宽的占用.


4.重删对数据可靠性的影响：

上述这些技术使得共享数据块的文件之间产生了依赖性, 几个关键数据块的丢失或错误可能导致多个文件的丢失和错误发生, 因此它同时又会降低存储系统的可靠性, 为此, 一些研究者又引入了冗余复制技术和纠删码技术等来提高重复数据删除系统的可靠性.

二：五种重复数据删除技术

如今，经验丰富的IT人员都已经了解了重复数据删除的重要性，也深知当前市场上可以选择的重复数据删除方案各有利弊。无论厂商怎样美化自己的产品，能够自由的根据自己不断变化的独特需求而自由定制的重复数据删除处理，对于用户来说，绝对是具有非常重要的意义。本文，将对各种重复数据删除处理方式进行一一介绍。需要提请读者注意的是：我们这里介绍的去重方案，都是可以应用于业务系统的，从而使IT员工能够针对其管理的众多数据类型轻松的进行调节。

1.Inline重复数据删除
其主要优点是能够最大程度地降低存储需求，最多可达40%。这种处理方式非常适合需要即时复制的小型存储配置或环境。为了获得最高的性能水平，推荐的最佳做法是使用灵活的重复数据删除策略，在初始备份时采用后处理重复数据删除(post-process deduplication)，以便提高速度，而后续的备份操作则切换到inline重复数据删除。

2.后处理(Post-process)重复数据删除
如果用户希望尽快完成备份，后处理的重复数据方式则是最为理想的选择。顾名思义，它是在备份过程完成后进行的，因而可在任何时间运行。

3.并发(Concurrent)重复数据删除
这种去重的运行方式与后处理重复数据删除相似，只不过它是在写入第一组记录时立即启动，并与备份同时运行。重复数据删除引擎会立即启动，充分利用所有可用的CPU资源，因而非常适合集群化的 VTL 环境。由于复制启动的非常快，因此数据能够快速地从远程站点进行恢复。

4.FalconStor Turbo 重复数据删除
这是飞康公司提供的一种非常独特的混合去重的方法，是从VTL本身而非重复数据删除引擎进行inline重复数据删除处理，从而提高后处理重复数据删除或并发重复数据删除的性能。FalconStor Turbo重复数据删除最适合CPU处理能力强劲的企业级环境或集群化环境，这种环境有足够的CPU处理能力进行inline预处理。 FalconStor Turbo 重复数据删除可以有效的减少重复数据删除的I/O需求，后处理和并发处理时的性能提升可以达到300%。

5.无重复数据删除
适用于重复数据删除效率不佳的数据，或者需要导出到物理磁带的数据，例如影像文件，以及预先经过压缩和加密的数据。这时，用户可以通过选择性地“关闭”重复数据删除功能，从而节省重复数据删除周期，而专注于为可以获得更高去重比率和价值的数据执行重复数据删除。


生活中常常会出现众口难调的情况，存储管理和重复数据删除更是如此。您也许还在担心，这么多种重复数据删除方式我如何选择，哪个才是最适合自己的?其实，您只要选择同时具备多种重复数据删除选项的产品，如近来市场中最新发布的FalconStor VTL v7.5解决方案，这一疑问即可迎刃而解!根据自己的切实需求，根据需要自由选择去重方式，随时调整最佳去重方案，用户将不会再被某一种类型的重复数据删除技术所局限，真正体会到灵活性的优势。

三：企业重删应用问题十大解疑

几年前，重复数据删除是一个独立的功能，是企业存储系统的一个选项，主要集中在备份和归档部分。随后，它在云网关中找到新用途，在进入阵列或者虚拟磁带库之前删除了不必要的数据块。现在，随着统一计算系统采用常见的预集成功能，人们需要关注如何最有效地利用这些技术。
1.重复删除技术对备份性能有什么影响?
对于需要快速增长的大型企业来说，高性能是很必要的，并在有限的备份窗口内，确保大规模数据量备份环境的安全。了解每个重复数据删除技术的性能差异，(特别是随着时间的变化)是特定环境选取最合适的技术的关键。

2.重复数据删除会降低恢复性能吗?
了解恢复备份(恢复请求最常见的类别)上周文件所需要的时间。询问供应商是否他们的技术能够保存前次用于即时恢复和快速磁带的备份。

3.随着环境的增长，容量和性能扩展怎么样?
通过特定的重复删除比率，数据类型和增长率，计算在单一的重复数据删除系统中能够存储多少数据。了解超额容量的含义。例如，如果超额容量需要你通过额外的系统传播备份，你必须要考虑额外管理的复杂性成本、资本开支和对环境的破坏。

4.针对大型数据仓库的重复数据删除效率怎么样?
确保您的重复数据删除IT是处理子8KB数据比较是最优化的，同时维持性能水平。大型的，关键的数据库，例如Oracle，SAP, SQL服务器和DB2通常更改8KB段的数据或者更少的数据。然而，许多数据重复删除功能不能提供少于16KB段的数据比较，没有明显地降低备份过程。

5.渐进的增量备份环境中重复数据删除效率怎么样?
有些重复数据删除技术软件包在重复数据删除TSM渐进的增量备份中和将数据分成碎片的应用程序中备份效率较低，例如NetWorker和HP数据保护。询问供应商是否重复数据删除技术能够使用来自备份应用程序的元数据，来确认可能包括重复删除数据的数据域，以便于他们执行字节级的数据比较实现最优化容量的减少，同时保持高性能。

6.对于容量减少，切实的期望是什么?
比起争取更高的重复删除技术比率，大型企业更有效的策略是选择确保将数据移动到备份窗口内安全的地方，同时提供高效的重复数据删除。并行处理、确定的接收速率、重复数据删除和复制是企业环境的关键因素。

7.管理员可以监视企业范围内的备份，重复数据删除，复制和恢复吗?
数据保护环境的整体视图使备份管理员管理更多数据，调整备份环境达到最佳利用率和效率，并为企业未来的性能和容量要求精确地计划。

8.重复数据删除技术可以帮助减少大型企业数据卷的复制带宽需求吗?
有些重复删除技术使企业通过WAN复制数据。只复制字节级的改变，减少WAN带宽需求和提高安全时间，实现高效复制。

9.IT是否能调整重复删除技术以满足需求?
企业数据保护环境可能有特殊的重复删除技术要求的数据类型。寻找解决方案，使IT能够选择他们想要的重复数据删除，通过备份政策，数据类型和那些自动检测被备份和执行的数据类型。选择技术使IT能够应用针对每个数据类型都最有效的重复数据删除方法。

10.实施过大型企业备份环境的供应商有多少经验?
有大规模数据卷和复杂策略的企业数据中心，需要一个专业的企业级备份应用程序的数据保护供应商，例如NetBackup、NetBackup OST和Tivoli存储经理人。他们应该提供数据评估和指导，对于在这些环境中优化需要最大量备份的整体备份基础设施，复制和数据重复删除性能。

附1：布隆过滤器简介

1.算法描述
一个empty bloom filter是一个有m bits的bit array，每一个bit位都初始化为0。并且定义有k个不同的hash function，每个都以uniform random distribution将元素hash到m个不同位置中的一个。在下面的介绍中n为元素数，m为布隆过滤器或哈希表的slot数，k为布隆过滤器重hash function数。

为了add一个元素，用k个hash function将它hash得到bloom filter中k个bit位，将这k个bit位置1。
为了query一个元素，即判断它是否在集合中，用k个hash function将它hash得到k个bit位。若这k bits全为1，则此元素在集合中；若其中任一位不为1，则此元素比不在集合中（因为如果在，则在add时已经把对应的k个bits位置为1）。
不允许remove元素，因为那样的话会把相应的k个bits位置为0，而其中很有可能有其他元素对应的位。因此remove会引入false negative，这是绝对不被允许的。

当k很大时，设计k个独立的hash function是不现实并且困难的。对于一个输出范围很大的hash function（例如MD5产生的128 bits数），如果不同bit位的相关性很小，则可把此输出分割为k份。或者可将k个不同的初始值（例如0,1,2, … ,k-1）结合元素，feed给一个hash function从而产生k个不同的数。
当add的元素过多时，即n/m过大时（n是元素数，m是bloom filter的bits数），会导致false positive过高，此时就需要重新组建filter，但这种情况相对少见。


2.时间和空间上的优势
当可以承受一些误报时，布隆过滤器比其它表示集合的数据结构有着很大的空间优势。例如binary_search_tree, tries, hash table或者array, chain，它们中大多数至少都要存储元素本身，对于小整数需要少量的bits，对于字符串则需要任意多的bits（tries是个例外，因为对于有相同prefixes的元素可以共享存储空间）；而chain结构还需要为存储指针付出额外的代价。对于一个有1%误报率和一个最优k值的布隆过滤器来说，无论元素的类型及大小，每个元素只需要9.6 bits来存储。这个优点一部分继承自array的紧凑性，一部分来源于它的概率性。如果你认为1%的误报率太高，那么对每个元素每增加4.8 bits，我们就可将误报率降低为原来的1/10。add和query的时间复杂度都为O(k)，与集合中元素的多少无关，这是其他数据结构都不能完成的。

附2：trie树简介

Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。它有3个基本特性：
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。