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

摘要:隨著全球數(shù)字數(shù)據(jù)的快速增長，預(yù)計到2025年，全球的數(shù)字信息總量將達到175ZB。這種爆炸性的數(shù)據(jù)增長帶來了大規(guī)模存儲系統(tǒng)中冗余數(shù)據(jù)的問題。為了有效地管理和存儲這些數(shù)據(jù)，研究人員和工程師們提出了多種壓縮技術(shù)來消除數(shù)據(jù)冗余。

"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)

背景綜述

壓縮技術(shù)的種類:

• 通用壓縮: 能夠消除細粒度的冗余，但對于大規(guī)模數(shù)據(jù)來說速度較慢。

• 數(shù)據(jù)去重: 能夠識別和消除粗粒度的冗余，但可能會錯過較小的冗余。

• Delta壓縮: 結(jié)合了上述兩種技術(shù)的優(yōu)點，通過在存儲系統(tǒng)中檢測非常相似的項目，然后消除它們之間的冗余。

"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壓縮的關(guān)鍵步驟是相似性檢測。大多數(shù)現(xiàn)有的相似性檢測方法都遵循一個框架，即從每個項目中獲取特征，并基于特征比較來估計它們的相似性。這通常涉及三個步驟：特征化(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的引入:

• 為了解決上述挑戰(zhàn)，本文介紹了一種名為"Odess"的快速相似性檢測方法。Odess使用一種新穎的基于內(nèi)容定義的采樣方法來生成一個更小的代理哈希集，然后在這個小哈希集上應(yīng)用變換。這大大減少了變換步驟中的計算量。

"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哈希方法來生成滾動哈希，從而在保持高檢測準(zhǔn)確性和壓縮比的同時，大大減少了計算開銷。

"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的優(yōu)勢:

• 與現(xiàn)有的方法相比，如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)

• 在實際應(yīng)用中，Odess不僅提高了吞吐量，而且還保持或提高了壓縮比。

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

方法說明：

總體說明：

Odess是一個為了快速檢測相似性而設(shè)計的方法，其核心思想是通過新穎的基于內(nèi)容定義的采樣方法來生成一個更小的代理哈希集，然后在這個小哈希集上應(yīng)用變換。

"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. 基于內(nèi)容定義的采樣:

• 傳統(tǒng)的相似性檢測方法通常需要處理大量的哈希值，這會導(dǎo)致計算量大和速度慢。Odess通過基于內(nèi)容定義的采樣方法來解決這個問題。

• 這種采樣方法的目的是從大量的哈希值中選擇出一個代表性的子集，這個子集可以有效地代表原始數(shù)據(jù)的特征。

• 通過這種方法，Odess可以大大減少需要處理的哈希值的數(shù)量，從而提高相似性檢測的速度。

2. 小哈希集上的變換:

• 一旦得到了基于內(nèi)容定義的采樣后的小哈希集，Odess會在這個小哈希集上應(yīng)用特定的變換。

• 這種變換的目的是進一步提取數(shù)據(jù)的特征，并為相似性檢測提供更準(zhǔn)確的結(jié)果。

• 由于變換是在小哈希集上進行的，所以計算量大大減少，速度得到了提高。

3. 使用Gear哈希生成滾動哈希:

• Gear哈希是一種快速的哈希方法，它可以有效地為數(shù)據(jù)生成哈希值。

• Odess采用Gear哈希來生成滾動哈希，這樣可以在保持高檢測準(zhǔn)確性的同時，大大減少計算開銷。

• 滾動哈希是一種特殊的哈希方法，它可以為數(shù)據(jù)塊中的每個連續(xù)的子串生成一個哈希值，這使得Odess可以檢測到數(shù)據(jù)塊中的任何小的變化。

實現(xiàn)細節(jié)

Odess使用Content-Defined Sampling生成代理，這已被證明是生成代理的可行方法，可以在選擇步驟中減少計算開銷?；诖?，此研究提出了一種新的使用Content-Defined Sampling的相似性檢測方法，名為Odess，它在保持與N-Transform相似的高檢測準(zhǔn)確性的同時，以更高的速度生成序列敏感特征。因此，Odess的原則是在代理上使用不同的線性變換進行獨立的重復(fù)試驗。

"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遵循細粒度風(fēng)格，并應(yīng)用Gear滾動哈希方法快速為每個項目收集一組特征（即所有滾動哈希值）。

2. Selecting:

• Odess為每個項目生成一個使用Content-Defined Sampling的代理。

• 之后，將在代理上應(yīng)用幾個預(yù)定義的線性變換以減少計算，然后將從每個線性變換中提取最小值作為特征。

3. Indexing:

