版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024股份有限公司股份转让合同协议书范本
- 摩托车行驶中的路况与驾驶感受考核试卷
- 建筑物拆除中的工程工艺与管理考核试卷
- 公司债券的发行与投资考核试卷
- 防汛防洪应急
- 时尚服饰企业的人力资源管理考核试卷
- 服饰品牌的差异化竞争与品牌价值考核试卷
- 广告与社会媒体互动考核试卷
- SH1573-生命科学试剂-MCE
- 世界杯管理模式
- JT-T 617.2-2018 危险货物道路运输规则 第2部分:分类 含2024年第1号修改单
- 2024年合肥兴泰金融控股(集团)有限公司招聘笔试冲刺题(带答案解析)
- 大学生职业生涯展示
- 《金属非金属地下矿山监测监控系统建设规范》
- “国家中小学智慧教育平台”应用工作实施方案
- 《中国慢性阻塞性肺疾病基层诊疗与管理指南(2024年)》解读
- 安全操作规程、作业指导书
- MOOC 软件安全之恶意代码机理与防护-武汉大学 中国大学慕课答案
- 档案工作协调机制
- 肝硬化门静脉高压食管胃静脉曲张出血的防治指南( 2022)
- 2023年1月自考00804金融法二试题及答案
评论
0/150
提交评论