HF-Dedupe: Hierarchical Fingerprint Scheme for High Efficiency Data Deduplication on Flash-based Storage Systems

Even though flash memory is widely used in many applications as storage due to its high performance, demands for lower storage cost and better I/O performance are still high because of the continuous growth of data. Data deduplication has the potential to address these issues by eliminating redundant writes in I/O workloads and different strategies have been proposed to improve its efficiency. However, existing designs mainly rely on time-consuming SHA-1 fingerprint scheme or byte-by-byte comparison to identify duplicate data, and these methods cause much overhead and become a bottleneck in data deduplication. To tackle this issue, we propose the hierarchical fingerprint scheme (HF-Dedupe) to improve the efficiency of data deduplication for flash-based storage systems. By leveraging multiple levels of light-weight hashes in the fingerprint, our design only takes the minimal effort to distinguish different data in write traffic. In order to evaluate our design, a series of experiments were conducted based on trace-driven simulations. Compared with other designs, the experimental results show that HF-Dedupe further reduces the deduplication time by 34.76%-65.02 % while retaining high deduplication ratio, and therefore achieves the most improvement to overall I/O performance.