背景：分布式存储系统中越来越多地使用冗余编码减少存储开销，保证数据冗余。但存在的问题就是在一个节点发生失效时，需要从网络上的节点下载大量数据修复丢失的数据块，也称修复问题。基于异或（XOR）的冗余编码速度快，易于实现。本文选自FAST12 中Rethinking erasure codes for cloud file systems: Minimizing I/O for recovery and degraded reads ，介绍减少基于异或编码的修复带宽。

问题：通常的修复过程是下载等于原始数据量的数据块，解码得到原始数据，然后经历一个再编码的过程得到丢失的数据块，但这样往往浪费了一些下载的数据，如何为基于XOR 的冗余编码找到最优的修复数据块，使得修复带宽最小呢？

以生成矩阵（Generator Matrix）为下图的编码为例，如果丢失的第一个数据节点，相应地丢失了R₀ 和R₁ 对应的数据块，下载任意其他四块数据块可以修复这两块数据块，但显然不是最优的，最优的情况是下载R₂、R₄ 和R₇ 所对应的数据块，就可以解码得到R₀ 和R₁。

定义：

• F 表示为丢失的数据块对应行号的集合；
• {……} 表示相关数据块对应行号的一个最小集合，且有且仅有一个失效的数据块在其中。比如{R₀，R₂，R₄} 满足R₀ = R₂ +R4，且R₂ 和R₄ 都不在F 中，以问题给出的图为例，这样的集合还有{R₀，R₃，R₆} 等；
• {R₀，R₂，R₄}  可以表示为10101000，其中对应的位上为1 表示该数据块在集合中；
• E_i 是所有{……} 中失效节点为i 的集合，即所有相关集合中包含i 的子集，按顺序写作e_i,0，e_i,1，……；

方法：构造一个有向图（如Figure 5），起点为全零的Z 串（00000000），边为E_i 中的元素e_i,j ，边的权重为起点和终点的汉明距离，也就是需要的数据块的个数，每一层代表修复一个数据块。路径中权重最小的路径为最优修复路径（图中粗箭头所指）。

为构建该图，首先将F 中所有节点对应相关集合都计算出来，即E（e_i,j 中i 表示节点，j 表示序号）：

以问题中的例子为例。从Z 开始，首先修复第一个数据块（R₀），对应e 的权值为3,3,5,5，接着分别在已有的基础上修复第二个数据块（R₁），并得到第二步的权值。使用Dijkstra 可得到最短路径，即最优修复数据块集合。