QuickCDC: A Quick Content Defined Chunking Algorithm Based on Jumping and Dynamically Adjusting Mask Bits
Zhen Xu, Wenbo Zhang · 2021
Data chunking refers to the process of splitting files or data stream into multiple chunks of fixed length or variable length. Chunking determines the performance of underlying storage system. Content Defined Chunking (CDC) has been widely employed and plays an important role in backup and primary storage systems. Due to time-consuming byte by byte calculation on data stream, chunking speed and deduplication ratio of Rabin CDC are low, which is CPU intensive and based on sliding window. QuickCDC utilizes three technologies to enhance chunking speed, deduplication ratio and throughput of CDC. Firstly, for duplicate chunks that appear many times, QuickCDC can jump directly to their chunk boundaries. The mapping of the first n bytes and the last m bytes of the duplicate chunk to chunk length needs to be recorded. When executing chunking, the first n bytes and the last m bytes of the current chunk are judged whether they are in the mapping table. If they are in the mapping table, QuickCDC can skip corresponding chunk length. Secondly, for unique chunks, QuickCDC can skip the minimum chunk length on them. Thirdly, QuickCDC is able to dynamically adjust mask bits length so that the chunk length distributes in a small specific region, and is always greater than the minimum chunk length. We should employ longer mask bits when current chunk length is less than the expected chunk length, and use shorter mask bits when current chunk length is larger than the expected chunk length. Experiments reveal that chunking speed of QuickCDC is 11.4x of RapidCDC, and corresponding deduplication ratio is slightly improved, the maximum improvement of deduplication ratio is 222.3% and the improvement of throughput is 111.4%.