非MDS码存储系统的通用可靠性模型

doi:10.19665/j.issn1001-2400.2021.04.015

Abstract

Abstract:

An open problem is how different configurations influence the reliability of a storage system using non-maximum distance separable codes as redundancy strategy.This paper proposes a repairable probability algorithm for solving data objects with non-maximum distance separable code encoding by considering the construction matrix of non-maximum distance separable codes.This algorithm exhaustively loses all possible combinations of several blocks and judges whether the matrix corresponding to each combination is reversible for calculating the probability of recoverability.We propose an analytical model based on the Markov chain to quantify the reliability of the non-maximum distance separable coded storage system.This model could quantify the impact of a series of design factors on the reliability of the storage system,such as the effect of non-maximum distance separable code configuration,the capacity of the storage system,the capacity of the object-based storage device nodes,the repair bandwidth,the mean time to data loss of the object-based storage device nodes and so on.Finally,the numerical analytical method is used to verify the correctness of the model and the influence of different factors on the reliability of the storage system.Our model enables system practitioners to decide the appropriate configuration based on their reliability requirements.

Key words: storage system, reliability, non-maximum distance separable code, markov model, mean time to data loss

CLC Number:

TP302.1

NIE Shiqiang,ZHENG Xuda,LIU Zhaohua,WU Weiguo,DONG Xiaoshe,ZHANG Xingjun. General reliability model of the non-MDS coded storage system[J].Journal of Xidian University, 2021, 48(4): 113-119.

Figures/Tables 7

References 20

[1]	FORD D, LABELLE F, POPOVICI F I, et al. Availability in Globally Distributed Storage Systems[C]//Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation.Piscataway:IEEE, 2010:1-7.
[2]	XU E, ZHENG M, QIN F, et al. Lessons and Actions:What We Learned from 10k SSD-Related Storage System Failures[C]//Proceedings of the 2019 USENIX Annual Technical Conference.Piscataway:IEEE, 2019:961-976.
[3]	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 Presented as Part of the 5th USENIX Workshop on Hot Topics in Storage and File Systems.Piscataway:IEEE, 2013: 8.
[4]	KADEKODI S, RASHMI K V, GANGER G R, et al. 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.Piscataway:IEEE, 2019 :345-358.
[5]	王意洁, 许方亮, 裴晓强. 分布式存储中的纠删码容错技术研究[J]. 计算机学报, 2017, 40(1) :236-255.
	WANG Yijie, XU Fangliang, PEI Xiaoqiang. Research on Error-Tolerance Technology of Error Correcting Codes in Distributed Storage[J]. Chinese Journal of Computers, 2017, 40(1) :236-255.
