【论文阅读】Odess:通过代理抽样的重复记录消除系统

Odess: Speeding up Resemblance Detection for Redundancy （冗余）Elimination（消除） by Fast Content-Defined Sampling

摘要:随着全球数字数据的快速增长，预计到2025年，全球的数字信息总量将达到175ZB。这种爆炸性的数据增长带来了大规模存储系统中冗余数据的问题。为了有效地管理和存储这些数据，研究人员和工程师们提出了多种压缩技术来消除数据冗余。

"The rapid growth of global digital data is expected to reach a total digital information volume of 175ZB by 2025. This explosive data growth has brought about the issue of redundant data in large-scale storage systems. To effectively manage and store these data, researchers and engineers have proposed various compression techniques to eliminate data redundancy." (Page 1)

背景综述

压缩技术的种类:

• 通用压缩: 能够消除细粒度的冗余，但对于大规模数据来说速度较慢。
• 数据去重: 能够识别和消除粗粒度的冗余，但可能会错过较小的冗余。
• Delta压缩: 结合了上述两种技术的优点，通过在存储系统中检测非常相似的项目，然后消除它们之间的冗余。

"There are three main types of compression techniques: general-purpose compression, deduplication, and delta compression. General-purpose compression can eliminate fine-grained redundancy but is slow for large-scale data. Deduplication can identify and eliminate coarse-grained redundancy but may miss smaller redundancies. Delta compression combines the advantages of the above two techniques by detecting very similar items in the storage system and then eliminating the redundancy between them." (Page 2)

相似性检测的重要性:

• Delta压缩的关键步骤是相似性检测。大多数现有的相似性检测方法都遵循一个框架，即从每个项目中获取特征，并基于特征比较来估计它们的相似性。这通常涉及三个步骤：特征化(Characterizing)、选择(Selecting)和索引(Indexing)。

"The key step of delta compression is resemblance detection. Most existing resemblance detection methods follow a framework, which is to obtain features from each item and estimate their resemblance based on feature comparison. This usually involves three steps: characterizing, selecting, and indexing." (Page 3)

Odess的引入:

• 为了解决上述挑战，本文介绍了一种名为"Odess"的快速相似性检测方法。Odess使用一种新颖的基于内容定义的采样方法来生成一个更小的代理哈希集，然后在这个小哈希集上应用变换。这大大减少了变换步骤中的计算量。

"To address the above challenges, this paper introduces a fast resemblance detection method called Odess. Odess uses a novel content-defined sampling method to generate a smaller proxy hash set and then applies a transform on this small hash set. This greatly reduces the computational cost in the transformation step." (Page 4)

• 此外，Odess还采用了更快的Gear哈希方法来生成滚动哈希，从而在保持高检测准确性和压缩比的同时，大大减少了计算开销。

"Furthermore, Odess also adopts a faster Gear hash method to generate rolling hashes, thereby significantly reducing computational overhead while maintaining high detection accuracy and compression ratio." (Page 5)

Odess的优势:

• 与现有的方法相比，如N-Transform和Finesse，Odess在生成相似性检测的特征方面明显更快。

"Compared to existing methods such as N-Transform and Finesse, Odess is significantly faster in generating features for resemblance detection." (Page 6)

• 在实际应用中，Odess不仅提高了吞吐量，而且还保持或提高了压缩比。

"In practical applications, Odess not only improves throughput but also maintains or enhances the compression ratio." (Page 7)

方法说明：

总体说明：

Odess是一个为了快速检测相似性而设计的方法，其核心思想是通过新颖的基于内容定义的采样方法来生成一个更小的代理哈希集，然后在这个小哈希集上应用变换。

"In this work, we propose Odess, a fast resemblance detection approach, that uses a novel Content-Defined Sampling method to generate a much smaller proxy hash set and then applies transforms on this small hash set." (Page 2)

以下是Odess方法的详细步骤：

