论文部分内容阅读
众多实际的问题可以抽象为图的模型,如网络拓扑、社交网络、网页超链接等。针对这些应用需求,业界和学术界开发了很多基于图的算法、计算框架、开源软件、函数库,这在一段时间内满足了应用的需求。这些方案的重点是提升离线计算的效率,不关注图数据的实时处理、快速查询,部分方案可处理数据的规模有限,但随着当前图应用规模的扩大和新需求的产生以及分布式处理、流式处理的发展,旧的这些解决方案已经不能适应当前应用的要求,因此设计一个高效的图处理框架或工具是有意义的。基于IBM的流处理系统(InfoSphere StreamS),设计和实现了一个可以处理图的中间件原型,运行于StreamS的应用可以直接调用它的接口来进行与图相关的处理。中间件在功能上,以图的查询为核心功能做设计,综合考虑图的更新、计算、查询和流式处理;在图的表示上,以顶点为核心,并设计了附属结构,加快图的遍历和查询,采用内存预分配和缓回收等技术来优化图的基本操作的性能;在图的计算上,采用Google的图处理框架Pregel;在数据传输和容错处理上,采用StreamS的内部库实现部分数据传输和容错处理;在流处理方面,通过在缓存、通信、并行处理、在线计算方面做优化来满足流处理应用的特点;在接口方面,根据StreamS的规范编写交互接口,内部实现对应用透明。通过实验,验证了原型系统在图的存储、计算和查询方面的功能,并对系统进行了测试。在核心功能查询性能上,中间件(三个工作结点)相对于采用通用函数库实现的单机传统的图处理框架,性能提高130%,相对于其它多机(三个工作结点)并行图处理框架平均性能提高14%。计算对查询性能的影响由64%降为0.5%,减少了计算对查询的影响。高并发查询时,CPU的使用率由单机的100%降为69%,内存使用率由单机的98%降为40%。结果表示,中间件原型在功能上满足了InfoSphereStreamS的需求,在性能上优于传统的单机模型和并行处理框架。