作者：京东科技 李永萍
图计算框架
图计算系统按照计算方式划分可分为：单机内存图处理系统，单机核外图处理系统，分布式内存图处理系统，分布式核外图处理系统。本文将详细介绍单机核外图处理系统GridGraph。
GridGraph论文分析
单机核外图处理系统
GridGraph
GridGraph是一种单机核外图处理系统，在大规模图处理系统中充分利用磁盘读写，在有限内存中高效完成大规模图计算。
主要贡献
GridGraph的主要贡献有：
2、2-level hierarchical partitioning 使用两层分区划分模式，该模式不仅适用于核外，在内存中同样有效。
4、提供灵活的点边流式接口函数，通过用户自定义过滤函数来跳过非活跃顶点（活跃顶点：bitmap中该顶点index的状态为1）或非活跃边的计算。对于活跃顶点集随着收敛而缩小的迭代算法，这种方法显著提高了算法的性能。
Grid Representation网格划分
1、顶点集划分成P个均匀的chunk。
The Grid Format 网格格式
1、主线程从原始的无序边集中读取边，读取到一批边后，将这批边数据加入队列中。（根据磁盘带宽，一般选择24M做为这批边的大小）
分区过程结束后，GridGraph就可以进行计算了。然而，由于现实世界图的不规则结构，一些边block可能太小，无法在HDD上实现大量的连续带宽。因此，可能由于频繁的磁盘寻道，有时无法实现顺序带宽。为了避免这种性能损失，GridGraph需要一个额外的合并阶段，以便在基于HDD的系统上更好地执行，该阶段将边block文件逐个追加到一个大文件中，并在元数据中记录每个块的起始偏移量。
而对于X-Stream来说，X-Stream不需要显式的预处理。根据流分区，边被打乱到几个文件。不需要排序，分区的数量非常少。对于许多顶点数据都能装进内存的图，只需要一个流分区。然而，这种划分策略使得它在选择调度中效率低下，这在很大程度上影响了它在许多迭代算法中的性能，因为在某些迭代中只使用了一部分顶点。（GraphChi和X-Stream都是单机核外图计算系统，在此不赘述。）
GridGraph完成预处理的时间非常短。此外，生成的网格格式可用于运行在同一图上的所有算法。通过分区，GridGraph能够进行选择性调度，减少对没有活跃边的边块的不必要访问。这在许多迭代算法(如BFS和WCC中贡献很大，因为其中大部分顶点在许多迭代中都是不活动的。
粒度越细(即P值越大，预处理时间越长，P越大，每一个chunk能表示的范围越广，那么每个block能存储的边数据越多，顶点数据的访问局部性越好，block置换概率越低，选择性调度潜力就越大。因此，在划分时，P越大越好。目前，我们暂时选择P的最大值，这样顶点数据可以适应最后一级缓存。那么P的最小值可以这样设定：
其中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总量。
Fe和Fv是用户自定义的描述流处理的函数，Fe接受一个边做为输入，Fv接受一个顶点做为输入，返回一个R类型的值，返回值被累加，并作为最终结果提供给用户。该值通常用于获取活跃顶点的数量，但不限于此用法，例如，用户可以使用这个函数来获得PageRank中迭代之间的差异之和，以决定是否停止计算。
以PageRank为例，我们来看看GridGraph是如何实现算法的。
Dual Sliding windows 双滑动窗口模式
通过P的设定，使得block足够小，能够将一个block放入最后一级缓存中，这样在访问与block相关的顶点数据时，可以确保良好的局部性。
1、初始化，每个顶点初始的PR值都为1
读窗口：读取src.chunk 1的PR和Deg
IO总量：读取block中2条边，读取src.chunk 1中的顶点（1，2），读取dest.chunk 1中的顶点（1，2）
读窗口：读取src.chunk 2的PR和Deg
IO总量：读取block中2条边，读取src.chunk 2中的顶点（3，4）
读窗口：读取src.chunk 1的PR和Deg
IO总量：读取block中2条边，将dest.chunk 1中的顶点（1，2）的结果写入磁盘，读取src.chunk 1中的顶点（1，2），读取dest.chunk 2中的顶点（3，4）
读窗口：读取src.chunk 2的PR和Deg
IO总量：读取block中1条边，读取src.chunk 2中的顶点（3，4）
IO总量：将dest.chunk 2中的顶点（3，4）的结果写入磁盘中。
E+(2+P*V
2：读取和写入目标顶点的数据
通过对边的只读访问，GridGraph所需的内存非常紧凑。事实上，它只需要一个小的缓冲区来保存正在Stream的边blocl，以便页缓存可以使用其他空闲内存来保存更多的边block，当活跃边block变得足够小以适合内存时，这是非常有用的。这种Streaming-Apply-Processing-Model流式应用模型的另一个优点是它不仅支持经典的BSP模型，而且还允许异步更新。由于顶点更新是即时的，更新的效果可以通过跟踪顶点的遍历来获得，这使得许多迭代算法收敛得更快。由此可看出：P应该是使顶点数据放入内存的最小值。因此，更小的P应该是最小化I/O量的首选，这似乎与上面我们所说P越大越好，更大的网格分区原则相反。
Selective scheduling 选择调度
P越大，粒度越细，更好的局部性，选择调度更好，访问顶点的次数更多
2-level hierarchical partitioning
在P*P的网格中再进行一层网格划分，第二层网格有Q*Q个边网格。将Q*Q的分区应用在P*P的网格中。
(V/Q*U <= M
在前面我们提到，P的选择是为了将顶点数据放入容量远小于内存的上一级缓存中，因此P应该远大于Q。
总结
GridGraph定义了一种新的图表示形式：网格划分，用于适应有限的内存；使用双窗口模式减少IO访问的总量，特别是写IO；使用选择调度减少掉无用的IO；使用2级分区划分方式保证了P尽可能大的同时减少IO访问。GridGraph在有限的内存中，并提高IO效率，高效的完成了核外图计算过程。
GridGraph源码分析
数据预处理模块
将原始二进制文件处理成grid格式的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]文件中。如下图所示：
1、打开文件读取数据，将数据加入task处理，在这里，buffers的定义是全局的，tasks保存cursor和buffers数据大小。
Graph实现
代码位于：core/graph.hpp
init
stream_vertices:
顶点大小）大于0.8内存字节数，先获取partitions的begin_vid和end_vid，再遍历每一个partition，每个partition中的每个vertex按照process执行，将返回值求和相加。最后等待所有partition执行结束，得到begin_vid和end_vid。
stream_edges:
PageRank算法实现
代码位于：example/pagerank.cpp
总结
1）、在读取输入文件时，可以根据文件个数并行读取文件，加快文件处理速度。
3）、thread线程中，因为每个线程处理的是不同的cursor的buffers数据，每个thread生成自己的local_buffer写入block文件，因为threads中没有数据交互，因此也可以并行化。
1、可将Z型边遍历可更改一下，改成U形遍历，以列主序为例，当遍历到最后一行的src时，src不变保持在内存中，此时dst向右移，src从下往上遍历，以此类推，可节省P次的页面置换。
GridGraph将顶点划分为P个顶点数量相等的chunk，将边放置在以P*P的网格中的每一个block中，边源顶点所在的chunk决定其在网格中的行，边目的顶点所在的chunk决定其在网格中的列。它对Cache/RAM/Disk进行了两层级的网格划分，采用了Stream vertices and edges的图编程模型。计算过程中的双滑动窗口（Dual Sliding Windows）也大大减少了I/O开销，特别是写开销。以block为单位进行选择调度，使用原子操作保证线程安全的方式更新顶点。论文中提到在边网格上采用压缩技术，以进一步降低所需的I/O带宽，提高效率。
参考文献：
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
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