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

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

Sparse Random Erasure Code:a Fault Tolerance Scheme for Large-Scale Storage System