infosphere+streams中图处理中间件设计和实现 (1)

《infosphere+streams中图处理中间件设计和实现 (1)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AThesisSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringTheDesignandImplementationofGraphProcessingMiddlewareonInfoSphereStreamSCandidate:LiuXiaohuaMajor:ComputerArchitectureSupervisor:Assoc.Prof.CaoQiangHuazhongUniversityofScience&TechnologyWuhan43

2、0074,P.R.ChinaJanuary,2012独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本

3、学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在年解密后适用本授权书。本论文属于不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日华中科技大学硕士学位论文摘要众多实际的问题可以抽象为图的模型，如网络拓扑、社交网络、网页超链接等。针对这些应用需求，业界和学术界开发了很多基于图的算法、计算框架、开源软件、函数库，这在一段时间内满足了应用的需求。这些方案的重点是提升离线计算的效率，不关注图数据的实时处理、快速查询，部分方案可处理数据的规模有限，但随着当

4、前图应用规模的扩大和新需求的产生以及分布式处理、流式处理的发展，旧的这些解决方案已经不能适应当前应用的要求，因此设计一个高效的图处理框架或工具是有意义的。基于IBM的流处理系统（InfoSphereStreamS)，设计和实现了一个可以处理图的中间件原型，运行于StreamS的应用可以直接调用它的接口来进行与图相关的处理。中间件在功能上，以图的查询为核心功能做设计，综合考虑图的更新、计算、查询和流式处理；在图的表示上，以顶点为核心，并设计了附属结构，加快图的遍历和查询，采用内存预分配和缓回收等技术来优化图的基本操作的性能；在图的计算上，采用Google

5、的图处理框架Pregel；在数据传输和容错处理上，采用StreamS的内部库实现部分数据传输和容错处理；在流处理方面，通过在缓存、通信、并行处理、在线计算方面做优化来满足流处理应用的特点；在接口方面，根据StreamS的规范编写交互接口，内部实现对应用透明。通过实验，验证了原型系统在图的存储、计算和查询方面的功能，并对系统进行了测试。在核心功能查询性能上，中间件（三个工作结点）相对于采用通用函数库实现的单机传统的图处理框架，性能提高130%，相对于其它多机（三个工作结点）并行图处理框架平均性能提高14%。计算对查询性能的影响由64%降为0.5%，减少了

6、计算对查询的影响。高并发查询时，CPU的使用率由单机的100%降为69%，内存使用率由单机的98%降为40%。结果表示，中间件原型在功能上满足了InfoSphereStreamS的需求，在性能上优于传统的单机模型和并行处理框架。关键词：图模型，图表示，图并行处理，图计算框架，流处理I华中科技大学硕士学位论文AbstractManypracticalproblemscanbeabstractedasgraphmodels,suchasnetworktopology,socialnetwork,weblinksandsoon.Inresponsetothe

7、seneeds,industryandacademiadevelopedanumberofgraph-basedalgorithms,computationalframework,opensourcesoftwarelibrary,thefocusoftheseprogramsistoenhancethecomputationalefficiencyandflexibilityofgraph,whichintimetomeetthedemandofapplication.Butwiththeexpansionoftheseapplicationsnow

8、andthenewgenerationofapplicationsanddistributed