基于数据共享的高并发图计算系统及核心技术研究

Graph data is one of the typical type of the big data and graph computing has become a research hotspot in present. There have been many graph computing systems which are represented by Pregel， Giraph，GraphLab，GraphX and so on. The processing mode adopted by these systems is task oriented, in which,a graph computing procedure is divided into a series individual tasks in which the processing procedure and data are tightly coupled together. Such mode woks well with lower concurrency. However with the various applications continue to expand, more and more tasks need to be processed concurrently. In this case the coupling of procedure and data become the bottle neck for efficiency. Because the task oriented model does not support the data sharing, each task has to store their graph data in memory, which causes the redundant graph data exhausting the memory which extremely limits the concurrency of tasks processing, thereby heavily impede the improvement of performance of graph computing systems. In this proposal, we present a novel data oriented graph computing model which based on the data sharing technology to achieve efficient utilization of memory to support high concurrency task processing and to increase the whole efficiency of graph computing systems. Enclosing the aim, we will deeply study related the data manager method, stream computing model, execution mechanism and related core technologies.

图数据是大数据的重要数据类型之一，图处理技术是当前的研究热点，出现了以Pregel， Giraph，GraphLab，GraphX等为代表的图处理的系统。这些系统大多基于"面向任务"的处理模式：将图计算分解成一个个相互独立的任务来完成，每个任务中计算程序和数据紧密耦合。这样的模式在并发度不高的情况下，收到了预期的效果。但是，随着应用的不断扩展，要求并发处理的任务越来越多，数据和计算绑定的模式则遇到性能瓶颈。由于面向任务的模式，不支持共享数据，每个任务都需导入各自所需的数据，往往造成冗余数据占据内存，消耗巨大，并发执行的任务极其有限，严重阻碍了图处理系统性能的提升。 本申请提出一种新型的"面向数据"的图计算模式，以支持图数据共享为基础，目的是有效使用内存，支持高并发的任务执行，从而从整体上提高图计算的效率。本项目将对支持高并发图计算系统的图数据管理、流式计算模型、执行机制和技术展开详细研究。

图数据是大数据的重要数据类型之一，图处理技术以及图计算系统的研究是当前科技领域的研究热点，国家科技计划对图计算系统的持续支持，进一步表明图计算系统研究的重要性。.本课题的研究目标是通过实现图数据共享，使得不同处理程序可在同一图数据集上运行，增加并发执行度，从而提高图计算系统的效率。围绕这个目标，课题分别从系统设计、硬件支持、机制优化以及新技术融合四个层面对高并发任务场景下的图计算系统的关键技术展开研究。（1）从模型层面，分析了现有图计算系统在多并发任务场景下的性能问题，分别提出解耦合的图计算模型、异构集群中最优子集群选取机制和异构感知的流式图切分技术，基于解耦和图计算模型设计了面向并发任务的共享图计算系统；（2）充分利用硬件发展带来的红利，研究了基于RDMA和GPU的图计算系统相关问题，包括针对可扩展性问题提出的基于RDMA高速网络以及针对线程计算冲突和存储体冲突的GPU图计算模式，从而在保证高性能的前提下，实现了图计算的高并发性和高可扩展性；（3）图计算系统作为一种分布式系统，仍面临很多系统结构设计问题的挑战，为此我们针对性地开展了图计算系统和分布系统中的优化问题研究；（4）伴随着人工智能应用的强大需求，将图计算技术应用到人工智能领域也出现了新的契机，我们及时跟进国际主流研究，这部分工作包括图计算系统对机器学习系统的支持和融合。.本课题的研究成果是以论文、专利和系统的形式展示出来。共发表了12篇论文，项目执行期间新申请专利2项，获授权专利3项（授权专利虽然是在项目之前申请，但所涉及的工作是本课题的前期基础）。我们实现了图计算系统原型Seraph以及GPU升级版的Garaph，大部分系统实现的源代码在开源社区开源。我们注重加强和其他单位的科研合作，上述很多工作是和微软亚洲研究院的同行们共同完成。