xStripeMerge：基于纠删码存储的高效宽条带生成方法

doi:10.11959/j.issn.1000-436x.2023217

通信学报 ›› 2023, Vol. 44 ›› Issue (11): 213-224.doi: 10.11959/j.issn.1000-436x.2023217

• 学术论文 • 上一篇

xStripeMerge：基于纠删码存储的高效宽条带生成方法

郑美光, 化韬斐, 张心宇, 胡志刚

中南大学计算机学院，湖南长沙 410083

修回日期:2023-10-24 出版日期:2023-11-01 发布日期:2023-11-01
作者简介:郑美光（1983− ），女，江西新余人，博士，中南大学副教授、硕士生导师，主要研究方向为云边计算、云存储、联邦学习
化韬斐（1998− ），男，山西介休人，中南大学硕士生，主要研究方向为存储编码、分布式存储系统等
张心宇（1992− ），男，湖南浏阳人，中南大学博士生，主要研究方向为云存储、边缘计算和深度强化学习等
胡志刚（1963− ），男，山西孝义人，博士，中南大学教授、博士生导师，主要研究方向为云边计算、机器视觉
基金资助:
国家自然科学基金资助项目(62172442);国家自然科学基金资助项目(62172451);湖南省自然科学基金青年基金资助项目(2020JJ5775)

xStripeMerge: efficient wide stripe generation approach based on erasure coding storage

Meiguang ZHENG, Taofei HUA, Xinyu ZHANG, Zhigang HU

School of Computer Science and Engineering, Central South University, Changsha 410083, China

Revised:2023-10-24 Online:2023-11-01 Published:2023-11-01
Supported by:
The National Natural Science Foundation of China(62172442);The National Natural Science Foundation of China(62172451);Youth Science Foundation of Natural Science Foundation of Hunan Province(2020JJ5775)

摘要/Abstract

摘要：

为了解决纠删码存储系统的已有宽条带生成方法中扩容方案将产生大量宽条带生成带宽，合并方案受限于双条带的问题，提出了一种针对多条带合并下的宽条带生成问题的高效宽条带生成方法。定义了多条带合并过程的2个关键算子，并将宽条带生成问题建模为组合优化问题，提出了优先寻找具有小的奇偶校验块传输成本的窄条带组合方案的高效宽条带生成方法 xStripeMerge。实验结果表明，与目前最优的存储扩容方法相比， xStripeMerge 可以减少 75%宽条带生成带宽。xStripeMerge 的时间和空间复杂度远优于扩展的双条带合并方法， xStripeMerge可以在更短的时间内获得与其性能相近的宽条带生成方案，并且xStripeMerge可以适用于大规模存储系统。

关键词: 分布式存储, 纠删码, 宽条带, 条带合并, 奇偶块对齐

Abstract:

To address the issue of wide stripe generation in existing erasure coding storage systems, where storage scaling approaches resulted in a significant increase in wide stripe generation bandwidth and stripe merge scheme was constrained by dual-stripes, an efficient wide stripe generation approach was proposed for the wide stripe generation problem under multi stripes merging.Two key operators for the multi-stripes merging progress were defined, and the wide stripe generation problem was modeled as a combinatorial optimization problem.The efficient wide stripe generation approach xStripeMerge was proposed that prioritize the search for narrow-stripes combining schemes with small parity block transmission costs.Experimental results show that xStripeMerge can reduce the wide stripe generation bandwidth by 75% compared to the advanced storage scaling method.The time and space complexity of xStripeMerge is much better than that of the extended dual-stripes merge approach.xStripeMerge can get the wide stripe generation scheme with similar performance in a shorter period of time and it is also suitable for large-scale storage systems.

Key words: distributed storage, erasure coding, wide stripe, stripe merge, parity align

中图分类号:

TP302.8

郑美光, 化韬斐, 张心宇, 胡志刚. xStripeMerge：基于纠删码存储的高效宽条带生成方法[J]. 通信学报, 2023, 44(11): 213-224.

Meiguang ZHENG, Taofei HUA, Xinyu ZHANG, Zhigang HU. xStripeMerge: efficient wide stripe generation approach based on erasure coding storage[J]. Journal on Communications, 2023, 44(11): 213-224.

图/表 10

表1

图1

图2

图3

图4

表2

图5

图6

图7

图8

参考文献 26

