两种最小带宽再生码(MBR)

[1] 和[2] 都是有Rashmi K.V. 提出的精确修复最小带宽再生码。精确修复(exact repair)指的是修复的存储节点数据和节点丢失的数据是完全一致的。RAID 和RS 码都是精确修复,NCCloud 中提出的F-MSR 就不是精确修复。相对于精确修复是功能性修复(functional repair),这种修复只保证了一定的数据冗余性,使得数据可以被恢复出来,并且在下一次丢失一定量数据时可以功能性修复该数据并继续保持数据冗余性。相比精确修复,功能性修复更具不可控性。

早在[1] 中就提出了一种精确修复的再生编码,更重要的是证明了两点:1. 精确修复的最小带宽再生码(exact repair MBR)码率R 大于等于 1/2;2. 精确修复的最小带宽再生码只有一种文中提出的构造方式,所有其他构造的精确修复的最小带宽再生码都是和这种方法同构的。

之前的文章中已经介绍了第一种编码方法。简单的讲,这是一种先进行MDS 编码,后进行复制副本的一种编码方式,码率R = RMDS×1/2 。这里的视频举了一个例子进行(10,9)-MDS编码,再等分的exact repair MBR。下面将介绍 twin codes[2] ,虽然和[1] 是同构的。

Twin Codes

编码过程(encode):先将原始数据分割为等大的k×k 块,排列成k×k 矩阵大小,如下所示:

             | m1   m2   m|

M0  =     | m4   m5   m6 |

             | m7   m8   m9 |

将M0 转置(transpose)形成新的原始数据矩阵M1

            | m1   m4   m7 |

M0 =     | m2   m5   m8 |

            | m3   m6   m9 |

两个不同的原始数据矩阵通过不同的编码/生成矩阵(Generator Matrix)得到两份不同的编码数据,两份编码数据可看做是一对双胞胎,所以称为Twin Codes。编码分别存储的两类节点约定为Type 0 节点和Type 1 节点。

17

 

修复过程也非常简单,仔细观察编码过程,M0G0 和M1G1 分别对应着列编码和行编码,每个节点保存k 份数据,是对应k 列数据的线性组合(我没有说错,即使是m1 也可以看做事m1,m4,m7 的线性组合,只是后两者组合系数为0 )。两类编码后数据,对方的行编码对应着自己的列编码,反之亦然。那么只要两类节点Type 0 和Type 1 的存储节点都大于等于k 个,那么无论Type0 或者Type 1 节点失效第i 个节点,只需要从另一类节点中任意k 个节点各取第i 行数据用于重建失效节点即可。下面给出了修复一个节点的示意图:

18

 

下图是对应上图编码数据对应的原始数据和编码矩阵。

19

 

 

参考文献:

[1] Explicit construction of optimal exact regenerating codes for distributed storage

[2] Enabling node repair in any erasure code for distributed storage

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据