联系方式请留下您的联系方式方便我们沟通确认必填项，请输入正确的QQ号必填项，请输入正确的手机号必填项，请输入正确的邮箱确定亲，要输入内容才能提交哦~感谢您的支持，我们会尽快核实~豆丁微信公众号
君，已阅读到文档的结尾了呢~~
基于p2p的分布式存储系统的应用研究及实现
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
基于p2p的分布式存储系统的应用研究及实现
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口赞助商链接
当前位置： >>
基于erasure+code的高可用分布式存储系统的设计与实现
分类号ＵＤＣ学号罾级！！！！！ｉ！！！垒匠工程硕士学位论文基于Ｅｒａｓｕｒｅ Ｃｏｄｅ的高可用分布式存储系统 的设计与实现硕士生姓名崮堑缝研究方向＝ｉ士篡扭厘用撞丕国防科学技术大学研究生院 二ｏｏ六年十月国防科学技术大学研究生院工程硕士学位论文摘要自“９?１１”事件之后，数据存储日益受到重视，如何确保数据的安全性成为 人们关注的焦点，这要求具有安全可靠的分布式数据存储系统的出现，它将信息 分散在网络或数个存储节点上，使用户在持续有效且高度可靠的方式下访问信息， 即使系统在节点失效，网络断开，或受到恶意攻击的情况下，仍能有效的提供数据存储服务。分布式散列表技术ＤＨＴ的引入，使得基于Ｐ２Ｐ的广域存储系统的研究成为当 今的热点，在研的系统包括：ＯｅｅａｎＳｔｏｒｅ（Ｂｅｒｋｅｌｅｙ）、ＣＦＳ（ＭＩＴ）、 Ｐａｓｔ（Ｒｉｃｅ＆Ｍｉｅｒｏｓｏ舢、Ｇｒａｎａｒｙ（清华大学）等。但由于实际Ｐ２Ｐ环境中的异构性，动 态性，不可信任性及易受攻击性，影响了存储系统的可用性。本文在８６３项目“协 作式应急响应服务与基于漂移的可生存系统研究”的基础上，将ｅｒａｓｕｒｅ ｃｏｄｅ与 ＤＨＴ结合起来，研究高可用的分布式存储系统的设计与实现，主要工作包括以下方面：１）分析了Ｐ２Ｐ技术在分布式存储系统研究方面的优势，对分布式存储系统的 研究现状做了总结和归纳，并且研究了Ｐ２Ｐ技术的相关理论； ２）分析、实现了基于Ｖａｎｄｅｒｍｏｎｄｅ矩阵与基于Ｃａｕｅｈｙ矩阵的ｅｒａｓｕｒｅｃｏｄｅ算法，并对两种算法进行了对比测试，结果表明基于Ｃａｕｃｈｙ矩阵的算法 较之基于Ｖａｎｄｅｒｍｏｎｄｅ矩阵的算法编解码效率分别提高了４３％和７６％；３）提出一种基于ｅｌ＇ａｓｕｒｅ ｃｏｄｅ技术的高可用分布式存储系统的体系结构，详细设计了系统的各个关键模块：文件编解码模块、分块分发与获取模块、 动态维护模块、其它功能模块，并进行了性能分析； ∞实现了基于ｅｌ－ａｓｕｒｅ ｃｏｄｅ技术的高可用分布式存储系统原型ＨＨＳｔｏｒｅ。对 系统的性能测试表明，集中式服务器的下载方式在节点数激增时，节点下 载所用的时间也增加非常迅速，其性能下降也非常快，而ＨＨＳｔｏｒｅ在网络规模非常大时，也能保持良好的性能。通过以上工作，本文设计并且实现了高可用的分布式存储系统，该系统能安 全可靠地实现数据的存储与下载，能满足国防等关键部门涉密数据的分布存储要 求，同时能够适应广域网中海量节点的并发下载请求，具有较好的可用性、安全性和易管理性，具有一定的军事及民用价值。主题词：ｅｌ＇ａＳｕｌ＇ｅ ｃｏｄｅ，Ｐ２Ｐ，冗余，高可用性，存储系统，分布式第ｉ页国防科学技术大学研究生院工程硕士学位论文ＡＢＳＴＲＡＣＴＡｆｔｅｒ ｔｈｅ ９１ ｌ ａｃｃｉｄｅｎｔ．ｄａｔａ ｓｔｏｍｇｅ ｂｅｃｏｍｅｓ ｍｏｒｅ ａｎｄ ｍｏｒｅ ｃｒｉｔｉｃａｌ．Ｉｔ ｂｅｃｏｍｅｓ ｆｏｃｕｓ ｈｏｗ ｔｏ ｅｎｓｕｒｅ ｔｈｅ ｓｅｃｕｒｉｔｙ ｏｆ ｔｈｅａｄａｔａ，ｗｈｉｃｈ ｄｅｓｉｒｅｓ ｔｈｅ ａｐｐｅａｒａｎｃｅ ｏｆ ｔｈｅ ｓａｆｅｔｙｃａｎａｎｄｔｒｕｓｔｙ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ．Ｉｔｕｓｅｒｄｉｓｔｒｉｂｕｔｅ ｄａｔａｏｎｔｈｅ ｎｅｔｗｏｒｋｏｒＳｅｖｅｒａｌｎｏｄｅｓ ａｎｄ ｍａｋｅｏｂｔａｉｎ ｔｈｅ ｄａｔａ ｉｎ ｔｈｅ ｃｏｎｔｉｎｕａｌｌｙ－ｅｆｆｅｃｔｉｖｅ ａｎｄ ｈｉｇｒａｙ ｔｒｕｓｔｙ ｗａｙ． ｄｉｓｃｏｎｎｅｃｔｉｎｇ，ｏｒ ｓｕｆｆｅｒｉｎｇ ｈｏｓｔｉｌｅ ａｔｔａｃｋｓ，ｔｈｅ ｓｙｓｔｅｍＥｖｅｎ诵ｔｌｌ Ｃａｎｎｏｄｅｓｆａｉｌｉｎｇ，ｎｅｔｗｏｒｋｄａｔａｓｔｉｌｌ ｓｕｐｐｏｒｔ ｔｈｅｓｔｏｒａｇｅ ｓｅｒｖｉｃｅ． ｄｉｓｔｒｉｂｕｔｅｄ ｈａｓｈ ｔａｂｌｅ。ｉｔ ｂｅｃｏｍｅｓｏｎ ａＡｆｔｅｒ ｔｌｌｅ ｉｎｔｒｏｄｕｃｔｉｏｎ ｏｆ ｔｈｅｈｏｔ ｔｏｐｉｃｎｏｗａｄａｙｓ ｔｈｅ ｗｉｄｅ―ａｒｅａ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ ｂａｓｅｄ ｃａｒｒｉｅｄ ｏｕｔ ｃｕｒｒｅｎｔｌｙ ｉｎｃｌｕｄｅｔｈｅ ｐｅｅｒ－ｔｏ―ｐｅｅｒ．１１１ｅ ｐｒｏｊｅｃｔｓ ｂｅｉｎｇＯｃｅａｎＳｔｏｒｅ（Ｂｅｒｋｅｌｅｙ），ＣＦＳ（ＭＩＴ），Ｐａｓｔ（Ｒｉｃｅ＆Ｍｉｃｒｏｓｏｆｔ），Ｇｒａｎａｒｙ（Ｔｓｉｎｇｈｕａ）ａｎｄｉｓＳＯｏｎ．Ｂｕｔ ｂｅｃａｕｓｅ ｏｆｓｕｃｈ ｃｈａｒａｃｔｅｒｓ ａｓ ｈｅｔｅｒｏｇｅｎｅｉｔｙ，ｄｙｎａｍｉｃ， ｉｎ ｔｈｅ ｒｅａｌ Ｐ２Ｐ ｅｎｖｉｒｏｎｍｅｎｔ，ｔｈｅ ａｖａｉｌａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｓｔｏｒａｇｅｏｎｄｉｓｔｒｕｓｔ，ａｎｄ ｖｕｌｎｅｒａｂｉｌｉｔｙｓｙｓｔｅｍｄｅｃｒｅａｓｅｄ．Ｂａｓｅｄｔｈｅｒｅｓｅａｒｃｈｏｆｔｈｅ８６３ｐｒｏｊｅｃｔ‘＇ｃｏｏｐｅｒａｔｉｖｅｅｍｅｒｇｅｎｃｙ―ｃｏｒｒｅｓｐｏｎｄｉｎｇ ａｎｄ ｄｒｉｆｔ－ｂａｓｅｄ ｓｕｒｖｉｖａｂｌｅ ｓｙｓｔｅｍ ｒｅｓｅａｒｃｈ’’ａｎｄ ｃｏｍｂｉｎｉｎｇ ｔｈｅ ｅｒａｓｎｒｅ ｃｏｄｅ ａｎｄ ＤＨＴ．ｔｈｉｓ ｄｉｓｓｅｒｔａｔｉｏｎ ｓｔｕｄｉｅｓ ｔｈｅ ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆｔｈｅｈｉｇｈｌｙ－ａｖａｉｌａｂｌｅ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ．１１１ｅ ｍａｉｎ ｃｏｎｔｒｉｂｕｔｉｏｎｓ ａｒｅ ａｓ ｆｏｌｌｏｗｉｎｇ．Ｆｉｒｓｔｌｙ，ｔｈｉｓ ｄｉｓｓｅｒｔａｔｉｏｎ ａｎａｌｙｓｅｓ ｔｈｅａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅＰ２Ｐ ｔｅｃｈｎｏｌｏｇｙ ｉｎ ｔｈｅｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ ａｎｄ ｓｕｍｍａｒｉｚｅｓ ｔｈｅ ｃｕｒｒｅｎｔ ｒｅｓｅａｒｃｈ ａｃｔｕａｌｉｔｉｅｓ．Ｉｔ ａｌｓｏ ｓｔｕｄｉｅｓ ｔｈｅ ｒｅｌａｔｉｏｎａｌ ｔｈｅｏｒｙ ｏｆＰ２Ｐｔｅｃｈｎｏｌｏｇｙ．ｉｍｐｌｅｍｅｎｔｓ ｔｈｅ ｅｒａｓｕｒｅ ｃｏｄｅ ａｌｇｏｒｉｔｈｍｓ Ｃａｕｃｈｙ ｍａｔｒｉｘ ａｎｄ ｍａｋｅａＳｅｃｏｎｄｌｙ，ｔｈｅ ｄｉｓｓｅｒｔａｔｉｏｎ ａｎａｌｙｓｅｓ ａｎｄ ｂａｓｅｄ ｏｎ ｔｈｅ Ｖａｎｄｅｒｍｏｎｄｅ ｍａｔｒｉｘ ａｎｄ ｔｈｅｃｏｍｐａｒｉｓｏｎｂｅｔｗｅｅｎ ｔｈｅｍ．ｎｅ４３ｒｅｓｕｌｔｓｈｏｗｓ．ｃｏｍｐａｒｅｄ ｅｆｆｉｃｉｅｎｃｙｔｏｔｈｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄｏｎｏｎｔｈｅ Ｖａｎｄｅｒｍｏｎｄｅｍａｔｒｉｘ，ｔｈｅ ｅｎｃｏｄｉｎｇ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄＣａｕｃｈｙ ｍａｔｒｉｘ ｉｎｃｒｅａｓｅｓ ｂｙｐｅｒｃｅｎｔ ａｎｄｏｎｄｅｃｏｄｉｎｇｏｆｔｈａｔ ｉｎｃｒｅａｓｅｓ ｂｙ ７６ ｐｅｒｃｅｎｔ．ａＴｈｉｒｄｌｙ，ｔｈｉｓ ｄｉｓｓｅｒｔａｔｉｏｎ ｐｒｏｐｏｓｅｓｈｉｇｈｌｙ－ａｖａｉｌａｂｌｅ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ｓｙｓｔｅｍｂａｓｅｄｔｈｅ ｅｒａｓｕｒｅ ＣＯｄｅ ａｎｄａｎａｌｙｓｅｓｕｐｉｎ ｄｅｔａｉｌ ｔｈｅ ｆｉｌｅ ｅｎ―ｄｅｃｏｄｉｎｇ ｍｏｄｕｌｅ．ｂｌｏｃｋｄｉｓ仃ｉｂｕｔｉｎｇ ａｎｄ ｆｅｔｃｈｉｎｇｆｕｎｃｔｉｏｎ ｍｏｄｕｌｅ，ｗｈｉｃｈｍｏｄｕｌｅ，ｄｙｎａｍｉｃａｌｌｙ ｍａｉｎｔａｉｎｉｎｇ ｍｏｄｕｌｅ ａｎｄ ｔｈｅ ｏｔｈｅｒｍａｋｅｏｆ ｔｈｅ ｓｙｓｔｅｍ．Ａｎｄ ｉｔ ａｌｓｏ ａｎａｌｙｓｅｓ ｔｈｅ ｓｙｓｔｅｍｐｅｒｆｏｒｍａｎｃｅ．Ｆｏｕｒｔｈｌｙ，ｔｈｉｓ ｄｉｓｓｅｒｔａｔｉｏｎ ｉｍｐｌｅｍｅｎｔｓｔｈｅＨＨＳｔｏｒｅ，ｔｈｅｐｒｏｔｏｔｙｐｅｏｆｔｈｅｈｉｇｈｌｙ―ａｖａｉｌａｂｌｅ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ ｂａｓｅｄｏｎｔｈｅ ｅｒａｓｌｌｒｅ ｃｏｄｅ．１１１ｅ ｔｅｓｔ ｏｆ ｔｈｅｓｙｓｔｅｍ ｐｅｒｆｏｒｍａｎｃｅ ｓｈｏｗｓ ｔｈａｔ ｔｈｅ ｄｏｗｎｌｏａｄｉｎｇ ｔｉｍｅ ｏｆ ｔｈｅｖｅｒｙｃｅｎｔｒａｌｓｅｒｖｅｒｉｎｃｒｅａｓｅｓｆａｓｔ，ｂｕｔ ｔｈｅｒａｐｉｄｌｙ ｗｈｉｌｅｐｅｒｆｏｒｍａｎｃｅ ｄｒｏｐｓ ｆａｓｔ ｗｈｅｎ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｔｈｅ ｎｏｄｅｓ ｉｎｃｒｅａｓｅｓ ｔｈｅ ＨＨＳｔｏｒｅ Ｃａｎ ｋｅｅｐ ｅｘｃｅｌｌｅｎｔ ｐｅｒｆｏｒｍａｎｃｅ ｅｖｅｎ ｗｈｅｎ ｔｈｅ ｎｅｔｗｏｒｋ ｓｉｚｅｌａｒｇｅ．ｂｅｃｏｍｅｓ ｖｅｒｙＦｒｏｍ ｗｈａｔ ｈａｓ ｂｅｅｎ ｄｏｎｅ ａｂｏｖｅ，ｔｈｅ ｄｉｓｓｅｒｔａｔｉｏｎ ｄｅｓｉｇｎｓ ａｎｄ ｉｍｐｌｅｍｅｎｔｓ ｔｈｅｈｉ曲ｌｙ?ａｖａｉｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ ｂａｓｅｄｏｎｔｈｅ ＤＨＴａｎｄ ｅｒａｓｕｒｅｃｏｄｅ．ｍ第ｉｉ页国防科学技术大学研究生院工程硕士学位论文 ｓｙｓｔｅｍｃＢｎ ｄｏｗｎｌｏａｄ ａｎｄ ｓｔｏｒｅ ｄａｔａ ｓａｆｅｌｙ ａｎｄ ｔｒｕｓｔｉｌｙ．Ａｎｄ ｉｔ ａｌｓｏＣａｌｌｓａｔｉｓｆｙ ｔｈｅｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ｄｅｍａｎｄ ｏｆ ｔｈｅ ｓｅｃｒｅｔｅ ｄａｔａ ｉｎ ｓｕｃｈ ｋｅｙ ｄｅｐａｒｔｍｅｎｔｓ ｌｉｋｅ ａｒｍｙ ａｎｄｔｈｅ ｐａｒａｌｌｅｌ ｒｅｑｕｅｓｔｓ ｆｒｏｍ ｔｈｅ ｎｕｍｅｒｏｕｓ ｎｏｄｅｓ ｉｎ ｗｉｄｅ－ａｒｅａ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ．Ｉｔ ｈａｓ ｔｈｅ ｂｅＲｅｒ ａｖａｉｌａｂｉｌｉｔｙ，ｓｅｃｕｒｉｔｙ ａｎｄ ｍａｎａｇｅａｂｌｅ ａｎｄ ｆｉｔｓ ｆｏｒ ａｌｌ ｋｉｎｄｓ ｏｆｄａｔａ ｓｔｏｒａｇｅ．ＫｅｙＷｏｒｄｓ：Ｅｒａｓｕｒｅｃｏｄｅ，Ｐ２Ｐ，Ｒｅｄｕｎｄａｎｃｙ，Ａｖａｉｌａｂｉｌｉｔｙ，Ｓｔｏｒａｇｅ ｓｙｓｔｅｍＤｉｓｔｒｉｂｕｔｅｄ第ｊｉｉ页国防科学技术大学研究生院工程硕士学位论文表目录表２．１常见的度数和网络的维数……………………………………………………。８ 表２．２ ｆｉｎｇｅｒ表的符号与定义网…………………………………………………………９ 表３．１算法复杂度对比．表３．２编码时间对比表………………………………………………………………２９表３．３解码时间对比表． 表５．１存储文件容量与节点数的关系………………………………………………５６第１Ｖ页国防科学技术大学研究生院工程硕士学位论文图目录图２．１ Ｃｈｏｒｄ标识环【９】…………………………… 图２．２ ＪＸＴＡ构架ｎ羽………………………………图３．１用两个校验块提供两次容错【２４１…………． 图３．２编码矩阵等式１【２４１………………………。一屹博博图３．３编码矩阵等式２㈨…………图３．４ ＧＦ（２３）上的加法和乘法表【拥…………………………………………………２４图３．５查表构造的生成矩阵【拥………………………………………………………２５ 图３．６生成矩阵变化图【２５】……………………………………………………………２５图３．７基于Ｃａｕｃｈｙ矩阵的ＫＳ编码…………………………………………………２５ 图４．１系统结构图…………………………………………………………………………………………．．３２ 图４．２插入文件Ｆ示意图（ｍ．２，ｎ．２）…………………………………………．．３４图５．１ ＪＸＴＡ整体结构图…………．图５．２节点加入对等网络后的界面…………………………………………………４５图５．３ＪＮＩ实现流程图………………………………………………………………４６图５．４存储文件…………………。图５．５分发内容分块时的消息传递过程…………………………………………。５１图５．６获取文件……………………． 图５．７获取文件时的消息传递过程…………………………………………………．５２图５．８导入全局存储表……………． 图５．９登录晁面………………………………………………………………………５４ 图５．１０节点配置……………………。 图５．１ １下载时间与节点数的关系…。第ｖ页独创性声明本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：基王坠！！！！！￡！韭盐直互旦ｌ迫直叁壶篮盘缠盟遮盐生塞理学位论文作者签名：：迫暨虚日期：，“年，ｙ月，珀学位论文版权使用授权书本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 （保密学位论文在解密后适用本授权书。）学位论文题目：基土！！！！！！！！！韭的直互周金查盎壶篮丞缠盟遮让皇塞理学位论文作者签名：煎丝缝 作者指导教师签名：塑蛰迅日期：尹６年，ｐ月，归日期：ｊ００６年ｆ’月ｌｊ日国防科学技术大学研究生院工程硕士学位论文第一章绪论１．１课题研究背景及来源自“９?１１”事件之后，数据存储日益受到重视，我国有关部门规定金融、电 信等八个行业必须建立数据灾难恢复机制，因此银行、保险、电信等行业先后建 立起了灾难恢复机制。而我军作为秘密信息的密集载体，目前部队机关各部门的 资料由各部门保管，没有集中的存储、备份（特别是异地备份）机制，一旦出现 突发事件，部队机关被毁，数据无法恢复，人员，物资，装备情况及各种文书， 方案无从掌握，将大大延长部队应急反应时间。面对可能的台海军事斗争，在部 队信息化日益提高的今天，建立我军各级军事机关的灾难恢复机制显得至关重要。 如何确保数据的可用性、可生存性、完整性和安全性已经成为人们关注的焦点，这要求具有安全可靠的分布式数据存储系统的出现，它将信息分散在网络或数个存储节点上，使用户在持续有效且高度可靠的方式下访问信息，即使系统在 节点失效，网络断开，或受到恶意攻击的情况下，仍能有效的提供数据存储服务。 最近几年，对等计算（Ｐｅｅｒ－ｔｏ―Ｐｅｅｒ，简称Ｐ２Ｐ）迅速成为计算机界关注的热门话题之一，《财富》杂志更是将Ｐ２Ｐ列为影响Ｉｎｔｅｒｎｅｔ未来的四项科技之一。Ｐ２Ｐ打破了传统的Ｃｌｉｅｎｔ／Ｓｅｒｖｅｒ（ｃ／ｓ）模式，在网络中的每个结点的地位都是对等的。 每个结点既充当服务器，为其它结点提供服务，同时也享用其它结点提供的服务。 相比传统的分布式系统，它具有一定的优势，体现在以下几个方面： ?非中心化（Ｄｅｃｅｎｔｒａｌｉｚａｔｉｏｎ）：网络中的资源和服务分散在所有结点上，信 息的传输和服务的实现都直接在结点之间进行，可以无需中间环节和服务器的介 入，避免了可能的瓶颈。Ｐ２Ｐ的非中心化基本特点，带来了其在可扩展性、健壮性 等方面的优势。 ?可扩展性：在Ｐ２Ｐ网络中，随着用户的加入，不仅服务的需求增加了，系 统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。整 个体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 ?健壮性：Ｐ２Ｐ架构天生具有耐攻击、高容错的优点。由于服务是分散在各个 结点之间进行的，部分结点或网络遭到破坏对其它部分的影响很小。Ｐ２Ｐ网络一般 在部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。Ｐ２Ｐ网络通常 都是以自组织的方式建立起来的，并允许结点自由地加入和离开。Ｐ２Ｐ网络还能够根据网络带宽、结点数、负载等变化不断地做自适应式的调整。?高性能／价格比：性能优势是Ｐ２Ｐ被广泛关注的一个重要原因。随着硬件技 术的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速第ｌ页国防科学技术大学研究生院工程硕士学位论文增长。采用Ｐ２Ｐ架构可以有效地利用互联网中散布的大量普通结点，将计算任务 或存储资料分布到所有结点上。利用其中闲置的计算能力或存储空问，达到高性 能计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更低的成本提供更高的计算和存储能力。?隐私保护：在Ｐ２Ｐ网络中，由于信息的传输分散在各节点之间进行而无需 经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目 前解决Ｉｎｔｅｍｅｔ隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏 在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖于某 些中继服务器节点。而在Ｐ２Ｐ中，所有参与者都可以提供中继转发的功能，因而 大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。 ?负载均衡：Ｐ２Ｐ网络环境下由于每个节点既是服务器又是客户机，减少了 对传统Ｃ／Ｓ结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点，更好的实现了整个网络的负载均衡。冗余是分布式存储的核心，适当的冗余能提高数据的有效性，保密性和可生 存性，相比以前简单的数据完全复制（镜像）或数据分割（ＲＡＩＤ），ｅｒａｓｕｒｅ 低了对网络带宽和存储容量的占用【１１。 本课题的前期研究是在国家“８６３”项目“协作式应急响应服务与基于漂移的 可生存系统研究”（项目编号：２００３ＡＡｌ４２０８０）的支持下进行的，并且通过几个 月的研究实践，基于ＬＩＮＵＸ系统ＮＦＳ Ｖ２文件系统，已经初步建立了一个系统原 型。该原型系统实现了在局域网内四个节点间的分布存储功能，仍存在以下几方面需要解决的问题：ｃｏｄｅ增强了数据的有效性和保密性，被广泛应用到计算机网络安全存储中，并大大降≯信息分布算法效率不高，无法扩展到节点更多的情况下； ≯系统不易扩展和移植。系统对应特定需求环境设计，由于借助ＮＦＳ（网络 文件系统）实现，每个节点既是服务器（ｓｅｒｖｅｒ），又是客户端（ｃｌｉｅｎｔ）， 当节点较多时，节点负载会很大，无法有效扩展。也因为同一个原因，此系统无法移植到别的操作系统应用；≯未建立有效的节点恢复机制；≯安全方面考虑较少，不能检测分割的数据是否被篡改；由于ＮＦＳ Ｖ２缺乏 必要的用户验证与控制机制，易被冒充访问；本文在此基础上，设计并实现了一个基于Ｐ２Ｐ技术和ｅｒａｓｕｒｅ ｃｏｄｅ技术高可用 的分布式存储系统，解决了存在的问题，实现了数据在广域网上的高可用分布式存储。第２页国防科学技术大学研究生院工程硕士学位论文１．２高可用的分布式存储系统的研究现状高可用的分布式存储系统的研究目前主要集中在广域存储系统方面。广域存 储系统【２１是近年来在存储系统研究方向兴起的一个新兴研究领域。广域存储系统试 图在全球范围内建立超大规模的网络存储系统，实现存储的可靠、可用、高性能、 易访问等特性，向用户提供单一系统映像，成为下一代存储系统框架。 广域存储系统当前还处于研究兴起阶段，没有实际商业化产品，主要的在研项目包括ＯｅｅａｎＳｔｏｒｅ（Ｂｅｒｋｅｌｅｙ）例、ＣＦＳ（ＭＩＴ）１４Ｊ、Ｐａｓｔ（Ｒｉｃｅ＆Ｍｉｃｒｏｓｏｆｔ）ｏ”、Ｇｒａｎａｒｙ（清华大学）【６１等。 ＯｃｅａｎＳｔｏｒｃ是最早提出广域存储系统的，系统功能比较全面，ＯｃｅａｎＳｔｏｒｅ希望 在系统中融入各种规模、能力的结点，构造出超大规模的存储系统，并保证数据 的强一致性，也就是说，在多用户并发访问并且系统中存在恶意结点时仍保证数 据的线性一致性。但是，这种系统过于复杂，在当前的网络能力和结点状况下还 难以实现‘刀，因此后续的Ｐ２Ｐ存储服务系统不再提供强一致性语义，一般只保证 单用户数据读写的正确性，并且暂不讨论如何防止恶意结点对数据一致性带来的破坏。这样的系统主要包括：ＣＦＳ，ＰＡＳＴ，Ｇｒａｎａｒｙ等。ＣＦＳ（Ｃｏｏｐｅｒａｔｉｖｅ ＦｉｌｅＳｙｓｔｅｍ）是一种基于ｐ２ｐ的只读存储系统。它实现了文件存取的安全、高效、健壮及负载平衡。ＣＦＳ系统的核心包括两层：Ｄｈａｓｈ和ｃｈｏｒｄ。 Ｄｈａｓｈ为客户从服务器上获取分块，将分块分散到各个服务器上去，并维护缓存和 副本。它利用ｃｈｏｒｄ的分布式查找来定位分块所在的服务器。和其它类似系统一样， ＣＦＳ通过用公钥或对内容的ｈａｓｈ来命名，并以此对数据进行验证。它采用虚拟服务器（ｖｉｒｔｕａｌ ｓｅｒｖｅｒ）的方法来消除服务器间存储空间的差异，采用限制配额的方法来防止入侵者恶意插入大量无用的数据以耗尽存储空间。用复制及缓存的方法 实现了负载平衡：对大文件实施分块复制，对小文件进行缓存。ＣＦＳ只将数据保 存一段时间，对过期的数据自动删除。如要对永久保存数据，可定期请求ＣＦＳ．延长保存期。ＰＡＳＴ也是基于ｐ２ｐ，它是一种可扩展的安全的持久的完全自组织的广域存储 系统。它的核心包括ｐａｓｔｒｙ和Ｄｈａｓｈ两层。相比ＣＦＳ，它有如下特点：（１）采用ｐａｓｔｒｙ路由策略：（２）使用智能卡，它有三个作用：一是确保对节点配额的安全有效地控制； 二是确保节点ＩＤ和文件ＩＤ分配的完整性；三是实现了匿名的中间媒介； （３）使用匿名来增强安全性，利用假名机制（Ｐｓｅｕｄｏｎｙｍｉｔｙ）实现匿名。Ｇｒａｎａｒｙ是广域对象存储系统。它以对象为存储单位。提供数据高可靠性、高安全性、高访问性能等特性。并提供数据查询和事件驱动。它采用用户加密和系第３页国防科学技术大学研究生院工程硕士学位论文统加密双重安全措施，保证关键数据即使对于系统也不可见，提供了最高的安全性。它以ｏｖｅｒｌａｙ ｎｅｔｗｏｒｋ（Ｐａｓｔｒｙ）和ＤＨＴ（分布式散列表）为底层协议进行数据的存放与定位，保证存在的数据总可以以低于１０９Ｎ步被访问到。它通过数据的 复制提高可靠性和访问效率，并通过概率复制算法保证复本之间的一致性。它提 供数据查询功能，提供较强的查询语义，并通过一系列方法提高查询性能。它提 供事件驱动的数据访问方式，简化了数据主动迁移等应用的开发。 上述广域存储系统，功能全面，实现复杂，在数据复制方式上采取文件复制 或数据分块的方式，而没有采用编码的方式，在存储空间及带宽的利用率上还可 以继续提高。因此，本课题将综合比较、利用目前各系统的优点及研究成果，着 重从编码算法入手，设计并实现尽量简单，高效，实用的分布式存储系统。１．３本文主要的研究内容本文主要的研究内容为：１分析了Ｐ２Ｐ技术在分布式存储系统研究方面的优势，对分布式存储系统的 研究现状做了总结和归纳，并且研究了Ｐ２Ｐ技术的相关理论；２分析、实现了基于Ｖａｎｄｅｒｍｏｎｄｅ矩阵与基于Ｃａｕｃｈｙ矩阵的ｅｒａｓＢｒｅｃｏｄｅ算法，并对两种算法进行了对比测试，结果表明基于Ｃａｕｃｈｙ矩阵的算法 较之基于Ｖａｎｄｅｍｌｏｎｄｅ矩阵的算法编解码效率分别提高了４３％和７６％；３提出了一种基于ｅｒａｓｕｒｅ ｃｏｄｅ技术的高可用的分布式存储系统体系结构， 详细设计了系统的各个关键模块：文件编解码模块、分块分发与获取模块、 动态维护模块、其它功能模块，并对系统进行了性能分析；４实现了基于ｅｒａｓｕｒｅ ｃｏｄｅ技术的高可用分布式存储系统原型ＨＨＳｔｏｒｅ。对系 统的性能测试表明，集中式服务器的下载方式在节点数激增时，节点下载 所用的时间也增加非常迅速，其性能下降也非常快，而ＨＨＳｔｏｍ在网络规 模非常大时，也能保持良好的性能。全文共分六章，各章的组织结构如下： ≯第一章为绪论部分，主要介绍了课题研究的背景、高可用分布式存储系统 的研究现状、本文主要的研究内容和研究成果；＞第二章介绍了Ｐ２Ｐ的相关理论，包括ＤＨＴ算法、ＹＸＴＡ及ＸＭＬ技术；Ｃａｕｃｈｙ矩阵的ｅｒａｓｕｒｅ ｃｏｄｅ算法的基本原理及实现过程，并对两者的性能≯第三章介绍了ｅｒａｓｕｒｅ ｃｏｄｅ算法，包括基于Ｖａｎｄｅｒｍｏｎｄｅ矩阵和基于进行了对比分析；＞第四章提出了一种基于ｅｒａｓｕｒｅ ｃｏｄｅ的高可用分布式存储系统架构，并对 该系统进行了性能分析；第４页国防科学技术大学研究生院工程硕士学位论文 ≯第五章实现了基于ｅｒａｓｕｒｅ ｃｏｄｅ技术的高可用分布式存储原型系统ＨＨＳｔｏｒｅ，包括各个关键模块的实现，这些关键模块有：文件编解码模块、 分块分发与获取模块、动态维护模块、其它功能模块； ＞第六章为结束语，总结了本文的工作并对进一步的研究工作进行了展望。１．４研究成果本文主要的研究成果是：设计并实现了基于ｅｒａｓｕｒｅ ｃｏｄｅ技术的高可用分布式 存储系统ＨＨＳｔｏｒｅ，该系统能安全可靠地实现数据的存储与下载，能满足国防等关 键部门涉密数据的分布存储要求，同时能够适应广域网中海量节点的并发下载请 求，具有较好的可用性、安全性和易管理性。另外，分析、实现了基于Ｖａｎｄｅｒｍｏｎｄｅ矩阵与基于Ｃａｕｃｈｙ矩阵的ｅｒａｓｕｌ－ｅ ｃｏｄｅ算法，其中编解码效率较高的基于Ｃａｕｃｈｙ 矩阵的ｅｌ＇ａｓｕｒｅ ｃｏｄｅ算法在ＨＨＳｔｏｒｅ系统中得到了应用。最后，以第一作者在２００６年网络、通信与信息系统学术会议上发表论文一篇。第５页国防科学技术大学研究生院工程硕士学位论文第二章Ｐ２Ｐ技术相关理论为了介绍Ｐ２Ｐ技术在高可用分布式存储系统中的应用，本章详细介绍了Ｐ２Ｐ 技术的相关理论。因为ＤＨＴ算法为Ｐ２Ｐ系统提供了可扩展的路由模型，提高了 Ｐ２Ｐ系统消息路由的效率，而ＪＸＴＡ为Ｐ２Ｐ系统提供了实现的平台，其平台无关性 提供了构建Ｐ２Ｐ体系结构的基础，其中ＸＭＬ是ＪＸＴＡ的主要消息格式，所以主要 介绍的Ｐ２Ｐ技术相关理论包括ＤＨＴ、ＪＸＴＡ和ＸＭＬ。２．１ＤＩｔＴ算法概述由于Ｐ２Ｐ系统的出现，例如Ｎａｐｓｔｅｒ、Ｇｎｕｔｅｌｌａ和Ｆｒｅｅｎｅｔ，促进了对ＤＨＴ的 研究，其采用分布在Ｉｎｔｅｍｅｔ上的资源来提供应用。特别是，它们利用不断增长的带宽和硬盘容量来提供文件共享服务。这些系统的区别在于如何定位它们的节点所包含的数据。Ｎａｐｓｔｅｒ拥有一个集 中的索引服务器：每个节点在其加入时将把它拥有的文件列表发送给服务器，该 服务器将负责执行搜索并且发送查询请求给拥有所需文件的节点。这种系统的缺 点是服务器容易受到攻击，并且服务器由于被攻击而失效后系统无法继续运行。 Ｇｎｕｔｅｌｌａ和相似的网络使用泛洪查询模型，也就是每个查询将导致消息被广播给所 有在网络中的其它节点。虽然这种系统避免了出现单点失效，但是这种方法在效 率方面比Ｎａｐｓｔｅｒ低得多。Ｆｒｅｅｎｅｔ也是完全分布式的，但是引入了基于ｋｅｙ进行路 由的技术，即每个文件与一个ｋｅｙ相关，并且拥有相似ｋｅｙ的文件簇聚于一系列相 似的节点上。查询可能只需要被路由到这些节点上，而不需要访问许多节点。然 而，Ｆｒｅｅｎｅｔ没有确保可以找到数据。ＤＨＴ使用一个基于更加结构化的ｋｅｙ进行查询的技术，从而既获得Ｇｎｕｔｅｌｌａ和Ｆｒｅｅｎｅｔ的分布性，又可以获得Ｎａｐｓｔｅｒ的效率并且确保能够查找到数据。ＤＨＴ 的缺点是，如同Ｆｒｅｅｎｅｔ一样，只能够直接支持精确匹配的查询，而不支持关键字查询。最初的四种ＤＨＴ算法是ＣＡＮｌ８１、Ｃｈｏｒｄｌ９１、Ｐａｓｔｒｙｔｌｏ】和Ｔａｐｅｓｔｒｙｔｌ”。ＤＨＴ是一种简化大规模分布应用的方法。ＤＨＴ将数据的多个块存储在Ｉｎｔｅｒａｃｔ 上分布的一系列节点上。每一块通过一个唯一的ｋｅｙ来标识。这些ＤＨＴ的目标是 将存储和提供数据的负载均匀地分布到所有节点上，达到负载均衡，并且当节点加入和退出系统时保持数据的可用性。２．１．１ＤＨＴ的基本原理ＤＨＴ的基本原理是：ＤＨＴ为每个节点指定一个标识符（ＩＤ），给数据也指定 一个标识符（ｋｅｙ），将对数据的ｋｅｙ的拥有权进行划分，并且地分布到系统中的国防科学技术大学研究生院工程硕士学位论文各个节点上，各个节点所负责的数据ｋｅｙ与本身的ＩＤ非常接近，每个节点也只需 维护少数几个其它节点的信息，从而根据以上原则，能够有效地将消息路由到任何给定ｋｅｙ的拥有者。ＤＨＴ非常适合于有大量节点加入和退出的情况，并且被广泛地应用于分布式文件系统、Ｐ２Ｐ文件共享系统、协作式ｗｅｂ ｃａｃｈｉｎｇ、多播和域名服务等领域。另外，ＤＨＴ提供了简化的统一应用接口，可以作为许多大规模分布式应用的底层结 构，应用程序可以通过使用ＤＨＴ来获得负载均衡、可扩展性等性能。２．１．２ＤＨＴ的特点１分布化：节点在网络中既充当客户端的角色，也充当服务器的角色，而且 所有节点之间的通信无需经过服务器等中心设备进行。 可扩展性：即使是成千上万的节点，系统也能有效地工作。 容错性：即使节点不断地加入、退出和失效，系统也能够继续正常工作。２ ３达到这些目标的关键技术是每个节点只需要在网络中维护一部分其它节点的 信息，通常是Ｏ（１０９Ⅳ）个节点的信息，从而当网络发生变化时，每个节点不需要执行很多的工作。 ＤＨＴ可以处理传统的分布式系统存在的问题，例如负载均衡、数据的完整性以及性能，特别是，确保路由、存储数据或者获取数据等操作能够快速地完成。２．１．３ＤＨＴ的结构理解ＤＨＴ的结构需要知道它的两个重要部分：ｋｅｙ空间划分机制和覆盖式网 络。ｋｅｙ空间划分机制将对ｋｅｙ的所有权进行划分并且分布到所有节点上；覆盖式 网络连接所有的节点并且允许节点查询给定ｋｅｙ的拥有者。２．１．３．１ｋｅｙ空间划分机制大多数ＤＨＴ算法使用一些不同的一致性散列法（ｃｏｎｓｉｓｔｅｎｔ ｈａｓｈｉｎｇ）来将ｋｅｙ 与节点进行匹配。该技术引入一个函数，该函数定义了两个ｋｅｙ（ｋｌ和ｋ２）之间 距离的抽象概念。每个节点被指派一个唯一的ｋｅｙ，并且称该ｋｅｙ为节点的标识。通过函数计算，ＩＤ为ｉ的节点拥有与ｉ最接近的所有的ｋｅｙ。例如，Ｃｈｏｒｄ算法将ｋｅｙ分配给环上的一个节点，而函数的值表示在环上从ｋ１到ｌ（２按顺时针方向传输的距离。所以，圆形的ｋｅｙ空间被分成邻近的几段，每段都以节点的ｉｄ为端点。如果订和ｉ２是两个邻接的ＩＤ，则ＩＤ为ｉ２的节点拥有所有在ｉ１和ｉ２之间的ｋｅｙ。一致性散列法的本质属性是当一个节点加入或者退出时，只需要改变邻近节点所拥有的ｋｅｙ的集合，而不需要改变所有其它的节点。第７页国防科学技术大学研究生院工程硕士学位论文２．１３．２覆盖式网络 每个节点维护一组到其它节点的连接，包括它的邻居或者路由表等，从而， 对于任何ｋｅｙ，节点或者拥有该ｋｅｙ，或者拥有一个连接，该连接指向根据在前面 定义的ｋｅｙ空间距离来计算的离该ｋｅｙ最近的节点。根据以下的贪婪算法，可以很 容易地将消息路由到任何ｋｅｙ的拥有节点：在每一步，将消息转发给ＩＤ离ｋｅｙ最 近的邻居。这种形式的路由有时被称为基于ｋｅｙ的路由。邻居是通过结构化的方 式选择的，称为网络的拓扑，从而在任何路由线路中的跳数（网络的维数）和每 个节点的邻居数（度数）都会比较少。常见的度数和网络维数如表２．１所示。表２．１常见的度数和网络的维数度数 ００）ＤｆｌｏｇＮ） ０ｆｌｏｇＮ）网络的维数 ０（ＩｏｇＮ） Ｏ（１０９Ｎ／ｌｏｇｌｏｇＮ）ＤｆｌｏｇＮ）ｏ（４ｆｆ）００）最常见的是第三种选择，虽然它不是最优的，但是这种拓扑结构在邻居的选 择上有更大的灵活性，而且在物理底层网络中产生的延迟也非常低。２．１．４ Ｃｈｏｒｄ算法概述２…１ ４１Ｃｈｏｒｄ的主要思想Ｃｈｏｒｄ算法为每个节点指定一个ｉｄ。其ｉｄ空问可以认为是一个环，在这个环 中最大的ｉｄ为０。Ｃｈｏｒｄ将每个ｋｅｙ与一个节点匹配，该节点的ｉｄ与该ｋｅｙ最接 近。每个Ｃｈｏｒｄ节点保存一部分其它节点的信息，从而可以有效地将ｋｅｙ与节点 匹配并且具有一定的容错性。Ｃｈｏｒｄ确保每个节点知道其后继节点的标识信息，包括球地址、Ｃｈｏｒｄ ｉｄ等，并且可以根据ｉｄ将节点连接成环状的列表。Ｃｈｏｒｄ查询协议的标识拓扑结构是如图２．１所示的环。该环所拥有的节点数不 会超过２”，范围从０到２”．１。在该图中，ｍ－－－－３。大的圆点表示节点，小的圆点表 示ｋｅｙ。ＩＤ和ｋｅｙ是通过使用一致性散列法指定的，ｓＨＡ一１算法是一致性散列法的基本散列函数。其中每个节点有一个后继节点和前置节点。后继节点是指在环 上按顺时针方向的下一个节点。前置节点是指在环上按逆时针方向的下一个节点。 例如，节点ｌ的后继节点是节点３，节点ｌ的前置节点是节点０。第８页国防科学技术大学研究生院工程硕士学位论文１３图２．１ Ｃｈｏｒｄ标识环ｆ９】当节点失效时，为了维护系统的完整性，每个节点保持一个后继表。如果节 点的后继节点失效了，该节点将使用后继表中下一个有效的节点来替换失效的节 点。由于使用了ｆｉｎｇｅｒ表，查询所耗费的时间在Ｏ（１０９Ｎ）级别，一个节点的ｆｉｎｇｅｒ 表保存了ｌｏｇＮ个实体。ｆｉｎｇｅｒ表、后继节点和前置节点的定义如表２．２所示。表２．２ ｆｉｎｇｅｒ表的符号与定义【９】符号 ｆｉｎｇｅｒ［ｋ］ 后继节点 前置节点定义在标识环上按顺时针方向满足ｉｄ继（ｎ＋２“１）ｍｏｄ ２ｍ之后的第一个节点。在标识环上的下一个节点 在标识环上的前一个节点一个Ｃｈｏｒｄ节点周期性地检查它的ｆｍｇｅｒ表和后继表中各项的有效性，该 过程称为ｓｔａｂｉｌｉｚａｔｉｏｎ。Ｃｈｏｒｄ通过该过程可以适应节点失效和节点加入等动态情 况。Ｃｈｏｒｄ也周期性地试图联系过去存活但现在无法联系上的节点；Ｃｈｏｒｄ通过这 个过程来知道网络被分割时的时间。２．Ｉ．４．２Ｃｈｏｒｄ的性能分析Ｃｈｏｒｄ简化了Ｐ２Ｐ系统的设计，其主要性能包括以下几个方面：≯负载均衡：Ｃｈｏｒｄ充当了分布式哈希函数，将ｋｅｙ均匀地分布在节点上，从而满足一定程度的负载均衡。 》非集中化：Ｃｈｏｒｄ是完全分布化的，即所有节点的地位相当。这一点增加了系统的鲁棒性，并且使得Ｃｈｏｒｄ适合于组织松散的Ｐ２Ｐ应用。≯可扩展性：Ｃｈｏｒｄ查询的开销为０（１０９Ｎ），其中Ｎ为节点的数量，而且不 需要额外的参数，所以甚至是大型的系统也能够正常提供服务，即Ｃｈｏｒｄ第９页国防科学技术大学研究生院工程硕士学位论文的可扩展性很好。 ＞可用性：Ｃｈｏｒｄ自动调整节点内部的表项来反映最新加入的节点以及失效 的节点，并且在底层网络没有发生主要的失效情况下确保可以查找到负责 某个ｋｅｙ的节点。即使系统处于连续的变化当中，其可用性也是可以满足的。≯命名的灵活性：Ｃｈｏｒｄ对于要查询的ｋｅｙ的结构没有任何限制，因为Ｃｈｏｒｄ 的ｋｅｙ空间是平面的。这一点使得应用对于如何将它们本身的名字映射到 Ｃｈｏｒｄ的ｋｅｙ具有很大的灵活性。２．１．４．３Ｃｈｏｒｄ的主要应用Ｃｈｏｒｄ的应用范围比较广泛，主要包括以下几个方面： 协作式镜像：内容的多个提供者通过互相合作来存储和提供各自的数据。例 如，共享的内容可能是一组软件开发项目，并且每个项目都要定期进行升级。将 整个负载均匀地分布在所有共享内容的节点上将降低系统全部的开销，因为每个节点只需要提供达到平均负载的容量，而不需要达到最大负载。分时共享存储：这种应用主要针对节点之间的连接不连续的情况。如果希望 数据一直是可用的，但是服务器只是偶尔可用，它们可以在互相连接时存储其它 服务器的数据，从而其它服务器在它们没有互相连接时会拥有这些服务器的数据。 在任何时间，数据的名字都可以作为ｋｅｙ来标识负责存储数据项的Ｃｈｏｒｄ节点。 分布式索引：用以支持类似Ｇｎｕｔｅｌｌａ或者Ｎａｐｓｔｅｒ的关键字搜索。在这种应用 中，可以从需要的关键字中产生ｋｅｙ，其值可以是提供包括那些关键字的文档的机器列表。大规模的组合搜索：例如代码破坏（ｃｏｄｅ ｂｒｅａｋｉｎｇ）。在这种情况下，ｋｅｙ是 问题的候选解决方案，例如密钥；Ｃｈｏｒｄ将这些ｋｅｙ映射到负责将这些ｋｅｙ作为解决方案进行测试的机器上。２．２ＪＸＴＡ综述ＪＸＴＡｔｌ２１【１３】是Ｓｕｎ在Ｐ２Ｐ计算领域的重要项目，同时ＪＸＴＡ也是Ｓｕｎ的ＯＮＥ 互联网战略的延续。ＪＸＴＡ的创始人是Ｓｕｎ首席科学家Ｂｉｌｌ Ｊｏｙ，ＪＸＴＡ是开放源码 项目，目前最新版本是Ｖ２．４，现在已有不少其它研究机构和工业界伙伴参与其中。 ＪＸＴＡ技术是一种网络编程和计算的平台，用以解决现代分布计算尤其是Ｐ２Ｐ计算中出现的问题，解决目前的Ｐ２Ｐ计算的局限性。ＪＸＴＡ将建立核心的网络计算技术，提供支持在任何平台、任何地方以及任何时间实现Ｐ２Ｐ计算的一整套简单、灵活 和有效的机制。ＪＸＴＡ仅提供几乎所有的应用程序都能使用的构件要素，创建基本第ｌＯ页国防科学技术大学研究生院工程硕士学位论文的机制，而不考虑目标用户的策略和特定实现，具体的策略选择等都交给应用的 开发者。ＪＸＴＡ技术可使各软件开发商能够根据统一的要求和统一的标准，在同一 平台开发它们的应用产品。ＪＸＴＡ必将扩展Ｐ２Ｐ计算，实现分布计算的大量新应用， 克服目前存在于许多Ｐ２Ｐ应用中的众多限制。２．２．１ ＪＸＴＡ的技术特点１）互操作性：现在的大多数Ｐ２Ｐ系统用来实现一个单一类型的网络服务，例 如Ｎａｐｓｔｅｒ只提供音乐文件交换服务，Ｇｎｕｔｅｌｌａ只提供一般的文件交换服务， 由于缺乏一个通用的Ｐ２Ｐ基础平台，这些Ｐ２Ｐ系统难以互相交互，从而局 限了Ｐ２Ｐ系统的潜力的发挥。如果一个对等体参与了多个Ｐ２Ｐ系统，该对 等体必须支持多种Ｐ２Ｐ系统的实现。ＪＸＴＡ技术目的是改变这种困境，使 得物理上互连的但属于不同Ｐ２Ｐ系统或团体的对等体能够互相定位、通信、 协同以及为对方提供服务，使得不同的Ｐ２Ｐ系统之间能够无缝地进行互操作。２）平台独立：ＪＸＴＡ技术是平台独立的。ＪＸＴＡ独立于编程语言（如Ｃ，Ｊａｖａ 等），独立于操作系统平台（如Ｗｉｎｄｏｗｓ或ＵＮＩＸ等），独立于网络平台 （如ＴＣＰ／ＩＰ，蓝牙技术等）。任何人都可以在任何硬件平台上，用任何操 作系统、任何编程语言实现基于ＪＸＴＡ的网络。３）无处不在：．ＩＸＴＡ能运行在任何拥有数字心脏的设备上，包括传感器、消费电子产品、ＰＤＡ设备、网络路由器、桌面电脑、服务器和存储设备。 ４）核心处使用ＸＭＬ：ＪＸＴＡ目前使用ＸＭＬ作为消息和广告的格式，这对于 使ＪＸＴＡ具有互操作性很有帮助。因为ＸＭＬ技术的简单性和普遍可访问性，软件几乎可以创建在任何平台上以生成并解析ＪＸＴＡ消息。２．２．２ＪＸＴＡ构架ＪＸＴＡ的架构如图２．２所示。ＴＸＴＡ构架分为三层：．ＰｘＴＡ核心层（ＪＸＴＡＣｏｒｅ）、ＪＸＴＡ服务层（ＴＸＴＡ Ｓｅｒｖｉｃｅｓ）和ＪＸＴＡ应用层（ＪＸＴＡ Ａｐｐｌｉｃａｔｉｏｎｓ）。第１１页国防科学技术大学研究生院工程硕士学位论文蛔呻 稿墓｛｜ 艘激ｓｅ图２．２ ＪＸＴＡ构架…ＪＸＴＡ核心层处理对等体的建立、通信管理（如路由等）以及对等体的监测等。 ＪＸＴＡ服务层提供更高层的一些基本服务，如索引、搜索、文件共享等。ＪＸＴＡ服 务层的这些服务使用ＪＸＴＡ核心层提供的各种功能，可以被本层的服务所使用， 也可以作为整个Ｐ２Ｐ系统中的一个通用组件。ＪＸＴＡ应用层是一些Ｐ２Ｐ应用，如 Ｅｍａｉｌ、Ｐ２Ｐ存储系统等，ＪＸＴＡ ｓｈｅｌｌ是ＪＸＴＡ开发包的一个缺省应用。ＪＸＴＡ的每 一层都是简单而有效的，能够为应用的开发提供基本的支持。２．２．３ＪＸｌＡ核心概念在ＪＸＴＡ中，有一些基本的概念：对等体、对等组、标识、通告、消息、管 道。下面将首先对这些概念进行解释。 夺对等体：对等体是可以理解实施协议的实体。对等体是组成Ｐ２Ｐ网络的基本元素。夺对等组：对等组是指协作提供某一种服务的对等体的集合。对等组成员资 格没有任何限制，任何对等体有必要属于几个对等组，就可以属于几个对 等组。ＪＸＴＡ规范并没有规定或推荐对等组创建、组织的时机和方式， ＪＸＴＡ只是定义了对等体发现协议。在ＪＸＴＡ网络中，对等组就是共享资 源和服务的对等体的集合。有一个缺省的特殊对等组，称为全体对等组，它包含了所有的ＪＸＴＡ对等体。夺标识：ＪＸＴＡ使用１２８位的ＵＵＩＤ来指向任一个实体（对等体、通告或服务等）。 夺管道：管道是发送和接收消息的通道。管道是异步的、单向的。要双向通信的两个对等体需要创建两个独立的管道。管道也是虚拟的，管道的一端 可以连接到多个对等体上。管道通常是通过管道绑定协议（Ｐｉｒｅ第１２页Ｂｉｎｄｉｎｇ国防科学技术大学研究生院工程硕士学位论文Ｐｒｏｔｏｃ０１）在运行时连接到一个对等体上。目前ＪＸＴＡ规范提供了两种类 型的管道：点对点管道和多播管道。对等体可以使用点对点管道连接到另 一个对等体并单向传输消息。对等体可以使用多播管道连接到一个或多个 其它对等体并向它们全体传输消息。点对点管道是一对～的消息传输机 制，多播管道则是一对多的消息传输机制。ＪＸＴＡ项目组目前正在在多对 多消息传输机制（即ＪＸＴＡ Ｗｉｒｅ）方面努力。 夺消息：ＪＸＴＡ消息是指通过管道从一个对等体传送到另一个对等体的信息 块。消息是在异步、不可靠、单向的信道上传输。消息包含了一个信封和 消息体。信封是标准格式，它包括报头、源端点信息（ＵＲＩ格式）、目 的地端点信息（ｕＩｕ格式）以及可选的消息摘要（为了安全性目的）。 消息正文包含了可选的身份验证信息（以增加安全性）和内容，消息正文 的长度是任意的。ＹＸＴＡ这种消息格式的目的是为了适应各种不同的网络 （从ＴＣＰ／ＩＰ网络到蓝牙网络等），支持多种传输标准。ＪＸＴＡ消息编码 目前采用ＸＭＬ文档格式，利用了ＸＭＬ的普适访问性和易使用、易编 程的特点，使得ＪＸＴＡ可以用大多数编程语言在大多数平台上很容易地 实现。但ＪＸＴＡ规范本身并不要求ＪＸＴＡ消息编码一定要使用ＸＭＬ。 夺通告：通告的内容用来命名、描述和发布现有的资源，如对等体、对等组、 管道或服务等。ＪＸＴＡ通告也采用ＸＭＬ文档格式。ＪＸＴＡ定义通告的基 本集合。例如可以访问一个对等组的通告的对等体可以通过通告加入对等 组。ＹＸＴＡ规范没有规定如何创建、传播或删除通告。２．２．４ＪＸＴＡ协议抽象的看，ＪＸＴＡ技术实际上就是一些协议。ＪＸＴＡ技术中目前定义了六大协 议，所有这些协议都是建立在ＸＭＬ消息交换的基础上的，它们可以用几乎所有 的编程语言在几乎所有平台上实现。这些协议都可以很容易的实现并集成到Ｐ２Ｐ服务和应用中，这样不同的Ｐ２Ｐ系统之间可以方便的实现互通、互操作。ＪＸＴＡ主 要包括以下协议【１４１： ＞对等节点发现协议（ＰｅｅｒＤｉｓｃｏｖｅｒｙ Ｐｒｏｔｏｃ０１）≯对等节点解析协议（Ｐｅｅｒ Ｒｅｓｏｌｖｅｒ Ｐｒｏｔｏｃ０１）》对等节点信息协议（ＰｅｅｒＩｎｆｏｎｎａｔｉｏｎ Ｐｒｏｔｏｃ０１）≯对等节点成员关系协议（Ｐｅｅｒ Ｍｅｍｂｅｒｓｈｉｐ Ｐｒｏｔｏｃ０１） ＞管道绑定协议（ＰｉｐｅＢｉｎｄｉｎｇ Ｐｒｏｔｏｃ０１）≯端点路由协议（Ｅｎｄｐｏｉｎｔ Ｒｏｕｔｉｎｇ Ｐｒｏｔｏｃ０１）第１３页国防科学技术大学研究生院工程硕士学位论文２．３ＸＭＬ简介２．３．１ ＸＭＬ的定义ＸＭＬｌｌ ５Ｊ是可扩展标志语言（ｅＸｔｅｍｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）的简称。象ＨＴＭＬ一样，ＸＭＬ是从所有标志语言的元语一一标准通用标志语言ＳＧＭＬ（ＳｔａｎｄａｒｄＧｅｎｅｒａｌｉｚｅｄＭａｒｋｕｐ Ｌａｎｇｕａｇｅ）］］ｌｊ里派生出来的，是一套定义语义标记的规则，这些标记将文档分成许多部件并对其加以标识。ＸＭＬ是与特定领域有关的、具有语义 和结构化等特点的元标记语言。我们可以用ＸＭＬ来定义种种不同的标志语言满足 不同的需要，特别在数据表现方面。 简而言之，可以称ＸＭＬ为“表达数据中结构的共同语法”，而所谓的结构化 的数据指的是其内容、意义或应用被标记的数据。进一步讲，ＸＭＬ是在互联网时 代与Ｊａｖａ、ＣＯＲＢＡ类似的一个概念。Ｊａｖａ解决了语言实施的同一，ＣＯＲＢＡ解决 了通讯协议的同一，ＸＭＬ则解决了信息表示、关联的同一。２．３．２ＸＭＬ的特点及其应用数据与其表现的分离是ＸＭＬ最重要的特点，ＸＭＬ以其良好的数据存储格式、 可扩展性、高度结构化、便于网络传输等优势将在许多领域一展身手，这些优势 不仅能满足不断增长的网络应用需求，而且还能够确保在通过网络进行交互合作时，具有良好的可靠性与互操作性。基于上面论述的，可以看出ＸＭＬ具备的特点包括以下几个方面： 》易于扩展：ＸＭＬ是摒弃了ＳＧＭＬ中一些复杂性并考虑到适合ｗｅｂ特性的 一个子集。可以定义其它语言，同时ＸＭＬ的标记是用户定义的，所以从 理论上讲，其类型的数量可以是无限的； ≯结构性强：ＸＭＬ的文件结构嵌套可以复杂到任意程度，能表示面向对象的等级层次；≯交互性好：用户与应用进行交互时，使用ＸＭＬ可以非常方便地进行数据 操作，不需要与服务器进行交互，减轻了服务器的负担； ≯语义性强：ＸＭＬ能够表达丰富的语义，并且以直观的方式显示出来。 ＸＭＬ的实际应用非常广泛，主要包括以下几个方面【１６１：存储数据库，结构化 文档，存储矢量图形，描述软件包及其依赖的软件，Ｗｅ ｂ应用程序之间的通信， 交换金融信息等。２．３．３ＸＭＬ与ＪＸＴＡ的关系第１４页国防科学技术大学研究生院工程硕士学位论文因为ＸＭＬ是结构化数据跨平台表示的一种事实上的标准，所以ＪＸＴＡ的协议 技术规范是根据ＸＭＬ数据结构来定义ＪＸＴＡ消息的。但是，ＪＸＴＡ并不要求一个 对等节点具有处理ＸＭＬ结构数据的所有功能。例如，包含有限资源的对等节点可 能会选择将ＪＸＴＡ的消息交换协议预编译为一种二进制的表示形式。只要该对等 节点处理的消息遵循这个协议规范，那么该对等节点就能在不需处理ＸＭＬ结构数据的情况下加入到Ｊｘ，ｒＡ网络中。尽管ＪＸＴＡ技术规范目前定义了７种协议，但是，为了成为ＪＸＴＡ虚拟网络的 一部分，一个对等节点并不需要理解所有这７种协议。实际上，虽然这些协议定 义了一个对等节点的行为方式，但只有当该对等节点确定要实现该协议定义的行 为时，这些协议才能产生对该对等节点的影响。当然，一个对等节点支持的协议 越多，那么该对等节点参与ＪＸＴＡ网络的行为就越充分。此外，一个对等节点也 可以通过耨的行为来扩展任何现有的协议。 在ＪＸＴＡ技术的７种协议中，对等节点解析协议的ＸＭＬ模式如下所示：＜ｘｓ：ｅｌｅｍｅｎｔｎａｍｅ＝”ＲｅｓｏｌｖｅｒＱｕｃｒｙ”ｔｙｐｅ＝’＇ｊｘｔａ：ＲｅｓｏｌｖｅｒＱｕｅｒｙ”，＞ ｎａｍｅ＝’’ＲｅｓｏｌｖｅｒＱｕｅｒｙ”＞＜ｘｓ：ｅｏｍｐｌｅｘＴｙｐｅ ＜ｘｓ：ｓｅｑｕｅｎｃｅ＞ ＜ｘｓ：ｅｌｅｍｅｎｔｒｅｆ－－－－‘＇ｊｘｔａ：Ｃｒｅｄ”ｎｌｉｎＯｃｅｕｒｓ＝”０”６， ＜ｘｓ：ｅｌｅｍｅｎｔ ｎａｍｅ＝”ＳｒｅＰｅｅｒｌＤ”ｔｙｐｅ２。＇ｊｘｔａ：ＪＸＴＡＩＤ”胁＜！一Ｔｈｉｓ ｃｏｕｌｄ ｂｅ ｅｘｔｅｎｄｅｄ ｗｉｍａｐａ：ｔｃｅｍｒｅｓｔｒｉｃｔｉｏｎ??＞＜ｘｓ：ｅｌｅｍｅｎｔ ｌ－ｌａｍｅ＝’’ＨａｎｄｌｅｒＮａｍｅ”ｔｙｐｅ＝”ｘｓ：ｓｔｒｉｎｇ”／＞ ＜ｘｓ：ｅｌｅｍｅｎｔｌｌａｍｅ＝”ＱｕｅｒｙｌＤ”ｔｙｐｅ＝”ｘｓ：ｓｔｒｉｎｇ”／），ｒｅａｓｏｎｓ＜ｘｓ：ｅｌｅｍｅｎｔ ｎａｍｅ＝”ＨＣ’’ｔｙｐｅ＝”ｘｓ：ｕｎｓｉｇｎｅｄＩｎｔ。’胁 ＜！一Ｆｏｒ ｈｉｓｔｏｒｉｃａｌ ＜ｘｓ：ｅｌｅｍｅｎｔ ＜／ｘｓ：ｓｅｑｕｅｎｃｅ＞ ＜／ｘｓ：ｅｏｍｐｌｅｘＴｙｐｅ＞ ｔｈｅ ｑｕｅｒｙ ｉｓａｗｈｏｌｅ ｆｌａｔｔｅｎｅｄ ｄｏｃｕｍｅｎｔ一―＞ｎａｍｅ＝”Ｑｕｅｒｙ”ｔｙｐｅ＝”ｘｓ：ａｎｙＴｙｐｅ”胁２．４本章小结本章详细介绍了Ｐ２Ｐ技术的相关理论，其中分析了ＤＨＴ算法的基本原理、特 点和结构，以及Ｃｈｏｒｄ的主要思想、性能分析和主要应用，给出了ＪＸＴＡ技术的 相关概念，最后介绍了ＸＭＬ协议的相关知识。第１５页国防科学技术大学研究生院工程硕士学位论文第三章ｅｒａｓｕｒｅ ｃｏｄｅ算法分析与实现由于ｇｌ＇ａＳＬＥｅ ｃｏｄｅ算法是我们设计和实现高可用分布式存储系统的基础，因此，本章我们详细介绍了基于Ｖａｎｄｅｒｍｏｎｄｅ矩阵和基于Ｃａｕｃｈｙ矩阵的两种ｅｒａｓｕｒｅ ｃｏｄｅ算法的基本原理及代码实现，并进行了对比性能测试。由于基于Ｃａｕｃｈｙ矩阵的ｅｒａｓｕｒｅ ｃｏｄｅ算法较好的编解码效率，该算法在后述的高可用分布式存储系统中 得到了应用。３．１ｅｒａｓｕｒｅｃｏｄｅ概述编码理论与技术研究至今已有４０多年的历史了，在香农编码定理的指导下， 信道编码（亦称纠错码）理论和技术逐步发展成熟。早在２０世纪５０年代初，汉明（Ｒ．Ｗ．Ｈａｍｍｉｎｇ）提出了重要的线性分组码一汉明码后，人们把代数方法引入到纠错码的研究，形成了代数编码理论。１９５７年普兰奇（Ｐｒａｎｇｅ）提出了循环码， 在随后的十多年里，纠错码理论研究主要是围绕着循环码进行的，取得了许多重要结果。由于循环码具有性能优良、编译码简单、易于实现等特点，因此，目前在实际差错控制系统中所使用的线性分组码几乎都是循环码。１９５９年由霍昆格姆 （Ｈｏｃｑｕｅｎｇｈｅｍ）、１９６０年由博斯（Ｂｏｓｅ）和查德胡里（Ｃｈａｕｄｈａｒｉ）各自分别提 出了ＢＣＨ码，这是一种可纠正多个随机错误的码，使迄今为止所发现的最好的线 性分组码之一。１９６０年Ｉ．Ｓ．Ｒｅｃｄ和Ｇ．．Ｓｏｌｏｍｏｎｄ提出Ｒｓ“”码，ＲＳ码是一类纠错能 力很强的多进制ＢＣＨ码。它不但可以纠正随机错误、突发错误以及二者的组合，而 且可以用来构造其它码类。因此，ＲＳ码在卫星通信，数字电视传输以及磁记录系统 等许多领域得到广泛应用。１９５５年埃莱亚斯（Ｅｌｉａｓ）提出了不同于分组码的卷积 码，接着沃曾克拉夫特（Ｗｏｚｅｎｃｒａｆｔ）提出了卷积码的序列编码。１９６７年维特比 （Ｖｉｔｅｒｂｉ）提出了卷积码的最大似然译码法―Ｖｉｔｅｒｂｉ译码法，这种译码方法效 率高、速度快、译码较简单，目前得到了极为广泛的应用。１９６６年福尼（Ｆｏｒｎｅｙ） 提出级联码概念，用两次或更多次编码的方法组合成很长的分组码，以期获得性 能优良的码，尽可能接近香农限。如２０世纪８０年代采用的一种以码长ｎ＝２５５的ＲＳ码为外码、约束长度为７、码率为１／２的卷积码为内码进行级联，且内码采用Ｖｉｔｅｒｂｉ译码，即具有非常好的性能，在ｌＯ。误码率条件下，所需信噪比仅为０．２ｄＢ．ｅｒａｓｕｒｅｃｏｄｅ原来是无线通信中有噪信道编码的一种，也叫纠删码，后来由Ｋａｍｉｎ提出的密钥共享【ｌＳ］（ｓｅｃｒｅｔ ｓｈａｒｉｎｇ）以及Ｍ．０．Ｒａｂｉｎ提出ＩＤＡ［１９］（ＩｎｆｏｒｍａｔｉｏｎＤｉｓｐｅｒｓａｌＡｌｇｏｒｉｔｈｍ）算法，将其引入到计算机应用中，发展到现在，已有数十种编码，主要包括Ｒｓ ｃｏｄｅ和ｔｏｒｎａｄｏ ｃｏｄｅ【２０１【２１１１２２１等，最常用的是Ｒｓ编码（后来分第１６页国防科学技术大学研究生院工程硕士学位论文析发现，ＩＤＡ的实质也是Ｒｓ编码［２３１），它适合于ｍ，ｒｌ较小的情况下（如ｒｅ＋ｎ＜２５６），ｔｏｒｎａｄｏ ｃｏｄｅ能实现很高的编解码效率，但它是在ｍ，ｎ较大（如ｍ＝２００，ｎ－－－２００）的前提下才能体现出优势。本文主要考虑ｍｊｌ较小的情况，故主要研究ＲＳｅＩ＇ａＳｌｌｌ＇ｅｃｏｄｅ。ｃｏｄｅ的基本思想是：将一个数据文件划分为ｉｎ个等长的数据块（不足的以０补充），通过编码生成ｎ个检验块，根据其中任意ｍ个分块就可恢复出原 文件，而少于ｍ个分块无法获取原文件，这样能容忍多达ｎ个节点的失效。这里 ｍ／（ｍ＋ｎ）称为编码率。ｅｆａ￥１１ｆｅｃｏｄｅ具有良好的容错性和安全性，在计算机存储及安全领域应用很广。在２１世纪的今天，信息的安全性和可用性受到了极大的挑战，尤其是在分布 式存储系统中，通过采用纠错编码技术在相当大的程度上提高了信息的安全性和 可用性，纠错编码技术显示了巨大的魔力。３．２基于Ｖａｎｄｅｒｍｏｎｄｅ矩阵的ＲＳ算法‘２４１分析与实现３．２１基本思想１ ｑ０２０吃 口２２定义ｌ：形如玩２ｑ２的矩阵，称为Ｖａｎｄｅｒｍｏｎｄｅ矩ｑ”一１吃”１…％”１阵。我们首先举个例子，来说明校验块的生成过程。如图３．１所示，当ｎ＝８，ｍ＝２ （ｎ为信息块数目，ｍ为校验块数目）时，将数据Ｍ分为Ｄ．，Ｄ２，．．．，Ｄ．／ｋ个数据块， ｃ。、Ｃ：两个校验块由Ｆｌ，Ｆ２两个算子分别运算得到。第１７页国防科学技术大学研究生院工程硕士学位论文④⑤ ⑤⑨ ④⑤＝乃（玖，Ｄ２：现：现：晚：协：Ｄ易侥）④④＠④ ＝为（ＤＩ：Ｄ２：Ｄ３：玩撬：撬：历：乃８）图３，１用两个校验块提供两次容错【２４Ｊ我们把每个数据块分成字处理，字的长度为Ｗｂｉｔｓ，Ｗ可由程序设计者自行选 择，每个数据块包含ｋ个字。为简化描述，假设每个块只包含一个字，我们把数据分为ｄｌ，ｄ２…．ｄｎ共ｎ个字的数据块，经运算后产生１１１个字（ｃｌ～．，Ｃ。）的校验块。为了计算校验块ｃｉ的校验字，我们定义Ｆｉ为数据字的线性组合，对数据字作如下处理：ｃｊ＝只（碣，易…，ｄ．）－－Ｅ嘭毛。如果我们把数据字和校验字分别表Ｊ１１示为向量Ｄ和ｃ，函数Ｆｉ是矩阵Ｆ的行向量，则有等式ＦＤ＝Ｃ成立。 我们把Ｆ定义为ｍ×ｎ的Ｖａｎｄｅｒｍｏｎｄｅ矩阵，其中＾Ｊ―Ｊ 变成如图３，２所示：ｌ ２ ２，一Ｊ，－ｌ，故上述等式即可＾．。 厂２．。 六．。ｄｌ ｄ２ ｄ３：●ｌ工厶六厶１１ １ｌ‘厶六２Ｊ厶０１ ２ｄ。１” 刀２●ｄ１ ｄ２ ｄ３：●Ｃｌ Ｃ２４：Ｃ３●：１２ｍ－Ｉ甩肌一１ｄ。Ｃｍ图３．２编码矩阵等式１ 第１８页国防科学技术大学研究生院工程硕士学位论文下面我们再说明如何进行数据恢复。为了说明数据恢复的过程，我们定义矩阵Ａ和懈…一阱料瓢糊将有等式∞锄立，矩阵Ａ称为生成矩阵。如图３．３所示：１ ０ ０ ｌ Ｏ一一●０ ０●匾 吃：●：Ｏ ｌ １０ ｌ ２０；Ｏ 一１ ３～●●１ １一●刀：｜１ ＝●以ｑ Ｑ；１２ｍ一１．－．３十０●疗ｍ―Ｉ％图３．３编码矩阵等式２１２４１若ｍ个数据块丢失，则将ｍ个数据块对应的矩阵Ａ，Ｅ中的行删掉，得到新的 疗×ｎ阶矩阵Ａ’和ｌｘⅣ阶矩阵Ｅ’，由于Ｆ是Ｖｍｄｅｒｒａｏｎｄｅ矩阵，所以Ａ的任意ｎ 行子集都能保证是线性独立的，因此矩阵Ａ’必是非奇异的，即可以对４’求逆得到 ４”，恢复数据则只需通过Ｄ＝Ａｔ－Ｉ Ｅ‘完成。如果少于ｍ个数据块丢失，刚任选其 中ｎ个数据块对应的ｎ行，同样能得到ｎＸ”阶矩阵Ａ’，进行恢复。这样此算法能容忍不多于ｍ个数据块丢失时的数据恢复。３．２２ ＧａｉＮｓ域上的运算ＧＦ（２”）上的元素为０―２…．１的整数，加法和减法很简单，他们都是ＸＯＲ运算，例如：在ＧＦ（２４）中：１１＋７＝１０１１ ００１１１＝１１００＝１２ １１―７＝１０１ｌ００１１１＝１１００＝１２乘法和除法要复杂的多，以乘法为例，其运算过程是伫町：先要将元素的二进 制形式转化为多项式的形式，然后作多项式的乘法，再将结果对本原多项式（砸ｍｉｔｉｖｅ ｐｏｌｙＩｌｏｍｉａｌ，ＧＦ（２４）中本原多项式为工４＋ｚ＋１）求余，最后再把结果转化为二进制的形式。以１１×７为例进行说明：１１的二进制形式（１０１１）对应的多项式为，＋ｘ＋１，７ 的二进制形式（０１１１）对应的多项式为Ｘ２＋ｘ＋１，两个多项式作多项式乘法后的结果再对本原多项式Ｘ４＋工＋１求余，结果是Ｘ２，转化为二进制形式为１００，即为４。当ｗ比较小（１６或者更小），我们用两个对数表来加快运算速度，每个长２…．１，第１９页国防科学技术大学研究生院工程硕士学位论文两个表分别为ｇｎｏｇ和ｇｆｉｌｏｇ：≯ｉｎｔｇｎ０９１］：这个表是定义了ｌ一２＂－１，并给出他们在Ｇａｌｏｉｓ域上的对数。》ｉｎｔ西ｌｏｇＨ．＂这个表定义了Ｏ一２…一２，并给出了他们在Ｇａｌｏｉｓ域上的反对 数，显然，有ｇｎｏｇ［ｇｆｉｌｏｇ［ｉ】】＝ｉ，和西ｌｏｇ【ｇｆｌｏｇ［ｉ］】＝ｉ成立。 下面是两个表在ＧＦ（２８）和ＧＦ（２１６）上的ｃ语言实现代码：２ Ｏ： ｓｔａｔｉｃ ｉｎｔ ｇｆ＿ａｌｒｅａｄｙ ｓｅｔｕｐ＃ｉｆｄｅｆ贮占ｓｍｉｌｅ ｈａｔ ｓｔａｔｉｃ ｉｎｔ ｓｔａｔｉｃ ｈａｔＭｏｄａｒ＿ｎｗ２２５６；２Ｍｏｄａｒ＿ｎｗｍｌ Ｍｏｄａｒ＿ｐｏｌｙ Ｍｏｄａｒ ｎｗ ２２２５５；０４３５；＃ｅｌｆｆＷ二１６ｓｔａｔｉｃ ｈａｔ ｓｔａｔｉｃ ｉｎｔ ｓｔａｔｉｃ ｉｎｔ ＃ｅｎｄｉｆ ６５５３６；５Ｍｏｄａｒ＿ｎｗｍｌ Ｍｏｄａｒ＿ｐｏｌｙ２６５５３５；０２１００１３；忸ＴＯ Ｊ为龃ｏｇ表，ＪＪｏ＿里为面ｌｏｇ表ｓｔａｔｉｃ ｓｔａｔｉｃ ｖｏｉｄｈａｔ＋Ｂ＿Ｔｏ－Ｊ；ｉｎｔ’】ｊｏＪ；ｇｆ＿ｍｏｄａｒ＿ｓｅｔｕｐＯ．｛ ｉｎｔｊ，ｂ，ｔ；ｉｆ（ｇｆ＿ａｌｒｅａｄｙ＿ｓｅｔｕｐ）ｒｅｔｕｒｎ；Ｂｊｏｊ＝（ｒｏｔ｜）ｍａｌｌｏｅ（ｓｉｚｅｏｆ（ｉｎｔ）’Ｍｏｄａｒ＿ｎｗ）；Ｊ―ＴＯ―Ｂ＝（ｉｎｔ＋）ｍａｌｌｏｅ（ｓｉｚｅｏｆ（ｉｎｔ）＋Ｍｏｄａｒ＿ｎｗ）；ｆｏｒ０＝０；ｊ＜Ｍｏｄａｒ ｎｗ；ｊ抖）｛ Ｂ＿ＴＯＪ啪＝Ｍｏｄａｒ＿ｎｖａｎｌ；Ｊ』０－ＢＤ】．Ｏ；｝ｂ２ １；ｆｏｒ（ｊ＝０；ｊ＜Ｍｏｄａｒ＿ｎｗｍｌ；ｊ‘∽｛８Ｔ０．Ｊ［ｂ】－ｊ；ＪＪＯ』Ｄ】２ｂ； ｂ＝ｂ“１：ｉｆ（ｂ＆Ｍｏｄａｒ ｎｗ）ｂ＝（ｂ“Ｍｏｄａｒ＿ｐｏｌｙ）＆Ｍｏｄａｒ＿ｎｗｍｌ；第２０页国防科学技术大学研究生院工程硕士学位论文ｇｆ＿ａｌｒｅａｄｙｓｅｔｕｐ＝１；）通过查表实现的乘除法代码如下：＃ｄｅｆｉｎｅ ｉｎｔＭｏｄａｒ―ｎｗｍｌ（１“ｗ），／即Ｍｏｄａｒ―ｎｗｒａｌ为２的Ｗ次幂ｘｘｘ．ｉｎｔｇｆ＿ｓｉｎｇｌｅ＿ｍｕｌｔｉｐｌｙ（ｉｎｔ ｊ；ｙｙｙ）｛ｉｎｔ ｓｕｍｇｆ＿ｍｏｄａＬｓｅｔｕｐＯ；／／建立鲷ｏｇ表与ｇｆｉｌｏｇ表，如两表己存在，则跳过 ｉｆ（ｘｘｘ一０ Ｊ｜ＹＹＹ―Ｏ）｛ｒｅ！ｔｕｍ Ｏ：ｆ『Ｂｊｏｊ为ｇｆｌｏｇ轰ｊｊｏ卫为ｇｆｉｌｏｇ表ｓｕｍＡ＝Ｂ＿ＴＯＪ［ｘｘｘ］＋Ｂ＿ＴＯ＿Ｊ［）ｒｙｙ】； ｉｆ（ｓｕｍ＿．ｊ＞２ Ｍｏｄａｒ＿ｎｗｍｌ）ｓｕｍＡ?＝Ｍｏｄａｒ＿ｎｗｍｌ；ｒｅｔｕｒｎＪｊ、ｏ―Ｂ【ｓｕｒｎｊ】；ｉｎｔｇｆ＿ｓｉｎｇｌｅ＿ｄｉｖｉｄｅ（ｉｎｔａ，ｉｎｔｂ）｛ｉｎｔｓｕｍ．ｊ；ｍｏｄａｒ＿ｓｅｔｕｐ０；ｇｆｉｆ（ｂ―Ｏ）ｒｅｔｕｒｎ一１；ｉｆ（ａ一０）ｒｅｔｕｒｎＯ； ２ ｓｕｍＡ Ｂ＿Ｔ０＿Ｊ【ａ】－Ｂ３０』［ｂ】；ｉｆ（ｓｕｍ＿ｊ＜Ｏ、ｓｕｍＡ＋＝Ｍｏｄａｒ＿ｎｗｍｌ； ｒｅｔ啪Ｊ』Ｏ＿Ｂ［ｓｕｍ ｊ］；３．２３程序简介给定ｎ个数据块和ｉｒｌ个校验块，则实现基于Ｖａｎｄｅｒｍｏｎｄｅ算法的主要步骤如下： １、选定ｗ的值使得２”＞ｒｅ＋ｔ；，容易选ｗ＝８或者１６，这是因为Ｗ刚好是 一个字节的整数倍；２、按上述算法建立对数表及反对数表；第２ｌ页国防科学技术大学研究生院工程硕士学位论文３、建立矩阵Ｆ为研×疗的Ｖａｎｄｅｒｍｏｎｄｅ矩阵， 注意乘法运算是在ＯＦ（２”）上进行的；五，＝ｊ，－Ｉ（１≤ｉ≤坍，ｌ≤／≤功，４、用矩阵Ｆ和数据块进行运算，来生成和维护校验块，注意加法和乘法运 算同样是在ＧＦ（２”）上进行的； ５、如果有不多于ｍ个数据块丢失，都可以以如下方式进行恢复：从剩余的 块中选取ｎ个块（无论数据块还是校验块），按照３．２．１节方法建立矩阵一’及向量 Ｅｔ，从公式Ｄ＝一”．Ｅ’中求出Ｄ，即可以恢复出原数据。 下面把源程序里各主要函数的功能做一下介绍：ｖｏｉｄｇｆ＿ｍｏｄａｒ＿ｓｅｔｕｐ０：此函数用来建立驵ｏｇ表与ｇｆｉｌｏｇ表，如两表已存在，ｍｕｌｔｉｐｌｙ（ｉｎｔａ．ｉｎｔ则跳过。ｉｎｔ ｇｆ＿ｓｉｎｇｌｅｂ）：此函数做两个数的乘法，并返回所得结果。ｉｎｔ ｖｏｉｄｇｆ＿ｓｉｎｇｌｅ＿ｄｉｖｉｄｅ（ｉｎｔａ’ｉｎｔｂ）：此函数完成ａ除以ｂ，并返回结果。ｇｆ＿ａｄｄ＿ｐａｒｉｔｙ（ｖｏｉｄ＊ｔｏ＿ａｄｄ，ｖｏｉｄ＊ｔｏ＿＿ｍｏｄｉｆｙ，ｉｎｔ ｓｉｚｅ）：此函数的工作是计算两个存储区域的奇偶值，ｔｏ＿ａｄｄ和ｔｏ＿ｍｏｄｉｆｙ，大小均为ｓｉｚｅ字节， 结果存放在ｔｏ＿ｍｏｄｉｆｙ．ｖｏｉｄｇｆ＿ｆａｓｔ＿ａｄｄ ｐａｒｉｔｙ（ｖｏｉｄ＊ｔｏａｄｄ，ｖｏｉｄ＊ｔｏ ｍｏｄｉｆｙ，ｉｎｔｓｉｚｅ）：此函数用来计算ｔｏ＿ａｄｄ和ｔｏ＿ｍｏｄｉ秒两个存储区域的奇偶值，每个区域的大小均 为ｓｉｚｅ字节，结果存放在ｔｏ＿ｍｏｄｉｆｙ．ｖｏｉｄｇｆ＿ｍｕｌｔ＿ｒｅｇｉｏｎ（ｖｏｉｄ＊ｒｅｇｉｏｎ，ｉｎｔｓｉｚｅ，ｉｎｔｆａｃｔｏｒ）：此函数完成ｒｅｇｉｏｎ中的字与ｆａｃｔｏｒ的乘法。Ｓｉｚｅ定义了ｒｅｇｉｏｎ中的字节数。Ｒｅｇｉｏｎ是 可重写的。然而，如果ｆａｃｔｏｒ不是０的话，可以通过调用ｇｆ＿ｍｕｌｔ＿ｒｅｇｉｏｎ（ｒｅｇｉｏｎ，ｓｉｚｅ。ｇｆ＿ｓｉｎｇｌｅ＿ｄｉｖｉｄｅ（１，ｆａｃｔｏｒ））来恢复ｒｅｇｉｏｎ。 ｉｎｔ＊ｇｆ＿ｍａｋｅ＿ｖａｎｄｅｒｍｏｎｄｅ（ｉｎｔｒｏｗｓ，ｉｎｔｃｏｌｓ）：此函数生成并返回一个 ｃｏｌｓ）：此函数生成并返回ｒｏｗｓ｛ｅｃｏｌｓ的Ｖａｎｄｅｒｍｏｎｄｅ矩阵。这个矩阵是一个ｒｏｗｓ￥ｃｏｌｓ的数组。ｉｎｔ＊ｇｆ＿ｍａｋｅ＿ｄｉｓｐｅｒｓａｌ＿ｍａｔｒｉｘ（ｉｎｔ 一个ｒｏｗｓ＊ｃｏｌｓ的ｄｉｓｐｅｒｓａｌｍａｔｒｉｘ。 ｒｏｗｓ，ｉｎｔＣｏｎｄｅｎｓｅｄ Ｍａｔｒｉｘ＊ｇｆ＿ｃｏｎｄｅｎｓｅ ｅｘｉｓｔｉｎｇ ｒｏｗｓ，ｉｎｔ ｒｏｗｓ，ｉｎｔ ｄｉｓｐｅｒｓａｌｄｉｓｐｅｒｓａｌ＿ｍａｔｒｉｘ（ｉｎｔ木ｄｉｓｐ．ｉｎｔ木ｃｏｌｓ）：当进行解码的时候，必须根据情况删掉ｍａｔｒｉｘ中出错的行，得到的矩阵将被用来计算丢失的块。这个函数就是用来完成删除的工作。历印是原先的ｄｉｓｐｅｒｓａｌ ｍａｔｒｉｘ，是从ｇｆ＿ｍａｋｅ＿ｄｉｓｐｅｒｓａｔ＿ｍａｔｒｉｘ（ｉｎｔｒｏｗｓ，ｉｎｔｃｏｌｓ）得到的。Ｅｘｉｓｔｉｎｇ＿ｒｏｗｓ是一个有ｒＯＷＳ元素的数组，包含０，１。如果你有块ｉ的话，元素ｆ将为Ｉ，如果块ｉ丢失的话，将为０。国防科学技术大学研究生院工程硕士学位论文此函数生成并返回一个按如下定义的压缩矩阵：ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛‘／宰Ｔｈｅｎ＊ｎｉｎｔ＊ｃｏｎｄｅｎｓｅｄ＿ｍａｔｒｉｘ； ｄｅｌｅｔｅｄ卑｜ｄｉｓｐｅｒｓａｌｍａｔｒｉｘ ｗｉｔｈｒｏｗｓｉｎｔ＊ｒｏｗ＿ｉｄｅｎｔｉｔｉｅｓ：ｉｄｅｎｔｉｔｉｅｓ ｏｆ ｔｈｅｃｏｎｄ＿ｍａｔｒｉｘ木／｝Ｃｏｎｄｅｎｓｅｄ＿Ｍａｔｒｉｘ： 注意，总是可以通过调用ｇｆ＿ｃｏｎｄｅｎｓｅ＿ｄｉｓｐｅｒｓａｌ＿ｍａｔｒｉｘ０，来获得一个压 缩矩阵。即使没有行需要被删除。Ｒｏｗｉｄｅｎｔｉｔｉｅｓ说明了压缩矩阵中哪些行被留了下来。 ｉｎｔ＊ｇｆ＿ｉｎｖｅｒｔ＿ｍａｔｒｉｘ（ｉｎｔｓｍａｔ．ｉｎｔｒｏｗｓ）．此函数完成方阵ｍａｔ的求 ｅｏｌｓ）：将一个矩阵保逆，返回舾｝彤透够筝ｏｇｆ ｗｒｉｔｅｍｔｒｉｘ（ＦＩＬＥ蟠，ｉｎｔ木ａ，ｉｎｔｒＯＷＳ，ｉｎｔ存在文件中。 ｉｎｔ＊ｇｆ＿ｒｅａｄ＿ｍａｔｒｉｘ（ＦＩＬＥ木ｆ’ｉｎｔ＊ｒｏｗｓ，ｉｎｔ＊ｃｏｌｓ）：从文件中读取矩阵。 ３．２．４算法复杂度１２５】编码复杂度：Ｏ（ｍｎ） 解码复杂度：Ｏ（ｎ３）３．３基于Ｃａｕｃｈｙ矩阵的ＲＳ算法分析与实现３．３．１ Ｃａｕｃｈｙ矩阵简介３．３．１．１Ｃａｕｃｈｙ矩阵的定义定ｙ．１２６１：令Ｆ为Ｇａｌｏｉｓ域，令｛＾，而，…，‰｝，｛乃，均，…％）是域Ｆ中的两组元素，满足：（ｉ）Ｖｉｅ｛１，…，ｍ｝Ｗ∈｛１，…，聊｝：ｔ＋＂≠ｏ一 ａｎｄＶｉ，＿，∈｛ｌ，。一，以｝，ｆ≠，：Ｍ≠乃， （ｉｉ）Ｖｆ，歹∈｛１，．一，川ｊ，ｆ≠，：ｔ≠ｘ』国防科学技术大学研究生院工程硕士学位论文ｌ ‘＋Ｙｌ ｌ 而＋Ｍ ｌ ｌ而十儿１而＋只１恐＋ｙ２毛＋％矩阵１ １ ｘｍｄ＋ｙ２ ｌ ｘｍ＋ｙｌ １称为域Ｆ上的Ｃａｕｅｈｙ矩阵。靠－１＋乃１ ｘｍ＋Ｍ…ｘｍｄ＋ｙＨ … １ｘｍ＋ｙＨ定理１［２６］：令Ｃ为一Ｃａｕｃｈｙ矩阵，则其任意一个子方矩阵必是非奇异的。 定理２１２６１：任意一个＂×＂阶的Ｃａｕｃｈｙ矩阵在Ｇａｌｏｉｓ域Ｆ上的求逆运算，都可 以在Ｆ上的Ｏ（ｎ２）运算内完成。３．３．１．２Ｃａｕｃｈｙ矩阵的构造定义：ｎ代表信息块的数目，ｍ代表冗余块的数目，２…为信息块的字长，１３．，ｍ，ｗ满足ｌｌ＋ｍ≤２…。令）仁｛■，…，靠｝，Ｙ≮Ｍ，…，ｙ。｝，Ｖｘ。，Ｙ，，是ＧＦ（２…）上的独立元素，并且１ＪｎＹ≠Ｏ，那么由Ｘ，Ｙ定义的Ｃａｕｃｈｙ矩阵在（ｉ，ｊ）位置的元素为―二一。ｘｔ＋ｙｉ我们以ｎ＝５，ｍ＝２为例，构造在ＧＦ（２３）上的Ｃａｕｃｈｙ矩阵。令ｘ彳｛１，２｝， Ｙ－－－｛Ｏ，３，４，５，６，，通过查加法表和乘法表（如图３．４），所得的生成矩阵如图 ３．５，Ｃａｕｃｈｙ矩阵是其中的后１３１行。０ ０ １２ｌ ｌ Ｏ３２ ２ ３３《Ｓ ３ ２ｌ ０ ７ ６ ５ ４６ ６ ７ ４ ５７ ７０ｌ２３４Ｓ‘７５４ ７５６ 了 Ｏ ｌ６５０ Ｏ ―Ｏｌ §６２３ｉ‘ 矗 工 ２ 矗 ５ ｔ ２ ５ ｌ ３ ７ 岳Ｓ ；６７ ３７Ｏ １矗 ７ ４ｌ７３２６虚３毒 ５２５矗ｌ４３ｒｊ ０ ０ Ｏ？ ２ ３ ｛Ｓ ４ ６ ３６ ｌ ４ ２‘ ７ ｌ §３ ５ ２ １４０３３Ｏ２ ｌ６ ６４３２ｌ０加法乘法图３．４ ＧＦ（２３）上的加法和乘法表口１第２４页国防科学技术大学研究生院工程硕士学位论文图３．５查表构造的生成矩阵１２７】二｛豳当ｎ＝５，ｍ＝３时，将数据Ｍ分为Ｄｌ，Ｄ２，Ｄ３，Ｄ４，Ｄｓ五个数据块，我们先 按上述方法生成生成矩阵，然后对该矩阵中Ｇａｌｏｉｓ域元素用ｍ＊ｍ阶的Ｏ．１矩阵进行了替换，结果如图３．６所示：图３．６生成矩阵变化图１２ｑ通过编码（解码过程类似），生成ｃ１，Ｃ２，Ｃ３三个校验块，如图３．７所示：图３．７基于Ｃａｕｅｈｙ矩阵的Ｒｓ编码因为新矩阵的运算是基于ＧＦ（２）的，所以校验块的运算可以通过数据块的ＸＯＲ 来完成。要计算Ｃｉｊ的值，可以用ｃｉＪ在Ｃａｕｃｈｙ矩阵中的相应行中的所有对应位为 １的数据块来进行ＸＯＲ．，以Ｃ１，１为例说明：Ｃｌ，１＝Ｄｌ，１。Ｄ２，１。Ｄ２，２＊０３，３。Ｄ４。Ｉ第２５页国防科学技术大学研究生院工程硕士学位论文ｏＤ４，２ｏＤ４ｊｏＤ５，２．３．３．２基于Ｃａｕｃｈｙ矩阵的ＲＳ算法实现基于Ｃａｕｃｈｙ矩阵的ＲＳ编码是在基于Ｖａｎｄｅｒｍｏｎｄｅ矩阵的ＲＳ编码上作了两点改进：＞用Ｃａｕｃｈｙ矩阵来代替Ｖａｎｄｅｒｍｏｎｄｅ矩阵，由于Ｖａｎｄｅｒｍｏｎｄｅ矩阵求逆运 算的复杂度为Ｏ（ｎ３），而Ｃａｕｃｈｙ矩阵求逆运算的复杂度为Ｏ（ｎ２），替换后 能降低矩阵求逆运算的复杂度；＞用基于ＧＦ（２Ｌ）雕Ｊ Ｌ?Ｌ的Ｏ－１矩阵代替Ｇａｌｏｉｓ域中的元素，从而以ＸＯＲ运算来代替基于Ｏａｌｏｉｓ域的乘除运算，能大大提高运算效率。 在具体实现上可以在基于Ｖａｎｄｅｒｍｏｎｄｅ矩阵的ＲＳ算法代码基础上，分为三步 来完成： 第一步，修改函数ｉｎｔ＊ｇｆ＿ｍａｋｅ＿ｖａｎｄｅｒｍｏｎｄｅ（ｉｎｔＣａｕｃｈｙ矩阵，并代替原来的Ｖａｎｄｅｒｍｏｎｄｅ矩阵。ｒｏｗｓ，ｉｎｔｃｏｌｓ），生成＃Ｃａｕｃｈｙ矩阵生成过程ｉｎｔ‘ｇｆ＿ｍａｋｅ＿ｄｉｓｐｅｒｓａｌ＿ｍａｔｒｉｘ（ｉｎｔ ｒｏｗｓ，ｉｎｔ ｃｏｌｓ，ｉｍ ｗ）｛ｉｎｔ＋ｖｄｍ，ｉ，ｊ，ｋ；ｉｎｔ＋ｘｍ，＋ｙｎ；／／ｘ＝｛Ｏ，１…ｍ一１）ｙ＝｛ｍ，ｍ＋ｌ，．．．ｒｅ＋ｎ－ｌ｝Ｘｎｌ２（ｉｍ＋）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｉｎｔ）＋（ｒｏｗｓ―ｃｏｌｓ））；ｙｎ２（ｉｎｔ＋）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｉｎｔ）＋ｃｏｌｓ）；ｆｏｒ（ｉ＝Ｏ；ｉ＜ｒｏｗｓ―ｃｏｌｓ；ｉ＋＋） ｛ ｘｍ［ｉ］＝ｉ； ｝ｆｏｒ（ｊ－ｏ；ｊ＜ｃｏｌｓ；ｊ州｛ ｙｎ［ｊ】－ｊ＋ｒｏｗｓ―ｃｏｌｓ； ｝ ）ｖｏｉｄｇｆ＿ｍｏｄａｒ＿ｓｅｔｕｐ（）；ｖｄｍ＝（ｉｎｔ＋、ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｉｎｔ）＋ｒｏｗｓ＋ｃｏｌｓ）；ｉｆ（ｖｄｍ―ＮＵＬＬ）｛ｐｅｒｒｏｒ（”Ｍａｌｌｏｅ：Ｃｈａｕｃｈｙ ｍａｔｒｉｘ”）； ｅｘｉｔ（１）； ）第２６页国防科学技术大学研究生院工程硕士学位论文ｆｏｒ（ｉ２０；ｉ＜ｃｏｌｓ；ｉ＋＋）｛ｆｏｒ（ｊ＝Ｏ；ｊ＜ｃｏｌｓ；ｊ抖）｛ｉｆ（ｉ―ｊ）ｖｄｍ［ｉ’ｅｏｌｓ＋ｊ】＝１；ｉｆ（ｉ！＝ｊ）ｖｄｍ［ｉ＋ｅｏｌｓ＋ｊ】＝０； ｝ ）ｉ－－ｊ＝１： ｆｏｒ（ｉ２ １；ｉ＜ｒｏｗｓ―ｃｏｌｓ＋ｌ；ｉ＋＋）｛ｆｏｒａ｝２１；ｊ＜ｅｏｌｓ＋ｌ；ｊ‘Ｈ）｛ｖｄｍ［（ｉ一１）４ｅｏｌｓ＋ｊ－１＋ｃｏｌｓ＋ｃｏｌｓ】２ ｇｆ＿ｓｉｎｇｌｅ＿ｄｉｖｉｄｅ（１，ｘｍ［ｉ一１】“ｙｎ［ｊ?１】）；）ｇｆ＿ｆｐｒｉｎｔ＿＿ｍａｔｒｉｘ（ｓｔｄｏｕｔ，ｖｄｍ，ｒｏｗｓ，ｃｏｌｓ）； 第二步，新增函数ｉｎｔ＊＊ｇｆ＿ｍａｋｅ ｗ ｍａｔｒｉｘ（ｉｎｔ＋ｙｄｍ，ｉｎｔｍ，ｉｎｔ ｎ，ｉｎｔＷ），用基于ＧＦ（２’）的Ｗ＊Ｗ的Ｏ一１矩阵代替Ｇａｌｏｉｓ域中的元素，以ＸＯＲ运算来代替基于Ｇａｌｏｉｓ域的乘除运算。第三步，对ｆｏｒ循环进行了优化。在编码实现中，核心程序为如下ｆｏｒ循环：／／计算冗余块 ｆｏｒ（ｉ＝Ｏ；ｉｑｎ；ｉ＋＋） ｆｏｒ＠＝ｏ；ｋ《ｗ；ｋ＋＋）ｆｏｒ（ｈ－－０；ｈ＜ｎ＋ｗ；ｈ州｛ｉｆ（ｗｗｄｍ［ｉ＋、Ⅳ＋ｋ】【ｈ】一１）｛ ｆｏｒ（ｃ＝０；ｃ＜ｐａｃｋｅｔｓｉｚｅ／ｓｉｚｅｏｆ（ｕｎｉｔ）；ｃ＋＋、 ｛ ｐａｃｋｅｔｍ［ｉ］［ｋ＋ｐａｅｋｅｔｓｉｚｅ／ｓｉｚｅｏｆ（ｕｎｉ０＋ｅ］Ａ＝＿ ｂｕｆｆｅｒ［ｈ／ｗ］０ａ％ｗ＊ｐａｅｋｅｔｓｉｚｅ／ｓｉｚｅｏｆ（ｕｎｉｔ）＋ｃ］；）’ ）通过在循环执行之前对循环中要使用的常量提前计算和存储，应用流水线的 思想减少了循环等待时间；尽量以移位运算来代替乘除法；替换求余运算，以减 小运算的强度，优化后算法效率得到了明显提高，优化后的代码如下：ｉｎｔｔＯ，ｔｌ妲，ｔ，ｔ４，ｔｍ，ｔｍｌ；ｊ＝ｐａｃｋｅｔｓｉｚｅ／ｓｉｚｅｏｆ（ｕｎｉ０；ｄ＝ｎ’ｗ：一―――――――――百ｉｉ―――――――――――一ｆｏｒ（ｉ＝Ｏ；ｉ＜ｍ；ｉ＋＋）国防科学技术大学研究生院工程硕士学位论文｛ ｔｍ＝ｉ（Ｑ：ｔ０＝ｔｍ－ｉ；／／以移位运算来代替乘法运算ｆｏｒ（ｋ卸；ｋ＜ｗ；“＋）｛ｔｌ＝ｔ０＋ｋ；ｔ２＝ｋ＊ｊ；ｆｏｒＯＦＯ；ｈ＜ｄ；ｈ十卜）｛ｉｆ（ｗｗｄｍ［ｔ１］【ｈ】一１）｛ｔ＝ｂＪ３；ｔｍｌ－－－ｔ＜＜２；ｔ４＝（１１－ｔｍｌ＋ｔ）々；／／替换求余运算以提高效率ｆｏｒ（ｅ＝０；ｃ＜ｊ；ｃ抖）｛ ｐａｃｋｅｔｍ［ｉ］Ｉｔ２＋ｅｌ＾＝ｂｕｆｆｅｒ［ｔ】［ｔ４＋ｃ】； ｝ ｝ ） ）给定ｎ个数据块和ｎｒｌ个校验块，则实现基于Ｃａｕｃｈｙ算法的主要步骤如下： １、选定ｗ的值使得２”≤肌＋栉，这里ｗ可以任意选取满足条件的值； ２、建立矩阵Ｆ为ｍｘｎ的Ｃａｕｃｈｙ矩阵，＾Ｊ＝上（１≤ｆ≤肌，ｌ≤．，≤力；１确十Ｍ３、建立矩阵Ｈ，用基于ＧＦ（２”）的ｗ?ｗ的Ｏ一１矩阵代替矩阵Ｆ中各个元素； ４、用矩阵Ｈ和数据块进行运算，来生成和维护校验块，运算是基于ＸＯＲ进行的； ５、如果有不多于ｍ个数据块丢失，都可以以如下方式进行恢复：从剩余的块中选取ｎ个块（无论数据块还是校验块），按照３．２．１节方法建立矩阵彳’及向量Ｅ’，用基于ＧＦ（２ｗ）的Ｗ＋Ｗ的０－１矩阵代替矩阵４’１中各个元素，从公式Ｄ＝Ａ”．Ｅ’ 中求出Ｄ，即恢复出了原数据。 ３．３．３算法复杂度【２５】由于文件分块原因，编码算法复杂度为Ｏ（ｍ（ｎ一肌）），改进后解码算法由于异 或运算取代乘法运算，减少了乘法运算的次数，解码复杂度降为Ｏ（ｎ２）。两种算法第２８页国防科学技术大学研究生院工程硕士学位论文的复杂度对比如表３．１－表３．１算法复杂度对比基于Ｖａｎｄｅｒｍｏｎｄｅ矩阵的ＲＳ算法编码 解码 ３．３．４性能测试 Ｏ（ｍｎ） Ｏ（ｎ３）基于Ｃａｕｃｈｙ矩阵的ＲＳ算法 Ｏ（ｍ（ｎ－ｍ）） Ｏ（ｎ２）在测试平台为ｒｅｄｈａｔｌｉｎｕｘ９．０，赛扬２．６Ｇ ｃｐｕ，内存７６８Ｍ，取当ｎ＝５，ｍ＝４，ｗ＝４时，通过对大小不同的数据块分别进行了测试，实验结果如表３．２和表３－３， 对以上两表结果进行分析，经计算得到如下结果：编码效率平均提高４３．１２％，解 码效率平均提高７６．９６％。表３．２编码时间对比表＼算法文赫１Ｍ ２Ｍ ５Ｍ基于Ｖａｎｄｅｒｍｏｎｄｅ基于Ｃａｕｃｈｙ矩阵的ＲＳ算法（ｓ）０．０２７０２６ ０．０５４９０３ ０．１６６６３０ ０．３１７２５８ ０．６３８３０６ １．２４９２８７＼ 矩阵的ＲＳ算法（ｓ）０．０５２８７６ Ｏ．１１２６９５ ０．３０８４４２ ０．５８２７１８ １．０２５９２５ １．７６５２６９１０Ｍ ２０Ｍ ４０Ｍ表３．３解码时间对比表＼＼算法 文件套ｋ１Ｍ ２Ｍ ５Ｍ ｌＯＭ ２０Ｍ ４０Ｍ基于Ｖａｎｄｅｒｍｏｎｄｅ基于Ｃａｕｃｈｙ矩阵 的ＲＳ算法（ｓ）０．０２６１２５ ０．０６２１６４ Ｏ．２１８１１８ ０．３９７６１３ ０．６５９８３８ １．３５４９６６＼ 矩阵的ＲＳ算法（ｓ）Ｏ．１３９５２４ ０．２３６８１５ ０．８７３４８３ １．５８０６３４ ２．５５３２８６ ７．８０９７７ｌ３．４本章小结本章首先简要介绍了ｅｌａｓｔｌｒｅ ｃｏｄｅ的发展及基本思想，分析并实现了基于第２９页国防科学技术大学研究生院工程硕士学位论文Ｖａｎｄｅｒｍｏｎｄｅ矩阵和基于Ｃａｕｃｈｙ矩阵的两种ｅｒａｓｕｒｅ ｃｏｄｅ算法，并详述了其代码实现，最后给出了性能测试。由于基于Ｃａｕｃｈｙ矩阵的ｅｒａｓｕｒｅ ｃｏｄｅ算法良好的编解 码效率，该算法在后述的高可用分布式存储系统中得到了应用。第３０页国防科学技术大学研究生院工程硕士学位论文第四章基于ｅｒａｓｕｒｅ ｃｏｄｅ的高可用分布式存储体系结构设计４．１相关工作Ｐ２Ｐ技术以非中心化、健壮性、可扩展性、高性价比、负载均衡等优点日益受 到人们的关注，在各个方面得到了广泛的应用，特别是在文件共享方面取得了巨 大的成功，如Ｎａｐｓｔｅｒ，Ｇｎｕｔｅｌｌａ，ＫａＺａａ等。 由于分布式散列表技术（ＤＨＴ：Ｄｉｓｔｒｉｂｕｔｅｄ Ｈａｓｈ Ｔａｂｌｅ）的引入，使得基于Ｐ２Ｐ 的广域存储系统的研究成为当今的研究热点之一，在研的项目有很多，如 ｃｆｓ（ｃｈｏｒｄ）、ｐａｓｔ（ｐａｓｔｒｙ）、ｇｒａｎａｒｙ（ｐａｓｔｒｙ）等。ＤＨＴ类结构有着良好的可扩展性、鲁 棒性、结点ＩＤ分配的均匀性和自组织能力，它假设每个节点具有相同的能力，但 由于在实际Ｐ２Ｐ环境中节点所具有的异构性，动态性，不可信任性及易受攻击性， 影响了存储系统的可用性，致使这些系统都没有形成实际的商业化产品。 冗余是一种提高数据的有效性和安全性的基本方法。实现冗余有两种最基本 的方式，一种是完全复制，如镜像（ｍｉｒｒｏｒｉｎｇ），一种是编码（ｅｒａｓｕｒｅ ｃｏｄｅ）实现，如ＲＡＩＤ．５，ＲＳ ｃｏｄｅ，ｔｏｒｎａｄｏ ｃｏｄｅ等。相关的技术在计算机系统内部面临部件失效解决数据可用性问题方面相对成熟，但在无边界网络环境下面临智能攻击解决信 息生存性问题的研究还有相当多的问题亟待解决。文献１１】通过对比分析，发现ｅｒａｓｕｒｅｃｏｄｅ只须较少甚至是低几个数量级的存储及网络带宽开销，就可以实现和完全复制（ｒｅｐｌｉｃａ）相同的系统要求，并且具有更好的容错性能。 在８６３项目“协作式应急响应服务与基于漂移的可生存系统研究”［２８］［２９１ｄｐ， 我们构造了基于Ｐ２Ｐ的无中心安全协作和安全信息发布平台，在该平台基础上针 对Ｐ２Ｐ节点的动态变化对系统可用性的影响，本章将ｅｒａｓｕｒｇ ｃｏｄｅ与ＤＨＴ技术结 合起来，提出了一种高可用的分布式存储体系结构１３０】。 该系统除民用外，还可以应用在军事上，主要有几个方面： 一是可以充分利用各级部队机关局域网的空闲空间，用于机密信息的分布存 储，避免了采购专用存储服务器的投资；同时增强了保密性能，面ｌ临敌意的网络 攻击时，即使数个节点数据被破坏或被窃取，攻击者也无法获取完整有效的信息； 二是可用于保护军网中重要的门户网站的日志文件，可将其日志文件分布到 多个节点上存储，以达到防止敌意攻击者实施攻击后删除或篡改； 三是可用于建立军事信息仓库，用于秘密以上等级军事信息的集中存储与获取，便于数据的备份与灾难恢复。目前ＤＨＴ算法主要有Ｐａｓｔｒｙ，Ｃｈｏｒｄ，ＣＡＮ，Ｔａｐｅｓｔｒｙ等。本系统以Ｃｈｏｒｄ为 例来研究。每个节点除维护一个路由表（ｆｉｎｇｅｒ ｔａｂｌｅ）外，还维护一个后继表第３１页国防科学技术大学研究生院工程硕士学位论文 （Ｓｕｃｃｅｓｓｏｒ ｔａｂｌｅ），用于容错：当继承者失效后，可由后继表中的下一个继承者接替相应位置；此外还能提供数据冗余：可将某节点上的数据复制到它后继表 中的各节点上，来提高数据的有效性。本系统也是将文件的分块存储到后继表中 的各个节点上。ｃｈｏｒｄ具体细节描述见上述２．１．４节。ｃｈｏｒｄ基于最基本的ｌｏｏｋｕｐ（ｋｅｙ），向上层提供如下ＡＰＩ： Ｌｏｏｋｕｐ（ｋｅｙ，ｍ）：返回ｋｅｙ所在的节点的ｍ个继承者的地址列表；Ｇｅｔ―ｓｕｃｃｅｓｓｏｒ＿ｌｉｓｔ（ｋｅｙ）：返回某个ｋｅｙ的全部继承者列表。４．２体系结构本系统体系结构是面向广域网中的数据存储提出的，它在ｃｈｏｒｄ基础上，结 合ｅｒａｓｕｒｅ ｃｏｄｅ编码，通过跟踪维护节点的动态变化，保证在部分节点（ｎ个节 点）同时失效的情况下仍能可靠恢复原数据，从而实现了高可用的数据存储。如 图４．１，系统由系统接口、ｃｈｏｒｄ层及功能模块层三部分组成，其中系统接口为上 层应用程序提供接口；ｃｈｏｒｄ层维护路由表，完成数据块的定位；中间层包括文件 编解码模块，分块分发与获取模块，动态维护模块及其它功能模块等，它利用ｃｈｏｒｄ 提供的接口，实现对数据块的可靠存储、维护及相关功能，各个模块的具体实现介绍如下： ；”。”≈。，ｉ。篓÷蓐５；承虢丝”、？磁貉鼍搿’，鹾魏文件编｝分。块分｝动态Ｉ其”它功 解码模ｆ”发与获Ｉ维护ｌ能模块 块．。 ｌ取模块｜模块ｌ≈Ｉ―ｒ‘，ｐ一、ｒ：５％“ｒ’图４．１系统结构图４．２．１文件编解码模块 该模块负责对文件进行ｅｒａｓｕｒｅ ｃｏｄｅ编码与解码。本系统采用Ｃａｕｃｈｙ－ＲＳ ｃｏｄｅ编码作为它的ｅｒｆｌｓｕｌ＇ｅ ｃｏｄｅ，它是ＶａｎｄｅｒｍｏｎｄｅＲＳｃｏｄｅ的改进，主要操作基于异或进行，大大提高了编解码的效率。具体编解码算法见前述３．３．节。 ４．２．２分块分发与获取模块 本系统中，ＤＨＴ设置每个节点的ｓｕｃｃｅｓｓｏｒ ｔａｂｌｅ的数量为ｍ＋ｎ（ｍ为数据分块 数量，ｎ为校验分块数量），用来容纳文件经Ｃａｕｃｈｙ―ＲＳ ｃｏｄｅ编码后的ｍ＋ｎ个分块。 源节点将编码后的ｍ＋ｎ个分块发送到标识为ｉｄ＝ｓｕｅｅｅｓｓｏｒ（ｓｈａ－ｌ（ｆｉｌｅ））的目的节点的ｓｕｃｃｅｓｓｏｒｔａｂｌｅ中的ｍ＋ｎ个节点上，并在源节点及目的节点上各保留一份元数据文第３２页国防科学技术大学研究生院工程硕士学位论文件，用来记录文件名，ｋｅｙ（即ｓｈａ－ｌ（ｆｉｌｅ）），文件大小，分块大小，发送时间，文 件上次访问时间，发送者的ＩＰ及ＩＤ，ｍ，ｎ，代码的生成矩阵，以及ＡＣＬ（Ａｃｃｅｓｓｃｏｎｔｒｏｌｌｉｓｔ）表。如果从源节点直接读取文件，则无须访问ＡＣＬ；如果从其它节点读取文件，则需要访问ＡＣＬ，并通过相应的验证，才能读取文件。 该模块在ＤＨＴ上实现了两个可以提供给外部应用程序的ＡＰｈ Ｐｕｔ（ｋｅｙ，ｂ）：插入文件ｂ，其中ｋｅｙ＝ｓｈａ－１（ｂ）；Ｇｅ