Erasure-code在分布式存储系统中的研究.ppt

1、Erasure code在分布式存储系统中的研究,学 院： 计算机科学与技术学院 专 业： 计算机科学与技术 学 号： 08S003045 姓 名： 王佳 导 师： 余翔湛 副教授,主要内容,研究背景及研究意义 研究内容 设计与实现 关键技术分析 分布式存储技术的应用,研究背景及研究意义,灾难数据损失公司瘫痪 容灾！ 容灾有效有意义 数据本地化存储的局限性 分布式存储！,研究背景及研究意义,较高的数据持续性和可靠性 冗余容错！ 冗余容错 完全数据复制 RAID,目的意义,研究内容,Erasure code理论基本思想 基于Vandermonde矩阵的RS算法 有限域理论 内存文件映射技术 分布

2、式存储,有限域理论,GF(2w) ：02w-1的整数 加法、减法：XOR运算 乘法、除法：多项式相乘（除）并模除基本多项式,有限域运算,例如在GF(24 )中： 11 + 7=10110111=1100=12 11 7=10110111=1100=12 乘法：先要将元素的二进制形式转化为多项式的形式，然后作多项式的乘法，再将结果对本原多项式（GF (24)中本原多项式为x4+x+1）求余，最后再把结果转化为二进制的形式。 以117为例： 11（1011）对应的多项式为x3+x+1 7 （0111）对应的多项式为x2+x+1 两个多项式作多项式乘法后的结果再对本原多项式 x4+x+1求余，结果是

3、x2，转化为二进制形式为0100，即为4 。,Erasure code理论基本思想,将一个数据文件划分为n个等长的数据块（不 足以0补充），通过编码生成m个校验块。根据 其中任意n个分块就可恢复出原文件，而少于n 个分块无法获取原文件，这样能容忍多达m个节 点的失效。其中n/(m+n)为编码率。,基于Vandermonde矩阵的RS算法,基本思想：n=8，m=2 = F1(D1,D2,D3,D4,D5,D6,D7,D8) = F2(D1,D2,D3,D4,D5,D6,D7,D8) 注：F1，F2为Vandermonde矩阵算子,C1,C2,基于Vandermonde矩阵的RS算法,基于Vand

4、ermonde矩阵的RS算法,基于Vandermonde矩阵的RS算法,若m个块丢失，则将m个块对应的A矩阵 和E矩阵中的行删去，得到新的nn阶矩 阵A和n1阶矩阵E 。 A是非奇异的，对A求逆得到A-1 恢复数据：D = A -1E,设计,C语言实现galois有限域运算 + 基于Vandermonde矩阵的RS算法思想 不涉及文件操作验证上述结果正确性 引入文件操作，先小后大 模块独立化 改进验证,文件分割模块,文件合并模块,数据的可用性 分割的可控性 数据的冗余性,实现,冗余容灾,文件分割实现,文件分割实现,文件合并实现,文件合并实现,达到了： 数据的分布式 冗余存储！,遇到的问题,文件

5、末补“0”，去“0” 如何操作文件 .txt文件的普及 如何获取对应数据分块所在的数据碎片,内存文件映射技术,Windows的一种内存管理方法 直接对被映射的文件进行访问，而不必执行文件I/O操作，无需对文件内容进行缓冲处理 适合处理大文件,内存文件映射技术,性能分析,性能测试 测试平台为Visual Studio 2008，奔腾2.8G cpu，内存 480M，取当数据块数n=5，校验块数m=3，w=8时：,t分割t合并， t合并略大 t分割（t合并）/文件大小微呈减小趋势变化，但比例一定 同样大小不同类型文件分割合并耗时存在一定差别,性能分析,数据可用性分析 例：存储系统中由1 000 0

6、00个结点组成，其 中10%的结点不可用 传 统 复 制 算 法：存储数据D的2个副本 0.99 编 码 率 为 0.5 的 基 于erasure code 的 复 制 算 法：对D的32个数据块进行编码 0.999999998,基于Erasure code的高可用分布式存储体系,分布式存储技术的其他应用,基于peer-to-peer计算模型的海量分布式文件系统 （1）存储体系结构问题 （2）Peer-to-Peer路由算法 （3）分布式索引、检索问题 （4）资源访问效率问题 （5）分布式安全体系问题,云计算(Cloud Computing) What is Cloud Computing? Grid Computing Computing as Utility Web Services in the cloud SAAS (Software as a service) PAAS (Platform as a service) CC = SAAS + PAAS + Data + Infrastructure A simple example : 分布式邮件系统,The value transparently make software and data available everywhere prom