文章来源：Erasure Coding vs. Replication: A Quatitative Comparison

继续阅读 →

上篇论文讨论了再生码的来源：从OMMDS 改进而来，从理论上证明了再生码的可行性与存储开销，维持带宽。下面这篇文章：A practical study of regenerating codes for peer-to-peer backup systems 则详细讨论了再生码的存储开销、恢复带宽开销、计算开销等等。

继续阅读 →

本文讨论分布式存储系统如果采用编码方式保存数据，那么允许最多失效的节点个数与码率之间的关系。这个关系也可以通过图论中“最小分割最大流”定理来求证。

一个原始文件S（假设没有冗余信息）大小自信息量/文件大小为I ，进行冗余编码[n’,k]（这里考虑系统码，为和分不到n 个节点区分开，用n’ 代替）的编码率为R = k/n’ ，则编码后文件大小为C：I → C = I/R。将编码后的数据分布在n 个节点上，每个节点的数据记做：X1 ，X2 ，X3 ……Xn ，每个节点数据的大小为C/n = I/R·n 。而每个节点数据/信息又有两部分组成，前一部分是系统码中的原始信息：X_ii = I/n，另一部分是系统码中的校验信息：X_ih = C/n – I/n ，且X_i = X_ii + X_ih。如下图所示

当a 个节点发生故障失效时，那么剩下的校验/冗余信息和原始信息应该能够恢复出丢失的原始信息，进而恢复出所有的校验信息。即：

  因为H = C – I =I/R – I。得结果：

这也就是说，所有没有损坏节点的个数与所有节点比率（n-a/n）应该大于编码码率R。

在传统的分布式存储系统中，数据为了保证安全、可靠、不丢失，一般采用副本策略，不使用编码技术有几点考虑：一是会增加了额外的计算开销；二是当某个存储节点发生失效时，会有多个存储节点涉及到该节点的恢复，且占用带宽超过副本策略的恢复带宽。下面是五种存储编码方法：

• Replication 副本策略（分布式文件系统hadoop 等采用）

优点：简单易实现，数据恢复带宽最小（C=1，C 什么意思看后面解释）

缺点：占用存储资源，现在云存储提供商都是按照存储容量来收费。

• Simple 简单策略

这里“+”代表的是按位加运算（0+0=0，1+0=1，1+1=0），简单策略允许至多两个节点失效，代价就是恢复需要额外的计算和两倍C=2 的恢复带宽。

• NCCloud （FAST12 中文章）

NCCloud 中改进了简单策略，在节点内部如果能够进行计算的情况下，恢复代价C 下降为1.5

• Infocomm（Infocomm12 中文章）

• RAID5

介绍一个参数向量，<N , T , C , A > 是用于衡量该编码方式应对存储节点失效的能力和效率：

• N =(单个节点存储容量)/(原始数据容量)，反映的是单个节点保存的信息占原始数据信息的比率。
• T 指最多可失效存储节点的个数。
• C =(恢复数据带宽)/(单个节点存储容量)，反映的是恢复单个失效节点的代价。
• A 指恢复单个节点涉及到的节点数。

从编码的角度来看，[n,k] 码最多能检测发现n-k 个错误。同样的，k/n 指码率，即编码的效率，编码的效率越高，存储的效率也就越高，但如果要求存储效率高，那么能进行纠错的能力就弱。将数据通过编码保存在多个节点即将编码后的信息等长分片，分别保存在多个存储节点。这样每个节点保存了编码信息后的多个分片，如果一个存储节点保存的信息分片信息总量越多，节点失效后需要能够检测出的错误就必须越多，相应的n-k 就必须越大，码率越小。上面两种此消彼长的关系如下：

单个节点存储容量*允许失效节点<—>编码效率

存储利用率<—>编码效率

