The Design of Fast Delta Encoding for Delta Compression Based Storage Systems
ACM Transactions on Storage · 30.11.2024 · 20 (4) · 1-30
DOI: 10.1145/3664817 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Storage, online erschienen am 06.08.2024. Verfasst von Haoliang Tan und 5 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 42 Literaturangaben. Gefördert von: Major Key Project of PCL, National Natural Science Foundation of China, Guangdong Major Project of Basic and Applied Basic Research.
Abstract (Originalsprache)
Delta encoding is a data reduction technique capable of calculating the differences (i.e., delta) among very similar files and chunks. It is widely used for various applications, such as synchronization replication, backup/archival storage, cache compression, and so on. However, delta encoding is computationally costly due to its time-consuming word-matching operations for delta calculation. Existing delta encoding approaches either run at a slow encoding speed, such as Xdelta and Zdelta, or at a low compression ratio, such as Ddelta and Edelta. In this article, we propose Gdelta, a fast delta encoding approach with a high compression ratio. The key idea behind Gdelta is the combined use of five techniques: (1) employing an improved Gear-based rolling hash to replace Adler32 hash for fast scanning overlapping words of similar chunks, (2) adopting a quick array-based indexing for word-matching, (3) applying a sampling indexing scheme to reduce the cost of traditional building full indexes for base chunks’ words, (4) skipping unmatched words to accelerate delta encoding through non-redundant areas, and (5) last but not least, after word-matching, further batch compressing the remainder to improve the compression ratio. Our evaluation results driven by seven real-world datasets suggest that Gdelta achieves encoding/decoding speedups of 3.5X∼25X over the classic Xdelta and Zdelta approaches while increasing the compression ratio by about 10%∼240%.
Förderung
- Major Key Project of PCL
- National Natural Science Foundation of China
- Guangdong Major Project of Basic and Applied Basic Research
- Shenzhen Science and Technology Program
Zitieren
APA
Tan, H., Xia, W., Zou, X., Deng, C., Liao, Q., & Gu, Z. (2024). The Design of Fast Delta Encoding for Delta Compression Based Storage Systems. ACM Transactions on Storage, 20(4), 1-30. https://doi.org/10.1145/3664817
Vancouver
Tan H, Xia W, Zou X, Deng C, Liao Q, Gu Z. The Design of Fast Delta Encoding for Delta Compression Based Storage Systems. ACM Transactions on Storage. 2024;20(4):1-30. doi:10.1145/3664817
BibTeX
@article{Tan2024,
author = {Tan, Haoliang and Xia, Wen and Zou, Xiangyu and Deng, Cai and Liao, Qing and Gu, Zhaoquan},
title = {The Design of Fast Delta Encoding for Delta Compression Based Storage Systems},
journal = {ACM Transactions on Storage},
year = {2024},
volume = {20},
number = {4},
pages = {1--30},
doi = {10.1145/3664817}
}
EUVIMED