CSF: An Efficient Parallel Deduplication Algorithm by Clustering Scattered Fingerprints

摘要

Deduplication is one of the most effective and efficient techniques to save memory space. It is widely used in data centers and cloud storage systems. Multi-stream concurrency is expected to increase the throughput of deduplication. However, multiple data streams hurt the locality of accessed data and weaken the benefit of data concurrency, which forms a challenge for data deduplication. Usually, the ordered index can reshape the locality of data streams, which can improve the cache hit rate during deduplication. In this paper, we first propose an efficient parallel deduplication algorithm by clustering scattered fingerprints, called CSF, to exploit the data locality as much as possible. It tries to improve the utilization rate of the fingerprint page by the clustered fingerprints. Moreover, it retains the scattered fingerprint to next round fingerprint comparison by re-using the fingerprints on the same page. Thus the number of the fingerprint pages to read is reduced. We further optimize the proposed algorithm by a scheduling strategy, which effectively schedules the task of part streams ahead while ensuring the overall performance. Finally, we evaluated the performance of our algorithm with various data sets in experiments. The experimental results show that our proposed algorithm achieves better performance than the state-of-the-art method.