一种基于子图构建的磁盘图处理方法及系统

摘要

本发明公开了一种基于子图构建的磁盘图处理方法及系统，包括：将图数据组织为双向边块结构；开始迭代图计算；加载图数据到内存中；通过高效的子图构建方法构建以顶点为中心的内存子图；对子图进行更新；将更新的图数据写回磁盘；判断是否达到收敛条件；结束迭代图计算。本发明提出的基于子图构建的磁盘图处理方法通过将子图构建过程中需要访问的顶点和边连续地组织在一起，确保在子图构建过程中内存访问局部性得到充分利用，很好地解决了现在磁盘图处理系统中的高子图构建开销问题，显著的提升了系统的整体性能。

说明书

技术领域

本发明属于计算机大数据处理技术领域，更具体地，涉及一种基于子图构建的磁盘图处理方法及系统。

背景技术

在当前大数据背景下，呈现出越来越多的对大规模图数据进行分析、处理及挖掘的应用需求。近年来，基于磁盘的图处理系统由于其成本低、可扩展性强等特点得到了广泛的关注，例如卡内基梅隆大学的GraphChi、洛桑联邦理工学院的X-Stream、清华大学的GridGraph等。这些磁盘图处理将图数据分为若干个子图，并且每次从磁盘中加载和处理一个子图。另外，这些系统大多采用以顶点为中心的计算模型，在处理每个子图之前，需要在内存中构建以顶点为中心的子图数据结构。这个子图构建过程要求系统为子图中的每个顶点添加入射边和出射边。然而，由于边的源顶点或目的顶点不连续的存储在内存中，构建子图的过程通常会带来很大的开销。例如，GraphChi在执行PageRank图算法时，其子图构建时间占到整个运行时间的60％，导致高子图构建开销的主要原因是子图构建过程导致了大量的内存随机读写。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种基于子图构建的磁盘图处理方法及系统，由此解决现有磁盘图处理系统中的高子图构建开销较大的技术问题。

为实现上述目的，按照本发明的一个方面，提供了一种基于子图构建的磁盘图处理方法，包括：

将输入图的顶点划分为P个不相交的顶点区间，对于每个顶点区间，分别创建一个入射边块结构和一个出射边块结构，以利用所述入射边块结构存储对应顶点区间中顶点的入射边，利用所述出射边块结构存储对应顶点区间中顶点的出射边，然后对所述输入图中的边进行遍历，根据每条边的源顶点和目的顶点，将边写入相应的入射边块和出射边块，其中，P的取值需要确保每一个入射块或出射块的大小小于内存的容量；

设定各顶点的初始化值并选定活跃顶点后，按照划分的顶点区间，加载当前顶点区间的顶点及当前顶点区间的入射边块和出射边块到内存中得到目标图数据；

将所述目标图数据中的每条入射边写入该入射边目的顶点的入射边队列，将每条出射边写入该出射边源顶点的出射边队列，构建以顶点为中心的内存子图；

所述内存子图中的每个顶点并发地从各自的入射边读取数据，并根据读取的数据对顶点值进行更新，然后将被更新的顶点写回磁盘。

优选地，在所述入射边块结构中的边按边的目的顶点进行排序，在所述出射边块结构中的边按边的源顶点进行排序。

优选地，所述活跃顶点为顶点值在上一轮迭代中被更新的顶点。

优选地，所述将所述目标图数据中的每条入射边写入该入射边目的顶点的入射边队列，将每条出射边写入该出射边源顶点的出射边队列，构建以顶点为中心的内存子图，包括：

对于所述目标图数据中的每条入射边，首先访问该入射边的目的顶点的内存地址，然后将该入射边添加到其目的顶点的入射边队列；

对于所述目标图数据中的每条出射边，首先访问该出射边的源顶点的内存地址，然后将该出射边添加到其源顶点的出射边队列。

优选地，所述将被更新的顶点写回内存之后，所述方法还包括：

判断是否达到预设收敛条件，若没有达到所述预设收敛条件，则执行所述加载当前顶点区间的顶点及当前顶点区间的入射边块和出射边块到内存中得到目标图数据，若达到所述预设收敛条件，则结束迭代图计算。

按照本发明的另一方面，提供了一种基于子图构建的磁盘图处理系统，包括：

双向边块结构构建模块，用于将输入图的顶点划分为P个不相交的顶点区间，对于每个顶点区间，分别创建一个入射边块结构和一个出射边块结构，以利用所述入射边块结构存储对应顶点区间中顶点的入射边，利用所述出射边块结构存储对应顶点区间中顶点的出射边，然后对所述输入图中的边进行遍历，根据每条边的源顶点和目的顶点，将边写入相应的入射边块和出射边块，其中，P的取值需要确保每一个入射块或出射块的大小小于内存的容量；

加载模块，用于设定各顶点的初始化值并选定活跃顶点后，按照划分的顶点区间，加载当前顶点区间的顶点及当前顶点区间的入射边块和出射边块到内存中得到目标图数据；

内存子图构建模块，用于将所述目标图数据中的每条入射边写入该入射边目的顶点的入射边队列，将每条出射边写入该出射边源顶点的出射边队列，构建以顶点为中心的内存子图；

子图更新模块，用于将所述内存子图中的每个顶点并发地从各自的入射边读取数据，并根据读取的数据对顶点值进行更新，然后将被更新的顶点写回磁盘。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：