• 使用Super-Feature技術(shù)，因此特征被分組成更少的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方法的基本工作原理，并展示了如何使用它來檢測數(shù)據(jù)塊之間的相似性。在實際應(yīng)用中，Odess方法會考慮更多的因素，如數(shù)據(jù)塊的大小、特征的數(shù)量和類型等，以提高檢測的準(zhǔn)確性和效率。

數(shù)據(jù)示例:
假設(shè)此研究有兩個數(shù)據(jù)塊：

• 數(shù)據(jù)塊A: "HELLO_WORLD"

• 數(shù)據(jù)塊B: "HELLO_WORLDS"

此研究的目標(biāo)是檢測這兩個數(shù)據(jù)塊之間的相似性。

步驟1: Characterizing: 從每個項目中獲取特征。
首先，此研究需要從每個數(shù)據(jù)塊中獲取特征。使用滾動哈希方法，此研究可以得到以下的哈希值：

• 數(shù)據(jù)塊A的哈希值: [12345, 67890, 11112, 13141, ...]

• 數(shù)據(jù)塊B的哈希值: [12345, 67891, 11113, 13142, ...]

這里，滾動哈希是通過在數(shù)據(jù)塊上滑動一個固定大小的窗口并為窗口中的每個字節(jié)計算哈希值來工作的。

步驟2: Selecting: 選擇某些生成的特征作為項目的特征。
接下來，此研究選擇某些生成的哈希值作為數(shù)據(jù)塊的特征。假設(shè)此研究使用Top-k方法，選擇前k個哈希值作為特征。

• 數(shù)據(jù)塊A的特征: [12345, 67890]

• 數(shù)據(jù)塊B的特征: [12345, 67891]

在這個步驟中，此研究可能還會使用其他的選擇技術(shù)，如“Fixed Position”或“Top-1 on each linear transform”來進一步優(yōu)化特征選擇。

步驟3: Indexing: 基于它們的特征識別相似的項目。
最后，此研究基于這些特征來識別相似的數(shù)據(jù)塊。使用簡單的特征比較，此研究可以得到：

• 數(shù)據(jù)塊A和數(shù)據(jù)塊B有一個共同的特征: 12345

為了進一步優(yōu)化這個步驟，可能會使用如“Super-Feature”或“Bloom Filter”等技術(shù)來組織和索引特征，從而更快地找到相似的數(shù)據(jù)塊。

結(jié)論:
通過上述步驟，此研究成功地檢測到了數(shù)據(jù)塊A和數(shù)據(jù)塊B之間的相似性。這只是一個簡化的示例，實際的Odess方法在處理大規(guī)模數(shù)據(jù)時會更加復(fù)雜和高效。

解釋

1. 滾動哈希是怎么找的:

   滾動哈希是一種特殊的哈希算法，它可以在常數(shù)時間內(nèi)為連續(xù)的數(shù)據(jù)塊計算哈希值。當(dāng)此研究從數(shù)據(jù)塊的一個部分移動到下一個部分時，滾動哈?？梢岳们耙粋€哈希值的信息來快速計算新的哈希值，而不需要重新計算整個數(shù)據(jù)塊的哈希值。這種方法特別適用于大數(shù)據(jù)流，因為它可以快速地為連續(xù)的數(shù)據(jù)段生成哈希值。

   數(shù)據(jù)示例1: 假設(shè)此研究有一個字符串："HELLO_WORLD"，并使用一個4字節(jié)的滑動窗口。

   1. 初始哈希值計算: 首先，此研究為窗口中的"HELL"計算哈希值。為簡化起見，假設(shè)每個字符的ASCII值代表其哈希值，那么"HELL"的哈希值可以是： H(72) + E(69) + L(76) + L(76) = 293

   2. 滾動哈希值計算: 當(dāng)窗口從"HELL"滑動到"ELLO"時，此研究不需要重新計算整個窗口的哈希值。而是使用前一個哈希值的計算結(jié)果來更新哈希值。

   首先，從前一個哈希值中減去離開窗口的第一個字符的值： 293 - H(72) = 221

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

   數(shù)據(jù)示例2: "HELLO_WORLD"

   假設(shè)此研究使用一個4字節(jié)的滑動窗口來計算哈希值。

   這樣，此研究為數(shù)據(jù)塊A生成了一系列的哈希值。這些哈希值可以被視為數(shù)據(jù)塊的特征，用于與其他數(shù)據(jù)塊進行比較，以檢測它們之間的相似性。

1. 窗口1: "HELL" -> 哈希值: 12345

2. 窗口2: "ELLO" -> 哈希值: 67890

3. 窗口3: "LL_W" -> 哈希值: 11112

