Reducing Fragmentation for In-line Deduplication Backup Storage via Exploiting Backup History and Cache Knowledge

Min Fu, Dan Feng, Yu Hua, Xubin He, Zuoning Chen, Jingning Liu, Wen Xia, Fangting Huang, Qing Liu

Abstract

In backup systems, the chunks of each backup are physically scattered after deduplication, which causes a challenging fragmentation problem. We observe that the fragmentation comes into sparse and out-of-order containers. The sparse container decreases restore performance and garbage collection efficiency, while the out-of-order container decreases restore performance if the restore cache is small. In order to reduce the fragmentation, we propose History-Aware Rewriting algorithm (HAR) and Cache-Aware Filter (CAF). HAR exploits historical information in backup systems to accurately identify and reduce sparse containers, and CAF exploits restore cache knowledge to identify the out-of-order containers that hurt restore performance. CAF efficiently complements HAR in datasets where out-of-order containers are dominant. To reduce the metadata overhead of the garbage collection, we further propose a Container-Marker Algorithm (CMA) to identify valid containers instead of valid chunks. Our extensive experimental results from real-world datasets show HAR significantly improves the restore performance by 2.84-175.36 × at a cost of only rewriting 0.5-2.03 percent data.
BibTeX
@article{fu2016reducing,
  author = {Min Fu and Dan Feng and Yu Hua and Xubin He and Zuoning Chen and Jingning Liu and Wen Xia and Fangting Huang and Qing Liu},
  title = {{Reducing Fragmentation for In-line Deduplication Backup Storage via Exploiting Backup History and Cache Knowledge}},
  journal = {IEEE TPDS},
  year = {2016},
  doi = {10.1109/tpds.2015.2410781},
}

Loading related content...

Figure