减少分布式存储系统中基于异或(XOR)冗余编码的修复带宽

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

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

以生成矩阵(Generator Matrix)为下图的编码为例,如果丢失的第一个数据节点,相应地丢失了R0 和R1 对应的数据块,下载任意其他四块数据块可以修复这两块数据块,但显然不是最优的,最优的情况是下载R2、R4 和R7 所对应的数据块,就可以解码得到R0 和R1

gm

定义

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

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

graph

为构建该图,首先将F 中所有节点对应相关集合都计算出来,即E(ei,j 中i 表示节点,j 表示序号):

equations

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

减少分布式存储系统中基于异或(XOR)冗余编码的修复带宽》上有2条评论

  1. 完全看不懂

    请教个问题,按文章里的意思…
    使用4 + 2 的CRS编码, 可以做到读取少于4份数据来恢复丢失的数据么?

    • 文章差不多是这个意思,但不是对所有节点数据的丢失都能够少于4份来修复,
      当丢失的是第一个节点数据块R0 和R1时,只需要3个数据块R2、R4、R7就可以恢复出,因为R0 = R2异或R4、R1 = R2异或R7 。
      当丢失的是第三个或者第四个节点的数据块时,就必须要四个数据块了。
      文章就是找出了怎样找出需要最少修复数据块的方法。

发表回复

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

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