原文地址

从文章字面意思来看讲的是最优再生码的显示结构。文章主要贡献是给出了d = n-1 情况下的精确修复（Exact repair）MBR 一个通用的结构。

在分布式存储系统中，通过传输信息修复失效节点中的数据可以分为两类：精确修复（Exact repair，即修复得到的新数据和原来因节点失效的数据相同）、功能性修复（Functional repair，即修复得到的数据可能和原失效数据不同，但修复保持着数据的冗余度）。精确修复又有一类只对系统码中的原始数据部分进行精确修复，对校验部分进行功能性修复。三者包含范围关系如下：

考虑到d=n-1 ，即新节点和存活的所有节点都进行连接并下载相应数据。这一特性和全连通图中每个节点与其他所有相连的特性类似，因此作者使用了B-code 的模型。对应如下图所示（这里是一个简单的再生码修复的视频，包含了一个(5, 3)精确修复的例子）：

图中V1-V9 代表着原始数据块，V10 等于从V1 到V9 的异或，那么V1-V10 中任意9 块数据都可以恢复出原始数据。将全连通图中的顶点作为存储节点，节点之间边作为存储数据（可以看到每个节点连接四条线，则每个节点保存四块数据），边两端上的顶点（节点）存储边对应的数据块，比如上图中node 2 和node 3之间有边（V5）连接，那么node 2 和node 3 同时保存着V5 的副本。当其中某个节点发生失效时，这个节点与其他相连的节点将对应和该节点连线对应的数据块传给新的节点。不难看出：

1. 每个节点保存的数据块等于该节点和其他节点的连线数目（n-1）；
2. 修复每个节点的数据块数等于该节点和其他节点的连线数目（n-1）；

下图是节点上存储对应的数据块表（1 代表该节点存储有对应列的数据块）：

可以看出任意两个节点在列上只有一个重合，因此当一个节点失效时，总有一个节点（就是在这一列上同为1 的那个节点）可以帮助失效节点恢复对应的所有数据块。

而上图还有一个特性就是任意三个节点连接了十条边中的九条，也就是三个存储节点存储了十个数据块中的九块，也就是说客户端连接五个节点中任意三个都可以获取原始数据。

我们再来回顾下MBR 的性质：α_MBR = γ_MBR ，在n = 5、k = 3 时，d = n-1 = 4，有α_MBR = γ_MBR = 4/9M，这正好对应着上图中的存储模型，正是一个MBR 编码方法。这篇文章在后续继续证明了：如果还有其他构造出exact repiar MBR的方法，也是和这种方法同构的。

这样的编码方式可以是系统码，即保存了原始数据，并达到了MBR 存储和带宽的最优，但这样的还是存在些问题：

1. 从理论上可容两个节点失效，但实际上只允许一个节点失效，当两个节点失效了时，两个节点之间的连线对应的数据块就无法恢复了。（起码无法通过MBR 的方式恢复了）
2. 第二点类似于第一电特性，无论n 多大，都只允许一个节点失效。
3. 并不是任意三个节点都可以读到系统码中的原始数据。（这点也是没有办法改进了，但可以借鉴RAID5 VS RAID4 的方法）

作者已经证明了exact repair MBR 只有这么一种方法，而这样的MBR 在两个以上节点失效时性能下降到了一般的erasure code 的修复性能。那么是不是可以认为exact repair MBR 只有这样的一种存在方式呢？

最后再来看看exact repair MBR 修复的实质吧！（还是n = d-1）由：

知道每个数据块的大小（即节点上数据总量除以 n-1）为：

如果连接k 个节点，k 节点之间连线为k(k-1)/2，k 个节点和除去k 个节点以外的n-k 个节点连线k(n-k)，因此最多可以获取kn-k²/2-k/2 块数据块（同样地，每个节点连接n 个节点，再减去k 个节点之间的连线也是一样的结果）。那么k 个节点获取的数据块数乘以每个数据块的大小：

结果正好是M ，也就是说如果每个数据块之间是通过MDS 编码，那么从k 个节点总是可以恢复出原始数据，并且修复带宽最小，因为恢复时传输的总是副本。这样看来exact repair MBR 首先通过(n(n-1)/2, kn-k²/2-k/2)-MDS 实现数据冗余（第一个参数是图中连线对应数据块总数，后一个参数是k 个节点可获取数据块总数），再利用模型中数据的放置方法，将编码后的n(n-1)/2 块数据放在n 个节点上。每个数据块将放置在两个节点上，共计n(n-1) 块数据块。又由于MDS 编码后数据块总是有至少两个副本，那么整个MBR 效率一定小于1/2 。