NCCloud: Applying Network Coding for the Storage Repair in a Cloud-of-Clouds

Posted on by

该文出现在FAST12 会议上，介绍了在多个云存储服务提供商之上，利用随机网络编码（RNC）搭建一个可靠存储系统，实现了功能性最小存储再生码（F-MSR）来减少修复数据的带宽。

优点：提供了一种实现MSR 的简单方法。

问题：在已经非常可靠的云存储之上做编码是否得不偿失，而且文中实现的(4,2) 编码实用性有待讨论。

 

下面就介绍下文中提到的F-MSR 的实现，在这之前有三个需要注意的：

  1. 在上一篇日志介绍了再生码，在修复一个数据分片时，需要 d 个节点内参与、进行计算，然后返回数据给新节点。但在大部分云存储服务并不允许存储节点内数据的计算，因此F-MSR 谈到了这里和理论上再生码唯一的不同就是不需要节点有编码能力（计算能力）。
  2. 另外F-MSR 保证在每次修复的新的数据分片都和剩余数据分片都满足MDS 性质，以保证数据可用性。
  3. F-MSR 中F 是Functional （功能性的）意思。如果修复的新的分片和原来失效的分片完全相同，则称为精确修复（exact repair），如果新的分片和源失效分片不同，则称为功能性修复（functional repair）。

F-MSR 分为三个部分：①文件上传；②文件下载；③修复。

 

一、文件上传

  1. 为了上传文件F ，首先将文件分为k(n-k) 等大的原始块，表示为(Fi)i=1,2,…,k(n-k) 。
  2. 将这k(n-k) 个原始块编码为n(n-k) 个编码块，表示为(Pi)i=1,2,…,n(n-k) 。每一个Pi 都是k(n-k) 个原始数据块的线性组合。
  3. 令 EM = [αi,j] 为k(n-k)×n(n-k) 大小的编码矩阵，矩阵中系数为αi,j（其中i = 1,2,…,k(n-k)，j = 1,2,…,n(n-k)）属于域GF(2m)，其中m = 8。
  4. EM 中每个行称为ECV(encoding coefficient vector)，其中包含了k(n-k) 个元素。ECVi 表示 EM 矩阵中第i 行。那么可以通过计算向量的乘积得到Pi ：

        $$P_i = \sum_{j=1}^{k(n-k)} \alpha F_j for i = 1,2,\cdots,n(n-k)$$

    ，所有的计算都是在域GF(28) 内进行的。

  5. n 个存储节点每个保存(n-k) 个编码数据块，EM 将作为元数据保存在所有的存储节点。EM 在恢复过程中始终保持着MDS 的性质就可以保证原始数据一定可以恢复出来。

二、文件下载

  1. 下载一个文件首先获取文件对应的元数据信息（包括EM）。
  2. 然后选择n 个存储节点中的k 个共计下载k(n-k) 份数据块，每份数据块对应着一个ECV ，因此相应的得到一个k(n-k)×k(n-k) 的正方矩阵。
  3. 将下载下来的数据乘以这个正方矩阵的逆矩阵，即可以得到原始数据。

三、循环修复

修复判定成功的标准为每次修复后MDS 性质仍旧保持。利用归纳法，我们假设第(r-1)th 次修复是满足MDS 性质的，那么检查第rth 次修复是否满足MDS 性质。MDS 性质指的是(n,k) 编码中可以最多容n-k 个块错误，任意k 个数据块可以恢复出原始数据。假设有存储节点失效或者数据损坏导致编码分片丢失，下面是一次修复的步骤：

  1. 从一个活跃的存储节点下载编码矩阵EM。
  2. 从活跃的n-1 个节点中每个存储节点随机选择一个ECV。记做$ECV_{i_1} , \cdots , ECV_{i_{n-1}}$。
  3. 生成一个(n-k)×(n-1) 大小的修复矩阵RM = [γi,j]。其中每个元素γi,j （i = 1,…,n-k 且 j = 1,…,n-1）随机从GF(28) 中选取。
  4. 为新数据块生成ECV 并重建一个新的编码矩阵EM’。第3 步RM 乘以第2 步中ECVs 得$ECV_{I}^{'} = \sum_{j=1}^{n-1} \gamma_{i,j}ECV_{i_{j}}$，i = 1,2,…,n-k。利用新的$ECV_{I}^{'} 代替丢失的编码数据块对应的ECVi ，重建整个编码矩阵EM’ 。
  5. 对应第四步生成的EM’ 检查MDS 性质和修复MDS 性质是否满足。直观地，MDS 性质我们验证$\binom{n}{k}$ 个k 个节点的子集对应的编码向量形成的矩阵（k(n-k)×k(n-k) 大小）是否满秩。对于修复MDS 性质，指的是，对于任一失效的数据块，可以从n-1 个剩余活跃存储节点中每n-k 个数据块下载一个恢复出新的节点（上面是翻译的原话，我的理解就是假设任意存储节点失效，节点上n-k 个分片对应的n-k 个ECV 向量存在由剩余n-1 个节点中各取出一个分片线性组合得到）。如果这一步失败，则跳回至第2 步。
  6. 下载随机选择的n-1 个ECV 对应的数据块，利用第4 步的方法重建新的编码分片，上传到新的节点并更新所有节点元数据信息。

文章最核心的也就是这一部分，通过了解F-MSR 是如何修复一个失效节点可进一步了解如果利用随机网络线性码来构造一个冗余存储。

《NCCloud: Applying Network Coding for the Storage Repair in a Cloud-of-Clouds》上有8条评论

  1. Pingback引用通告： NCCloud 实现 | 呆鸥

  2. Pingback引用通告： 编/解码矩阵和文件的关系 | 呆鸥

  3. NCCLOUD编码的时候除了把数据块分成k(n-k)，其它过程如解码的时候几乎和reed-solomon一样。那么如果这样的话，network coding 如何在文中体现？

    回复 ↓

  5. Pingback引用通告： Analysis and Construction of Functional Regenerating Codes with Uncoded Repair for Distributed Storage Systems | 呆鸥

  6. 循环修复部分：

    第二步总共选择的是n-1个ECV, 第四步ECV‘的计算似乎涉及到(n-k)(n-1)个不同ECV,文章的意思是修复一个失效节点从剩下的n-1个节点中每个下载一个进行修复，并非为每一个失效编码块下载n-1个ECV，不知道是不是理解有误？

    回复 ↓

    • 第四步，ECVs 可能的集合是(n-k)^(n-1) 个，因为节点个数n-1 每个节点有n-k 个ECVs。

      失效是以节点为单位的（每次都假设n-k 个数据块都损坏），所以修复的也是一个失效节点，不是失效编码块。你的理解没有问题

      回复 ↓

回复 dullgull 取消回复

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

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