[1]	KADEKODI S , RASHMI K V , GANGER G R . Cluster storage systems gotta have HeART:improving storage efficiency by exploiting disk-reliability heterogeneity[C]// Proceedings of the 17th USENIX Conference on File and Storage Technologies. New York:ACM Press, 2019: 345-358.
[2]	HU Y C , WANG Y S , LIU B ,et al. Latency reduction and load balancing in coded storage systems[C]// Proceedings of the Symposium on Cloud Computing. New York:ACM Press, 2017: 365-377.
[3]	CALDER B , WANG J , OGUS A ,et al. Windows Azure storage:a highly available cloud storage service with strong consistency[C]// Proceedings of the 23th ACM Symposium on Operating Systems Principles (SOSP). New York:ACM Press, 2011: 143-157.
[4]	ZHANG Y , LI H , LIU S ,et al. PBS:an efficient erasure-coded block storage system based on speculative partial writes[J]. ACM Transactions on Storage, 2020,16(1): 1-25.
[5]	BRAKENSIEK J , GOPI S , MAKAM V . Generic Reed-Solomon codes achieve list-decoding capacity[C]// Proceedings of the 55th Annual ACM Symposium on Theory of Computing. New York:ACM Press, 2023: 1488-1501.
[6]	CORBETT J C , DEAN J , EPSTEIN M ,et al. Spanner:Google’s globally distributed database[J]. ACM Transactions on Computer System, 2013,31(3): 1-22.
[7]	SHVACHKO K , KUANG H R , RADIA S ,et al. The Hadoop distributed file system[C]// Proceedings of IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST). Piscataway:IEEE Press, 2010: 1-10.
[8]	SHEN Z R , LEE P P C . Cross-rack-aware updates in erasure-coded data centers[C]// Proceedings of the 47th International Conference on Parallel Processing. New York:ACM Press, 2018: 1-10.
[9]	MURALIDHAR S , LLOYD W , ROY S ,et al. f4:Facebook’s warm BLOB storage system[C]// Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation. New York:ACM Press, 2014: 383-398.
[10]	OVSIANNIKOV M , RUS S , REEVES D ,et al. The quantcast file system[J]. VLDB Endowment, 2013,6(11): 1092-1101.
[11]	KADEKODI S , SILAS S , CLAUSEN D ,et al. Practical design considerations for wide locally recoverable codes (LRCs)[C]// Proceedings of the 21st USENIX Conference on File and Storage Technologies (FAST). Berkeley:USENIX Association, 2023: 1-16.
[12]	YAO Q R , HU Y C , CHENG L F ,et al. StripeMerge:efficient wide-stripe generation for large-scale erasure-coded storage[C]// Proceedings of IEEE 41st International Conference on Distributed Computing Systems (ICDCS). Piscataway:IEEE Press, 2021: 483-493.
[13]	ZHANG X Y , HU Y C , LEE P P C ,et al. Toward optimal storage scaling via network coding:from theory to practice[C]// Proceedings of IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2018: 1808-1816.
[14]	HUANG J Z , LIANG X H , QIN X ,et al. Scale-RS:an efficient scaling scheme for RS-coded storage clusters[J]. IEEE Transactions on Parallel and Distributed Systems, 2015,26(6): 1704-1717.
[15]	PAMIES-JUAREZ L , BLAGOJEVIC F , MATEESCU R ,et al. Opening the chrysalis:on the real repair performance of MSR codes[C]// Proceedings of the 14th USENIX Conference on File and Storage Technologies. Berkeley:USENIX Association, 2016: 81-94.
[16]	YE L Q , FENG D , HU Y C ,et al. Hybrid codes:flexible erasure codes with optimized recovery performance[J]. ACM Transactions on Storage, 2020,16(4): 1-26.
[17]	魏征, 窦禹, 高艳珍 ,等. 一种基于条带的一致性散列数据放置算法[J]. 计算机研究与发展, 2021,58(4): 888-903.
	WEI Z , DOU Y , GAO Y Z ,et al. A consistent hash data placement algorithm based on stripe[J]. Journal of Computer Research and Development, 2021,58(4): 888-903.
