重删基础

数据去重

数据去重是一种在存储系统中对数据进行无损压缩的方法

工作过程

如上图所示，

1. 首先对文件进行分块(可使用FCS, CDC)，分块(data chunks)之后求取数据块的指纹(fingerprint, 即数据块内容的哈希值)
2. 根据数据块的哈希值构建指纹索引，并存储索引(index)，索引、指纹等统称为元数据信息(metadata)
3. 根据指纹索引找到指纹进行比较，若已经存在则不写入，只写入唯一块(unique chunks)

优点

• 减少备份所需的存储空间
• 最小化冗余数据的网络传输

FCS

FCS 即Fixed-Sized Chunking，固定大小的分块

固定大小的分块：根据字节偏移量进行分块，即按照固定的大小(例如：8KB)进行分块

存在问题：边界偏移问题，即插入新的数据可能会导致重复数据无法被检测到，如下图所示插入数据FF后，无法检测到重复的数据块

 

CDC

CDC 即Content-Defined Chunking，基于内容定义的分块

基于内容定义的分块

• 根据文件内容进行分块，块边界由一个字节偏移量决定，在这个字节偏移量内的内容在之前的边界和当前偏移量之间满足预定义的分块条件时进行分块。本质是逐字节扫描整个文件，避免遗漏。同时为了避免分块大小太大或大小，会进行预定义。
• 如上图所示，最基本的使用一个滑动窗口对文件流进行取模运算，在对取模结果相等时进行分块

优点：可以解决固定大小分块所产生的边界偏移问题，导致的无法找到重复数据块，具体如下所示

缺点：计算密集型，耗时，是重删系统的性能瓶颈

相关论文

1. FastCDC: A Fast and Efficient Content-defined Chunking Approach for Data Deduplication.
2. Ddelta: A Deduplication-inspired fast delta compression approach 、
3. RapidCDC: Leveraging Duplicate Locality to Accelerate Chunking in CDC-based Deduplication Systems *
4. Design Tradeoffs for Data Deduplication Performance in Backup Workloads *