Erasure-code在分布式存储系统中的研究PPT课件

Erasurecode在分布式存储系统中的研究,学院：计算机科学与技术学院专业：计算机科学与技术学号：08S003045姓名：王佳导师：余翔湛副教授,主要内容,研究背景及研究意义研究内容设计与实现关键技术分析分布式存储技术的应用,研究背景及研究意义,灾难数据损失公司瘫痪容灾！容灾有效有意义数据本地化存储的局限性分布式存储！,研究背景及研究意义,较高的数据持续性和可靠性冗余容错！冗余容错完全数据复制RAID,目的意义,研究内容,Erasurecode理论基本思想基于Vandermonde矩阵的RS算法有限域理论内存文件映射技术分布式存储,有限域理论,GF(2w)：02w-1的整数加法、减法：XOR运算乘法、除法：多项式相乘（除）并模除基本多项式,有限域运算,例如在GF(24)中：11+7=10110111=1100=12117=10110111=1100=12乘法：先要将元素的二进制形式转化为多项式的形式，然后作多项式的乘法，再将结果对本原多项式（GF(24)中本原多项式为x4+x+1）求余，最后再把结果转化为二进制的形式。以117为例：11（1011）对应的多项式为x3+x+17（0111）对应的多项式为x2+x+1两个多项式作多项式乘法后的结果再对本原多项式x4+x+1求余，结果是x2，转化为二进制形式为0100，即为4。,Erasurecode理论基本思想,将一个数据文件划分为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算法,基于Vandermonde矩阵的RS算法,基于Vandermonde矩阵的RS算法,若m个块丢失，则将m个块对应的A矩阵和E矩阵中的行删去，得到新的nn阶矩阵A和n1阶矩阵E。A是非奇异的，对A求逆得到A-1恢复数据：D=A-1E,设计,C语言实现galois有限域运算+基于Vandermonde矩阵的RS算法思想不涉及文件操作验证上述结果正确性引入文件操作，先小后大模块独立化改进验证,文件分割模块,文件合并模块,数据的可用性分割的可控性数据的冗余性,实现,冗余容灾,文件分割实现,文件分割实现,文件合并实现,文件合并实现,达到了：数据的分布式冗余存储！,遇到的问题,文件末补“0”，去“0”如何操作文件.txt文件的普及如何获取对应数据分块所在的数据碎片,内存文件映射技术,Windows的一种内存管理方法直接对被映射的文件进行访问，而不必执行文件I/O操作，无需对文件内容进行缓冲处理适合处理大文件,内存文件映射技术,性能分析,性能测试测试平台为VisualStudio2008，奔腾2.8Gcpu，内存480M，取当数据块数n=5，校验块数m=3，w=8时：,t分割t合并，t合并略大t分割（t合并）/文件大小微呈减小趋势变化，但比例一定同样大小不同类型文件分割合并耗时存在一定差别,性能分析,数据可用性分析例：存储系统中由1000000个结点组成，其中10%的结点不可用传统复制算法：存储数据D的2个副本0.99编码率为0.5的基于erasurecode的复制算法：对D的32个数据块进行编码0.999999998,基于Erasurecode的高可用分布式存储体系,分布式存储技术的其他应用,基于peer-to-peer计算模型的海量分布式文件系统（1）存储体系结构问题（2）Peer-to-Peer路由算法（3）分布式索引、检索问题（4）资源访问效率问题（5）分布式安全体系问题,云计算(CloudComputing)WhatisCloudComputing?GridComputingComputingasUtilityWebServicesinthecloudSAAS(Softwareasaservice)PAAS(Platformasaservice)CC=SAAS+PAAS+Data+InfrastructureAsimpleexample:分布式邮件系统,Thevaluetransparentlymakesoftwareanddataavailableeverywhe