作者：京东科技 李永萍
GridGraph：Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning
图计算框架
图计算零碎依照计算形式划分可分为：单机内存图解决零碎，单机核外图解决零碎，分布式内存图解决零碎，分布式核外图解决零碎。本文将具体介绍单机核外图解决零碎 GridGraph。
GridGraph 论文剖析
单机核外图解决零碎
单机内存图解决零碎受限于内存空间和单机算力，可能解决的图规模无限。分布式内存图解决零碎实践上能够随着集群规模的增大进而解决更大的图规模，但集群间的网络带宽问题，负载不平衡，同步开销大，容错开销和图宰割挑战也愈变显著。无论是单机还是分布式，内存式图解决零碎可能解决的图规模都是无限的。因而想要应用更少的资源解决更大的图规模，能够应用单机核外图解决零碎。单机核外图解决零碎应用磁盘程序读写进行数据置换，可能在无限的内存中计算更大规模的图。单机核外图解决零碎在最大化利用磁盘程序读写，在抉择调度和同异步计算模式等方面做出了重要摸索。
GridGraph
GridGraph 是一种单机核外图解决零碎，在大规模图解决零碎中充分利用磁盘读写，在无限内存中高效实现大规模图计算。
GridGraph 充分利用磁盘大容量，解决单机内存无限时实现大规模图计算问题。GridGraph 采纳 Streaming-Apply 形式缩小计算中的 IO 申请数量，通过文件调入程序缩小不必要的 io 开销。同时 GridGraph 也利用程序读和程序写的特点，尽可能的较少硬盘的写操作。
次要奉献
GridGraph 的次要奉献有：
1、基于边列表疾速生成一种新的图示意模式 – 网格划分。网格划分是一种不同于邻接矩阵和邻接链表的示意模式，网格划分不须要将 index 排序，网格的边 block 能够由未排序的边列表转换而来，数据前置预处理开销小，可利用于不同的算法和不同的机器。
2、2-level hierarchical partitioning 应用两层分区划分模式，该模式不仅实用于核外，在内存中同样无效。
3、提出 streaming-apply 模式，以进步 IO。通过双滑动窗口（Dual sliding windows）保障顶点拜访的局部性。
4、提供灵便的点边流式接口函数，通过用户自定义过滤函数来跳过非沉闷顶点（沉闷顶点：bitmap 中该顶点 index 的状态为 1）或非沉闷边的计算。对于沉闷顶点集随着收敛而放大的迭代算法，这种办法显著进步了算法的性能。
Grid Representation 网格划分
为了在无限的内存中实现大规模图计算，并严格控制内存耗费，须要将图进行网格划分。
1、顶点集划分成 P 个平均的 chunk。
2、边集划分在 P * P 个 block 中，行示意源顶点，列示意目标顶点。
The Grid Format 网格格局
GridGraph partition 预处理形式如下：
1、主线程从原始的无序边集中读取边，读取到一批边后，将这批边数据退出队列中。（依据磁盘带宽，个别抉择 24M 做为这批边的大小）
2、每个工作线程从队列中获取工作，计算边所属的 block，将边退出到边 block 文件中。为了进步 I / O 吞吐量，每个工作线程保护每个 block 的本地缓冲区，一旦缓冲区满就刷新到文件。
分区过程完结后，GridGraph 就能够进行计算了。然而，因为事实世界图的不规则构造，一些边 block 可能太小，无奈在 HDD 上实现大量的间断带宽。因而，可能因为频繁的磁盘寻道，有时无奈实现程序带宽。为了防止这种性能损失，GridGraph 须要一个额定的合并阶段，以便在基于 HDD 的零碎上更好地执行，该阶段将边 block 文件一一追加到一个大文件中，并在元数据中记录每个块的起始偏移量。
不同于 GraphChi 的 shard 分片模式，GridGraph 不须要对边 block 排序，缩小了 IO 和计算开销，咱们只须要在磁盘上读写一次边，而不是在 GraphChi 中屡次遍历边。
而对于 X -Stream 来说，X-Stream 不须要显式的预处理。依据流分区，边被打乱到几个文件。不须要排序，分区的数量非常少。对于许多顶点数据都能装进内存的图，只须要一个流分区。然而，这种划分策略使得它在抉择调度中效率低下，这在很大水平上影响了它在许多迭代算法中的性能，因为在某些迭代中只应用了一部分顶点。（GraphChi 和 X -Stream 都是单机核外图计算零碎，在此不赘述。）
何为抉择调度？抉择调度是将图数据文件（个别是边文件）划分为多个 block 并按程序编号，设置一个 bitmap 记录所有 block 的拜访状态，若是须要拜访则将 bitmap 中 index 为 block 编号的状态置为 1，在调度时跳过状态为 0 的 block，抉择状态为 1 的 block 从磁盘置入内存中进行计算。若是 bitmap 为空，则默认所有 block 都须要参加计算，则将 block 按序从磁盘置入内存。block 的大小决定了抉择调度的差别，block 越大，蕴含的数据越多，block 置换的概率越低，抉择调度越好。反之，block 越小，蕴含的数据越少，计算时须要置换 block 的概率越高，抉择调度越差。
GridGraph 实现预处理的工夫十分短。此外，生成的网格格局可用于运行在同一图上的所有算法。通过分区，GridGraph 可能进行选择性调度，缩小对没有沉闷边的边块的不必要拜访。这在许多迭代算法 (如 BFS 和 WCC) 中奉献很大，因为其中大部分顶点在许多迭代中都是不流动的。
内存（In-memory）图计算零碎将全都数据读取到 Memory 内存中，应用到零碎中的 Cache（缓存）和 Memory（内存）来实现图计算过程，核外（Out-of-core）图计算零碎则将数据存储到 Disk 磁盘中，计算时再将所需数据置换到 Memory（内存）中，为了缓解 CPU 和 Memory 之间的速度差别，通常会将数据存储至 Cache 缓存中。磁盘存储空间 > 内存存储空间 > 缓存存储空间。
那么如何抉择 Partition 呢？
粒度越细(即 P 值越大)，预处理工夫越长，P 越大，每一个 chunk 能示意的范畴越广，那么每个 block 能存储的边数据越多，顶点数据的拜访局部性越好，block 置换概率越低，选择性调度后劲就越大。因而，在划分时，P 越大越好。目前，咱们临时抉择 P 的最大值，这样顶点数据能够适应最初一级缓存。那么 P 的最小值能够这样设定：
(V/P)*U<=C<=>P>=C/UV
其中 V 是图的顶点数，C 是最初一级 cache 缓存的大小，U 是每个顶点的大小。(V/P)示意 chunk 中可示意的顶点范畴，(V/P)* U 则示意每个 chunk 的大小，为了适应最初一级缓存，可能一次将一个 chunk 的所有数据放入最初一级缓存中，则 chunk 的大小应小于等于 C，公式进行变换失去 P 的最小值为 C /UV.
这种分区形式不仅体现出良好的性能(特地是在内存状况下)，而且节俭了很多的预处理老本。
The Streaming-Apply Processing Model
GridGraph 应用流利用解决模型，在该模型中只须要读取边一次，并且只需遍历一次顶点即可实现写 I / O 总量。
GridGraph 提供了两个流式处理函数别离解决顶点（Algorithm1）和边（Algorithm2）：
F 是一个可选的用户自定义函数，它承受顶点作为输出（StreamVertices 时是以后顶点，StreamEdges 时是 block 中每一条边的源顶点），并且返回一个布尔值来批示流中是否须要该顶点。当算法须要选择性调度用于跳过一些无用的流时通常与位图一起应用，位图能够紧凑地示意流动顶点集。
Fe 和 Fv 是用户自定义的形容流解决的函数，Fe 承受一个边做为输出，Fv 承受一个顶点做为输出，返回一个 R 类型的值，返回值被累加，并作为最终后果提供给用户。该值通常用于获取沉闷顶点的数量，但不限于此用法，例如，用户能够应用这个函数来取得 PageRank 中迭代之间的差别之和，以决定是否进行计算。
GridGraph 将顶点数据存储在磁盘上。应用内存映射机制（将顶点数据文件通过 mmap 内存映射机制映射到内存中）来援用文件中的顶点数据，每个顶点数据文件对应一个顶点数据数组。因而拜访顶点数据文件就像拜访内存中的数组一样，并简化了编程模型：开发人员能够将其视为一般数组，就像它们在内存中一样。
以 PageRank 为例，咱们来看看 GridGraph 是如何实现算法的。
PageRank 是一种链接剖析算法（Algorithm3），计算图中每个顶点的数值权重，以测量其在顶点之间的绝对重要性。初始所有顶点的 PR 值都是 1，在每次迭代中，每个顶点向街坊发送本人的奉献，即以后 PR 值除以它的出度。每个顶点将从街坊收集到的奉献进行汇总，并将其设置为新的 PR 值。当均值差达到某个阈值时，算法收敛。
Dual Sliding windows 双滑动窗口模式
GridGraph 流式读取每个 block 的边，当 block 在第 i 行第 j 列时，和这个 block 相干的顶点数据也落在第 i 行第 j 列的 chunk 中，每个 block 都蕴含两个顶点 chunk，source chunk（源顶点 chunk）和 destination chunk（目标顶点 chunk）。
通过 P 的设定，使得 block 足够小，可能将一个 block 放入最初一级缓存中，这样在拜访与 block 相干的顶点数据时，能够确保良好的局部性。
依据更新模式，block 的拜访程序能够是面向行或面向列的。假如顶点状态从源顶点流传到指标顶点(这是许多应用程序中的典型模式)，即源顶点数据被读取，指标顶点数据被写入。因为每个边 block 的列对应于指标顶点块，须要对指标顶点块进行写操作，在这种状况下优先采纳面向列的拜访程序。当目标顶点所在 block 被缓存在内存中时，GridGraph 从上到下流向同一列中的 block，因而低廉的磁盘写操作被聚合和最小化。特地是对于 SSD 零碎来说，这是一个十分重要的性能，写入大量数据写性能会相应降落。另一方面，因为 SSD 有写入周期的下限，因而尽可能减少磁盘随机写入以实现理想的持久性是很重要的。
以 PageRank 为例，咱们来看看 GridGraph 是如何应用双滑动窗口对顶点信息进行更新。读窗口 (从源顶点数据中读取以后顶点的 PageRank 值和出度) 和写窗口 (对指标顶点的新 PageRank 值的奉献进行累加) 作为 GridGraph 流沿 block 以面向列的程序滑动。
1、初始化，每个顶点初始的 PR 值都为 1
2、Stream edge block(1,1)，此时 src.chunk 1 和 dest.chunk 1 都加载进内存中
读窗口：读取 src.chunk 1 的 PR 和 Deg
写窗口：写 dest.chunk 1 的 NewPR
IO 总量：读取 block 中 2 条边，读取 src.chunk 1 中的顶点（1，2），读取 dest.chunk 1 中的顶点（1，2）
3、Stream edge block (2,1)，此时 dest.chunk 1 在内存中，将 src.chunk 2 也加载进内存中
读窗口：读取 src.chunk 2 的 PR 和 Deg
写窗口：写 dest.chunk 1 的 NewPR
IO 总量：读取 block 中 2 条边，读取 src.chunk 2 中的顶点（3，4）
4、Stream edge block (1,2)，dest.chunk 1 曾经全副更新实现，将更新后的 dest.chunk1 写回磁盘种，将 src.chunk 1 和 dest.chunk 2 加载进内存中
读窗口：读取 src.chunk 1 的 PR 和 Deg
写窗口：写 dest.chunk 2 的 NewPR
IO 总量：读取 block 中 2 条边，将 dest.chunk 1 中的顶点（1，2）的后果写入磁盘，读取 src.chunk 1 中的顶点（1，2），读取 dest.chunk 2 中的顶点（3，4）
5、Stream edge block (2,2)，此时 dest.chunk 2 在内存中，将 src.chunk 2 也加载进内存中
读窗口：读取 src.chunk 2 的 PR 和 Deg
写窗口：写 dest.chunk 2 的 NewPR
IO 总量：读取 block 中 1 条边，读取 src.chunk 2 中的顶点（3，4）
6、实现 dest 所有 chunk 的遍历，将 dest.chunk 2 更新后的后果写入磁盘中。
IO 总量：将 dest.chunk 2 中的顶点（3，4）的后果写入磁盘中。
在下面的一次流利用迭代中给出了网格图的 I / O 剖析，其中所有的边和顶点都被拜访。以面向列的程序拜访边 block 为例：所有边被拜访一次，源顶点数据被读取 P 次，而指标顶点数据被读写一次。在一次残缺迭代并收敛中应用的 IO：
E+(2+P)*V
E：示意读取所有边
2：读取和写入指标顶点的数据
P：读取每个 P 中源顶点数据
通过对边的只读拜访，GridGraph 所需的内存十分紧凑。事实上，它只须要一个小的缓冲区来保留正在 Stream 的边 blocl，以便页缓存能够应用其余闲暇内存来保留更多的边 block，当沉闷边 block 变得足够小以适宜内存时，这是十分有用的。这种 Streaming-Apply-Processing-Model 流式利用模型的另一个长处是它不仅反对经典的 BSP 模型，而且还容许异步更新。因为顶点更新是即时的，更新的成果能够通过跟踪顶点的遍从来取得，这使得许多迭代算法收敛得更快。由此可看出：P 应该是使顶点数据放入内存的最小值。因而，更小的 P 应该是最小化 I / O 量的首选，这仿佛与下面咱们所说 P 越大越好，更大的网格分区准则相同。
Selective scheduling 抉择调度
后面咱们曾经解释过什么是抉择调度，即跳过不沉闷的边 block。在 Stream 函数中的由 F 传入位图，由此跳过不沉闷的边 block。
P 越小，粒度越粗，拜访顶点的次数更少，更差的局部性，抉择调度更差
P 越大，粒度越细，更好的局部性，抉择调度更好，拜访顶点的次数更多
为了解决这个难题，在边网格上利用了二级分区，以缩小顶点的 I / O 拜访。
2-level hierarchical partitioning
在 P * P 的网格中再进行一层网格划分，第二层网格有 Q * Q 个边网格。将 Q * Q 的分区利用在 P * P 的网格中。
Q 的抉择应满足：
(V/Q)*U <= M
M 是给定的内存容量。
在后面咱们提到，P 的抉择是为了将顶点数据放入容量远小于内存的上一级缓存中，因而 P 应该远大于 Q。
整个网格被分成 4 个大块，每个大块蕴含 4 个小块。每个块内的数字示意拜访程序。在原始的 4×4 分区中应用了准确的面向列的拜访程序。在利用了二级分区后，P：2×2 变成 Q：4×4 分区之后，咱们以面向列的程序拜访粗粒度 (大) 块，在每个大块中，咱们拜访细粒度的块 (小) 块以列为导向的程序。这种 2 级分层分区不仅提供了灵活性，而且还进步了效率，因为高级分区（第二级分区）是虚构分区，GridGraph 可能利用较低级别分区（第一级分区）的后果，因而不会减少更多的理论开销。并且能够应用 P 网格划分的后果进行抉择调度。
总结
GridGraph 定义了一种新的图示意模式：网格划分，用于适应无限的内存；应用双窗口模式缩小 IO 拜访的总量，特地是写 IO；应用抉择调度缩小掉无用的 IO；应用 2 级分区划分形式保障了 P 尽可能大的同时缩小 IO 拜访。GridGraph 在无限的内存中，并进步 IO 效率，高效的实现了核外图计算过程。
GridGraph 源码剖析
源码地址：https://github.com/thu-pacman/GridGraph
数据预处理模块
将原始二进制文件解决成 grid 格局的 block 文件
咱们来看看 block 文件是如何划分解决的：
从 input 文件中遍历读取 IOSIZE 的数据放入 buffers[cursor]中，tasks 记录以后以后游标的字节数 <cursor, bytes>，在 threads 中获取 tasks 中的 cursor 和 bytes，依据 cursor 读取 buffers 中的数据，将 buffers[cursor]中的数据依据 src 和 dst 所属的 partition，放入 local\_buffer[i][j]中，将 local\_buffer[i][j]的数据别离写入 block[i][j]文件中。如下图所示：
代码位于：tools/preprocess.cpp
1、关上文件读取数据，将数据退出 task 解决，在这里，buffers 的定义是全局的，tasks 保留 cursor 和 buffers 数据大小。
2、那么咱们来看看 tasks 是什么，tasks 是一个队列，保留以后游标和数据大小。grid\_buffer\_size = 12*8*8，12 示意 <4 byte source, 4 byte destination, 4 byte float typed weight>，8* 8 示意每次读取到 64byte 的数据时写一次磁盘，是个 magic number。
3、真正进行数据处理的是 threads 的工作。每个 thread 解决一个 buffers[cursor]的数据。
将 local_buffer 的数据写入对应的 block 文件中
4、生成 column 文件，将所有 block 文件依照列遍历形式保留到 column 文件中，并将每个 block 文件的大小保留至 column_offset 文件中。
5、同理生成 row 文件，依照行遍历形式读取 block 文件写入 row 文件中，并记录 offset。
6、最初将解决好的数据信息（是否含有权重，顶点数，边数，partition 数）写入 meta 文件中。
执行 grid 代码后，会生成 P * P 个 block 文件，一个 column 文件、row 文件、column\_offset、row\_offset 及 meta 文件。
Graph 实现
代码位于：core/graph.hpp
init
空间初始化，并读取 meta 信息和 column\_offset、row\_offset 的数据，并记录每个 block 文件大小
stream_vertices:
如果 bitmap 为空，并且顶点数据字节总数（顶点数据字节总数初始化为 0，可在算法实现时设置，个别为顶点总数_顶点大小）大于 0.8_内存字节数，先获取 partitions 的 begin\_vid 和 end\_vid，再遍历每一个 partition，每个 partition 中的每个 vertex 依照 process 执行，将返回值求和相加。最初期待所有 partition 执行完结，失去 begin\_vid 和 end\_vid。
如果 bitmap 不为空或者顶点数据字节总数小于等于 0.8* 内存字节数，则遍历每一个 partition，获取每个 partition 的 begin\_vid 和 end\_vid。如果 bitmap 为空，则遍历 partition 中的所有顶点，依照 process 执行，返回值相加。否则，从 begin_vid 开始，依照 bitmap 遍历，bitmap 为 1 的 vid 执行 process，返回值相加。
stream_edges:
依据 bitmap 决定须要遍历的 partition，如果 bitmap 为空，则所有 partition 都要遍历，bitmap 不为空依据 partition 中是否蕴含 bitmap 中的 vid，蕴含则该 partition 须要遍历。
统计所有须要遍历的 partition 的文件总大小
默认 update\_mode=1，若 update\_mode= 0 则为行更新模式（行主序更新），update_mode= 1 则为列更新模式（列主序）。数据筹备阶段：
遍历须要拜访的分区，分区拜访形式为：列不变，行从小到大进行遍历，行遍历完后列再向右移。每次读取分区中 IOSIZE 大小的数据，最初不够 IOSIZE 则读取 PAGESIZE 大小的数据
每条边依照 process 的办法执行操作
若是行主序，实现则如下：依照行遍历形式读取须要遍历的 partition，每次解决 IOSIZE 大小的数据
数据处理形式则是读取 row 文件，从 offset 开始读取 length 的数据放入 buffer 中，而后遍历每一条边，每条边依照 process 执行。
上面咱们来看看理论应用，以 PageRank 算法实现为例，这里不再详述 PageRank 算法原理。
PageRank 算法实现
代码位于：example/pagerank.cpp
先初始化每个顶点的 degree：在这里 update_mode=0，应用行主序更新。
初始化每个顶点的 pr 值为 1：
遍历每一条边更新计算每条边的奉献值：
更新每个顶点上的 pr 值，最初一轮迭代则间接计算并更新 sum：
总结
在 grid 文件解决中，有几个可优化的点：
1）、在读取输出文件时，能够依据文件个数并行读取文件，放慢文件处理速度。
2）、初始化 grid 空间，因为初始化时每个 block 互不影响，能够应用 omp 并行初始化提高效率。
3）、thread 线程中，因为每个线程解决的是不同的 cursor 的 buffers 数据，每个 thread 生成本人的 local_buffer 写入 block 文件，因为 threads 中没有数据交互，因而也能够并行化。
在 stream\_vertices 和 stream\_edges 咱们都进行了剖析，能够看出，不论是行主序还是列主序，都免不了折线式（Z 型）的边 block 遍历策略，其可优化的点如下：
1、可将 Z 型边遍历可更改一下，改成 U 形遍历，以列主序为例，当遍历到最初一行的 src 时，src 不变放弃在内存中，此时 dst 向右移，src 从下往上遍历，以此类推，可节俭 P 次的页面置换。
GridGraph 提供一种在无限内存中实现大规模图计算零碎。解决单机内存或分布式内存无奈解决的大规模图计算问题。提供一种旧式的切图形式，将顶点和边别离划分为 1D chunk 和 2D block 来示意大规模图的网格示意；应用一种新的 streaming-apply 模型，进步 IO，对顶点的局部性敌对的形式流化读取边 block；GridGraph 可能在不波及 I / O 拜访的状况下拜访内存中的顶点数据，并且跳过不须要遍历的边 block，进步算法执行效率。
GridGraph 将顶点划分为 P 个顶点数量相等的 chunk，将边搁置在以 P * P 的网格中的每一个 block 中，边源顶点所在的 chunk 决定其在网格中的行，边目标顶点所在的 chunk 决定其在网格中的列。它对 Cache/RAM/Disk 进行了两层级的网格划分，采纳了 Stream vertices and edges 的图编程模型。计算过程中的双滑动窗口（Dual Sliding Windows）也大大减少了 I / O 开销，特地是写开销。以 block 为单位进行抉择调度，应用原子操作保障线程平安的形式更新顶点。论文中提到在边网格上采纳压缩技术，以进一步升高所需的 I / O 带宽，提高效率。
参考文献：
1. Xiaowei Zhu, Wentao Han and Wenguang Chen. GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning. Proceedings of the 2015 USENIX Annual Technical Conference, pages 375-386.
2. ZHU Xiaowei — GridGraph: Large-‐Scale Graph Processing on a Single Machine. Using 2-‐Level Hierarchical Parffoning. Xiaowei ZHU, Wentao HAN, Wenguang CHEN.Presented at USENIX ATC ’15
3. Amitabha Roy, Ivo Mihailovic, Willy Zwaenepoel. X-Stream: Edge-centric Graph Processing using Streaming Partitions
4. Aapo Kyrola Carnegie Mellon University akyrola@cs.cmu.edu, Guy Blelloch Carnegie Mellon University guyb@cs.cmu.edu,Carlos Guestrin University of Washington guestrin@cs.washington.edu. GraphChi: Large-Scale Graph Computation on Just a PC