Erasure_code在分布式存储系统中的研究.pptVIP

有限域理论 GF(2w) ：0—2w-1的整数 加法、减法：XOR运算 乘法、除法：多项式相乘（除）并模除基本多项式 有限域运算 例如在GF(24 )中： 11 + 7=1011⊕0111=1100=12 11 – 7=1011⊕0111=1100=12 乘法：先要将元素的二进制形式转化为多项式的形式，然后作多项式的乘法，再将结果对本原多项式（GF (24)中本原多项式为x4+x+1）求余，最后再把结果转化为二进制的形式。 以11×7为例： 11（1011）对应的多项式为x3+x+1 7 （0111）对应的多项式为x2+x+1 两个多项式作多项式乘法后的结果再对本原多项式 x4+x+1求余，结果是x2，转化为二进制形式为0100，即为4 。 基于Vandermonde矩阵的RS算法 遇到的问题 文件末补“0”，去“0” 如何操作文件 .txt文件的普及 如何获取对应数据分块所在的数据碎片 内存文件映射技术 Windows的一种内存管理方法 直接对被映射的文件进行访问，而不必执行文件I/O操作，无需对文件内容进行缓冲处理 适合处理大文件 内存文件映射技术 分布式存储技术的其他应用 基于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 ⊕promotes “Computing as Utility” “Data Intensive Business” ⊕profound impacts on economic 赋予互联网更大的内涵，并改变互联网企业的运营模式。 扩大软硬件应用外延，并改变软硬件产品的应用模式。 有哪些信誉好的足球投注网站是开启云计算的一把钥匙。 because of search , we research cloud computing ; because of cloud computing , we can search everything available and easily. 文件合并实现 文件合并实现 达到了： 数据的分布式 冗余存储！ 性能分析 性能测试 测试平台为Visual Studio 2008，奔腾2.8G cpu，内存 480M，取当数据块数n=5，校验块数m=3，w=8时： 操作 100K(ms) 500K(ms) 1M(ms) 10M(ms) 50M(ms) 100M(ms) 250M(ms) 分割时间 20 71 153 1540 5341 10000 30325 合并时间 22 82 179 1892 6637 13540 33612 分割时间/文件大小(ms/k) 0.2 0.142 0.149 0.15 0.104 0.098 0.118 合并时间/文件大小(ms/k) 0.22 0.164 0.175 0.185 0.13 0.132 0.131 t分割≈t合并， t合并略大 t分割（t合并）/文件大小微呈减小趋势变化，但比例一定 同样大小不同类型文件分割合并耗时存在一定差别 性能分析 数据可用性分析 例：存储系统中由1 000 000个结点组成，其 中10%的结点不可用 传 统 复 制 算 法：存储数据D的2个副本 — 0.99 编 码 率 为 0.5 的 基 于erasure code 的 复 制 算 法：对D的32个数据块进行编码 —0.999999998 基于Erasure code的高可用分布式存储体系 系 统 接 口 文件 编码 解码 模块 分块 分发 获取 模块 动态 维护 模块 其他 功能 模块 Chord 底层的infrastructure： 分布式 存储和计算！ Erasure code在分布式存储系统中的研究 学 院