FastCDC: a Fast and Efficient Content Defined Chunking Approach for Data Deduplication
Content Defined Chunking (CDC) has been playing a key role in data deduplication systems in the past 15 years or so due to its high redundancy detection ability. However, existing CDC based approaches introduce heavy CPU overhead because they declare the chunk cutpoints by computing and judging the rolling hashes of the data stream byte by byte. In this paper, we propose FastCDC, a Fast and efficient CDC approach, that builds and improves on the latest Gear based CDC approach, one of the fastest CDC methods to our knowledge. The key idea behind FastCDC is the combined use of three key techniques, namely, simplifying and enhancing the hash judgment to address our observed challenges facing Gear based CDC, skipping sub minimum chunk cut point to further speed up CDC, and normalizing the chunk size distribution in a small specified region to address the problem of the decreased deduplication ratio stemming from the cut point skipping. Our evaluation results show that, by using a combination of the three techniques, FastCDC is about 10x faster than the best of open source Rabin based CDC, and about 3x faster than the state of the art Gear and AE based CDC, while achieving nearly the same deduplication ratio as the classic Rabin based approach.
USENIX Annual Technical Conference