瞬态云环境下的自适应大图迭代查询处理关键技术研究

Recently, iterative computations over big graphs have been widely used in many scenarios, such as social network analysis, electronic commerce processing, and urban planning. On the other hand, transient cloud resources as a new service provided in cloud computing, can store big graph data and run complex analysis at a low price. This proposal concludes several features of transient resources and graph processing, mainly including the heterogeneous hardware configurations in many dimensions, the high-frequent revocation and reapplication of computational nodes, the large-scale data, and concurrent and multi-modal iterative queries. All of them make great challenges to traditional graph processing techniques in terms of computation efficiency. Given the problem of processing big graphs in transient cloud environments, this proposal plans to design new solutions from three different yet important perspectives: iterative model, data storage and index, and query sharing optimization. An open-source prototype system for distributed iterative computations over big graphs will be finally developed that can adaptively react to the change of runtime-statistics and hardware environments. This study is very theoretical and practical. Its results of course provide effective support for iterative queries over big graphs cheaply yet efficiently and finding more applications that can be run on transient resources.

近年来，大图迭代处理在越来越广泛的领域内得到了应用，如社交网络分析、电子商务交易和城市规划等。而瞬态云资源，作为云计算市场的新型服务，可为大图数据的存储和复杂处理提供廉价平台。本课题针对瞬态云环境下硬件资源多维异构和计算节点高频切换等特点，结合图数据规模的海量性和迭代查询的并发多态性，分析了传统图处理技术在计算性能方面遭遇的挑战。针对瞬态环境下的大图迭代查询问题，拟从迭代计算模型、数据存储与索引和查询共享优化三个角度提出创新的高效解决方案，并在此基础上实现一个开源的、能够自适应软硬件环境变化的分布式大图查询处理引擎。本课题的研究将为经济高效的大图迭代查询提供支持，可推动瞬态云服务的加速落地，具有重要的理论意义和实际价值。

大图迭代分析已经在学术界和工业界获得了越来越多的关注，但在大数据时代，巨大的数据规模和高频迭代导致的超高计算复杂度，使得图处理的经济开销急剧增大。另一方面，公共云服务厂商为提高闲置资源的利用率，推出了廉价但稳定性较差的瞬态计算资源，为大图处理提供了新的分布式硬件平台选择。本课题针对瞬态云环境下大图迭代分析的软硬件特征需求与资源协调问题展开深入研究。在迭代计算模型方面，设计了以块为中心的新型消息流处理框架并进一步提出了混合数据流管理架构，支持优先级任务调度和轻量级容错控制机制，建立代价收益评估模型，能够根据瞬态资源的变化与图迭代算法的计算负载变化，弹性自适应地选择合适的工作模式；在数据存储与索引方面，充分利用图数据在爬取阶段的原始局部性，提出了基于顶点备份与边迁移的分布式数据划分策略，通过数据分块对本地数据进行行列分割存储并构建索引，针对高纬度复杂消息提供弹性数据备份和误差补偿数据压缩功能，从而优化I/O访问与消息传输开销；在共享查询方面，首先针对常见的多源点图遍历查询应用，设计批处理调度机制与消息共享传输编码结构，实现批内图遍历操作的物理共享，减少冗余数据访问与消息传输开销，其次针对复杂应用场景中的超图处理，利用顶点与超边的逻辑结构共享关系，进行图结构转化，将依赖关系紧密的顶点与超边分配到相同的物理节点，以降低后续计算的通信开销。此外，本课题将图领域的数据分割技术与弹性迭代管理技术，分别应用到海洋领域的数值模式计算模型和人工智能领域的机器学习模型，均实现了性能优化。在本课题的资助下，已发表高水平论文10篇，发布开源图处理系统HGraph和机器学习系统Flegel，集成了大量常见图处理与机器学习算法，可供学术界与工业界使用。本课题成果验证了瞬态云资源在复杂数据分析领域的实际应用效果，对于提高硬件的算力使用效率、早日实现碳达峰与碳中和目标，具有重要意义。