《Erasurecode在分布式存储系统中的研究实用教案》由会员分享，可在线阅读，更多相关《Erasurecode在分布式存储系统中的研究实用教案（34页珍藏版）》请在金锄头文库上搜索。
1、主要主要(zhyo)内容内容研究研究(ynji)(ynji)背景及研究背景及研究(ynji)(ynji)意义意义研究研究(ynji)(ynji)内容内容设计与实现设计与实现关键技术分析关键技术分析 分布式存储技术的应用分布式存储技术的应用第1页/共33页第一页，共34页。研究背景研究背景(bijng)及研究意义及研究意义灾难灾难数据损失数据损失公司瘫痪公司瘫痪(tnhun)容灾！容灾！容灾有效有意义容灾有效有意义数据本地化存储的局限性数据本地化存储的局限性分布式存储！分布式存储！第2页/共33页第二页，共34页。研究研究(ynji)背景及研究背景及研究(ynji)意义意义较高的数据持续性和可靠
2、性较高的数据持续性和可靠性冗余容错冗余容错(rncu)！冗余容错冗余容错(rncu)完全数据复制完全数据复制RAID目的意义目的意义第3页/共33页第三页，共34页。研究研究(ynji)内容内容Erasurecode理论基本思想理论基本思想基于基于Vandermonde矩阵的矩阵的RS算法算法有限域理论有限域理论内存文件映射技术内存文件映射技术(jsh)分布式存储分布式存储第4页/共33页第四页，共34页。有限有限(yuxin)域理论域理论GF(2w)：02w-1的整数的整数加法、减法：加法、减法：XOR运算运算乘法乘法(chngf)、除法：多项式相乘（除）并模除基本多项式、除法：多项式相乘（
3、除）并模除基本多项式第5页/共33页第五页，共34页。有限有限(yuxin)域运算域运算例如例如(lr)在在GF(24)中：中：11+7=10110111=1100=12117=10110111=1100=12乘法：先要将元素的二进制形式转化为多项乘法：先要将元素的二进制形式转化为多项式的形式，然后作多项式的乘法，再将结果对式的形式，然后作多项式的乘法，再将结果对本原多项式（本原多项式（GF(24)中本原多项式为中本原多项式为x4+x+1）求余，最后再把结果转化为二进制）求余，最后再把结果转化为二进制的形式。的形式。以以117为例：为例：11（1011）对应的多项式为）对应的多项式为x3+x+
4、17（0111）对应的多项式为）对应的多项式为x2+x+1两个多项式作多项式乘法后的结果再对本原两个多项式作多项式乘法后的结果再对本原多项式多项式x4+x+1求余，结果是求余，结果是x2，转化为二，转化为二进制形式为进制形式为0100，即为，即为4。第6页/共33页第六页，共34页。Erasurecode理论理论(lln)基本思想基本思想将一个数据文件划分为将一个数据文件划分为n个等长的数据块（不个等长的数据块（不足以足以0补充），通过编码生成补充），通过编码生成m个校验个校验(xioyn)块。根据块。根据其中任意其中任意n个分块就可恢复出原文件，而少于个分块就可恢复出原文件，而少于n个分块无
5、法获取原文件，这样能容忍多达个分块无法获取原文件，这样能容忍多达m个节个节点的失效。其中点的失效。其中n/(m+n)为编码率。为编码率。校校验验块块原文件原文件原文件原文件生生成成第7页/共33页第七页，共34页。基于基于(jy)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矩阵矩阵(jzhn)算子算子D1D2D3D4D5D6D7D8C1C2第8页/共33页第八页，共34页。基于基于(jy)Vandermon
6、de矩阵的矩阵的RS算法算法第9页/共33页第九页，共34页。基于基于Vandermonde矩阵矩阵(jzhn)的的RS算法算法第10页/共33页第十页，共34页。基于基于(jy)Vandermonde矩阵的矩阵的RS算法算法若若m个块丢失，则将个块丢失，则将m个块对应的个块对应的A矩阵矩阵和和E矩阵中的行删去，得到新的矩阵中的行删去，得到新的nn阶矩阶矩阵阵A和和n1阶矩阵阶矩阵E。A是非奇异的，对是非奇异的，对A求逆得到求逆得到A-1恢复恢复(huf)数据：数据：D=A-1E第11页/共33页第十一页，共34页。设计设计(shj)C语言实现语言实现galois有限域运算有限域运算+基于基于
7、Vandermonde矩阵的矩阵的RS算法思想算法思想不涉及文件操作不涉及文件操作(cozu)验证上述结果正确性验证上述结果正确性引入文件操作引入文件操作(cozu)，先小后大，先小后大模块独立化模块独立化改进验证改进验证第12页/共33页第十二页，共34页。文件文件(wnjin)分割模块分割模块第13页/共33页第十三页，共34页。文件文件(wnjin)合并模块合并模块数据数据(shj)的可用性的可用性分割的可控性分割的可控性数据数据(shj)的冗余性的冗余性第14页/共33页第十四页，共34页。实现实现(shxin)冗余冗余(rn y)容灾容灾第15页/共33页第十五页，共34页。文件分割
8、文件分割(fng)实现实现第16页/共33页第十六页，共34页。文件分割文件分割(fng)实现实现第17页/共33页第十七页，共34页。文件合并文件合并(hbng)实现实现第18页/共33页第十八页，共34页。文件文件(wnjin)合并实现合并实现达到达到(d do)了：了：数据的分布式数据的分布式冗余存储！冗余存储！第19页/共33页第十九页，共34页。遇到遇到(ydo)的问题的问题文件末补文件末补“0”，去，去“0”如何操作文件如何操作文件.txt文件的普及文件的普及如何获取对应数据分块所在如何获取对应数据分块所在(suzi)的数据碎片的数据碎片第20页/共33页第二十页，共34页。内存文
9、件内存文件(wnjin)映射技术映射技术Windows的一种内存管理方法的一种内存管理方法直接对被映射直接对被映射(yngsh)的文件进行访问，而不必执行文件的文件进行访问，而不必执行文件I/O操作，无需对操作，无需对文件内容进行缓冲处理文件内容进行缓冲处理适合处理大文件适合处理大文件第21页/共33页第二十一页，共34页。内存内存(nicn)文件映射技术文件映射技术第22页/共33页第二十二页，共34页。性能性能(xngnng)分析分析性能性能(xngnng)测试测试测试平台为测试平台为VisualStudio2008，奔腾，奔腾2.8Gcpu，内存，内存480M，取当数据块数，取当数据块数
10、n=5，校验块数，校验块数m=3，w=8时：时：操作操作100K(ms)500K(ms)1M(ms)10M(ms)50M(ms)100M(ms)250M(ms)分割时间分割时间2071153154053411000030325合并时间合并时间2282179189266371354033612分割时间分割时间/文件大小文件大小(ms/k)0.20.1420.1490.150.1040.0980.118合并时间合并时间/文件大小文件大小(ms/k)0.220.1640.1750.1850.130.1320.131第23页/共33页第二十三页，共34页。t分割t合并(hbng)，t合并(hbng)略
11、大t分割（t合并(hbng)）/文件大小微呈减小趋势变化，但比例一定同样大小不同类型文件分割合并(hbng)耗时存在一定差别第24页/共33页第二十四页，共34页。性能性能(xngnng)分析分析数据可用性分析数据可用性分析例：存储系统中由例：存储系统中由1000000个结点组成个结点组成(zchn)，其，其中中10%的结点不可用的结点不可用传传统统复复制制算算法：存储数据法：存储数据D的的2个副本个副本0.99编编码码率率为为0.5的的基基于于erasurecode的的复复制制算算法：对法：对D的的32个数据块进行编码个数据块进行编码0.999999998第25页/共33页第二十五页，共34
12、页。基于基于(jy)Erasurecode的高可用的高可用分布式存储体系分布式存储体系系系 统统 接接 口口文件文件 编编码码解码解码模块模块分块分块分发分发获取获取模块模块动态动态维护维护模块模块其他其他功能功能模块模块Chord第26页/共33页第二十六页，共34页。分布式存储技术的其他分布式存储技术的其他(qt)应用应用基于基于peer-to-peer计算模型的海量分布式文件系统计算模型的海量分布式文件系统（1）存储体系结构问题）存储体系结构问题（2）Peer-to-Peer路由算法路由算法（3）分布式索引）分布式索引(suyn)、检索问题、检索问题（4）资源访问效率问题）资源访问效率问
13、题（5）分布式安全体系问题）分布式安全体系问题第27页/共33页第二十七页，共34页。云计算云计算(jsun)(CloudComputing)WhatisCloudComputing?GridComputingComputingasUtilityWebServicesinthecloudSAAS(Softwareasaservice)PAAS(Platformasaservice)CC=SAAS+PAAS+Data+InfrastructureAsimpleexample:分布式邮件系统分布式邮件系统第28页/共33页第二十八页，共34页。Thevaluetransparentlymakeso
14、ftwareanddataavailableeverywherepromotes“ComputingasUtility”&“DataIntensiveBusiness”profoundimpactsoneconomic第29页/共33页第二十九页，共34页。赋予互联网更大的内涵赋予互联网更大的内涵(nihn)，并改变互联网企业的运营模式。，并改变互联网企业的运营模式。扩大软硬件应用外延，并改变软硬件产品的应用模式。扩大软硬件应用外延，并改变软硬件产品的应用模式。底层底层(d cn)的的infrastructure：分布式分布式存储和计算！存储和计算！第30页/共33页第三十页，共34页。搜索搜
15、索(susu)是开启云计算的一把钥匙。是开启云计算的一把钥匙。becauseofsearch,weresearchcloudcomputing;becauseofcloudcomputing,wecansearcheverythingavailableandeasily.第31页/共33页第三十一页，共34页。第32页/共33页第三十二页，共34页。感谢您的欣赏(xnshng)！第33页/共33页第三十三页，共34页。内容(nirng)总结主要内容。灾难数据损失(snsh)公司瘫痪。乘法、除法：多项式相乘（除）并模除基本多项式。11（1011）对应的多项式为x3+x+1。基本思想：n=8，m=2。= F2(D1,D2,D3,D4,D5,D6,D7,D8)。若m个块丢失，则将m个块对应的A矩阵。阵A和n1阶矩阵E。A是非奇异的，对A求逆得到A-1。文件末补“0”，去“0”。t分割（t合并）/文件大小微呈减小趋势变化，但比例一定。感谢您的欣赏第三十四页，共34页。
