Accelerating Content-Defined Chunking for Data Deduplication Based on Speculative Jump
Xiaozhong Jin, Haikun Liu, Chencheng Ye, Xiaofei Liao, Hai Jin, Yu Zhang
Abstract
In data deduplication systems, chunking has a significant impact on the deduplication ratio and throughput. Existing <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Content-Defined Chunking</i> (CDC) approaches exploit a sliding window to calculate rolling hashes of the input data stream byte-by-byte, and then determine chunk cut-points if the rolling hash satisfies a given cut-condition. Since previous CDC approaches are extremely costly, it often significantly degrades the throughput of data deduplication systems. In this paper, we argue that calculating and checking the rolling hashes byte-by-byte is unnecessary. To reduce the CPU overhead of CDC, we propose a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">jump-based chunking</i> (JC) approach. The key idea is to introduce a jump-condition, and the sliding window can jump over a specific length of the input data stream if the rolling hashes satisfy the jump-condition. Moreover, we also explore the impact of the cut-condition and the jump-condition on the chunk size. Our theoretic studies demonstrate the effectiveness and efficiency of JC, without compromising the deduplication ratio. Experimental results show that JC improves the throughput of chunking by about 2× on average compared with the state-of-the-art CDC approaches while still guaranteeing high deduplication ratio.