本发明提出的基于子图构建的磁盘图处理方法及系统通过将子图构建过程中需要访问的顶点和边连续地组织在一起，确保在子图构建过程中内存访问局部性得到充分利用，很好地解决了现在磁盘图处理系统中的高子图构建开销问题，显著的提升了系统的整体性能。

附图说明

图1为本发明实施例提供的一种基于子图构建的磁盘图处理方法的流程示意图；

图2为本发明实施例提供的一种系统处理某个区间子图的整体过程示意图；

图3(a)为本发明实施例提供的一种有向图G的示意图；

图3(b)为本发明实施例提供的一种将有向图G组织为双重子块结构的示意图；

图4为本发明实施例提供的一种将有向图G中顶点区间1的顶点和边构建成内存子图的示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

本发明提供了一种基于子图构建的磁盘图处理方法及系统，其目的在于降低现有磁盘图处理系统中的高子图构建开销。

本发明实施例提供的基于子图构建的磁盘图处理方法，其流程如图1所示，包括以下步骤：

(1)将图数据组织为双向边块结构：首先将输入图的顶点划分为P个不相交的区间。对于每个顶点区间，分别创建一个入射边块和一个出射边块结构，分别存储此区间顶点的入射边和出射边；对输入图中的边进行遍历，根据每条边的源顶点和目的顶点，将其写入相应的入射边块和出射边块。

其中，P的取值需要确保每一个入射块或出射块的大小小于内存的容量。

(2)开始迭代图计算：根据图算法的要求和用户的设定，设定顶点的初始化值并选定活跃顶点，开始进行迭代处理；

在本发明实施例中，活跃顶点为顶点值在上一轮迭代中被更新的顶点。

(3)加载图数据到内存中：按照步骤(1)划分的顶点区间，加载当前区间的顶点及相应的入射边块和出射边块到内存中；

在本发明实施例中，在步骤(3)的加载过程使用图数据的流式读取保证了对磁盘的顺序访问，从而保证了对外存IO的最大利用。

(4)通过子图构建方法构建以顶点为中心的内存子图：根据步骤(3)加载的图数据，将每条入射边写入其目的顶点的入射边队列，将每条出射边写入其源顶点的出射边队列，构建成一个以顶点为中心的内存子图；

在本发明实施例中，在步骤(4)的子图构建方法中依次访问每条入射边的目的顶点和每条出射边的源顶点，由于所有的入射边是按照目的顶点进行排序，所有的出射边是按照源顶点进行排序，这种构建方法能够充分内存访问的局部性，极大的降低构建子图的开销。

(5)对子图进行更新：基于步骤(4)构建成的内存子图，采用以顶点为中心的方式进行更新。在这种更新方式下，每个顶点并发地从自己的入射边读取数据，根据读取的数据对顶点值进行更新。

在本发明实施例中，步骤(5)对内存子图进行更新时使用顶点数据和边数据分离的方法，在这种情况下，只有顶点值会被更新，而边数据则反映图的拓扑结构，不会被更新，这种方法很大程度的减少了磁盘读写的数据量，提升了系统的整体性能。

(6)将更新的图数据写回磁盘：将被更新的顶点写回磁盘，确保整体计算结果的一致性；

(7)判断是否达到收敛条件，如果达到，执行步骤(8)，否则进入下一次迭代，执行步骤(3)。其中，收敛条件由用户预设。

(8)结束迭代图计算，输出计算结果。

图2为系统处理某个区间子图的整体过程示意图。系统首先将某一顶点区间的顶点数据和边数据(以双向边块结构Dual-Chunks存储)加载到内存中。随后通过子图构建将这些数据构建成以顶点为中心的内存子图。当内存构建完成后，系统根据以顶点为中心的更新方式对子图进行更新。最后，系统将更新后的图数据写回磁盘。

图3为将有向图G组织为双向边块结构的示意图。在图3(a)的有向图G中包含6个顶点，被分成两个等大小的区间(1，3)和(4，6)。每个区间顶点的入射边和出射边分别存储在相应的入射边块(in-chunk)和出射边块(out-chunk)中。如图3(b)所示，顶点区间1的入射边和出射边分别存储在in-chunk(1)和out-chunk(1)中，顶点区间2的入射边和出射边分别存储在in-chunk(2)和out-chunk(2)中。入射边块中的边按照边的目的顶点进行排序，出射边块中的边按照边的源顶点进行排序。这样确保了子图构建中需要访问的顶点顺序地存储在内存中。例如，in-chunk(1)中的边存储顺序为(3,1)，(1,2)，(5,2)，(2,3)，(4,3)，(5,3)。Out-chunk(2)中的边存储顺序为(4,3)，(4,6)，(5,2)，(5,3)，(5,4)，(6,5)。

图4为将有向图G中顶点区间1的顶点和边构建成内存子图的示意图。系统并发地访问加载到内存中的入射边和出射边。对于每条入射边，首先访问其目的顶点的内存地址，然后将这条边添加到其目的顶点的入射边队列。对于每条出射边，首先访问其源顶点的内存地址，然后将这条边添加到其源顶点的出射边队列。如图4所示，依次访问顶点1,2,3的内存地址，并添加相应的入射边和出射边。由于所有的入射边按目的顶点进行排序，所有的出射边按源顶点进行排序，在添加顶点的入射边和出射边时对顶点的访问顺序是完全连续的。因此，内存访问的局部性得以充分利用，内存随机读写的次数极大的减少，构建子图的开销极大的降低。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。