论文部分内容阅读
随着数据规模的爆炸式增长,传统的集中式存储系统已不再能满足日益增长的存储需求。分布式存储系统因具有高可靠性、可扩展性、廉价性等优点因而在大数据中心,P2P存储系统等方面得到了广泛的应用。为确保可靠性,冗余对这些系统来说是至关重要的。常见的生成冗余数据的方法是采用纠删码,它能高效的存储数据且能抵抗节点失效。然而,传统的纠删码如RS (Reed-Solomon)码等MDS(Maximum Distance Separable)码的修复带宽太大。为了刻画存储开销和修复带宽,Dimakis等人给出了在功能修复下的存储-修复带宽的最优折中,得到了给定存储开销下的最小(优)修复带宽,并提出了最小存储再生(Minimum Storage Regenerating MSR)码,即具有最优修复性质的MDS存储码。目前大多数已知的高码率MDS存储码只有系统节点能被最优修复,且有些高码率MDS存储码在其它方面如更新性质、存取性质、系统节点的个数存在不足,而已知的高码率MSR码(即所有节点均能被最优修复的MDS存储码)非常稀少。本文给出了多类性质优良的系统节点具有最小修复带宽的高码率MDS存储码的构造,以及给出现有高码率MDS存储码校验节点的最优修复策略。首先,基于一种基集合的划分方法,提出了高码率MDS存储码的一种构造框架,并在该框架的一般性构造方法下,重新解释了 Hadamard design码等四类已知的高码率MDS存储码。其次,给出了五类具有较多系统节点、具有最优存取/更新性质的(k+2,k)MDS存储码,且其所需的有限域大小均已被确定。其中在给定的节点容量下,第一类码是目前系统节点个数最多的高码率MDS存储码,第三类和第四类码是目前具有最优更新性质的MDS存储码中系统节点个数最多的码,第五类码是目前具有最优存取性质且系统节点个数达到理论上界的码中所需有限域最小的MDS存储码。再次,给出了一种转换系统节点具有最优修复性质的高码率MDS存储码为MSR码的一般方法,该方法得到的新MSR码的校验节点具有最优存取性质,且能保持之前的MDS存储码的其他优良性质,如:有限域的大小,系统节点的最优存取性质。此外,该转换方法也能应用于系统节点不具有最优修复性质的MDS存储码。将该转换方法应用于已知的MDS存储码时与已知的Piggyback码和Ye-Barg码相比具有明显的优势,即1)校验节点具有最优修复性质,而已知的Piggyback码的校验节点不具有最优修复性质;2)在某些情况下相比Ye-Barg码,所需的有限域和节点容量更小。最后,讨论了(k+2, k) Zigzag码校验节点的修复方法。给出了一种改造(k +2,k) Zigzag码的方法,使得改造后的码的校验节点也能被最优修复且具有最优存取性质,同时保持系统节点的最优存取性质。该改造方法只需将(k+2,k)Zigzag码的节点容量扩大一倍,相比Wang等人需将(k+2,k) Zigzag码的节点容量扩大三倍的改造方法具有明显优势。此外,通过迭代以矩阵形式给出了 (k+2,k)Zigzag码的构造方法,并基于矩阵表示方法,给出了一种(k + 2,k) Zigzag码校验节点的最优修复方法。