Simple Regenerating Codes: Network Coding for Cloud Storage

文中提出了一类称为(n,k,f)-SRC(Simple Regenerating Codes) 的再生码,下面通过简述其编解码原理和分析其性能来看看SRC 是如何欺世盗名、利用再生码(RC)在Infocomm12 博取上位的。

一、(n,k,f)-SRC 核心思想

先将数据通过(k,n)-MDS 编码,使其满足(n,k) 性质:即n 个节点中任意k 个节点可以恢复出原始数据;然后通过简单的(f+1,f)-XOR 编码使得满足编码后数据的精确恢复。

二、(4,2,2)-SRC 编码的一个例子

下面以(4,2,2)-SRC 编码为例,来看看SRC 是如何编码的:

  1. 首先文件F ,大小为M,等分为分为四份f1 f2f3f4,每一份大小为M/2 ;
  2. 接着对四份数据两两进行(4,2)-MDS 编码(通过乘以一个2×4 的生成矩阵G 实现的),得到的结果分别为x1、x2、x3、x4 和y1、y2、y3、y4。
  3. 对4f 对数据进行异或,得到si = xi+y
  4. 将数据按照每个节点 [$x_{i}$, $y_{i \oplus 1}$, $s_{i \oplus 2}$] 的方法放置数据。最后两步可以看做是一种垂直编码。

src1

 

三、(4,2,2)-SRC 编码修复一个节点

src2

 

 

假设第一个节点失效,对应的x1,y2,x3+y3 三块数据失效。三块数据都是由对应的另外两块数据恢复得到,比如:

 $x_1 = x_1+y_1 \oplus y_1 $

修复的带宽放大倍数和磁盘写放大为2 。(后面我们将知道这个放大倍数即为f )。当失效其他节点也同样处理。

 

 

 

 

 

 

四、(n,k,2)-SRC 编码

通过将(4,2)-MDS 编码一般化为(n,k)-MDS 编码,可以将节点个数一般化为n 个,而不只限制为4 个。此时f=2。将文件分为两份,每一份数据都是k 的整数大小(可以看做是一个k 大小的数据向量),分别通过(n,k)-MDS 编码为x y 数据向量,大小为n 。并计算S= X + Y 。共计得到3n 块数据。按照上节方法放置于n 个节点上,如下图:

src3

 

五、(n,k,f)-SRC 编码

更一般化SRC 编码,将不指定f 的大小,下面我们将知道f 对应着每个节点存储数据块的个数。每个节点会保存f 个数据块和一个XOR 校验块。编码过程如下:

  1. 将文件F 分为f f1 、f2、…ff ,每份数据大小为k 的整数倍。
  2. 将每份文件做(n,k)-MDS 编码,编码后的结果为x(1)x(2),…,x(f)
  3. $ s = \sum_{i = 1}^{f} x^{(i)} $
  4. 将第二、第三步产生的(f + 1)n 块数据存储在n 个节点上。存储放置规则和最后结果如下图:

image             src4

从上图可以看出最后两步的编码效率为f/(f+1) ,f 块数据块产生一块校验块s 。而MDS 编码效率为k/n ,所以(n,k,f)-SRC 编码效率为k·f/n·(f+1) 。

(n,k,f)-SRC 修复一个节点就不细说了,基本思想就是将失去的数据块所在的对角线上的f 个剩余数据块下载下来,然后通过异或计算得到原始的数据块(不难发现对角线上实际上是一个RAID 5 )。

 

六、为什么说(n,k,f)-SRC 不是再生码

前面已经有一些文章介绍再生码了,再生码是通过组合数据块达到存储高效和修复带宽高效的一类编码。SRC 的确是对数据块进行了编码组合,但在高效的修复带宽面前走的太远了,修复一个数据块需要f 倍的数据是不能接受的,在f > k 的情况下,其修复带宽比MDS 还要差,这是SRC 不是再生码的一个主要表现。

第二看作者自己拿出来进行比较的一个参数磁盘访问Disk Access,这是修复一个数据节点所访问磁盘容量和节点容量的比值,(n,k)-MDS 的磁盘访问为k,则修复一个节点(容量为M/k)需要访问k×M/k = M 大小的磁盘;(n,k,f)-SRC 修复一个节点需要访问2(f+1)M/k 磁盘,当2f>n-1 时,SRC 在磁盘访问上要差于再生码。下面是文中列出来的一个SRC 和其他编码的性能比较。

image

SRC 宣称自己打破了exact repair 中码率小于等于1/2 的限制,可以达到任意高码率。但估计看完文章的人都会发现这只是一个噱头,SRC 偷换了exact repair 的概念,对MDS 之后的编码块进行了exact repair。实现任意高的码率在理论上是可以的因为MDS 的码率是可以任意高的。

还有一个很重要否定了SRC 是再生码的因素就是既然SRC 不是最小存储再生码MSR,也不是最小带宽再生码MBR,也没有达到其他再生码存储和修复带宽的均衡,怎么能说是再生码呢?

综上所述,SRC 只是一个想披着再生码皮的普通网络编码。

Simple Regenerating Codes: Network Coding for Cloud Storage》上有4条评论

  1. 我觉得你说得对,这篇文章看得我也很纠结。在MDS的基础上再做一层RAID5肯定不会有什么好效果。

发表回复

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

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