动态图计算系统设计与性能优化研究

Due to its good expressivity, graph has been widely used to model the relationship among data elements. As a result, many large-scale graph processing systems have been proposed, which extend their capability by either distributed processing or using the external storage. However, graphs generated in the real-world are continuously changing. The existing traditional graph processing systems are mainly designed for static graph processing, and hence not support dynamic graphs. Even for those systems that supports changing the graph data (e.g, Giraph), they are typically based on straightforward implementations that are not efficient.. To resolve this problem, this project intends to do researches mainly in three aspects: 1) new graph organization format, which can support lightweight graph changing and simultaneously can reserve the data locality; 2) incremental and concurrent execution of dynamic graph analysis applications, so that a small change on the graph will not revoke all the intermediate results obtained before; 3) extending the data graph model with the concept of time-stamp, and hence enable users to express their intension on time order.

由于具有良好的表达能力，图数据结构被广泛用于对元素间具有复杂联系的数据进行建模，如社交网络、知识图谱等。为了应对大规模图数据带来的挑战，当前主要的图计算系统通过分布式集群或者外存设备极大地提升了其能够处理的图数据容量。然而，在实际生产生活中产生的图数据往往是处于不断地动态变化的状态下的。传统的大规模图计算系统由于并未考虑到这一需求，往往并不提供对图结构进行变更的接口。即便是提供了相关接口的系统（如 Giraph），也仅仅是提供了简单地支持，效率并不高。. 针对这一问题，本项目拟进行三方面的研究：1）研究新型的图数据组织方式，使得其在支持轻量级的图数据修改的同时保持很好的数据局部性；2）研究支持增量和并发计算的动态图计算框架，使得对原图小规模的修改可以不至于完全重置之前的计算结果;3）增加时间戳的概念设计新型的编程模型，从而支持用户对时序要求的表达。

由于具有良好的表达能力，图数据结构被广泛用于对元素间具有复杂联系的数据进行建模，如社交网络、知识图谱等。为了应对大规模图数据带来的挑战，当前主要的图计算系统通过分布式集群或者外存设备极大地提升了其能够处理的图数据容量。然而，在实际生产生活中产生的图数据往往是处于不断地动态变化的状态下的。传统的大规模图计算系统由于并未考虑到这一需求，往往并不提供对图结构进行变更的接口。即便是提供了相关接口的系统（如 Giraph），也仅仅是提供了简单地支持，效率并不高。.本研究主要针对基于日志信息建模生成的时序图数据的高效分析进行研究。主要完成内容包括一套对时序图进行高效匹配分析的系统，一套对图上进行随机游走类算法进行优化的算法，以及一套针对现代新型硬件优化上层应用执行性能的框架。发表在 SOSP 2019，ASPLOS 2020 上的高水平论文 3 篇。相关受资助人参与发表在 TPDS 上高水平期刊论文 2 篇。其中针对日志图查询 CPU 资源浪费过多、中间结果庞大的问题，提出了时序 窗口匹配模型，将匹配的搜索空间限制到窗口内部。极大的降低了匹配的空间以 及中间状态数量，从而显著的提升了计算的性能。实验结果显示，在内存模式下， 比现有算法快出 1-2 个数量级;在外存模式下比现有算法快出 2 个数量级以上。同时进一步探索了在图上进行随机游走类分析的性能提升工作，通过提出一套统一的转移概率定义公式，提出了一套通用的计算方法，在极大的减少了计算量的同时，保证计算结果与原算法等效。同时，我们还提出了针对该方法的一些优化策略，进一步降低了计算开销。