稀疏随机纠删码:一种大规模数据存储容灾方法

发布时间：2019-11-06 22:04

【摘要】：针对海量数据存储容灾系统中对扩展性、可靠性及高效性方面的需求,提出了一种高容灾可扩展且能够高概率译码恢复的高效大数据存储容灾算法。该算法利用等行重稀疏随机矩阵高概率行满秩的性质,用来实现数据高效可靠的存储容灾。首先,根据存储系统规模及容灾需求设置相应的编码参数;然后,采用等行重稀疏随机矩阵构造校验矩阵,并且产生相应的生成矩阵;最后,将数据文件分块编码到n个存储节点上,实现不同规模、不同容灾需求下的数据容灾存储,并通过设置合理的随机冗余,从而实现对译码成功率的控制。实验和理论分析表明:算法所提存储容灾技术可实现容灾能力不受素数或有限域大小的限制,而是根据存储规模及容灾需求灵活扩展;基于合理的随机冗余,译码成功率趋于1,实现了高可靠的数据容灾存储;在较大规模存储系统中,算法编译码速率是相应经典RS和CRS编码方案的2倍以上,并在较大码长下具有近似最大距离可分(MDS)的性质,可达到近似最优的存储空间利用率。
【图文】：

模型图,存储系统,模型,纠删码

大数据时代高效、易扩展存储系统的需求，本文提出了稀疏随机纠删码（ＳＲＥＣ），这是一种概率性纠删码存储容灾技术，其编码参数不受素数或有限域大小限制可灵活设置，具有较高的容灾扩展性能；采用等行重稀疏随机矩阵作为校验矩阵，具有较高的计算效率；在较大码长下能够达到近似的ＭＤＳ性质，从而具有较高的存储空间利用率，非常适用于当前大规模存储容灾系统。１系统模型当前的大规模存储系统可抽象为由无数个存储节点构成的整体，每个节点均相互独立，而待存文件则可抽象为一个数据块，存储系统模型如图１所示。该系统由ｎ个存储节点构成，每个存储节点可以是一个磁盘或ＲＡＩＤ阵列，数据文件Ａ首先被分为ｋ个大小相同的数据块，随后通过编码产生ｍ个冗余数据块，最后将这ｋ＋ｍ个数据块存放在ｎ个存储节点上，从而实现任意ｔ个存储节点的失效，可利用剩余的ｎ－ｔ个节点高概率恢复出原来ｔ个节点的数据。图１存储系统模型稀疏随机纠删码的编码参数不再受到素数或有限域大小的限制，因此其容灾能力也可以自由设置，从而达到更高的容灾性能，而存储系统中随机冗余的节点数δ是保证稀疏随机纠删码能够高概率译码的一个关键因素。此外，，由于采用特殊稀疏随机矩阵作为校验矩阵，稀疏随机纠删码在译码效率上有了较大的提升，这为频繁发生的译码恢复提供了效率保障。本文所提稀疏随机纠删码利用特殊稀疏随机矩阵的性质，其定义和相关性质如下。定义有限域ＧＦ（２）上的矩阵Ｒｔ×ｍ，ｍ＞ｔ＞０，若其中的各个元素取值相互独立，且满足分布规律Ｑ｛ｅｉｊ＝ｑ｝＝ｐ，ｑ＝１１－ｐ，ｑ＝｛０，ｐ∈（０

矩阵,随机矩阵,纠删码,概率

上和数据的容灾恢复上，即存储系统的译码成功率上，根据稀疏随机纠删码的译码算法，可知译码成功率取决于等行重稀疏随机子矩阵行满秩的概率，因此可通过实验分析等行重稀疏随机矩阵行满秩的概率来增强对稀疏随机纠删码可靠性的认识。首先讨论ｔ×ｍ等行重稀疏随机矩阵Ｒｔ×ｍ行重对行满秩概率的影响。选取ｍ＝｛３２，６４，１２８，２５６，５１２｝，ｔ＝ｍ－δ，随机冗余δ＝２０，行重ｄ＝１～１５（间隔１），测试对应稀疏随机矩阵Ｒｔ×ｍ行满秩的情况，结果如图２所示。由图２可知，随着行重的增加，等行重稀疏随机矩阵行满秩的概率不断增加，当ｄ≥ｌｂｍ时，相应等行重稀疏随机矩阵行满秩的概率几乎等于１，同时稀疏随机纠删码的译码成功率也趋于１，从而保证了存储容灾系统译码恢复的高可靠性。因此，为了即保持较高的译码成功率，又保持较高的译码速率，即较低的稀疏度，一般选取略大于ｌｂｍ的行重。图２行重对矩阵行满秩的影响此外，行重ｄ的奇偶性对等行重稀疏随机方阵Ｒｔ×ｔ的满秩概率有着重要的影响。选取ｔ＝｛３２，６４，１２８，２５６，５１２｝，行重ｄ＝１～１５（间隔１）构造等行重稀疏随机方阵Ｒｔ×ｔ，编译码速率比较如图３所示。由图３可知，稀疏随机方阵Ｒｔ×ｔ在行重ｄ为奇数且ｄ≥ｌｂｍ时，Ｒｔ×ｔ满秩的概率较高，约为０．２８９，而当行重ｄ为偶数时，稀疏随机方阵Ｒｔ×ｔ满秩的概率则５１

【相似文献】