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

《Erasure code在分布式存储系统中的研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、0，即为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矩阵算子D1D2D3D4D5D6D7D8C1C2基于Vandermonde矩阵的RS算法

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

5、“0”如何操作文件.txt文件的普及如何获取对应数据分块所在的数据碎片内存文件映射技术Windows的一种内存管理方法直接对被映射的文件进行访问，而不必执行文件I/O操作，无需对文件内容进行缓冲处理适合处理大文件内存文件映射技术性能分析性能测试测试平台为VisualStudio2008，奔腾2.8Gcpu，内存480M，取当数据块数n=5，校验块数m=3，w=8时：操作100K(ms)500K(ms)1M(ms)10M(ms)50M(ms)100M(ms)250M(ms)分割时间2071153154053411000030325合并时间228217918926637135

6、4033612分割时间/文件大小(ms/k)0.20.1420.1490.150.1040.0980.118合并时间/文件大小(ms/k)0.220.1640.1750.1850.130.1320.131t分割≈t合并，t合并略大t分割（t合并）/文件大小微呈减小趋势变化，但比例一定同样大小不同类型文件分割合并耗时存在一定差别性能分析数据可用性分析例：存储系统中由1000000个结点组成，其中10%的结点不可用传统复制算法：存储数据D的2个副本—0.99编码率为0.5的基于erasurecode的复制算法：对D的32个数据块进行编码—0.999999998基于Erasur

7、ecode的高可用分布式存储体系系统接口文件编码解码模块分块分发获取模块动态维护模块其他功能模块Chord分布式存储技术的其他应用基于peer-to-peer计算模型的海量分布式文件系统（1）存储体系结构问题（2）Peer-to-Peer路由算法（3）分布式索引、检索问题（4）资源访问效率问题（5）分布式安全体系问题云计算(CloudComputing)＊WhatisCloudComputing?⊕GridComputing⊕ComputingasUtility⊕WebServicesinthecloud⊕SAAS(Soft