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

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

Abstract

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

CLC Number:

TP302.8

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.

Figures/Tables 10

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 26

Related Articles 5

Metrics

Recommended 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]	Junfeng TIAN, Qianyu YANG, Xiao Jitian. Distributed audit causal consistency model based on biased stability [J]. Journal on Communications, 2023, 44(3): 164-177.
[2]	Guangjun LIU, Wangmei GUO, Jinbo XIONG, Ximeng LIU, Changyu DONG. Lightweight privacy protection data auditing scheme for regenerating-coding-based distributed storage [J]. Journal on Communications, 2021, 42(7): 220-230.
[3]	Junfeng TIAN, Juntao ZHANG, Yanbiao WANG. Distributed storage causal consistency model with trusted constraint [J]. Journal on Communications, 2021, 42(6): 145-157.
[4]	Junfeng TIAN,Yanbiao WANG,Xinfeng HE,Juntao ZHANG,Wanhe YANG,Ya’nan PANG. Survey on the causal consistency of data [J]. Journal on Communications, 2020, 41(3): 154-167.
[5]	Zhan-zhan GAO,Guang-ming TANG,Wei-wei ZHANG. Anti-packet-loss joint encoding for voice-over-IP steganography [J]. Journal on Communications, 2016, 37(11): 146-155.