关键词:
图处理
分布式系统
高性能硬件
大规模数据处理
图聚合
图OLAP
摘要:
近些年来,随着互联网业务的飞速发展,大规模图数据集开始在许多领域大量出现,并且催生了许多相关的图计算应用。在系统设计层次,现阶段的大图场景主要产生了两类需求:对大规模数据的容纳与处理能力的需求;以及实现低响应延迟的高密度算力需求。对应地,大图分析系统主要基于两种路线进行构建:基于不同图计算模型的CPU分布式图分析系统,或者是基于高性能计算硬件(包括GPU、FPGA等)的单节点图分析系统。然而,这两种解决方案都仅能满足单方面的需求、而非全部。因此,设计一个能够同时对两方面扩展提供支持的大图分析系统就变得很有必要。就计算模式而言,图分析系统及其上层的图分析服务分别对应于迭代式图计算和聚合式图计算。迭代式图计算是这样一种计算模式,其通常基于图的拓扑结构,并且通过对于形式恒定的算法步骤的重复,从而迭代地生成最终的计算结果,或达到某个给定的计算边界。聚合式图计算对大规模图数据集产生小而易于理解的摘要,并且对应用场景下所指定的数据特征进行集中表示。迭代式图计算与聚合式图计算都面临着大数据规模和高密度算力需求所带来的挑战,但是现有的大图分析系统还不能对聚合式图计算提供很好的性能支持。因此,我们希望给出一种图分析系统的框架设计,能够同时向迭代式图计算与聚合式图计算提供集群上的横向规模扩展与在算力上的纵向规模扩展支持。鉴于以上需求,本文设计了一个支持集群的横向与算力的纵向扩展的图分析系统的高性能图分析中间件,可以接入分布式图分析系统和高性能计算硬件,也可以支持迭代和聚合式图计算,并在此基础上进行了一系列优化。我们的主要研究内容可以分为如下三部分进行阐述:1、通用的图计算框架设计。该部分的主要目标是构建一个能够同时支持在集群规模上的横向扩展与算力规模上的纵向扩展的中间件框架,主要可以分为如下几个部分:Daemon-Agent部分的设计在核心层面上保证了中间件在横向与纵向两个层面的扩展能力;基于共享内存的数据传输流程与可灵活实现与接入的API从数据与程序层面提供了对于图算法高效处理与多样性的支持。中间件还针对不同的部署环境提供了一系列的针对性优化措施,以保证在其上的部署能够被高效执行。2、面向迭代式图计算的中间件优化。该部分的主要目标是逐层剖析该系统的执行流程,找到导致潜在的性能低下的问题,并加以优化。这些优化从三个层次被组织起来:在每个计算迭代内,为了解决数据流转流程过多而导致的计算硬件利用率低下的问题,我们设计了流水线重组机制,其目的是在保证数据交换高效的同时,提升计算硬件的利用率和系统的整体性能;在计算迭代之间,为了解决由冗余的数据同步流程而导致的额外开销的增加,我们设计了同步缓存机制与同步跳过机制,因地制宜地减少乃至消除数据同步对系统所造成的性能影响;在计算流程之外的整体框架下,为了保证系统能够实现负载均衡,我们设计了一套代价模型来评估系统的开销,并在此基础之上提出了两种不同模式下的系统负载均衡方案,来帮助系统整体达到更优的性能。3、提供对于聚合式图计算相关应用的支持。为了能系统能够胜任更为复杂的实际应用场景,我们向中间件框架中引入聚合式图计算的计算模型以及性能优化手段。这些优化从三个层次被组织起来:在线程级别,我们通过定制的BSP模型实现了聚合无锁化,从而消除了锁带来的额外开销。在此基础之上,我们还提出了聚合紧凑化机制来保证性能更优的聚合计划能够被生成并执行;在线程块级别,我们通过实现数据分布感知的流式图分区来实现了对于分区之间聚合用数据的均匀分配;在系统整体级别,我们还建立了代价模型来对系统性能进行评估,并对线程块大小的配置进行指导来帮助系统达到更好的执行性能。综上所述,在本文中,我们提出了中间件GX-Plug。通过该中间件,人们能够构建定制化的图分析系统,同时为迭代式与聚合式图计算提供在集群规模上与在算力上进行灵活扩展的支持。在此基础之上,我们提出了针对图分析系统的多个性能优化手段,为系统在横向与纵向扩展上的高效性能提供了保障。