作者：京东科技 李永萍
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