[18]	LIU C J , WANG Q , CHU X W ,et al. ESetStore:an erasure-coded storage system with fast data recovery[J]. IEEE Transactions on Parallel and Distributed Systems, 2020,31(9): 2001-2016.
[19]	HU Y , CHENG L , YAO Q ,et al. Exploiting combined locality for wide-stripe erasure coding in distributed storage[C]// Proceedings of the 19th USENIX Conference on File and Storage Technologies. Berkeley:USENIX Association, 2021: 233-248.
[20]	REN K , KWON Y , BALAZINSKA M ,et al. Hadoop’s adolescence[J]. VLDB Endowment, 2013,6(10): 853-864.
[21]	XIA M Y , SAXENA M , BLAUM M ,et al. A tale of two erasure codes in HDFS[C]// Proceedings of the 13th USENIX Conference on File and Storage Technologies. Berkeley:USENIX Association, 2015: 213-226.
[22]	WU S , DU Q P , LEE P P C ,et al. Optimal data placement for stripe merging in locally repairable codes[C]// Proceedings of IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2022: 1669-1678.
[23]	GHEMAWAT S , GOBIOFF H , LEUNG S T . The Google file system[C]// Proceedings of the nineteenth ACM Symposium on Operating Systems Principles. New York:ACM Press, 2003: 29-43.
[24]	RASHMI K V , SHAH N B , GU D ,et al. A solution to the network challenges of data recovery in erasure-coded distributed storage systems:a study on the Facebook warehouse cluster[C]// Proceedings of the 5th USENIX Workshop on Hot Topics in Storage and File Systems. Berkeley:USENIX Association, 2013:8.
[25]	王意洁, 许方亮, 裴晓强 . 分布式存储中的纠删码容错技术研究[J]. 计算机学报, 2017,40(1): 236-255.
	WANG Y J , XU F L , PEI X Q . Research on erasure code-based fault-tolerant technology for distributed storage[J]. Chinese Journal of Computers, 2017,40(1): 236-255.
[26]	ZHOU H , YANG Y H , LI W P . An erasure code-based approach to improve data recovery and update capability[C]// Proceedings of the International Conference on Mechanical,Electronic,Control and Automation Engineering. Paris:Atlantis Press, 2018: 401-409.

方法	纠删码形式	应用	性能优化方向
设计新型纠删码^[15-16]	单一	适合热数据存储系统	编码性能、数据恢复性能、存储性能
改变条带布局^[17-19]	单一	适合热数据存储系统	数据恢复性能、数据更新性能
冗余转换^[12,21-22]	多种	适合冷、热数据共存的存储系统	存储性能、数据恢复性能

xStripeMerge：基于纠删码存储的高效宽条带生成方法

xStripeMerge: efficient wide stripe generation approach based on erasure coding storage

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 26

相关文章 13

Metrics

推荐阅读 0

条带/组					cost
条带/组	0	1	2		3		4		5	6
4	2	1	0	1	1	0	0	0	0	0
3	0	1	2	0	0	1	1	0	0	0
2	0	0	0	1	1	1	0	2	1	0
1	0	0	0	0	0	0	1	0	1	2

[1]	田俊峰, 杨乾宇, Jitian Xiao. 基于偏向稳定的分布式审计因果一致性模型[J]. 通信学报, 2023, 44(3): 164-177.
[2]	刘光军, 郭网媚, 熊金波, 刘西蒙, 董长宇. 适用于再生编码分布式存储的轻量型隐私保护审计方案[J]. 通信学报, 2021, 42(7): 220-230.
[3]	田俊峰, 张俊涛, 王彦骉. 具有可信约束的分布式存储因果一致性模型[J]. 通信学报, 2021, 42(6): 145-157.
[4]	田俊峰,王彦骉,何欣枫,张俊涛,杨万贺,庞亚南. 数据因果一致性研究综述[J]. 通信学报, 2020, 41(3): 154-167.
[5]	高瞻瞻,汤光明,张伟伟. 面向网络语音隐写的抗分组丢失联合编码[J]. 通信学报, 2016, 37(11): 146-155.
[6]	鄢喜爱,张大方,杨金民,张波云. 面向云存储容错系统的RS再生码[J]. 通信学报, 2016, 37(10): 65-74.
[7]	柳青，冯丹，李白. 基于再生码的云存储系统——Ustor[J]. 通信学报, 2014, 35(4): 19-173.
[8]	柳青,冯丹,李白. 基于再生码的云存储系统——Ustor[J]. 通信学报, 2014, 35(4): 166-173.
[9]	李军,劳凤丹,邹仁明. 校园网云盘系统构建研究[J]. 通信学报, 2013, 34(Z2): 133-137.
[10]	李军，劳凤丹，邹仁明. 校园网云盘系统构建研究[J]. 通信学报, 2013, 34(Z2): 25-137.
[11]	万武南1,2，索望1，陈运2，王拓1. 基于X-RDP阵列码的一种数据分布策略[J]. 通信学报, 2013, 34(Z1): 9-75.
[12]	万武南,索望,陈运,王拓. 基于X-RDP阵列码的一种数据分布策略[J]. 通信学报, 2013, 34(Z1): 67-75.
[13]	唐宏,祝烈煌,李剑,曹瑞强. 抗数据包插入的高效群组数据源认证协议[J]. 通信学报, 2008, 29(11A): 96-100.