1. 基于内容定义的采样:
   • 传统的相似性检测方法通常需要处理大量的哈希值，这会导致计算量大和速度慢。Odess通过基于内容定义的采样方法来解决这个问题。
   • 这种采样方法的目的是从大量的哈希值中选择出一个代表性的子集，这个子集可以有效地代表原始数据的特征。
   • 通过这种方法，Odess可以大大减少需要处理的哈希值的数量，从而提高相似性检测的速度。
2. 小哈希集上的变换:
   • 一旦得到了基于内容定义的采样后的小哈希集，Odess会在这个小哈希集上应用特定的变换。
   • 这种变换的目的是进一步提取数据的特征，并为相似性检测提供更准确的结果。
   • 由于变换是在小哈希集上进行的，所以计算量大大减少，速度得到了提高。
3. 使用Gear哈希生成滚动哈希:
   • Gear哈希是一种快速的哈希方法，它可以有效地为数据生成哈希值。
   • Odess采用Gear哈希来生成滚动哈希，这样可以在保持高检测准确性的同时，大大减少计算开销。
   • 滚动哈希是一种特殊的哈希方法，它可以为数据块中的每个连续的子串生成一个哈希值，这使得Odess可以检测到数据块中的任何小的变化。

实现细节

Odess使用Content-Defined Sampling生成代理，这已被证明是生成代理的可行方法，可以在选择步骤中减少计算开销。基于此，此研究提出了一种新的使用Content-Defined Sampling的相似性检测方法，名为Odess，它在保持与N-Transform相似的高检测准确性的同时，以更高的速度生成序列敏感特征。因此，Odess的原则是在代理上使用不同的线性变换进行独立的重复试验。

"Previous subsections suggest that Content-Defined Sampling is proven to be feasible for generating proxies, which can reduce the calculation overhead in the Selecting step. Based on that, we propose a new resemblance detection approach using Content-Defined Sampling, named Odess, with a much higher speed for generating sequence-sensitive features while maintaining a high detection accuracy similar to N-Transform. Therefore, the principle of Odess is running independent repeated trials on the proxy with different linear transforms." (Page 9)

Odess的一般原则

1. Characterizing:
   • Odess遵循细粒度风格，并应用Gear滚动哈希方法快速为每个项目收集一组特征（即所有滚动哈希值）。
2. Selecting:
   • Odess为每个项目生成一个使用Content-Defined Sampling的代理。
   • 之后，将在代理上应用几个预定义的线性变换以减少计算，然后将从每个线性变换中提取最小值作为特征。
3. Indexing:
   • 使用Super-Feature技术，因此特征被分组成更少的Super-Features。

"The general principle of Odess is shown in Figure 7, also following the typical three steps." (Page 9)

与N-Transform相比，Odess大大减少了计算量。在Characterizing步骤中，Gear的计算量几乎是Rabin的一半。在Selecting步骤中，生成Proxy的计算量减少到采样率，通常配置为1/128，因此Odess的Selecting步骤大约是N-Transform的1/128。尽管在生成代理时引入了更多的计算（即Content-Defined Sampling），但由于使用了Gear滚动哈希，这种增加的计算量被抵消了。

"Compared with N-Transform, the calculation of Odess is reduced substantially. In Characterizing, the calculation of Gear is nearly half of Rabin [25]. In Selecting, the calculation is reduced to the sampling rate in generating Proxy, which is usually configured as 1/128, so Selecting of Odess has approximately 1/128 of the calculations of N-Transform." (Page 9)

实例处理流程说明:

下面这个示例将说明Odess方法的基本工作原理，并展示了如何使用它来检测数据块之间的相似性。在实际应用中，Odess方法会考虑更多的因素，如数据块的大小、特征的数量和类型等，以提高检测的准确性和效率。

数据示例:
假设此研究有两个数据块：

• 数据块A: "HELLO_WORLD"
• 数据块B: "HELLO_WORLDS"

此研究的目标是检测这两个数据块之间的相似性。

步骤1: Characterizing: 从每个项目中获取特征。
首先，此研究需要从每个数据块中获取特征。使用滚动哈希方法，此研究可以得到以下的哈希值：

