分布式异步图处理的关键技术研究

With the development of big data technique, a huge amount of relational data that can be represented by graph structure are collected. For the sake of mining valuable information from these big graphs, many researchers focus on improving the techniques of big graph mining and processing, and as a result many excellent research works and open-source systems are proposed. Most of these research efforts target on optimizations on synchronous graph processing. On the other hand, people recently find the superiority of applying asynchronous graph processing on accelerating convergence and improving cluster efficiency, and believe it should be a promising technique. However, the different execution characteristics of asynchronous graph processing bring many challenges, such as low usability, inefficient processing due to blocking of key messages, and inefficient storage resulted from nondeterministic characteristics. To cope with these challenges, we will launch our research on the several key techniques in asynchronous graph processing based on the understanding of its execution characteristics. This includes the transformation from synchronous graph computation to asynchronous graph computation, efficient graph processing by promoting key-messages flow, efficient graph storage and management by avoiding nondeterministic processing. We will also design and implement a distributed computing framework that supports fast asynchronous graph processing, which will be helpful for popularize our research works.

随着大数据技术的发展，各种新型应用积累了大量表达关联关系的图数据，为了便于从这些“大图数据”中挖掘有价值的信息，研究人员在分布式环境下研究大图数据的处理与挖掘，涌现出了大批优秀的研究成果和开源系统。其中大部分基于同步图计算模型，而近年来研究表明异步图计算在加速算法收敛和提高集群效率等方面有着诸多优势，具有更广阔的发展前景。然而异步图处理的推广面临着可用性问题，另外由于其对关键消息的依赖性和执行时的非确定性，也面临着高效执行和高效数据存储管理等方面的挑战。为了应对这些挑战，本课题结合分布式异步图计算的执行特点，对异步图处理的几个关键技术进行研究，包括传统同步图计算到异步图计算的自动转换、以疏导关键消息为核心的图处理模型、结合异步处理非确定性的图数据存储与管理等。最后集成所有研究成果，设计并实现一个支持高效异步图处理的分布式计算框架，以便更好地推广研究成果。

近年来人们发现异步图计算在加速算法收敛和提高集群效率等方面有着诸多优势，具有更广阔的发展前景，是未来的发展趋势。然而异步图处理的推广面临着可用性问题，另外由于其对关键消息的依赖性和执行时的非确定性，也面临着高效执行和高效数据存储管理方面的挑战。为了应对这些挑战，本课题结合分布式异步图计算的执行特点，对异步图处理的几个关键技术进行研究。首先，深入研究了传统同步图计算到异步图计算的自动转换机制，设计实现了分布式图计算系统PowerLog，它支持同步-异步图算法的自动转换，提供的分布式计算引擎提供同步-异步混合等若干执行优化技术。其次，研究了以疏导关键消息为核心的异步图处理模型，以热度为中心刻画了关键消息，设计实现了HBP支持异步优先级调度的图计算系统，并提供优化的图划分策略。最后，研究了结合异步处理非确定性的图数据存储与管理，结合GPU、NVM、SSD等新型硬件对异步图计算系统进行的优化加速。.项目启动的四年以来，共发表论文23篇，包括CCF A类期刊会议论文8篇（包括短文2篇），B类论文4篇，CCF中文A类期刊论文3篇。出版了《Spark权威指南》译著一篇，申请7项国家技术专利。获辽宁省科技进步二等奖、CCF大数据学术会议最佳论文奖、辽宁省优秀硕士学位论文等奖励。在该项目的资助下，开发了Maiter、SEP-Graph等图计算系统，并在github上开放源代码。关于异步图计算和增量图计算的研究成果被阿里巴巴公司采用，关于无协调一致性自动验证的研究成果被华为公司采用。共培养3名博士生，8名硕士生，获1人次辽宁省优秀硕士学位论文，4人次校级优秀硕士学位论文，毕业生进入阿里巴巴、百度、华为、京东等公司成为优秀的图计算系统工程师。