分布式存储系统的MDS阵列码的研究

发布时间：2020-03-27 06:22

【摘要】：随着现代社会数据信息量的迅猛增加,现代存储系统的可靠性受到严重的挑战。提高存储系统的可靠性的主要方法是通过增加冗余信息来提高容错能力。增加冗余信息的方法有两种,一种是多副本方法,另一种是采用纠删码方法。由于多副本方法的存储开销很大,难以满足海量数据存储的要求,因此现代存储技术常使用纠删码的方式来提高数据的可靠性和可用性。在纠删码技术中,阵列码是一种不错的技术,采用简单的异或操作来进行运算,容易实现,应用广泛。当阵列码满足Maximum Distance Seperable(MDS)特性时,可以达到理论上最优的存储利用率。本文对MDS阵列码进行研究,首先针对BBV编码的参数条件,在现有的下限值情况,进行优化其下限值的研究工作。其次,对EVENODD码的拓展码,EVENODD(p,3)码的修复问题进行研究。由于在现实情况下,单个数据列丢失的情况最为常见,为此本文重点研究EVENODD(p,3)码单列数据列的修复问题。最后,从理论上分析EVENODD(p,4)码和RDP(p,4)码在修复单列数据列丢失时的信息位读取量。本文以阵列码为研究目标,重点研究其在满足MDS特性和单列数据修复方面的情况。本文的主要工作有:1.针对具有超过8列检验列的BBV码,在要满足MDS特性的条件下,优化其参数p的数学条件。结果表明,经过本文工作所优化的参数p的下限值比已有的结果要低很多,这使得具有超过8列检验列的BBV码在满足MDS特性条件下,其参数条件更为紧凑。2.从理论上推导出EVENODD(p,3)码单列数据列丢失时,其在修复时的最小信息位读取量,并且给出一种对EVENODD(p,3)码单列数据列丢失时的修复方案,该方案在修复单个数据丢失列时,所需的信息位读取量要优于EVENODD码的最小信息位读取量。3.从理论上对EVENODD(p,4)码和RDP(p,4)码在单列数据列丢失时,分析它们在修复时的信息位读取量。对比分析EVENODD码、EVENODD(p,3)码和EVENODD(p,4)码在修复单列数据列丢失时的信息位读取量。对比分析RDP码、RDP(p,3)码和RDP(p,4)码在修复单列数据列丢失时的信息位读取量。
【图文】：

示意图,示意图,斜率,复杂度

图 2-1 EVENODD 码的编码示意图（p=5）有研究表明，EVENODD 码的编码复杂度为 k 1/2，而修复复杂度为 k，接近理论下界值 k-1，但是它的更新复杂度比较高，约为 3，是理论下界的 1.5 倍。虽然 EVENODD 只有两列校验列，第一列称为水平校验列，也称斜率为 0 的校验列。第二列称为对角线校验列，也称斜率为 1 的校验列。在参考文献[32]中，EVENODD码的作者通过追加其他斜率对角线所运算得到的校验列，进一步把 EVENODD 码拓展

示意图,示意图,编码复杂度,下界

图 2-2 RDP 码的编码示意图（p=5）在参考文献[36]中，Mario Blaum 把类似 EVENODD 码的拓展码的生成方法，运用到 RDP 码上，最终形成具有纠正多列丢失能力的 RDP 码的拓展码。有趣的一件事是日本的研究人员基于循环置换矩阵的方式来定义 RDP 码的拓展码[37]，并且与 MarBlaum 在同一届的 ISIT 会议上提出 RDP 码的推广码的概念。类似于 EVENODD 码的拓展码，RDP 码的拓展码只有在 r =3时才确定是 MDS 码，在 r ≥4时，还需参数 p 满足一定的条件才能是 MDS 码。Liberation 码在 2008 年的 FAST 会议上首次提出的 Liberation 码[38]，其更新复杂度是所有水平阵列码中最低的，接近理论下界 2。Liberation 码是一个 p × ( p+2)的二维阵列，p 为素数。它的编码复杂度与 EVENODD 码差不多，当数据列数为 k 时，其编码复杂度为k 1 +(k 1)/(2p)，当 p 远远大于 k 时，，则编码复杂度接近下界 k-1。但是，Liberatio
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP333

【参考文献】