EUVIMEDEUVIMED entdecken
Crossref

The Design of Fast Delta Encoding for Delta Compression Based Storage Systems

Haoliang Tan, Wen Xia, Xiangyu Zou, Cai Deng, Qing Liao, Zhaoquan Gu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →