面向数据差量压缩的高效压缩率估计方法

doi:10.19678/j.issn.1000-3428.0068595

摘要/Abstract

摘要：

差量压缩不仅会消除数据中相同的数据块, 还会消除数据中相似数据块之间的重复部分, 因此可以实现比数据去重更高的数据压缩率。目前它已经被应用于许多商业产品中。然而, 进一步挖掘数据的可压缩性会额外引入大量的开销, 包括从存储设备中读取相似的数据块以获知它们的重复部分, 这使得差量压缩的速度通常只有数据去重的1/7。但是如此大的开销不能保证总是可以得到更好的压缩率, 因为并不是所有的数据都有足够的可压缩性可供挖掘。因此, 当考虑在存储系统中使用差量压缩时, 需要迅速了解当前的数据是否值得进行差量压缩。提出差量压缩估计框架EDCR, 它通过数据块的相似特征值来快速判断它们之间的可压缩性, 从而对数据进行差量压缩的价值做出快速而准确的判断。另外, 该框架引入采样和补偿方案, 进一步提升了压缩率估计的效率和准确性。最终, 在多个真实数据集上的测试表明, EDCR的估计错误率可以控制在1.5%以下。同时, 相对于实际的差量压缩框架, EDCR估计框架在固态硬盘(SSD)上的运行速度快18~24倍, 在机械磁盘(HDD)上的运行速度快16~146倍。

关键词: 差量压缩, 压缩率估计, 相似性特征, 采样, 估计修正

Abstract:

Delta compression not only eliminates identical data chunks but also removes duplicate fragmentations among similar chunks, achieving higher data compression ratios than deduplication. This technique has been integrated into many commercial products. However, further exploitation of data compressibility introduces significant overhead, including reading similar chunks from storage devices to identify their duplicates. Consequently, delta compression typically operates at only one-seventh the speed of deduplication. However, such substantial overhead does not guarantee better compression ratios because not all data possess sufficient compressibility for exploitation. Therefore, when evaluating the implementation of delta compression in storage systems, it is essential to quickly ascertain its applicability for current data. This study proposes a delta compression estimation framework, EDCR, which promptly assesses the compressibility of data chunks based on their similarity features to evaluate the applicability of delta compression accurately. Additionally, the framework incorporates sampling and correction schemes to enhance the efficiency and accuracy of compression ratio estimation. Evaluations conducted on multiple real-world datasets demonstrate that EDCR achieves an estimation error rate of less than 1.5%. Moreover, compared to existing delta compression frameworks, the EDCR estimation framework operates 18-24 times faster on Solid State Disk(SSD) and 16-146 times faster on Hard Disk Drive(HDD).

Key words: delta compression, compression ratio estimation, similarity feature, sampling, estimation correction

邹翔宇, 魏灿, 夏文, 李诗逸. 面向数据差量压缩的高效压缩率估计方法[J]. 计算机工程, 2024, 50(12): 70-82.

ZOU Xiangyu, WEI Can, XIA Wen, LI Shiyi. Efficient Approach of Compression Ratio Estimation for Data Delta Compression[J]. Computer Engineering, 2024, 50(12): 70-82.

https://www.ecice06.com/CN/Y2024/V50/I12/70

图/表 12

图1 EDCR框架

Fig.1 Framework of EDCR

图2 差量压缩和传统压缩运行过程对比

Fig.2 Operation process comparison of delta compression and general compression

图3 GDB数据集上实际压缩率、估计压缩率和错误率分布

Fig.3 The distribution of actual/estimated compression ratio and error rate on the GDB Dataset

图4 全采样和半采样方案示意图

Fig.4 Schematic diagram of all-sampling-based and semi-sampling-based schemes

图5 GDB备份数据集上的差量压缩估计结果(压缩率和错误率)

Fig.5 The evaluation results of delta compression on the GDB Dataset(compression ratio and error rate)

图6 4个真实世界数据集上的差量压缩率估计结果

Fig.6 The evaluation results of delta compression ratio on four real-world datasets

图7 不同介质2个代表数据集上的吞吐量测试结果

Fig.7 Throughput test results on two representative datasets on different media

图8 全采样设计在GDB数据集上的估计结果和吞吐量

Fig.8 The estimation results and throughput of the all-sampling approach on the GDB dataset

图9 使用不同采样率的基于半采样的EDCR框架的估计精度和吞吐量

Fig.9 The estimation accuracy and throughput of semi-sampling-based EDCR with different sampling rates

图10 基于历史信息补偿的EDCR框架在GDB数据集上的实验结果

Fig.10 The experimental results of historic-correction-based EDCR on the GDB dataset

图11 基于采样补偿的EDCR框架在GDB数据集上的实验结果

Fig.11 The experimental results of sampling-based EDCR on the GDB dataset

参考文献 29

1	REINSEL D , RYDNING J , GANTZ J F . Worldwide global data sphere forecast, 2021—2025: the world keeps creating more data-now, what do we do with it all. International Data Corporation Research, 2021, 6 (12): 41- 61.
2	XIA W , JIANG H , FENG D , et al. A comprehensive study of the past, present, and future of data deduplication. Proceedings of the IEEE, 2016, 104 (9): 1681- 1710. doi: 10.1109/JPROC.2016.2571298
3	SHILANE P, WALLACE G, HUANG M, et al. Delta compressed and deduplicated storage using stream-informed locality[C]//Proceedings of the 4th USENIX Workshop on Hot Topics in Storage and File Systems. Boston, USA: USENIX, 2012: 1-5.
4	XIA W , JIANG H , FENG D , et al. DARE: a deduplication-aware resemblance detection and elimination scheme for data reduction with low overheads. IEEE Transactions on Computers, 2016, 65 (6): 1692- 1705. doi: 10.1109/TC.2015.2456015
5	ZOU X Y, XIA W, SHILANE P, et al. Building a high-performance fine-grained deduplication framework for backup storage with high deduplication ratio[C]//Proceedings of 2022 USENIX Annual Technical Conference. Carlsbad, USA: USENIX, 2022: 19-36.
6	Vast Data. Universal storage explained[EB/OL]. [2023-09-20]. https://vastadata.com/.
7	Huawei. Smartdedupe and smart compression feature guide for block[EB/OL]. [2023-09-20]. https://info.support.huawei.com/storage/docs/en-us/dorado-6.1.2/smartdedupe-smartcompression-userguide-block/SmartDedupe_block_006.html/.
8	MUTHITACHAROEN A, CHEN B J, MAZIōRES D. A low-bandwidth network file system[C]//Proceedings of the 18th ACM Symposium on Operating Systems Principles. New York, USA: ACM Press, 2001: 174-187.
9	冯丹. 大数据时代存储相关技术研究(二). 智能物联技术, 2021, 4 (1): 1- 8.
	FENG D . Storage technologies in the big data era. Technology of IoT AND AI, 2021, 4 (1): 1- 8.
10	田磊, 冯丹, 岳银亮, 等. 磁盘存储系统节能技术研究综述. 智能物联技术, 2010, 37 (9): 1- 5.
	TIAN L , FENG D , YUE Y L , et al. Survey on energy-saving technologies of disk-based storage systems. Technology of IoT & AI, 2010, 37 (9): 1- 5.
11	QUINLAN S, DORWARD S. Venti: a new approach to archival storage[C]//Proceedings of the 1st USENIX Conference on File and Storage Technologies. Monterey, USA: USENIX, 2002: 89-101.
12	夏文. 数据备份系统中冗余数据的高性能消除技术研究[D]. 武汉: 华中科技大学, 2014.
	XIA W. Research on high performance elimination technology of redundant data in data backup system[D]. Wuhan: Huazhong University of Science and Technology, 2014. (in Chinese)
13	WILDANI A, MILLER E L, RODEH O. HANDS: a heuristically arranged non-backup in-line deduplication system[C]//Proceedings of the 29th International Conference on Data Engineering. Washington D. C., USA: IEEE Press, 2013: 446-457.
14	YOU L L, POLLACK K T, LONG D D E. Deep store: an archival storage system architecture[C]//Proceedings of the 21st International Conference on Data Engineering. Washington D. C., USA: IEEE Press, 2005: 804-815.
15	周玉坤, 冯丹, 夏文, 等. 面向数据去重的基于二次哈希的收敛加密策略. 计算机工程与科学, 2016, 38 (9): 1755- 1762.
	ZHOU Y K , FENG D , XIA W , et al. A twice-hash based convergent encryption strategy for data deduplication. Computer Engineering & Science, 2016, 38 (9): 1755- 1762.
16	Wikipedia. Data deduplication[EB/OL]. [2023-09-20]. https://en.wikipedia.org/wiki/Data_deduplication.
17	DOUGLIS F, IYENGAR A. Application-specific delta-encoding via resemblance detection[C]//Proceedings of the 2003 USENIX Annual Technical Conference. San Antonio, USA: USENIX, 2003: 113-126.
18	BRODER A Z. On the resemblance and containment of documents[C]//Proceedings of SEQUENCES'97. Washington D. C., USA: IEEE Press: 21-29.
19	MACDONALD J. File system support for delta compression[D]. Berkeley, USA: University of California at Berkeley, 2000.
20	ZOU X Y, DENG C, XIA W, et al. Odess: speeding up resemblance detection for redundancy elimination by fast content-defined sampling[C]//Proceedings of the IEEE 37th International Conference on Data Engineering. Washington D. C., USA: IEEE Press, 2021: 480-491.
21	KARP R M , RABIN M O . Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 1987, 31 (2): 249- 260. doi: 10.1147/rd.312.0249
22	XIA W , JIANG H , FENG D , et al. Ddelta: a deduplication-inspired fast delta compression approach. Performance Evaluation, 2014, 79, 258- 272. doi: 10.1016/j.peva.2014.07.016
23	NI F, JIANG S. RapidCDC: leveraging duplicate locality to accelerate chunking in CDC-based deduplication systems[C]//Proceedings of the ACM Symposium on Cloud Computing. New York, USA: ACM Press, 2019: 220-232.
24	WAN B, PU L F, ZOU X Y, et al. SuperCDC: a hybrid design of high-performance content-defined chunking for fast deduplication[C]//Proceedings of the IEEE 40th International Conference on Computer Design. Washington D. C., USA: IEEE Press, 2022: 170-178.
25	CONSTANTINESCU C, LU M H. Quick estimation of data compression and de-duplication for large storage systems[C]//Proceedings of the 1st International Conference on Data Compression, Communications and Processing. Washington D. C., USA: IEEE Press, 2011: 98-102.
26	KATTAN A, POLI R. Genetic-programming based prediction of data compression saving[C]//Proceedings of International Conference on Artificial Evolution. Berlin, Germany: Springer, 2010: 182-193.
27	MOULTON S. NetApp data compression and deduplication deployment and implementation guide[EB/OL]. [2023-09-20]. https://www.netapp.com/media/19753-tr-3966.pdf.
28	ZIV J , LEMPEL A . A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 1977, 23 (3): 337- 343. doi: 10.1109/TIT.1977.1055714
29	ZIV J , LEMPEL A . Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 1978, 24 (5): 530- 536. doi: 10.1109/TIT.1978.1055934

[1]	张玉鑫, 张雷, 欧冬秀. 面向磁浮轨道的多源点云数据的混合滤波方法[J]. 计算机工程, 2024, 50(9): 54-62.
[2]	汤志康, 武毓琦, 李春英, 汤庸. 基于知识图谱卷积网络的学习资源推荐[J]. 计算机工程, 2024, 50(9): 153-160.
[3]	郑秋梅, 赵丹, 牛薇薇, 林超. 基于多通道的彩色图像多重水印算法[J]. 计算机工程, 2024, 50(9): 246-254.
[4]	李云航, 潘晴, 田妮莉. 结构相似度优化的混合多尺度医学图像融合[J]. 计算机工程, 2024, 50(7): 264-270.
[5]	范晓宇, 贾新春, 李彬, 谢云飞. 多率采样机制下多智能体动态事件触发二分一致性研究[J]. 计算机工程, 2024, 50(3): 114-121.
[6]	薛羽, 卢畅畅. 基于有偏采样的连续进化神经架构搜索[J]. 计算机工程, 2024, 50(2): 91-97.
[7]	安峰民, 张冰冰, 董微, 张建新. 面向视频行为识别深度模型的数据预处理方法[J]. 计算机工程, 2024, 50(2): 281-287.
[8]	张旭, 陈慈发, 董方敏. 基于改进YOLOv7的PCB缺陷检测算法[J]. 计算机工程, 2024, 50(12): 318-328.
[9]	刘大兴, 顾乃杰, 黄章进, 苏俊杰, 齐东升. 一种用于软件预取的访存轨迹采样算法[J]. 计算机工程, 2024, 50(10): 362-369.
[10]	刘嘉杰, 刘国平, 胡文山. 基于电机数据图像化的多时序变量间接卡车误吊起检测[J]. 计算机工程, 2024, 50(10): 370-380.
[11]	沈志东, 岳恒宪. 基于分布式扰动的文本对抗训练方法[J]. 计算机工程, 2023, 49(9): 16-22.
[12]	张欣怡, 张飞, 郝斌, 高鹭, 任晓颖. 基于改进YOLOv5的口罩佩戴检测算法[J]. 计算机工程, 2023, 49(8): 265-274.
[13]	高峰, 李秋, 顾进广. 基于图结构特征采样数据摘要的联邦知识图谱查询[J]. 计算机工程, 2023, 49(1): 73-81.
[14]	孙扬威, 戚湧. 基于聚类混合采样与PSO-Stacking的车载CAN入侵检测方法[J]. 计算机工程, 2023, 49(1): 138-145.
[15]	于长志, 张连新, 孙鹏飞, 陈东生, 宋颖慧, 姚云飞, 李炼, 李代杨. 基于法向约束的背靠视觉端面对接定位方法[J]. 计算机工程, 2022, 48(9): 213-222,229.

选择文件类型/文献管理软件名称

选择包含的内容