Exploiting Fingerprint Prefetching to Improve the Performance of Data Deduplication

Data deduplication has become an important and economic way to remove the redundant data segments, thus alleviating the pressure incurred by large amounts of data need to store. Fingerprints are used to represent and identify identical data blocks when performing data deduplication. However, the amount of fingerprints grows with the increase of data. Due to the limited memory size, the fingerprints have to be stored in disk drives. When the fingerprints are not satisfied in memory, disk I/Os will be generated to obtain the on-disk fingerprints. This results in small and random I/Os, thus significantly degrading the performance of data deduplication. This paper introduces a fingerprint prefetching algorithm by leveraging file similarity and data locality. On the one hand, we present a similar file recognition algorithm to identify the similar files that are considered to have some modifications and share a large portion of identical data blocks. On the other hand, the on-disk fingerprints are organized according to the sequence of data streams, thus maintaining the data locality to improve the cache hit ratio. The proposed prefetching algorithm will request fingerprints from disk drives and place them in memory before they are actually needed. This will significantly improve the cache hit ratio when the fingerprints are actually needed, thus enhancing the performance of data deduplication. Two real data sets that represent typical cloud storage and cloud computing scenarios are collected to evaluate the effectiveness of the proposed approach.