《纠删码原理及应用讲解》由会员分享，可在线阅读，更多相关《纠删码原理及应用讲解（37页珍藏版）》请在金锄头文库上搜索。
1、 纠删码原理及应用 报告内容 王 欢 2013-1 主要内容 纠 删 码 原 理 纠 删 码 应 用 纠 删 码 研 究 b d a c AB b d a c a+b+x+y = A 2a+3b+x+y = B 机制：纠删 码 Client Server 通信实例 客户端和服务端相同的编解码 利用数学计算“存储”数据 网络传输的不可靠，通过技术手段来增强可靠性 Erasure codes用来解决链接层中不相关的错误，以及网 络拥塞和buffer限制造成丢包错误 ARQ(Automatic Repeat request)在单向传输的协议中 能起到很好的作用，但是对于多播协议，使用ARQ就十分 浪
2、费资源了 带宽资源 vs 计算资源 网络中的问题 网络传输 N元一次方程组，k = k，已知量数目大于等于未知量 网络中的应用，即时编码解码，RS编解码芯片 Data stripstripparity 条带stripe stripstripparity Disk1 存储应用 Disk3Disk2 对数据块进行分片 根据编码方式计算校验块 进行分片存储 parity 解码，数据恢复 Disk2 损坏，数据丢失 strip Replication VS Erasure Coding a=2 b=3 a=2 b=3 a=2 b=3 B=3 a=2 a+b=5 b=3 a=2 2a+b=7 Repli
3、cation Erasure Code 存储利用率，容错 22/62/4 RS/CRS 阵列码(array code) 奇偶校验码 LDPC码 纠删码分类 MDS Maximum Distance Separable (MDS) codes any m disks fail, the original data may be reconstructed 纠删码分类 RS类码是唯一可以满足，任意磁盘数目N和校 验数据M中丢失M块恢复的MDS编码。 RS 类 CRS coding operates on entire strips(条带块) = w * packet RS The strip un
4、it is a w-bit word Vandermonde matrix Cauchy matrices D 是Data Device ，用于保存数据，C 是校验位，用于重 建恢复数据 Di 条带块，Ci 是对应生成的校验数据块 RS 类 每个条带上的数据块生成对应条带上的校验块，数据 块大小和校验块大小相同， 一般把数据块的个数用k 表示，n 表示数据块和校验块 总数，这样的编码称为k,n 编码，最多可以容n-k 个 Data Devices 失效。m+n : m 数据 n 校验 RS 类 一个kk 大小的单位矩阵I ，下面是生成校验位的n- kk 大小的矩阵B* RS 类 这两部分分别与
5、数据矩阵D 相乘生成两部分分别为数 据部分D 和校验部分C RS 类 每个数据和编码有一个对应的矩阵中的 行数据 RS 类 m块数据丢失 行列式的初等变换：数据和校验行行对应 RS 类 任意m 块数据丢失 进行解码，根据删除的数据生成解码矩阵B B*D 与存在的数据之间相等 RS 类 计算B的逆矩阵 B-1 RS 类 求B的逆矩阵 等号两侧同时乘以 B的逆矩阵 因为B-1 *B = I, 所以得到了解码后的数据D RS 类 求B的逆矩阵 等号两侧同时乘以 B的逆矩阵 因为B-1*B = I, 所以得到了解码后的数据D RS 类 求B的逆矩阵 等号两侧同时乘以 B的逆矩阵 因为B-1*B = I
6、, 所以得到了解码后的数据D RS 类 文件编码示意图 read from file buffer encode write to the storage GF(2w) ：02w-1的整数 加法、减法：XOR运算 乘法、除法：多项式相乘（除）并模除基 本多项式 伽罗华域（有限域运算 ） 阵列码 二维阵列编码及校验矩阵 二维阵列码是奇偶校验的自然推广,磁盘阵列总是用异或(XOR)操作来产生奇 偶数据 保持单容错时奇偶校验码的最优编码复杂度，冗余度不再是最优的了 二维阵列码也很容易推广为k维阵列 阵列码 与RS编码相比，阵列码完全基于异或（XOR)运算 阵列码的含义就是将原始数据和冗余都存储在一个
7、2 维或者多维的阵列中。 实现容易，编码，更新，以及重构的过程相对简单 水平校验加其他一种校验共同构成双容错，不同 之处就在于“另一种校验”的不同选择 阵列码 横向阵列码 纵向阵列码 EVENODD, RDP, EEO, Liberation Code x-code, p-code, weaver code (p-1)*p的数据阵列，两个校验盘 第一个校验盘：水平校验，RAID4/5 第二校验盘：主对角线方向组织 S导致计算代价非最优 EVENODD编码 Open Source Libraries Luby -CRS coding was developed at the ICSI lab i
8、n Berkeley,Written entirely in C+ Zfec -built on top of a RS coding library developed for reliable multicast by Rizzo,Written in C. Jerasure -Jerasure is a C library released in 2007 that supports a wide variety of erasure codes Cleversafe: -In May, 2008, Cleversafe exported the first open source ve
9、rsion of its dispersed storage system .Written entirely in Java 纠删码应用 纠删码应用 Facebook-Hadoop 后台编解码 降级读解码 Map-reduce计算 QFS(KFS) QFS(KFS) 纠删码研究 纠删码研究 编解码算法 客户端重建，IO考虑 降级读优化 速度优化map-reduce（hadoop） 纠删码的研究 微软LRC 12+2+2 微软LRC 12+2+2 Summary 纠 删 码 原 理 纠 删 码 应 用 纠 删 码 研 究 数学计算求未知数X, Y, Z，数学科 学服务工业生产 存储成本 vs 计算资源 存储资源，计算资源，带宽资源的降 低