[6]	CHEN Y, MU S, LI J, et al. Giza:ErasureCoding Objects Across Global Data Centers[C]//Proceedings of the 2017 USENIX Annual Technical Conference(ATC 17).Piscataway:IEEE, 2017:539-551.
[7]	DOBRE D, VIOTTI P, VUKOLI M. Hybris:Robust Hybrid Cloud Storage[C]//Proceedings of the ACM Symposium on Cloud Computing.New York:ACM, 2014:1-14.
[8]	ULUYOL M, HUANG A, GOEL A, et al. Near-Optimal Latency Versus Cost Tradeoffs in Geo-Distributed Storage[C]//Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation.Piscataway:IEEE, 2020:157-180.
[9]	李静, 王刚, 刘晓光, 等. 存储系统可靠性预测综述[J]. 计算机科学与探索, 2017, 11(3):341-354.
	LI Jing, WANG Gang, LIU Xiaoguang, et al. Review of Reliability Prediction for Storage System[J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(3):341-354.
[10]	PATTERSON D A, GIBSON G, KATZ R H. A Case for Redundant Arrays of Inexpensive Disks (RAID)[C]//Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data.New York:ACM, 1988:109-116.
[11]	CARNS P, HARMS K, JENKINS J, et al. Impact of Data Placement on Resilience in Large-Scale Object Storage Systems[C]//Proceedings of the 2016 32nd Symposium on Mass Storage Systems and Technologies(MSST).Piscataway:IEEE, 2016:1-12.
[12]	ZHANG M, HAN S J, LEE P P C. SimEDC:A Simulator for the Reliability Analysis of Erasure-Coded Data Centers[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(12):2836-2848. doi: 10.1109/TPDS.71
[13]	穆飞, 薛巍, 舒继武, 等. 一种面向大规模副本存储系统的可靠性模型[J]. 计算机研究与发展, 2009, 46(5):756-761.
	MU Fei, XUE Wei, SHU Jiwu, et al. Reliability Model for Large-Scale Copy Storage System[J]. Journal of Computer Research and Development, 2009, 46(5):756-761.
[14]	HUANG C, SIMITCI H, XU Y, et al. Erasure Coding in Windows Azure Storage[C]//Proceedings of the 2012 USENIX Annual Technical Conference (USENIX ATC 12).Piscataway:IEEE, 2012:15-26.
[15]	SHAHABINEJAD M, KHABBAZIAN M, ARDAKANI M. A Class of Binary Locally Repairable Codes[J]. IEEE Transactions on Communications, 2016, 64(8):3182-3193. doi: 10.1109/TCOMM.2016.2581163
[16]	TAMO I, BARG A, FROLOV A. Bounds on the Parameters of Locally Recoverable Codes[J]. IEEE Transactions on Information Theory, 2016, 62(6):3070-3083. doi: 10.1109/TIT.2016.2518663
[17]	HAFNER J L. WEAVER Codes:Highly Fault Tolerant Erasure Codes for Storage Systems[C]//Proceedings of the 4th USENIX Conference on File and Storage Technologies.Piscataway:IEEE, 2005: 16.
[18]	HU Y, LIU Y, LI W, et al. Unequal Failure Protection Coding Technique for Distributed Cloud Storage Systems[J]. IEEE Transactions on Cloud Computing, 2021, 9(1):386-400. doi: 10.1109/TCC.6245519
[19]	郝晓慧, 车书玲, 张欣瑜. LRC码最小距离限的深入分析[J]. 西安电子科技大学学报, 2018, 45(5):75-79.
	HAO Xiaohui, CHE Shuling, ZHANG Xinyu. In-depth Analysis of the Minimum Distance Limit of LRC Codes[J]. Journal of Xidian University, 2018, 45(5):75-79.
[20]	HAFNER J L, RAO K K. Notes on Reliability Models for Non-MDS Erasure Codes[R]. New York:IBM, 2006.

变量名	含义
c	系统存储容量
n	对象存储设备节点数目
r	单对象存储设备节点失效速率
b	单对象存储设备节点修复带宽
d	非最大距离可分码的数据块数目
p	非最大距离可分码的校验块数目
k	非最大距离可分码临界可容错值

General reliability model of the non-MDS coded storage system

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 20

Related Articles 15

Metrics

Comments

Recommended 10

[1]	ZHANG Fei,MA Shiping,ZHANG Lichao,HE Linyuan,QIU Zhuling,HAN Yongsai. Joint spatial reliability and correlation filter learning for visual tracking [J]. Journal of Xidian University, 2021, 48(5): 167-177.
[2]	LIU Naian,CHEN Zhihao,LIU Guokun,LI Yang. Mechanism for proof-of-reputation consensus for blockchain validator nodes [J]. Journal of Xidian University, 2020, 47(5): 57-62.
[3]	SUN Qian,ZHANG Jiarui,GAO Ling,WANG Yuxiang,YANG Jianfeng. Health prediction algorithm for edge layer nodes [J]. Journal of Xidian University, 2020, 47(3): 32-39.
[4]	CAO Yi,HUANG Zilong,ZHANG Wei,LIU Chen,LI Wei. Urban sound event classification with the N-order dense convolutional network [J]. Journal of Xidian University, 2019, 46(6): 9-16.
[5]	JIA Dingcheng,WANG Leilei,GAO Wei. Analysis and detection of TDDB degradation for DRAM in 3D-ICs [J]. Journal of Xidian University, 2019, 46(4): 182-189.
[6]	QI Xiaogang, MA Jiulong, LIU Lifang. Topology control with a high reliability and low transmission overhead in DTN [J]. Journal of Xidian University, 2018, 45(5): 7-12.
[7]	HAO Xiaohui;CHE Shuling;ZHANG Xinyu. In-depth analysis of bounds on the minimum distance of LRCs [J]. Journal of Xidian University, 2018, 45(5): 75-79+135.
[8]	ZOU Hong;CHEN Xiao. Multi-path reliable transmission mechanism in the virtualized integrated fiber-wireless access network [J]. Journal of Xidian University, 2018, 45(5): 121-127+148.
[9]	XIONG Yu;LI Zhiqiang;YANG Yaya. Dynamic cross-layer protection strategy in optical inter-datacenter networks [J]. Journal of Xidian University, 2018, 45(3): 136-142.
[10]	FANG Min;ZHOU Shuyue;CHEN Yongmei;WANG Hongchun;QIU Zheng;ZHANG Zhendong;XIAO Chenguang. Variable sorting based on fault tree structure adjustment for multi-valued decision diagrams [J]. Journal of Xidian University, 2017, 44(6): 20-25+36.
[11]	JIN Hongling;GUO Chengyang;CHEN Jun;CHEN Jianjun. Dynamic reliability analysis of spacial flexible beam [J]. Journal of Xidian University, 2017, 44(6): 138-143.
[12]	LIN Feng;CHEN Jianjun;CAO Hongjun. Probabilistic and interval reliability design of the composite pressure vessel [J]. Journal of Xidian University, 2017, 44(1): 45-51.
[13]	LIU Shuaijie;DUAN Baoyan;YANG Dongwu. Interval and probability based analysis of seizure-preventing for synchronous gears of the astromesh deployable satellite antenna [J]. Journal of Xidian University, 2016, 43(3): 61-66.
[14]	SUN Jian;ZHANG Xingjun;DONG Xiaoshe. Availability evaluation model for the heterogeneous system based on RBD [J]. Journal of Xidian University, 2016, 43(3): 190-196.
[15]	JING Weipeng;WU Zhibo;LIU Hongwei;SHU Yanjun. Multiple DAGs dynamic workflow reliability scheduling algorithm in a cloud computing system [J]. Journal of Xidian University, 2016, 43(2): 83-88.