另外还需要重点谈到的是恢复带宽C 和恢复涉及的节点数目A ，当某个存储节点失效后，需要根据已有的节点上的数据恢复失效及诶单，恢复带宽大于或等于原节点存储容量，副本策略就是最优的带宽利用，只需要原始数据容量的带宽，特点策略的恢复带宽比较简单，但要计算出一般的普适规律也不是那么容易，首先来讨论恢复节点问题，我们希望恢复时所涉及到的节点越少越好，传统RAID 在这点表现的比较差劲，当一块盘发生故障时，进行该盘数据重建严重影响了其他磁盘对外服务，我们希望的情况是数据恢复、重建过程中涉及的节点越少越好。

考虑一种情况：将数据n 编码后等分为i 个分片存储，任意j 个分片参与至少可以恢复一个分片，那么任意j 个分片可恢复出整个数据n 。比如将数据a 分为a1/a2/a3/a3（i=4，j=2），任意一数据分片可以由其他两片恢复，那么如果a1+a2 恢复了a3，那么a1+a3 或者a2+a3 又可以恢复出下一个分片，这样所有的分片就都可以恢复出来，故有任意j 个分片具有数据n 的所有信息。（这里不考虑分区的情况，比如数据ab，都按照上面的分片方式，得a1/a2/a3/a3 和b1/b2/b3/b4（i=4，j=2），a 的分片和b 的分片都只能恢复各自的分片）这样根据需要恢复的节点数也可以得到存储效率小于或等于 j/i。比如副本策略j=1，i=3，存储效率 33%；简单策略j=2，i=4，存储效率 50%；infocomm 就出现了上面分区的现象，因为任意每个分片只需要两个分片就可以恢复，但是并不是任意的两个分片都能够恢复出一个分片。

接着考虑上面没有考虑到的第二种情况：任意一个分片可以由指定的j 个分片恢复，但是并不是任意两个分片就可以恢复出一个分片（与上面的不同的地方，这里更像RAID 一条strip 上只能互相恢复，与其他条带上数据无相关性）。其实这样每个条带上的各个数据分片还是满足上面任意j 个分片可以恢复出所有分片的要求的，i代表每个条带上数据分片数目，比如RAID5 j=i-1，RAID6 j=i-2，infocomm 策略 j=2，i=3。

存储节点保存一个或多个分片，分片和存储节点都可以是故障的单位，既可以是存储节点中的某个数据分片发生损坏，也有可能是整个存储节点失效。无论是上面第一种情况中的数据分片还是第二种情况中条带内数据分片必须分布在大于或等于j 存储节点。那么允许失效的节点最大即为所有节点数减去j。

下面结束上面两种情况的话题，继续谈恢复带宽，我们发现给出的replication、simple、NCCloud、Infocomm、RAID 五种编码方法中除了replication 副本策略，恢复一个节点的代价C 都是大于等于二（例子里都等于二），这是因为恢复的数据分片都是通过其他数据异或运算得到的，异或运算最少需要两个参数，所以一个恢复一个分片至少需要两个分片，而节点是由数据分片组成的，所以恢复一个节点至少需要两倍的数据量。而副本策略存储的是数据的副本，恢复时不需要计算，节省了带宽。那么我们可以考虑每个存储节点上一部分分片采用副本策略，一部分使用异或运算提高存储效率。下面给出这样一种混合编码Hybrid。

• Hybrid 策略

恢复每个节点的代价C 是8/5，存储效率是3/5，以恢复节点{A1/A2/A3/B1/C2+D2}为例：

A1 = A1

A2 = (A2+B2)+B2

A3 = (A3+B3)+B3

B1 = B1

C2+D2 = C2+D2

很明显，这样恢复代价C 越大，存储节点副本使用的就越少，恢复代价越大，也就是采用了更多的编码，恢复一个分片需要的分片数也就越多。恢复代价越小也就是存储节点内数据分片更多的采用了副本保存在其他节点，当存储节点恢复代价C=1 时，该节点上所有数据都在其他节点上保存有副本，这样存储效率也就<50%。

总结：存储效率等价于编码效率，反比于检错能力。恢复带宽正比于副本的使用，反比于异或编码比率。容最多节点反比于节点保存信息量，反比于编码效率和存储效率，即是码率越高，在节点保存信息一定的情况下，容失效节点越少。以上都是比较感性上的讨论，希望能够把信息论和编码的知识运用进去给出一个更加数学的结论。