4. 窗口4: "L_WO" -> 哈希值: 13141 ... 以此類推，直到窗口滑到數(shù)據(jù)塊的末尾。

2. 為什么選擇前k個哈希值作為特征:

   選擇前k個哈希值作為特征是基于一個假設(shè)，即數(shù)據(jù)塊的開始部分很可能包含其獨特性的信息。這種方法可以減少計算和存儲開銷，因為此研究只需要考慮k個特征而不是整個數(shù)據(jù)塊。然而，這只是一種策略，實際的策略可能會根據(jù)數(shù)據(jù)的性質(zhì)和應(yīng)用的需求進行調(diào)整。

3. 使用如“Super-Feature”或“Bloom Filter”等技術(shù)來組織和索引特征，從而更快地找到相似的數(shù)據(jù)塊，具體怎么操作:

• Super-Feature: 這是一種將多個特征組合成一個大的特征的方法。這樣，此研究可以減少索引的大小并加快查找速度。例如，如果此研究有三個特征f1, f2, 和f3，此研究可以將它們組合成一個超級特征sf = f1 + f2 + f3。

• Bloom Filter: 這是一種空間效率極高的數(shù)據(jù)結(jié)構(gòu)，用于測試一個元素是否屬于一個集合。它可以快速地檢查一個特征是否存在，但可能會有一些誤報。在這種情況下，此研究可以將所有的特征放入一個Bloom Filter中，然后使用它來快速檢查相似的數(shù)據(jù)塊。

  在這里，它可以用于快速檢查一個特征是否存在于數(shù)據(jù)塊中。示例: 假設(shè)此研究使用Bloom Filter來索引數(shù)據(jù)塊A的特征。當(dāng)此研究要檢查數(shù)據(jù)塊B是否包含某個特征時，此研究可以在常數(shù)時間內(nèi)得到答案。

4. 一旦得到了基于內(nèi)容定義的采樣后的小哈希集，Odess會在這個小哈希集上應(yīng)用特定的變換，這句話怎么理解:

   基于內(nèi)容定義的采樣是一種選擇數(shù)據(jù)塊中特定部分的方法，這些部分可能包含有關(guān)數(shù)據(jù)塊獨特性的信息。一旦此研究得到了這個小哈希集，Odess會應(yīng)用某種變換或算法來進一步處理這些哈希值。這可能包括排序、組合或其他操作，以生成一個更緊湊或更具代表性的特征集。這樣，此研究可以更有效地比較不同的數(shù)據(jù)塊，并快速地檢測它們之間的相似性。

   示例: 假設(shè)基于內(nèi)容定義的采樣得到的小哈希集是[1234, 5678]。Odess可能會應(yīng)用某種變換，例如將每個哈希值乘以一個常數(shù)，得到新的哈希集[2468, 11356]。

   總的來說，Odess方法通過一系列步驟和技術(shù)來提高相似性檢測的準(zhǔn)確性和效率。這些步驟和技術(shù)都是為了確保在大規(guī)模數(shù)據(jù)中快速、準(zhǔn)確地找到相似的數(shù)據(jù)塊。

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

   Content-Defined Sampling (CDS) 是一種受Content-Defined Chunking (CDC)啟發(fā)的方法，用于生成代理。以下是CDS的運行方式：

• 使用合理的采樣率（例如1/128），Content-Defined Sampling對檢測效率的影響很小。在理論和評估中，與N-Transform相比，此研究的Content-Defined Sampling方法只對檢測效率產(chǎn)生了輕微的影響。

• Content-Defined Sampling是一種直接的生成代理的方法。但是，根據(jù)這些前提條件，許多采樣方法都是不適用的，包括隨機采樣、系統(tǒng)采樣等。即使此研究使用固定的隨機種子，生成的隨機采樣點也是固定的，它會類似于“Fixed-Position”，這在第一節(jié)中已經(jīng)介紹過，不能處理“boundary-shift”問題。

• 為了滿足確定性前提條件，此研究發(fā)現(xiàn)“Content-Defined Sampling”是可行的。更具體地說，此研究可以通過Content-Defined Sampling生成代理：此研究檢查每個特征并決定它是否在代理中，也是通過檢查特征是否滿足某個條件來決定的。

• 在CDC中，此研究在每個滑動窗口上計算指紋，并檢查指紋?fp?是否滿足預(yù)定義的條件（例如?fp & mask == 0，其中mask是用戶指定的數(shù)字）來設(shè)置一個塊切割點。

• 類似地，在Content-Defined Sampling中，此研究檢查每個特征（即?fp）并決定它是否在代理中，也是通過檢查?fp?是否滿足某個條件來決定的。

