再生码开销的定量计算

Posted on by

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

形式化描述一个普通的冗余存储方案，可以将一个存储的生命周期分为几步：

  1. 插入：插入包括处理原始文件，将其编码为(k+h) 份冗余编码块，其中任意k 个块可恢复原始文件。
  2. 维护：维护包括重建丢失的数据块，重建要求d 个对等端发送数据给一个新的对等端，d 称为修复维度。
  3. 恢复：从k 个对等端恢复出原始数据（下面试图得到所有数据为恢复，得到数据块为重建）。

文件大小视为 |file| ，每个块大小 |piece| ，对象x 的大小为 |x| 。

从上面的描述可以看出这样的P2P 存储会有几类开销：

  1. 存储 Storage： |storage| = (k+h) · |piece| > |file|
  2. 通信 Communication：插入通信为 |storage| ，维护通信为 |repairdown| = d · |repairup| ，恢复通信为 |file| （看到这里我也以为是 k · |piece| ，后面会有解释）
  3. 计算 Computation：插入计算为 CPU(encoding) ，修复计算为 d · CPU(repair)up+ CPU(repair)down，恢复计算为 CPU(reconstruction)

============================= RS 码性质 =====================================

以传统的纠删码（比如RS 码）为例，则有：d =k ，|piece| = |file|/k → |repairup| = |piece| ，|repairdown| = |file| ，每个节点保存了 |file|/k 大小块数据，每次恢复或者维护从k 个对等端中每一个下载大小为 |repairup| = |piece| =|file|/k 的数据。

============================= RC 码性质 =====================================

还记得再生码牺牲了少量的存储效率，换取更少的维护通信开销么？再生码没每个对等端存储比|file|/k 更大的块，至于大多少和码率R 有关。在维护阶段每次修复一个块交互的对等端不再固定是k 个（d ≠ k），而比k 更大。可以用RC(k,h,d,i) 描述一般化的再生码，具有以下限制

d ∈ [ k , k+h-1 ]

|piece| = p(d,i) · |file| ， i∈[ 0 , k-1 ]

d，i 可以看做数据块扩展系数，p(d,i) 有这样的定义：

    $$p(d,i) = 2\frac{d-k+i+1}{2k(d-k+1)+i(2k-i-1)}$$

可以证明RC(k,h,d,i) 再生码每次重建数据块从其他每个节点下载数据量至少|repairup| = r(d,i) · |file|，r(d,i) 被定义为：

    $$r(d,i) = \frac{1}{2k(d-k+1)+i(2k-i-1)}$$

可得：|repairdown| = d · r(d,i) · |file| 。以RC(32,32,d,i) 为例，当d=32，i=0 的情况下，对应的也就是RS 码。下左图比较的是不同d 和i 情况下，每个数据块与RS 码相比块变大比率。当i=0 时，p(d,i) = 1/k ，对应的放大率即为1，i 越大每个数据块存储数据量就越多。右下图对应的是不同d 和i 情况，修复带宽与RS 码比较减少的百分比。i 越大修复带宽减少的就越多。总体上d 越大，RC 码效果越明显。

 

3  4

 

i = 0 时，每个节点上数据块大小最小，对应的是MSR：最小存储再生码（MSR）。i = k-1 时，聚合修复带宽最小，对应的是MBR：最小带宽再生码（MBR）。

============================= 随机线性再生码 =====================================

再生码不同之处在于每个数据块|piece| 不一定等于重建一个数据块时从每个存储部分获取数据大小|repairup| ，因此|repairdown| 也不存在是|piece| 的倍数的关系。

|file| = nfile · |fragment|

|piece| = npiece · |fragment|

|repairup| = nrepair · |fragment|

利用上面和之前再生码的知识，计算得到：

    $$\frac{|piece|}{|repair_{up}|} = \frac{p(d,i)}{r(d,i)} = d-k+i+1$$

    $$\frac{|file|}{|repair_{up}|} = \frac{1}{d(d,i)} = \frac{2k(d-k+1)+i(2k-i-1)}{2}$$

如果以重建一个数据块从单个节点下载的分片个数nrepair = 1 为基准，即是|fragment| = |repairup| ，于是有：

nfile = [2k(d-k+1)+i(2k-i-i)]/2

npiece = d-k+i+1

这两个系数也就是文件大小比上碎片大小和数据块大小比上碎片大小，经计算都是整数。

那么随机线性再生码会有以下行为：

插入：将原始文件分为nfile 个等大的原始分片，分别为$x_1 , x_2 , x_3 \cdots x_n_{file}$，以这些分片为未知数计算npiece 个方程的随机线性组合。这些组合随机系数被保存在数据块中，数据块中npiece 个分片中每个分片都是nfile 个分片的线性组合。

维护：数据块的重建涉及到d 个尚在的对等端，每个对等端发送npiece 个分片的一个随机线性组合，重建数据块的节点收到d 个分片和对应的系数后，计算出这些d 个分片的线性组合得到npiece 个分片。过程如下图所示：

 

5

 

恢复：从k 个对等端中得到npiece · k 个分片和相关系数形成了一个npiece · k × nfile 大小的矩阵（计算可以知道对于RS 码，npiece · k >nfile）。通过在相关矩阵中找到nfile 行不相关行，用对应的分片乘以这个子矩阵的转置。

========================== 随机线性再生码开销 ==================================