• 数据块A的哈希值: [12345, 67890, 11112, 13141, ...]
• 数据块B的哈希值: [12345, 67891, 11113, 13142, ...]

这里，滚动哈希是通过在数据块上滑动一个固定大小的窗口并为窗口中的每个字节计算哈希值来工作的。

步骤2: Selecting: 选择某些生成的特征作为项目的特征。
接下来，此研究选择某些生成的哈希值作为数据块的特征。假设此研究使用Top-k方法，选择前k个哈希值作为特征。

• 数据块A的特征: [12345, 67890]
• 数据块B的特征: [12345, 67891]

在这个步骤中，此研究可能还会使用其他的选择技术，如“Fixed Position”或“Top-1 on each linear transform”来进一步优化特征选择。

步骤3: Indexing: 基于它们的特征识别相似的项目。
最后，此研究基于这些特征来识别相似的数据块。使用简单的特征比较，此研究可以得到：

• 数据块A和数据块B有一个共同的特征: 12345

为了进一步优化这个步骤，可能会使用如“Super-Feature”或“Bloom Filter”等技术来组织和索引特征，从而更快地找到相似的数据块。

结论:
通过上述步骤，此研究成功地检测到了数据块A和数据块B之间的相似性。这只是一个简化的示例，实际的Odess方法在处理大规模数据时会更加复杂和高效。

解释

1. 滚动哈希是怎么找的:

   滚动哈希是一种特殊的哈希算法，它可以在常数时间内为连续的数据块计算哈希值。当此研究从数据块的一个部分移动到下一个部分时，滚动哈希可以利用前一个哈希值的信息来快速计算新的哈希值，而不需要重新计算整个数据块的哈希值。这种方法特别适用于大数据流，因为它可以快速地为连续的数据段生成哈希值。

   数据示例1: 假设此研究有一个字符串："HELLO_WORLD"，并使用一个4字节的滑动窗口。

   1. 初始哈希值计算: 首先，此研究为窗口中的"HELL"计算哈希值。为简化起见，假设每个字符的ASCII值代表其哈希值，那么"HELL"的哈希值可以是： H(72) + E(69) + L(76) + L(76) = 293

   2. 滚动哈希值计算: 当窗口从"HELL"滑动到"ELLO"时，此研究不需要重新计算整个窗口的哈希值。而是使用前一个哈希值的计算结果来更新哈希值。

   首先，从前一个哈希值中减去离开窗口的第一个字符的值： 293 - H(72) = 221

   然后，加上进入窗口的新字符的值： 221 + O(79) = 300所以，"ELLO"的哈希值是300。

   数据示例2: "HELLO_WORLD"

   假设此研究使用一个4字节的滑动窗口来计算哈希值。

   1. 窗口1: "HELL" -> 哈希值: 12345
   2. 窗口2: "ELLO" -> 哈希值: 67890
   3. 窗口3: "LL_W" -> 哈希值: 11112
   4. 窗口4: "L_WO" -> 哈希值: 13141 ... 以此类推，直到窗口滑到数据块的末尾。

   这样，此研究为数据块A生成了一系列的哈希值。这些哈希值可以被视为数据块的特征，用于与其他数据块进行比较，以检测它们之间的相似性。

2. 为什么选择前k个哈希值作为特征:

   选择前k个哈希值作为特征是基于一个假设，即数据块的开始部分很可能包含其独特性的信息。这种方法可以减少计算和存储开销，因为此研究只需要考虑k个特征而不是整个数据块。然而，这只是一种策略，实际的策略可能会根据数据的性质和应用的需求进行调整。

