基于网络编码理论的分布式存储.ppt

基于网络编码理论的分布式存储 自修复编码及进展李挥北京大学深圳研究生院深圳市云计算机重点实验室 1 报告提纲 1 网络编码理论简介 2 分布式存储介绍 3 存储需求及编码策略 4 自修复码的进展 5 未来研究方向 诞生于香港中文大学的网络编码理论 NC 简介 第1篇线性网络编码理论的论文由香港中文大学李硕彦 杨伟豪 Li Yeung Networkmulticastflowvialinearcoding Proc ISORAconference 8 1998 奠定网络编码理论基础的论文 获得了IEEE信息论学会2005年最佳论文奖 李硕彦等 LinearNetworkCoding 2 2003 IEEETrans OnInfo Theory 3 信息流不是水流 可以运算压缩后再传送 故节点的功能应该是 编码 转发 4 MIT科学家07年6月在 科学美国人 杂志以 BreakingNetworkLogjams 打破网络僵局 为题详细介绍了诞生于香港中大的NC理论 指出 网络编码是继60年前仙农发表 通信的数学原理 后 网络通信理论的一个全新突破 仙农解决了点对点信道的容量极限问题 而NC解决了如何达到单源对多点及多源对多点的网络通信容量极限的问题 IEEE数据库 NC论文35000篇 total320万Papers 云存储 分布式存储介绍 5 分布式存储介绍 6 分布式存储介绍 7 Google数据中心 Oregon Oklahoma 分布式存储介绍 8 由于自然灾害 电力故障等可能导致节点失效 分布式存储介绍 分布式存储 复制 A B A A B B 客户端 kshum 9 分布式存储介绍 数据的大小B 每个节点存储的数据量为B k n个存储节点 任意k个节点可恢复原始数据 MDS Max DistanceSeparable 特性 分布式存储 Reed Solomoncodes 节点1 节点2 节点3 节点4 10 A1A2 B1B2 A1 B12A2 B2 A1 A2 B1 B2 2A1 B1A2 B2 客户端 分布式存储介绍 分布式存储 Reed Solomoncodes 数据重建 11 A1A2 B1B2 A1 B12A2 B2 A1 A2 B1 B2 2A1 B1A2 B2 为修复B k 2的数据使用了K倍 B k 的带宽B 4带宽 分布式存储介绍 分布式存储 Reed solomoncodes 12 存储需求 9 最小I O 7 修复带宽 8 修复节点 4 编解码复杂度 5 重建带宽 可靠性 编解码时间 修复时间 1 MDS特性 2 存储节点的数量 3 每个节点的可靠性 6 编码率 13 编码策略 再生码 S In1 Out1 In2 Out2 In3 Out3 In4 Out4 14 最小割 S In1 Out1 Inn Outn 编码策略 15 编码策略 n 10 k 5 16 RGC MDS特性 修复带宽最小 但是 修复节点数 k 修复协议很复杂 编解码复杂度比RS码大一个数量级 RS码 MDS特性 修复带宽B 参与修复节点数k 自修复码SRC self repairingcodes 基于同态的自修复码 HSRC HomomorphicSelf RepairingCodes 基于射影几何的自修复码 PSRC ProjectiveSelf repairingCodes 编码策略 HSRC 基于同态的自修复码 优点 参与修复节点数为2 修复过程只涉及异或运算 缺点 编解码复杂度高 没有有效的重建过程 不满足MDS特性 PSRC 基于射影几何的自修复码优点 修复节点为2 修复过程 重建过程均只涉及异或运算 缺点 编码率不可控且很低 存储空间效率低 重建带宽不是最小 不满足MDS特性 编码策略 编码策略 RGC PSRC不实用 RGC 降低复杂度 减少I O消耗 PSRC 需提高编码率 最优化修复带宽 19 自修复码的进展 最近我们提出通用射影自修复码GPSRC GeneralProjectiveSelf repairingCodes 满足自修复码特性 编码率可控 较高 一般修复过程存在修复带宽和修复节点的折中 重建带宽达到最小 缺点 不满足MDS特性 20 自修复码的进展 射影几何介绍 W GF q 的m 维向量空间 射影几何PG m 1 q W的所有子空间组成的集合 t 空间 W的 t 1 维子空间 t 扩展 t 空间的集合S PG m 1 q 的存在t 扩展的充要条件 t 1 整除m 21 自修复码的进展 射影几何介绍 向量空间W m 维有限域GF qm GF q GF qt 1 GF qm GF qm 表示GF qm 的非零元素 是循环乘法群 w和v分别为GF qm 和GF qt 1 的本原元 zGF qt 1 zx x GF qt 1 表示GF qm 的陪集 z GF qm i 0 1 2 N qm 1 qt 1 1 1 陪集wiGF qt 1 为PG m q 的t 扩展 22 自修复码的进展 通用射影自修复码的参数定义 文件大小为B 用长度为B的GF 2 上的元素表示 t为满足 t 1 整除B的正整数 N为正整数 2B 1 2t 1 1 也是GF 2B 在GF 2t 1 中陪集的个数 GPSRC基本特征 每个节点存储 t 1数据 存储节点的数量n为B到N之间的一个整数 即B n N 失效节点可以通过d个修复节点精确修复 修复节点数量d为2到t 1的一个整数 2 d t 1 GPSRC n k n为存储节点个数 每个节点存储B k数据 23 自修复码的进展 通用射影自修复码的构造方法 Step2 V1 1 v v2 vt 为向量空间GF 2t 1 的一组基 对于i 1 2 n 节点i的编码向量分别为t 扩展的一组基 Vi wi 1 wi 1v wi 1v2 wi 1vt Step1 设v是GF 2t 1 的本原元 即1 v v2 vt为GF 2t 1 的一组基 1 v v2 vt在有限域GF 2 中线性独立 Step3 对于i 1 2 n 节点i存储的编码数据为数据文件与编码向量wi 1vj的乘积 j 0 1 2 t 乘积是指数据文件与编码向量对应的二进制数的异或运算 24 自修复码进展 重建过程 引理2 编码矩阵的任意一列的连续B个元素均相互独立 证明 假设数据收集者分别下载了节点i i 1 i B 1的第一个编码数据 编码向量分别为wi wi 1 wi B 1 如果存在B个不全为0的系数c1 c2 cB 使得c1wi c2wi 1 cBwi B 1 0 那么对上式两端同时除以wi 则得到c1 c2w1 cBwB 1等于0 这与1 w1 wB 1是GF 2B 的一组基相矛盾 由引理2知 编码矩阵的任意一列的连续的B个元素均相互独立 所以可以解码出B个原始数据 即可以恢复出原始数据B 故GPSRC重建数据的方法 下载连续的B个存储节点的第l列编码数据 且1 l t 1 25 自修复码的进展 修复过程 引理4 在GPSRC n k 码中 当一个存储节点失效时 那么最少情况下 只从 a 1 t 2 个存储节点中各下载1个数据 修复带宽为 t 2 达到最优 证明见下页 引理3 PSRC n k 码 当一个存储节点Nl失效时 可以通过选择任意1个存储节点及其相应的另一个存储节点并下载这2个存储节点来恢复出失效节点Nl存储的数据 26 证明 由引理3知 一个失效的数据可以通过任意的选择1个节点的数据并对应的下载另一个节点的1个数据来恢复 Step1 假设一个节点丢失数据的编码向量为v1 v2 va 那么可以任意的选择一个节点的编码向量u1以及其相对应的另一个节点的编码向量u2 使得v1 u1 u2 Step2 之后 选择修复v2的一个编码向量为u2以及其相对应的编码向量u3使得v2 u2 u3 Step3 同样的道理 可以得到v3 u3 u4 va ua ua 1 所以修复编码向量v1 v2 va共下载了最多 a 1 个存储节点的编码向量 u1 u2 ua 1 修复带宽为 a 1 称该修复过程为最佳带宽修复过程 自修复码的进展 修复过程 27 自修复码的进展 两个节点修复模型 多个节点修复模型 28 自修复码的进展 例子 以B 8位2进制数据o1 o2 o3 o4 o5 o6 o7 o8 为例 取t 3 满足 t 1 整除B 于是有 节点数n取值范围为B N 这里取n B 编码后存在n 8个节点 每个节点存 t 1 4位 29 自修复码的进展 例子 N2 w w18 w35 w52 N3 w2 w19 w36 w53 N4 w3 w20 w37 w54 N5 w4 w21 w38 w55 N6 w5 w22 w39 w56 N7 w6 w23 w40 w57 N8 w7 w24 w41 w58 由射影几何可知 1 v v2 v3 形成了子域GF 24 的基 不妨记节点1的编码向量为1 v v2 v3 即为N1 1 w17 w34 w51 同理 其它7个存储节点存储的向量空间分别为 30 自修复码的进展 例子 节点1的编码向量为1 v v2 v3 即为N1 1 w17 w34 w51 指定前8个元素分别表示为 1 00000001 w 00000010 w2 00000100 w3 00001000 w4 00010000 w5 00100000 w6 01000000 w7 10000000 31 自修复码的进展 例子 通过前面的介绍 我们知道节点1的存储向量空间为N1 1 w17 w34 w51 故节点1存储数据块依次为 o1 o4 o5 o8 o2 o3 o4 o7 o2 o4 根据其他节点的编码向量空间 同理可求出其他节点的数据块存储情况 如下图所示 32 自修复码的进展 节点数据块存储分布 33 自修复码的进展 通用射影自修复码的重建过程 编码矩阵的任意一列的连续B个元素均相互独立 下载连续的B个存储节点的第l列编码数据 在例子GPSRC 8 2 中 任意一列的编码数据都可以重建出原始数据文件 34 编码矩阵的任意一列的连续B个元素均相互独立 假设数据收集者分别下载了节点i i 1 i B的第一个编码数据 编码向量分别为wi wi 1 wi B 1 如果存在B个不全为0的系数c1 c2 cB 使得c1wi c2wi 1 cBwi B 1 0 那么对上式两端同时除以wi 则得到c1 c2w1 cBwB 1等于0 这与1 w1 wB 1是GF 2B 的一组基相矛盾 自修复码的进展 35 GPSRC码的重建数据的方法为 下载连续的B个存储节点的第l列编码数据 其中 由以上引理知 编码矩阵的任意一列的连续的B个元素均相互独立 所以可以解码出B个原始数据 即恢复出原始数据B 自修复码的进展 36 自修复码的进展 通用射影自修复码的修复过程 o1 o3 o5 o3 o5 o1 o5 o7 o1 o4 o7 o8 o1 o4 o5 o8 o3 o5 o2 o4 o5 o7 o2 o3 o4 o7 o5 o7 o2 o4 o5 o7 o2 o4 37 自修复码的进展 通用射影自修复码的性能评估 自修复能力 修复存储节点的修复节点对的个数 用Cr表示 B 8 t 1 2 n 8 38 自修复码的进展 通用射影自修复码的性能评估 B 8 t 1 2 n 10 B 8 t 1 2 n 12 39 自修复码的进展 通用射影自修复码的性能评估 GPSRC修复带宽表示为 再生码的修复带宽为 40 当B足够大时 GPSRC的修复带宽优于MSR 实际上 当B 32 t 1 4时 GPSRC的修复带宽为6 修复节点为3 而对于MSR码 修复带宽是由 2 式确定的 2 式是关于d个一个减函数 因此 如果d 15 MSR码可以达到其最小的修复带宽为7 5 大于GPSRC的修复带宽 自修复码的进展 通用射影自修复码的性能评估 B 16 k 4 41 自修复码的进展 通用射影自修复码的性能评估 由下图 一般情况下GPSRC在修复带宽和修复节点性能中均优于MSR码 而其代价为失去MDS特性 B 32 k 4 42 自修复码的进展 自修复码与RS码的开销评估 RS k n k w 1 w 1 SRC nw w 1 k w 8 k 2 43 自修复码的进展 自修复码与柯西优化RS码的开销评估 44 总结 GPSRC满足PSRC的基本特性 选择节点灵活 编码率高 修复过程 修复带宽和修复节点均优于MSR码 重建过程 重建带宽达到最优 构造过程 修复过程和重建过程 异或运算 计算复杂度很低 计算复杂度 修复带宽以及修复节点 优于擦除编码 再生码 GPSRC易于实施 精确修复代价低 一般情况 不满足MDS特性 45 未来研究方向 同时满足下面性质的码 1 MDS特性2 最小修复带宽3 最小重建带宽4 精确修复5 GF 2 6 最小I O 46 主要参考文献 1 A G Dimakis P B GodfreyandY WuandM J W