单机核外图计算系统之X-Stream（二）SOSP-2013

在

一

中介绍了单机图计算系统X-Stream的Abstract和Introduction部分，了解到它是“以边为中心”的scatter-gather图计算模型，本文将详细讲解X-Stream的Processing Model以及它相应的Stream划分方法。

The X-Stream Processing Model

The mutable state of the computation is stored in the vertices, more precisely in the data field of each vertex.图计算过程中的临时状态都存储于顶点上（属性），X-Stream的输入是无序的有向边，无向边中的每条边可用两条有向边表示。它提供两个主要的API表达图计算过程，分别是Edge-centric scatter和Edge-centric gather。

Edge-centric scatter takes as input an edge, and computes, based on the data field of its source vertex, whether an update value needs to be sent to its destination vertex, and, if so, the value of that update.“以边为中心”的Scatter将边作为输入，并根据其源顶点的数据字段计算，是否需要将更新值发送到其目标顶点，如果是，则更新该值。

Edge-centric gather takes as input an update, and uses its value to recompute the data field of its destination vertex.“以边为中心”的Gather将更新作为输入，并使用其值重新计算其目标顶点的数据字段。

X-Stream整体的计算被组织为一个循环，直到终止条件结束。其每个迭代由一个Scatter阶段和紧接着的Gather阶段组成。Scatter阶段使用scatter方法迭代所有的边，Gater阶段使用gather方法迭代Scatter阶段产生的所有更新集update。因此，X-Stream“以边为中心的scatter-gather”是同步的，并且保证只有在Scatter完成之后和下一个Scatter阶段开始之前才能看到前一个Scatter阶段的所有更新。

X-Stream使用streaming实现图计算模型。一个输入stream有一个方法，即从当前stream读下一个item。一个输出stream也有一个方法，即append一个item到当前stream。在图计算的Scatter阶段将边作为输入stream，然后产生一个更新的输出stream。每个迭代中它依次读每条边，以及边源顶点的数据（如果需要的话），然后append一个更新到输出stream。在Gather阶段把Scatter阶段的输出作为输入stream，它不产生任何输出stream。用输入中的（更新集）每条更新item去更新它的目的顶点值。

这种使用stream的图计算方法可以适用于In-memory和Out-of-core，允许顺序地接入慢速存储，获得大量的边stream和更新stream。唯一的问题是它会随机的接入顶点，幸运的是它们常位于快速存储中。

Streaming Partitions

一个Streaming Partition是有一个顶点集，一个边list和一个更新list组成。一个streaming partition的顶点集是图的顶点子集，并且各个partition中的顶点集互不相交。一个streaming partition的边list，其所有边的源顶点都位于当前partition的顶点集，而更新list中所有边的目的顶点都位于当前partition的顶点集。

在整个计算过程中，Streaming Partition的数量保持不变。在初始化期间，整个图的顶点集被划分为用于不同Partition的顶点集，并且计算每个Partition的边list。在整个计算过程中，这些顶点集和边list也保持固定。但是，分区的更新list会随着时间的推移而变化：在每个gather阶段之前重新计算。

Scatter-Gather with Partitions

有了streaming partitions后，Scatter阶段迭代所有的Partitions，而不是之前说的所有的边。同理在Gather阶段也是迭代所有的Partitions而不是所有的更新。如下图的伪代码所示：

对于每个streaming partition，Scatter阶段读取它的顶点集，stream它的边list，并产生一个更新的输出stream。输出stream被append到Uout list后，但这些更新需要被重新排列，以使每个更新出现在对应streaming partition的更新list（即包含它的目的顶点的partition）。我们称这个阶段为Shuffle阶段，Shuffle阶段是把Scatter阶段生成的更新集作为输入，然后把它们放置到相应的更新list中（即目的顶点所在的partition中的更新list）。Shuffle阶段完成后，Gather阶段才能开始。For each streaming partition, we read its vertex set, stream in its update list, and compute new values for the data fields of the vertices as we read updates from the update list.所以Streaming partitions是Scatter和Gather阶段天然的并行单元。

Size and Number of Partitions

选择准确的Partitions数量是性能的关键。为了更快的随机接入顶点，则一个streaming partition的所有顶点必须能载入到快速存储（即partition的数量越多越好）；为了最大化的顺序接入慢速存储来加载边list和更新list（即partition的数量越少越好）。X-Stream限制每个partition的顶点集中的顶点数量都相等，则partition的数量由快速存储的容量和单个partition中顶点集的顶点数量决定。

P=F/|V*C|，P表示partition数量，F表示快速存储的容量，V表示每个partition的顶点数量，C表示一个顶点所需的空间。

API Limitations and Extensions

X-Stream also supports vertex iteration, which simply iterates over all vertices in the graph, applying a user-specified function on each vertex.

X-Stream also supports interfaces other than edge-centric scatter-gather. For example, X-Stream supports the semi-streaming model for graphs or graph algorithms that are built on top of the W-Stream model.

Paper:https://infoscience.epfl.ch/record/188535/files/paper.pdf

PPT:http://sigops.org/sosp/sosp13/talks/roy_xstream_se09_04.pptx

Videos:https://www.youtube.com/watch?v=3YkpUEnLW4s

Source code:https://github.com/epfl-labos/x-stream