非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

中图分类号:

TP302.1

聂世强,郑旭达,刘钊华,伍卫国,董小社,张兴军. 非MDS码存储系统的通用可靠性模型[J]. 西安电子科技大学学报, 2021, 48(4): 113-119.

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.

图/表 7

图1

表1

图2

图3

图4

图5

图6

参考文献 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	非最大距离可分码临界可容错值