3. 使用如“Super-Feature”或“Bloom Filter”等技术来组织和索引特征，从而更快地找到相似的数据块，具体怎么操作:

   • Super-Feature: 这是一种将多个特征组合成一个大的特征的方法。这样，此研究可以减少索引的大小并加快查找速度。例如，如果此研究有三个特征f1, f2, 和f3，此研究可以将它们组合成一个超级特征sf = f1 + f2 + f3。

   • Bloom Filter: 这是一种空间效率极高的数据结构，用于测试一个元素是否属于一个集合。它可以快速地检查一个特征是否存在，但可能会有一些误报。在这种情况下，此研究可以将所有的特征放入一个Bloom Filter中，然后使用它来快速检查相似的数据块。

     ​ 在这里，它可以用于快速检查一个特征是否存在于数据块中。示例: 假设此研究使用Bloom Filter来索引数据块A的特征。当此研究要检查数据块B是否包含某个特征时，此研究可以在常数时间内得到答案。

4. 一旦得到了基于内容定义的采样后的小哈希集，Odess会在这个小哈希集上应用特定的变换，这句话怎么理解:

   基于内容定义的采样是一种选择数据块中特定部分的方法，这些部分可能包含有关数据块独特性的信息。一旦此研究得到了这个小哈希集，Odess会应用某种变换或算法来进一步处理这些哈希值。这可能包括排序、组合或其他操作，以生成一个更紧凑或更具代表性的特征集。这样，此研究可以更有效地比较不同的数据块，并快速地检测它们之间的相似性。

   示例: 假设基于内容定义的采样得到的小哈希集是[1234, 5678]。Odess可能会应用某种变换，例如将每个哈希值乘以一个常数，得到新的哈希集[2468, 11356]。

   总的来说，Odess方法通过一系列步骤和技术来提高相似性检测的准确性和效率。这些步骤和技术都是为了确保在大规模数据中快速、准确地找到相似的数据块。

5. Content-Defined Sampling代理是怎么运行的

   Content-Defined Sampling (CDS) 是一种受Content-Defined Chunking (CDC)启发的方法，用于生成代理。以下是CDS的运行方式：

   1. 原理:
      • 在CDC中，此研究在每个滑动窗口上计算指纹，并检查指纹 fp 是否满足预定义的条件（例如 fp & mask == 0，其中mask是用户指定的数字）来设置一个块切割点。
      • 类似地，在Content-Defined Sampling中，此研究检查每个特征（即 fp）并决定它是否在代理中，也是通过检查 fp 是否满足某个条件来决定的。
   2. 操作:
      • Content-Defined Sampling是一种直接的生成代理的方法。但是，根据这些前提条件，许多采样方法都是不适用的，包括随机采样、系统采样等。即使此研究使用固定的随机种子，生成的随机采样点也是固定的，它会类似于“Fixed-Position”，这在第一节中已经介绍过，不能处理“boundary-shift”问题。
      • 为了满足确定性前提条件，此研究发现“Content-Defined Sampling”是可行的。更具体地说，此研究可以通过Content-Defined Sampling生成代理：此研究检查每个特征并决定它是否在代理中，也是通过检查特征是否满足某个条件来决定的。
   3. 效果:
      • 使用合理的采样率（例如1/128），Content-Defined Sampling对检测效率的影响很小。在理论和评估中，与N-Transform相比，此研究的Content-Defined Sampling方法只对检测效率产生了轻微的影响。

6. 进阶实例

   数据示例: 假设此研究有一个数据块：

   • 数据块: "ABCDEF_ABCD"

   步骤1: 滚动哈希: 首先，此研究使用滚动哈希方法为数据块中的每个滑动窗口生成哈希值。假设此研究的窗口大小为3个字符。

   • 哈希值: [hash("ABC"), hash("BCD"), hash("CDE"), hash("DEF"), hash("EFA"), hash("FAB"), hash("ABC"), hash("BCD")]

   步骤2: Content-Defined Sampling: 接下来，此研究使用Content-Defined Sampling方法来选择哈希值。假设此研究的条件是哈希值的最后两位为00（这只是一个简化的示例）。

   从上面的哈希值列表中，假设以下哈希值满足条件：

   • hash("ABC")，hash("DEF")，hash("ABC")

   这些哈希值将被选为代理。

   步骤3: 生成代理: 基于上述选择的哈希值，此研究的代理如下：

   • 代理: [hash("ABC"), hash("DEF"), hash("ABC")]

   这个代理现在可以用于进一步的相似性检测和其他操作。

   结论: Content-Defined Sampling方法允许此研究从大量的哈希值中选择一个较小的代表性子集，这大大减少了后续步骤中的计算量。在这个简化的示例中，此研究使用了一个简单的条件来选择哈希值，但在实际应用中，这个条件可能会更复杂，以确保选择的哈希值能够代表原始数据块的内容。

