SampDedup：一种用于非易失性内存中高效内联数据去重的技术，通过采样预测实现去重过程

《ACM Transactions on Architecture and Code Optimization》：SampDedup: Sampling Prediction for Efficient Inline Data Deduplication on Non-volatile Memory

非易失性内存（NVM）的数据去重面临计算瓶颈，传统方法在NVM上效率低下。本文提出SampDedup方法，通过采样预测、优化哈希算法和索引设计，减少重复数据块的指纹计算和索引查找开销，实现高去重比（99%以上）和计算成本降低超90%。实验验证其在高冗余数据集（如Linux系统镜像）上加速效果显著，吞吐量达352MB/s，较传统方法提升近2倍。该方法有效解决了NVM低延迟高带宽特性与计算密集型去重流程的冲突问题。

　　在当前数据存储技术迅速发展的背景下，数据去重（Data Deduplication）作为一种高效减少冗余存储空间的技术，逐渐成为研究的重点。数据去重通常包括四个主要步骤：分块（Chunking）、指纹生成（Fingerprinting）、指纹查找（Fingerprint Lookup）和数据管理（Data Management）。传统的存储设备如硬盘驱动器（HDD）和固态硬盘（SSD）主要面临的是I/O瓶颈，但随着新型非易失性存储设备（Non-Volatile Memory, NVM）的出现，直接在NVM上应用数据去重技术却遇到了新的挑战。这些问题主要体现在计算瓶颈、指纹索引和元数据设计的重新考量以及对延迟的敏感性。为了克服这些挑战，我们提出了一种基于采样预测的内联数据去重方法，即SampDedup，它旨在在不牺牲去重率的前提下，通过优化分块、指纹生成和指纹查找这三个关键步骤，显著降低计算成本和延迟。

### 1. 分块的挑战与优化

在传统数据去重过程中，分块是计算密集型操作，而指纹查找和数据管理则是I/O密集型操作。然而，在NVM设备上，由于其读写延迟和带宽的显著提升，计算密集型操作反而成为主要瓶颈。这要求我们重新思考如何优化分块算法。为此，我们提出了SampChunk，一种基于采样预测的分块方法。该方法利用分块头的相似性来识别可能重复的分块，从而跳过不必要的分块操作。SampChunk能够兼容大多数基于滑动窗口和非滑动窗口的CDC分块算法，从而提高了整体效率。

SampChunk的核心思想是通过采样固定长度的分块头，预测下一个分块的大小。具体来说，我们从数据流的开始部分提取一个固定长度的字段，计算其指纹，并通过指纹查找来判断该字段是否重复。如果该分块头被认为是重复的，那么可以推测下一个分块也很可能是重复的，从而跳过分块过程。这种方法减少了分块的计算量，同时保持了较高的去重率。此外，为了进一步提升效率，我们还对分块头的处理进行了优化，确保采样过程的高效性。

### 2. 指纹生成的优化

在指纹生成过程中，SHA-1算法因其计算复杂性而被广泛采用，但这也带来了额外的计算开销。为了解决这一问题，我们对SHA-1算法进行了优化，以减少在SampChunk过程中产生的重复计算。通过记录分块头指纹的中间结果，我们能够在后续指纹生成中跳过重复区域的计算，从而降低整体计算时间。此外，我们还提出了一种异步指纹生成方法，将指纹计算任务分配给独立的线程，以便在不阻塞数据读取和写入的情况下完成指纹生成。

异步指纹生成方法通过引入缓冲区和同步机制，实现了指纹计算与数据处理的并行化。具体来说，我们使用一个全局消息数组作为缓冲区，将数据分块的指纹信息发送给异步线程进行计算。这些线程在接收到指纹信息后，独立完成指纹计算，并最终更新元数据和指纹索引。这种方法有效隐藏了指纹生成的延迟，使得数据读取和写入操作能够独立进行，从而提升了整体性能。

### 3. 指纹查找的优化

由于NVM具有极低的访问延迟，传统的指纹查找方法（如使用LRU缓存）可能不再适用。为此，我们设计了一种基于快速读取缓冲区（Fast-Read Buffer）的指纹查找方法，以替代传统的缓存机制。快速读取缓冲区利用了NVM的高带宽特性，通过预取相邻的指纹信息，提高了查找效率。此外，我们还引入了基于空间局部性的哈希表结构，以提高指纹查找的命中率。

在指纹查找过程中，我们首先在内存缓存中查找分块头指纹。如果命中，说明该分块可能是重复的，可以跳过分块操作。如果未命中，则通过Bloom过滤器进一步判断是否需要进行指纹查找。如果Bloom过滤器也未命中，则说明该分块头是唯一的，需要进行分块和指纹生成。通过这种方式，我们减少了指纹查找的延迟，同时提高了查找效率。

### 4. 系统设计与性能评估

SampDedup的整体设计包括三个主要部分：SampChunk、优化的SHA-1指纹生成和快速读取缓冲区。SampChunk通过采样分块头来预测分块大小，从而减少计算开销。优化的SHA-1算法通过记录中间结果，避免了重复计算。快速读取缓冲区则通过预取相邻的指纹信息，提高了指纹查找的效率。

为了验证SampDedup的有效性，我们在六个真实世界的数据集上进行了实验。这些数据集涵盖了从低冗余到高冗余的不同情况，以确保实验结果的全面性。实验结果显示，SampDedup在所有数据集上都实现了较高的去重率，同时大幅减少了分块时间。例如，在Linux数据集上，SampDedup的去重率达到了98.75%，而在Gnu数据集上，去重率约为11.35%。此外，SampDedup在分块时间上减少了超过90%的计算开销，显著提升了整体性能。

### 5. 未来工作

尽管SampDedup在现有数据集上表现出色，但仍有进一步优化的空间。例如，未来可以探索基于NVM的并行加速方法，充分利用CPU和GPU等硬件资源，进一步提升数据去重的性能。此外，还可以研究如何更好地利用NVM的高带宽特性，设计更高效的指纹索引和元数据管理方案。通过这些优化，SampDedup有望在更广泛的存储系统中得到应用，为数据存储提供更高效的解决方案。