为了计算方便会将原始数据根据选定的伽罗瓦域GF(2q ) 进行切分，将原始文件切分为等于2q 大小，于是每个分片可以又一个向量lfrag = (|fragment|/q) 表示，整个文件就表示为 nfile × lfrag 大小的矩阵，记做$F_{n_{file},l_{frag}}$。n 个编码后的分片表示为 n × lfrag 矩阵，记做$E_{n,l_{frag}}$ 。这个矩阵可以由原始分片的线性组合得到：

    $$f_{n,l_{frag}} = C_{n,n_file} \cdot F_{n_{file}\times l_{frag}}$$

其中Cn,nfile 中元素都在域上，是分片线性组合的相关系数。

相关系数的影响

之前谈到了随机线性再生码插入/源文件编码和维护、恢复过程都需要相关系数的参与，那么保存相关系数实际上也是一个开销。因为每一个分片，都和nfile 个相关系数有关联，我们可以用rcoeff 来表示这种相对影响比率，即对于每个bit 的数据需要rcoeff bit的相关系数。

    $$r_{coeff} = \frac{n_{file}q}{|fragment|} = \frac{}{}\cdot q$$

稍微解释下：对于|fragment| 大小的分片，需要nfile 个系数，每个系数大小为q 。由这个开销可以看出原始文件越大，每个分片越大，系数的开销就越小。文中举了一个例子，对RC(32,32,d,i) 再生编码方式下，如果d = 64 ，i =32 和q=16 （2bytes）的情况下，每1 bits 的数据就对应要有4 bits 的相关系数，这肯定是不希望看到的情况。

计算复杂度

所有的数值计算都是在伽罗瓦域进行的，所以选择合适的域大小对减少计算开销具有重要作用。如果我们选择域大小为2q 且q=16 的话，那么所有的计算都是在无符号短整型数上进行的。元素的加减法对应的是XOR 异或操作，乘法和除法是在log 空间进行的，比如a · b 实际上是exp(log a + log b)【不要问为什么，有限域的乘法就是这样的做的，为什么这么麻烦，因为硬件设计不是为了做有限域的计算】。所有log 和exp 计算的可能结果都是离线先计算后保存了的，对于q=16 需要256 KB 内存空间。每次乘法或者除法需要做三次查询和一次加法。

所有在再生码上的操作都可以归结为：1、线性组合与 2、矩阵转置。向量长度为l ，那么n 个向量的线性组合包括n · l 次加法和n · l 次乘法（又包含4n · l 次操作），共计5n · l 次操作。一个正方(n,n)矩阵包含n3 次加法和n3 次乘法，共计5n3 次操作。但对于再生码有些不同，它包含一个(m,n)大小的矩阵（m>=n），需要从m 行中取出线性不相关的n 行，组成(n,n) 子矩阵按后转置。提取和转置都是并行进行的，所以计算开销在5n3 和5mn2 之间。

由上面的定义可以得出再生码在插入、维护和恢复三个阶段的计算开销了：

插入：CPU(encoding) = 5(k+h) · nfile · npiece · lfrag = 5/2(k+h) · npiece · |file| （对nfile 个分片进行5(k+h)· npiece 次线性组合，除以二是因为计算按照两比特来计算，长度应该除以比特长度）

维护：在重建、修复一个分片时，一部分工作是由参与的对等端执行的：

CPU(repair)up = 5 · npiece · lfrag = CPU(repair)up = 5/2 |piece|

在新的节点中执行d 个分片的npiece 次线性组合，对应的计算开销为：

CPU(repair)down = 5 · d · npiece · lfrag = d · CPU(repair)up

恢复：分为两步，第一步是从k · npiece × nfile 矩阵中提取出nfile 线性不相关的行，并转置获得的子矩阵。第二步用对应的分片乘以这个子矩阵，因此计算开销为：

CPU(恢复) = CPU(转置) + CPU(解码)

转置的计算开销在这个范围内：

    $$5 \cdot n_{file}^{3} < CPU(inverse) < 5 \cdot k \cdot n_{piece} \cdot n_{file}^{2}$$

解码是nfile 分片的nfile 次线性组合：

    $$CPU(decoding) = 5 \cdot n_{file}^{2} \cdot l_{frag} = 5/2 \cdot n_{file} \cdot |file|$$

由此可以看出，几乎所有的计算都是和文件大小|file| 线性相关的。

============================ d 和 i 的关系 ====================================

d 定义为一个分片重建时交互对等节点的个数，那么d 越大，每次重建交互的节点越多，计算开销也越大，但每个节点存储体积减小，带宽减小了。

i 虽然没有具体定义为什么（没有实际意义比较难理解），但通过以上知识，i 越大每个节点上存储的分片越多，存储开销越大，相关系数存储更多，计算开销更大。但重建一个分片的带宽开销小，当i = k-1，重建带宽最小，称为MBR（最小带宽再生码）。

下图很好反应了d 和i 的关系，左上RC(k,h,k+h-1,k-1) 到左下RC(k,h,1,0) 对应的是最小带宽的编码。左下角对应的是副本策略，每次之和一个节点交互（d=1），在副本的策略上进行横向扩展得到erasure code 纠删码。牺牲一部分带宽和计算，节省了存储，从左下RC(k,h,1,0) 到右下RC(k,h,k,0) 。由再生码纵向上推演，通过和更多的节点交互可以进一步减少存储和带宽的开销，得到再生码。7_thumb[1]

发表回复

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

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