Rededup: Data Reallocation for Reading Performance Optimization in Deduplication System

Deduplication technology has been increasingly used to reduce the storage cost. In practice, it often causes additional on-disk fragments that impair the reading performance. To reduce the impact of fragments, traditional thought of defragmentation that reallocating files on-disk to achieve contiguous layout has been widely used in many operating systems. Unfortunately, file defragmentation is highly constrained by block sharing in deduplication system which makes it impossible for all files to have a perfect sequential on-disk layout. In this paper, we propose ReDedup which performs data reallocation in deduplication storage, with a goal to mitigate the impact of disk fragments. ReDedup is motivated by the observation of real world I/O workloads: non-uniform access frequency distribution of duplicated data. Leveraging this data skew, ReDedup can make a majority of I/O requests more sequential by eliminating the fragments of hot files and shifting them to the rarely read files. To achieve its objective, ReDedup dynamically estimates the access randomness and block sharing relationship, of individual files based on the history I/O activity, and then uses a greedy algorithm to selectively reallocate and place files sequentially on the disk. Our experimental evaluation of ReDedup prototype based on real-world datasets shows that ReDedup speeds up the reading performance by a factor of 28%-40%.