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

Erasurecode在分布式存储系统中的研究 学院 计算机科学与技术学院专业 计算机科学与技术学号 08S003045姓名 王佳导师 余翔湛副教授 主要内容 研究背景及研究意义 研究内容 设计与实现 关键技术分析 分布式存储技术的应用 研究背景及研究意义 灾难 数据损失 公司瘫痪 容灾 容灾有效有意义 数据本地化存储的局限性 分布式存储 研究背景及研究意义 较高的数据持续性和可靠性 冗余容错 冗余容错 完全数据复制 RAID 目的意义 研究内容 Erasurecode理论基本思想基于Vandermonde矩阵的RS算法有限域理论内存文件映射技术分布式存储 有限域理论 GF 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 转化为二进制形式为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矩阵中的行删去 得到新的n n阶矩阵A 和n 1阶矩阵E A 是非奇异的 对A 求逆得到A 1恢复数据 D A 1 E 设计 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 GridComputing ComputingasUtility WebServicesinthecloud SAAS Softwareasaservice PAAS Platformasaservice CC SAAS PAAS Data Infrastructure Asimpleexample 分布式邮件系统 Thevalue transparentlymakesoftwareanddataavailableeverywhere promotes ComputingasUtility DataIntensiveBusiness profoundimpactsoneconomic 赋予互联网更大的内涵 并改变互联网企业的运营模式 扩大软硬件应用外延 并改变软硬件产品的应用模式 底层的infrastructure 分布式存储和计算 搜索是开启云计算的一把钥匙