论文部分内容阅读
当前社会产生的大量数据需要更好的存储解决方案。近年来，基于网络技术的分布式存储，将数据存储在多个廉价设备上，已经得到了广泛的应用。但是考虑到系统的规模，系统中的构成节点以及其它网络组件故障已经是常见的情况。为了保证数据的可用性，就需要引进一定的冗余，而数据长期的可靠性，则依赖于对丢失冗余的修复。分布式存储系统一般采用复制策略产生冗余。最近，能够提供更好存储效率的纠删码已经被用来减少三副本系统中的大量存储开销。然而在修复过程中，纠删码要从多个节点中下载大量的数据，并不是修复丢失冗余的高效方案。为了解决这个问题，本文提供两种局部性编码技术，以减少修复过程中所需的修复带宽和修复局部性(称修复过程中需要连接的节点数为修复局部性)。
1.通过将(n，k)RS编码和X编码结合，为分布式存储系统设计了一类新的准确修复编码—(n，k,f)X再生码(XRC)，其中RS编码用于提供容忍n-k个节点故障的可靠性，X编码则用在RS编码之上，提供对单个或者两个节点故障的高效准确修复。一个显著的优势是在修复过程中，需要连接的节点数可以设置成与n，k独立的较小常数。文中对X再生码的存储代价、修复带宽、修复局部性和编码率进行了分析，并与RS编码、复制以及SRC进行了对比。结果显示，X再生码在修复一个或者两个节点故障时，在修复局部性以及修复带宽上都具有显著的优势，并能达到任意高的编码率。我们提供了使用马尔科夫模型估计平均数据丢失时间的可靠性分析，对XRC，RS编码，复制的可靠性进行了对比。X再生码的可靠性与RS编码相比有了显著的提升。
2.介绍了另一类新的准确修复编码，由RS编码和复制两部分结合而成，RS编码用于保证分布式系统的(n，k)性质，复制用于保证高效的无编码修复，我们称这种新编码为R再生码。文中主要介绍了两种:基于两副本的(n，k，2)-R再生码，以及基于三副本的(n，k，3)-R再生码。(n，k,2)-R再生码可以对一个节点故障进行无编码的修复，修复局部性为2，编码率为k/2n。(n，k，3)-R再生码可以对两个节点同时出现故障进行无编码的修复，修复局部性为3，编码率为k/3n。R再生码的容错能力与RS编码一致，随着n，k的增大(n-k固定)，存储开销可以与相应的复制策略任意接近。