实验说明

以下是关于实验步骤、设置和结果的详细说明：

A. 实验设置 (Experimental Setup)

• 硬件和软件环境: 实验在一台服务器上进行，该服务器配备了两个Intel Xeon Gold 6113处理器，主频为2.1GHz，内存为128GB，并有四个Intel S4600 1TB的SSD。服务器运行的操作系统为Ubuntu 16.04。
• 原型数据减少系统: 该系统具有五个阶段的流水线，包括读取、分块、哈希、去重和写入阶段。
• 实验数据: 为了实验，研究者构建了一个基准测试，生成具有不同相似性分布的数据块对，以研究Odess的检测准确性。此外，还构建了一个原型数据减少系统（去重+增量压缩）来展示Odess在系统级别的影响。
• 数据集: 为原型实验使用了六个数据集，如下所示：
  • TAR: 167 GB, 去重比率: 2.08
  • LNX: 116 GB, 去重比率: 2.00
  • RDB: 431 GB, 去重比率: 12.58
  • SYN: 452 GB, 去重比率: 13.77
  • VMA: 138 GB, 去重比率: 1.70
  • VMB: 314 GB, 去重比率: 8.14

B. 基准数据集上的检测准确性 (Detection Accuracy on Benchmark Datasets)

• 评估方法: 在此子部分中，研究者评估了三种相似性检测方法在基准测试上的表现，重点关注两个指标：平均估计误差（越低越好）和估计误差的标准偏差（越低越好）。估计误差是实际相似性（由基准记录）与估计相似性（经过检测后计算）之间的差值的绝对值。
• 基准测试的创建: 为了更好地评估相似性在受控方式下的变化，研究者创建了一个基准测试，而不是使用现有的数据集。他们生成随机块并对其进行一系列修改，以在基准测试中导出相似的块，其中记录了这些块对的实际相似性。

实验结果:

与N-Transform的比较: 结果显示，Odess的估计相似性的期望与N-Transform相同，这意味着与N-Transform相比，Content-Defined Sampling方法平均会产生相同的相似性。

"Therefore, the Inference 1 in Section III-D, 'compared with N-Transform, our Content-Defined Sampling approach will generate the same similarity on average', is verified in Figure 10." (Page 10)

Odess的采样率的影响: 结果显示，Odess在各种采样率下都有稳定的结果，尽管对于高采样率（1/512）误差确实增加了。较小的采样率导致较小的平均估计误差和估计误差的标准偏差，这意味着更好的鲁棒性。

"We explore the impact of the sampling rate in Odess, and the result is shown in Figure 11. In general, Odess has stable results across sampling rates, though error does increase for high sampling rates (1/512). A smaller sampling rate leads to smaller Average Estimating Error and Standard Deviation of Estimating Error, which means a better robustness." (Page 10)

未来方向

• 虽然Odess在相似性检测方面表现出色，但仍有进一步优化的空间。未来的研究可以探索如何进一步减少计算开销，同时保持或提高检测准确性。

  "In this paper, we propose a fast resemblance detection approach Odess, which uses a fast rolling hash and a novel Content-Defined Sampling method. Odess is extremely fast, about 26.9× faster than N-Transform at features generation for resemblance detection while maintaining an approximate detection accuracy." (Page 13)

• 另外，考虑到数据的持续增长，如何使Odess更具可扩展性，以便它可以处理更大的数据集，也是一个值得探讨的方向。

  "In the future, we will focus on improving the grouping." (Page 13)