概述
数据去重（Data Deduplication，也称为数据重删），作为一种高效的数据减少方法，由于数字数据的爆炸式增长，在大规模存储系统中越来越受到关注和青睐。它通过在文件或子文件级别消除冗余数据，并通过其具有密码学安全哈希签名（即抗碰撞指纹）来识别重复内容，这在大规模存储系统中被证明比传统的压缩方法更具计算效率。
介绍
图1显示了数据去重的一般工作流程。
- Chunking & fingerprinting：首先，文件被分成相等或类似大小的块（Chunk），每个块通过计算出一个指纹（fingerprint）来唯一表示。每个文件被切割成不同的块之后，内容相同的块（指纹也相同）就可以被复用，从而后端存储的时候，只需要针对不同的块进行存储。例如 FileA 和 File B 包含相同的块（指纹为 5d），存储的时候，5d 所代表的数据块，只存储1次，而不是2次。
- Indexing：Indexing 要解决的问题是对大量指纹的高效索引，例如如何快速判断一个指纹，在后端是否已经存在，从而判断是否要存储对应的数据块。
- Storing：最后是数据块的存储。这一部分同样面临多种挑战，例如不同场景下对后端存储的选型，存储后的数据块，如何在恢复的时候，被高效读取等。
文章整体结构：
论文主要贡献有三个方面：
- 我们研究了数据去重的背景和方法论。通过审视数据去重与传统压缩方法之间的主要差异，我们呈现了数据去重的关键特点和优势。
- 我们对数据去重工作流的每个阶段的最新状况进行了研究和分类，包括块处理方法、加速块处理的计算、指纹的索引、增量压缩、数据恢复、垃圾收集、安全性和可靠性等方面。基于对现有方法的深入阶段性研究，我们提出了一份详细的最新数据去重技术分类表，为基于去重的存储系统的重要设计问题提供了有用的见解。
- 我们讨论了数据去重的主要应用和行业趋势；提供了一系列针对数据去重研究社区的公开可用的开源项目、数据集和追踪信息；并概述了数据去重研究面临的未解问题和挑战。
冗余数据减少相关的技术
为了减少数据中的冗余数据，有3大方向：
- Lossless data compression
- Lossy Data Compression
- Intelligent Data Compression
总结如下：
可以看出，数据重删是冗余数据减少的手段之一，其它的手段包括各种数据压缩。
数据重删关键流程
数据分片（Chunking of Data Stream）
首先我们需要将文件分割成大小相同（Fixed）或大小不同的块（Chunk），这一过程称为 Chunking。通常使用的是CDC（Content-Defined Chunking）算法。
CDC 算法：在文件内容上使用滑动窗口技术，并计算窗口的哈希值（例如，使用 Rabin指纹），如果该滑动窗口的哈希值满足某些预定义条件，则基于当前的窗口的位点（个人理解是窗口的结束位点），确定一个块断点。因此，对于在文件V1的块C2上修改的文件V2，CDC算法仍然可以识别未被修改内容的块C3和C4的正确边界。
Rabin 算法：
给定一个字节序列： {B1, B2, …, Bα}，其 Babin 指纹为：
where D is the average chunk size and α is the number of bytes in the sliding window.
Rabin 比较方便计算，因为相同长度的一个滑动窗口下，后一个窗口的哈希值，可以由前一个窗口的哈希值计算而来，不需要完整的再算一遍：
Table III总结了面向CDC的数据去重的最新方法，这些方法解决了基于Rabin的CDC存在的三个不足之处，以下将进行详细阐述。
基于 Rabin 的 CDC 算法，有3个主要的优化方向：
- Reducing Chunk Size Variance by Imposing Limits on MAX/MIN Chunk Sizes for CDC.
- Reducing Computation to Accelerate the Chunking Process.
- Improving Duplicate-Detection Accuracy by Re-chunking Non-duplicate Chunks.yfAcceleration of Computational Tasks
计算任务加速（Acceleration of Computational Tasks）
数据去重是一个计算密集型的过程，包含两个耗时的计算任务，基于CDC的分块和基于安全哈希的指纹生成。前者通过CDC将数据流分成几个块，后者为每个块计算一个加密摘要（即指纹），以唯一表示它用于重复检测。因此，去重过程中的分块和指纹生成阶段需要计算哈希值（例如Rabin和SHA1），这可能会延长基于去重的存储系统的写入延迟，尤其是在使用基于闪存设备的高性能主存储系统中，由于内存处理能力的增加。
总之，在具有多核/多核处理器的计算机系统中，可以通过流水线化去重任务和并行分块和指纹生成来轻松实现基于多线程的解决方案。基于GPGPU的解决方案可以提供更高的吞吐量，但需要额外的硬件成本。另一种方法是将分块卸载到客户端，这不会影响计算任务的速度，但允许备份系统扩展到额外的客户端（相当于增加更多的客户端）。
指纹索引（Indexing of Fingerprints）
在对数据流进行分块和指纹生成后，分块指纹被索引以帮助确定重复和非重复的数据块，这是去重过程中的关键阶段。早期的去重系统将整个分块指纹索引存储在内存中，以便快速识别重复数据。随着数据量的爆炸性增长，指纹总数及其索引的大小呈指数级增长，很快就会超出去重系统的RAM容量。因此，对于大规模数据去重系统，需要一个高效的指纹索引方案。
目前，加速索引查找（index-lookup）过程并缓解磁盘瓶颈的方法通常可分为四类，即基于局部性（locality-based）、基于相似性（similarity-based）、闪存辅助（flash-assisted）和集群去重（cluster deduplication)。表V列出了这四类指纹索引的最新方法。
基于局部性的方法。在数据去重的背景下，局部性指的是这样一个观察：在多次完整备份中，类似或相同的文件（如A、B和C，以及它们的数据块）以非常高的概率大致以相同顺序出现。利用这种局部性来进行去重索引会增加RAM利用率，并减少对磁盘索引的访问，从而缓解磁盘瓶颈。
图6显示了基于局部性的方法的一个示例，即DDFS。这个著名的去重系统充分利用这种局部性特性，通过以备份流的顺序（例如文件A的数据块的指纹{3b, a7, 2f, 5c}）在磁盘上进行存储。当查找文件C的指纹“3b”的时候，DDFS将预取指纹{3b, a7, 2f, 5c} 并将这种局部性保留在RAM中，有助于在以后查找“a7”和“2f”的指纹时减少对磁盘索引的访问。通常，DDFS将非重复的数据块存储在称为容器的几个大型固定大小的存储单元中，以保持备份流的局部性。DDFS还使用Bloom过滤器来快速识别新的（即非重复的）数据块，避免对已知不存在的块进行索引查找；这有助于弥补没有或很少出现局部性的情况。Bloom过滤器是一种空间高效的数据结构，它使用具有多个独立哈希函数的位数组来表示一组项目（例如指纹）的成员资格。
基于相似性的方法。在去重上下文中，相似性指的是文件或数据流与先前类似文件或数据流的相似特征。常见的相似性检测技术是使用数据块指纹集合的最大值或最小值来表示文件。因此，选择的指纹可用于构建主索引，并最小化去重索引的RAM开销，特别是对于没有或很少局部性的数据集。
例如图7显示了极端分块如何利用文件相似性的示例，其中两组块指纹 {3b, a7, 2f, 5c} 和 {3b, a7, 2f, 9d} 分别属于文件 A 和 C。这里文件相似性由哈希集合中文件的最小指纹表示，其前缀位表示其中所有指纹中相同前缀位的最小值。因此，在检测到文件 C 的最小指纹“2f”与文件 A 的相同时，我们可以认为这两个文件是相似的，然后检测文件 A 和 C 之间的重复块，从而避免对文件 C 的块指纹进行全局索引。
Flash-assisted approaches. 由于磁盘指纹的查找吞吐量受到昂贵的磁盘寻道操作的限制（大约100 IOPS），因此提出了将随机访问闪存作为替代磁盘的选择，以提供高吞吐量的I/O操作（约100,000 IOPS）用于指纹索引。针对闪存指纹的内存高效和高性能主索引设计，称为键值存储，进一步被利用于这些基于闪存辅助的去重索引方法。
集群去重（cluster deduplication)。前述方法中，大多数方法都是在单个节点上消除重复项，这限制了数据去重的吞吐量和可扩展性。这一限制促成了由多个节点组成的集群去重系统的发展。集群去重的基本思想是通过支持节点间负载平衡并实现各个节点内独立去重的数据路由方案，将备份客户端的数据流分配给多个去重节点。
去重后压缩（Post-Deduplication Compression）
数据去重在存储系统中被广泛应用以节省空间。在实践中，基于指纹的去重方法未能识别大量冗余。每个块通常都具有内部冗余，可以使用传统的压缩器（如LZ）来消除。如果将添加到系统中的唯一块在更大的“压缩区域”中一起进行压缩，则总体压缩率将高于单独压缩每个块。例如，DDFS报告典型的2×压缩。
除了去重后块的简单可压缩性外，相似块之间可能存在高度重叠，这些块只包含少量不同的字节，例如图5中的块C2和C5。即使存在几个不同的字节，这些块的基于安全哈希的指纹也会完全不同 [8, 11, 68]。正如第III-A节所讨论的，重新分块方法旨在通过进一步将非重复块细分为更小的块来增加去重比例，从而有助于识别更多的冗余。相比之下，去重后的增量压缩消除了非重复但相似块之间的冗余，而无需重新分块操作即可实现更高的冗余消除比率 。因此，它被认为是一种有效的去重后处理过程，可以进一步消除数据冗余，但会增加额外的计算、索引和I/O开销，因此是一个可选的去重后存储管理阶段（见图4）。
数据恢复（Data Restore）
在识别重复数据并存储非重复数据后，高效地恢复数据并有效地管理碎片化的存储空间（在用户删除操作后）是非常重要的。后者的过程被称为垃圾收集。因此，数据恢复和垃圾收集已经成为数据去重系统存储管理阶段的两个重要问题。本小节主要回顾了数据恢复的最新方案，垃圾收集问题将在下一小节中详细讨论。
图8显示了基于去重的备份存储系统中数据碎片化的一个例子。在去重后，每个备份（例如，第3个备份）中的逻辑连续的块在几个数据容器（固定大小的存储单元）中被物理地分散，这也被称为块碎片化，而不是以传统方式紧凑连续地排列。由于HDD的随机I/O性能较差，块碎片化（如磁盘碎片化）显著降低了恢复性能。此外，块碎片化也影响了垃圾收集的性能。例如，如果用户在图8中删除第1个备份，由于第2个和第3个备份引用了第1个备份中的一些数据块，因此很难回收第1个备份中的数据块的存储空间。
一些数据恢复方案将去重后的碎片块进行重写（rewrite），以减轻读（恢复）性能的降低，从而权衡了去重比（容量节省）和读（恢复）性能。表VII全面研究了去重系统中改善恢复性能的最新技术，并根据去重部署的存储环境（即，主存储、备份存储和云存储）将其分类为三类。
主存储系统对I/O延迟敏感，这使得去重引起的、读延迟延长的碎片化问题非常重要。iDedup利用主存储工作负载的空间局部性，选择性地去重顺序重复的磁盘块，以减少碎片化并摊销由随机I/O引起的读延迟。性能导向的I/O去重（POD）通过识别在关键I/O路径中对容量不敏感但对性能敏感的小重复写和文件，进一步改善了基于去重的主存储系统的读性能。
对于基于去重的备份存储，由于块碎片化问题，最近备份的恢复速度可能会随着备份系统的寿命而减少数个数量级。Nam等人建议使用一个称为块碎片化级别（CFL）的定量指标，选择性地消除顺序和重复的块，这与iDedup类似。基于上下文的重写（CBR）和Capping算法使用它们的特定碎片化指标确定写缓冲区（例如，10∼20MB）中的碎片化块，然后选择性地写入碎片化块以改善恢复速度。此外，Capping使用前向组装技术，通过利用恢复已知备份时可用的未来块访问的完全知识，有效地缓存块。
对于基于去重的云存储，由于WAN的相对低带宽或者对云服务器中碎片化块的频繁访问，恢复速度可能会受到严重限制。SSD辅助恢复（SAR）在SSD 上存储具有高引用计数的唯一块，以改善恢复性能，这利用了SSD的良好的随机读性能特性。
总的来说，去重系统中的块碎片化问题导致了数据恢复性能的降低。最新的方案在去重中权衡了容量节省和性能惩罚，达到了适当的折衷。我们相信，高效和准确的碎片化整理可以显著减轻基于去重的存储系统中恢复性能的数量级性能下降。
Garbage Collection
这个小节讨论了基于重复数据删除的存储系统中垃圾收集（GC）的最新方法。由于唯一的数据块可能被多个文件共享，因此引用管理对于跟踪数据块的使用以及回收已释放空间（即GC）至关重要。一般来说，GC 包括两个关键步骤，找到无效的数据块，然后回收它们的存储空间。根据第一个步骤，即引用计数和标记-清除，GC 方法通常可以分为两类。
- Reference count approach and its variants. 基于引用计数及其种
- 在去重系统中，特定数据块的引用计数指的是该数据块被使用/引用的次数。例如，引用计数为N表示该数据块被引用了N次（在1-N个文件中），而引用计数为0意味着由于用户的删除操作，该数据块不再共享，并且可以被回收进行垃圾收集。然而，为每个数据块准确构建引用计数器会导致空间效率低下。此外，引用计数可能存在可靠性较低的问题：当发生错误时，一些数据块可能会被更新，而另一些则不会。
- Mark-and-sweep approach and its variants. 标记-清除方法及其变体
- 标记-清除是另一种由两个阶段组成的GC解决方案。在标记阶段，需要遍历所有文件以标记已使用的数据块。在清除阶段，需要扫描所有数据块，并回收未被标记的数据块。分组标记-清除（GMS）生成位图来标记每个备份引用的每个容器中的有效数据块（即如图8所示的一组数据块），并通过合并所有容器的位图来定位和回收所有无效数据块占用的存储空间。Botelho等人构建了一个完美哈希向量作为所有数据块的紧凑表示，然后遍历所有文件配方以回收无效数据块的存储空间。
总之，重复数据删除系统中的GC问题是由于在去重后文件/备份之间共享数据块而引起的。高效的数据块引用管理对于GC在去重系统中识别无效数据块并回收其存储空间至关重要。参考计数解决方案及其某些变体支持内联GC，而标记-清除及其变体则天生是离线的。需要注意的是，在基于去重的备份系统中，通常在一个或多个完整备份被删除后才执行GC作为后台进程，但在主存储系统中，GC通常是内联的或部分内联的。一般来说，现有的GC方法之间存在权衡。具体而言，即时GC会增加关键I/O路径的延迟，而延迟GC则会降低基于去重存储系统的空间利用率。
参考资料
《A Comprehensive Study of the Past, Present, and Future of Data Deduplication》 **