1. 原理:

2. 操作:

3. 效果:

6. 進階實例

   數(shù)據(jù)示例: 假設(shè)此研究有一個數(shù)據(jù)塊：

   步驟1: 滾動哈希: 首先，此研究使用滾動哈希方法為數(shù)據(jù)塊中的每個滑動窗口生成哈希值。假設(shè)此研究的窗口大小為3個字符。

   步驟2: Content-Defined Sampling: 接下來，此研究使用Content-Defined Sampling方法來選擇哈希值。假設(shè)此研究的條件是哈希值的最后兩位為00（這只是一個簡化的示例）。

   從上面的哈希值列表中，假設(shè)以下哈希值滿足條件：

   這些哈希值將被選為代理。

   步驟3: 生成代理: 基于上述選擇的哈希值，此研究的代理如下：

   這個代理現(xiàn)在可以用于進一步的相似性檢測和其他操作。

   結(jié)論: Content-Defined Sampling方法允許此研究從大量的哈希值中選擇一個較小的代表性子集，這大大減少了后續(xù)步驟中的計算量。在這個簡化的示例中，此研究使用了一個簡單的條件來選擇哈希值，但在實際應(yīng)用中，這個條件可能會更復(fù)雜，以確保選擇的哈希值能夠代表原始數(shù)據(jù)塊的內(nèi)容。

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

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

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

• 數(shù)據(jù)塊: "ABCDEF_ABCD"

實驗說明

以下是關(guān)于實驗步驟、設(shè)置和結(jié)果的詳細說明：

A. 實驗設(shè)置 (Experimental Setup)

• 硬件和軟件環(huán)境: 實驗在一臺服務(wù)器上進行，該服務(wù)器配備了兩個Intel Xeon Gold 6113處理器，主頻為2.1GHz，內(nèi)存為128GB，并有四個Intel S4600 1TB的SSD。服務(wù)器運行的操作系統(tǒng)為Ubuntu 16.04。

• 原型數(shù)據(jù)減少系統(tǒng): 該系統(tǒng)具有五個階段的流水線，包括讀取、分塊、哈希、去重和寫入階段。

• 實驗數(shù)據(jù): 為了實驗，研究者構(gòu)建了一個基準(zhǔn)測試，生成具有不同相似性分布的數(shù)據(jù)塊對，以研究Odess的檢測準(zhǔn)確性。此外，還構(gòu)建了一個原型數(shù)據(jù)減少系統(tǒng)（去重+增量壓縮）來展示Odess在系統(tǒng)級別的影響。

• 數(shù)據(jù)集: 為原型實驗使用了六個數(shù)據(jù)集，如下所示：

• 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. 基準(zhǔn)數(shù)據(jù)集上的檢測準(zhǔn)確性 (Detection Accuracy on Benchmark Datasets)

• 評估方法: 在此子部分中，研究者評估了三種相似性檢測方法在基準(zhǔn)測試上的表現(xiàn)，重點關(guān)注兩個指標(biāo)：平均估計誤差（越低越好）和估計誤差的標(biāo)準(zhǔn)偏差（越低越好）。估計誤差是實際相似性（由基準(zhǔn)記錄）與估計相似性（經(jīng)過檢測后計算）之間的差值的絕對值。

• 基準(zhǔn)測試的創(chuàng)建: 為了更好地評估相似性在受控方式下的變化，研究者創(chuàng)建了一個基準(zhǔn)測試，而不是使用現(xiàn)有的數(shù)據(jù)集。他們生成隨機塊并對其進行一系列修改，以在基準(zhǔn)測試中導(dǎo)出相似的塊，其中記錄了這些塊對的實際相似性。

實驗結(jié)果:

與N-Transform的比較: 結(jié)果顯示，Odess的估計相似性的期望與N-Transform相同，這意味著與N-Transform相比，Content-Defined Sampling方法平均會產(chǎn)生相同的相似性。

"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的采樣率的影響: 結(jié)果顯示，Odess在各種采樣率下都有穩(wěn)定的結(jié)果，盡管對于高采樣率（1/512）誤差確實增加了。較小的采樣率導(dǎo)致較小的平均估計誤差和估計誤差的標(biāo)準(zhǔn)偏差，這意味著更好的魯棒性。

"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在相似性檢測方面表現(xiàn)出色，但仍有進一步優(yōu)化的空間。未來的研究可以探索如何進一步減少計算開銷，同時保持或提高檢測準(zhǔn)確性。

  "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)

• 另外，考慮到數(shù)據(jù)的持續(xù)增長，如何使Odess更具可擴展性，以便它可以處理更大的數(shù)據(jù)集，也是一個值得探討的方向。

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