面对日益复杂的数据关联,图的结构变得越来越流行,社交应用,页面链接,用户对商品的偏好都可以用结构化的图来表示,这样大规模的图的分析、计算、查询已成为一个非常重要的需求,图计算和图查询系统应运而生。随着数据量的不断增大,算法的日趋复杂,分布式的图计算和图查询逐渐成为了研究的热点。真实世界中的自然图大多服从幂律分布的,多数顶点具有相对少的邻居,而少数具有非常多的邻居,如社交网络中的名人。不幸的是,现有的分布式图计算系统通常采用同样的处理方式处理不同的顶点,这导致分布式图计算系统的性能和可扩展性都很差。越来越多的公共知识数据以RDF图的形式被存储起来,然而现有的分布式RDF图查询系统却无法满足需要。无论是简单请求还是复杂请求,现有的分布式RDF图查询系统往往使用全部资源处理单个请求。由于需要机器进行同步,简单请求的延迟往往非常高,而且由于使用全部资源处理单个请求,并发处理多个请求的能力很弱,这导致整个系统吞吐量很低。针对上述问题,本文的主要贡献有以下方面:本文分析了现有的分布式图计算系统在图划分和计算引擎方面的不足,并实现了PowerLyra:采用随机和启发式的混合切割算法划分图,区别对待低度数顶点和高度数顶点,降低复制因子;采用混合计算模型和数据局部性优化,减少消息的传输,高了数据的局部性。本文针对现有分布式图查询系统的不足,结合RDMA的特性,设计并实现了分布式图查询系统Wukong。Wukong扩展了传统的向图模型,添加了索引顶点,采用混合切割算法区别对待普通顶点和索引顶点,并使用基于谓语的键值存储系统存储本地图数据;Wukong结合RDMA的特性,用全历史剪枝法取代现有的单步剪枝法,并且根据不同的请求类型动态决定的执行模式;Wukong每个线程可以独自执行一个查询,可以并发处理多个请求,因此有非常高的吞吐量。本文对PowerLyra和Wukong分别进行了详细的性能评测。测试显示,相比PowerGraph,PowerLyra在真实图上性能升最高可达5.5倍,在生成图上性能升最高可达3.3倍;相比TriAD和Trinity.RDF,Wukong单个查询性能高11.9倍,吞吐量升高达740倍。