英语原文共 17 页，剩余内容已隐藏，支付完成后下载完整资料
X-Stream: Edge-centric Graph Processing
using Streaming Partitions
Amitabha Roy, Ivo Mihailovic, Willy Zwaenepoel
{amitabha.roy, ivo.mihailovic, willy.zwaenepoel}@epfl.ch
EPFL
摘要
X-Stream 是在共享存储机器上既能处理存放于外存，又能处理存放于内存的图数据处理系统。虽然依然采用在顶点集中存储图状态的发散和收集编程模型，X-Stream 的新颖之处在于（i ）采用edge-centric 而不是vertex-centric 来实现这个模型，（ii ）对完全无序的边列表实行流式传输而不是随机访问。对所有的存储介质（主存，固态硬盘，磁盘 ）来说，顺序访问带宽实际上要比随机访问带宽大是促动这一设计的主要原因。
我们已经证实了大量的图算法可以用这种edge-centric 的发散与收集模型表示。 这个实现结果在具有不同数量的计算核心，不同数量的I/O设备，不同的存储介质的计算机上得到了很好的扩展。X-Stream 在和现有的图数据处理系统的竞争中表现突出。除了采用顺序访问外，我们认为X-Stream 在预处理过程中不需要存储边列表也是其表现突出的主要原因。
1 引言
对大规模图数据的分析是一个开始在研究领域吸引更多注意的应用程序。人们对其兴趣高涨一部分是因为在现实世界中不同种类的大量信息是用图来编码的。图数据处理面临一个有趣的系统挑战：在遍历边时缺少其位臵信息使获得好的性能变得困难。这篇论文描述了X-Stream ，用于在共享存储机器上处理大规模图数据的系统。类似于Pregel 和Powergraph ，X-Stream 在顶点集中维护图的状态并由此揭示了一个发散与收集编程模型。对图的计算被组织成一个循环，每次迭代由一个发散阶段后跟一个收集阶段组成，实例1说明了这个发散与收集模型的一般实现。发散和收集阶段均对所有的顶点进行迭代。用户提供一个发散函数用于向邻点传播状态和一个收集函数用于累计邻点的更新来重新计算顶点的状态。这个简单的模型对于包括从计算最短路径到在一个搜索引擎中对网页进行排序在内的大量图算法来说都是有效的，因此，这是一个图处理系统的流行接口。
一个可行（直接）的用于处理存放于内存或外存中大规模图数据的方法是根据源点对图中的边进行排序并在存储的边列表上建立索引。那么在执行过程中包括对索引的随机访问来确定一条边所关联的顶点。在这种设计中隐含了对于随机访问和顺序访问的折衷，尽量减少用于确定边所关联顶点的对索引的随机访问，流式传输大量无关边并选择那些和活跃顶点相关联的边，这就是要在这篇文章中重新描述的折衷。
对于任何存储介质来说，随机访问带宽比顺序访问带宽要小。例如，在我们的测试平台上（16 core/64 GB 1U server, 7200 RPM 3TB magnetic disk and 200 GB PCIe SSD），对磁盘来说，顺序读比随机读快500倍，对固态磁盘来说，这个数字是30，甚至于对主存来说，由于存在硬件预取，在单核计算机上，顺序访问比随机访问快4.6倍，对于16核计算机来说，这个数字是1.8。更多细节参见5.1节。 在这篇文章中我们证实了可以仅仅根据从存储器流动数据的原则，利用顺序访问比随机访问带宽大来建立一个图数据处理系统。我们展现了这种设计可以引导出一个既适用于处理内存中图数据又适用于处理外存中图数据的有效图数据处理系统，在大多数情况下，相同或更好性能的系统都建立在对索引进行随机访问的基础上。
为了达到这个层次的性能，X-Stream 引入了一个edge-centric 方法来处理发散与收集，如实例2所示：发散和收集阶段对所有的边进行迭代，并对边集进行更新而不是对顶点集。 edge-centric 方法同样避免对边集的随机访问，取而代之的是从存储器中流式传输。对图来说，边集远远大于顶点集，顺序访问边并更新它们控制了处理的开销，因此，对边进行流式传输通常比随机访问它们更具优势，这样做的结果是，要付出随机访问顶点集的代价。我们使用流分区来减少这种代价：我们对顶点集进行分割以使得每片分区可以适用于高速存储器（对基于内存的图指的是cache ，对基于外存的图指的是主存）。更进一步，我们对边集进行分区并使得边和它们的源点在同一片分区中。然后，我们每次对一片分区进行处理，首先读取它们的顶点集并从存储器中流式传输它们的边集，这种方法的有利之处在于我们不需要存储边列表，因此，不会像其它系统一样在预处理时导致延迟。 Graphchi 是首个实行避免对边集进行随机访问的系统。Graphchi 使用了一个新颖的包含名为“shards ”的由图的分区组成的核外数据结构。不同于流分区，shards 必须根据源顶点进行预排序，导致了不可忽视的预处理开销，特别是当图使用地不频繁时。Graphchi 仍然使用示例1所示的vertex-centric 实现，这就要求shard-vertex 和它们的传入和传出同时位于内存中，导致了比流分区数量多得多的shard ，后者仅仅要求将顶点存放于内存中。因此，流分区更好的利用了顺序访问的带宽优势。shards 为了在收集阶段直接对顶点进行更新，它还要求根据目的顶点对边进行预排序。
这篇文章对X-Stream 的设计，实现和评估做了如下贡献：
● 我们引入了edge-centric 处理过程作为图计算的新模型，并证明它可以被用于各种各样的图算法。
● 我们展示了如何使用流分区来实现既能处理基于外存又能处理基于内存的图数据的处理模型，仅仅是对不同的存储介质划分不同大小的流分区。
● 我们证实了X-Stream 在具有不同数量计算核心，不同数量I/O设备，不同类型的存储介质的计算机上可以得到很好的扩展。例如：X-Stream 可以在28秒内识别出具有5.12亿条边的图中的弱联通部件，对于具有多达40亿条边的存放于固态硬盘的图，需要33分钟，对于具有多达640亿条边的存放于磁盘的图，需要26小时。
● 我们将X-Stream 和可获得的图处理系统进行了比较，并证实无论是对于基于外存还是基于内存的图，X-Stream 和那些采用vertex-centric 和基于索引的系统表现的一样甚至更好。
2 X-Stream的处理模型
X-Stream 向用户提供了一个将计算时易变的状态存储于顶点集的图计算模型，更准确的说，是存储在每个顶点的数据域中。X-Stream 的输入是无序的有向图边集，至于无向图，可以将其视为在在每个方向上有一对有向边的有向图。
X-Stream 提供了两个主要的API 函数用于表示图计算。edge-centric 在发散阶段用一条边作为输入，然后根据边的源点进行计算，如果更新后的值需要被送到边的目的顶点，则更新目的顶点的值。edge-centric 的收集阶段用一个更新作为其输入，并用来重新计算目的顶点的数据域。
整个计算过程被组织成一个循环，当相对于特定应用程序的终止条件符合时，循环终止。每次循环迭代由一个发散阶段后跟一个收集阶段组成。发散阶段迭代所有的边并将发散函数应用于每一条边，收集阶段迭代发散阶段所产生的所有更新并将收集函数应用于每一个更新，因此，X-Stream 的发散和收集阶段是同步进行的，并保证来自前一发散阶段的所有更新只有在当前发散阶段完成后和下一发散阶段开始前开始。在这一点上来说，X-Stream 和分布式的图处理系统Pergel 类似。
2.1 Stream
X-Stream 使用流式传输来实现上述图计算模型。一个输入流有一个方法，就是从流中读取下一个项目。一个输入流作为一个整体进行读取，每次一个项目。一个输出流也有一个方法，就是在流中附加一个项目。
计算的发散阶段将边集作为输入流，并产生一个关于更新的输出流。每次迭代读取一条边并读取与边相关联的源点的数据域，然后，，如果需要的话，在输出流中附加一个更新。收集阶段将发散阶段产生的更新作为其输入流，它不产生任何输出流，对于输入流中的每一个更新，它将更新相关边目的顶点的数据域。 将流用于图计算同时适用于基于内存和基于外存的图数据，为了统一描述，我们使用下列术语。如果图是基于内存的，那么Fast storage指的是cache ，Slow storage指的是主存；如果图是基于外存的，那么Fast storage指的是主存，Slow storage指的是固态硬盘或磁盘。
实例3展示了在流式传输边模型中是如何对存储器进行访问的。这种用于图处理的流式传输方法基于可以对存放边和更新流的Slow storage进行顺序访问。这种方法的问题在于需要对顶点集进行随机访问，而对于很大的图来说，顶点集可能不能全部存放于Fast storage中。为了解决这个问题，我们引入流分区的概念，描述如下。
2.2 流分区
一个流分区包括顶点集，边列表和更新列表。一个流分区的顶点集是整个图的流分区的顶点集的子集，不同流分的顶点集相互不相交，它们的集合等于整个图的顶点集。流分区的边列表包括所有源点位于分区顶点集中的边，流分区的更新列表包括所有目的顶点位于分区顶点集中的边。
在计算过程中，流分区的数目保持固定。在初始化阶段，整个图的顶点集被分割为不同分区的顶点集，然后计算出每个分区的边列表。这些顶点集和边列表在整个计算过程中保持固定。然而，一个流分区的更新列表随时间而变化：在每次收集阶段前被重新计算，如下所述
2.3 分区下的发散与收集
有了流分区后，正如前面描述的一样，发散阶段迭代所有的流分区，而并不是所有的边。与之类似，收集阶段迭代所有的流分区，而不是所有的更新。示例4描述了使用了流分区后，edge-centric 下发散与收集阶段的为代码。
对于每个流分区，发散阶段读取它的顶点集并在它的边列表上进行流动，然后产生一个关于更新的输出流。这个输出流被添加在链表Uout 后。这些更新需要重新排列使得在流分区更新列表中出现的更新包括它们的目的顶点。我们把这个阶段称为shuffle 阶段。shuffle 阶段将发散阶段产生的更新作为其输入流，并将每个更新移至更新列表Uin （p ）。p 包含和更新相关的目的顶点，在shuffle 阶段完成后，可以开始收集阶段，对每个流分区，我们读取其顶点集并在更新列表中进行流动，在从更新列表中读取更新时，为顶点集的数据域计算新值。
流分区天然地支持在发散和收集阶段实行并行，我们将会在第4节展示如何发挥并行的优势。
2.4 分区的大小和数量
选择正确的流分区数目对性能来说是至关重要的。一方面，为了实现对顶点集的快速随机访问，一个流分区的所有顶点集必须适合存放于Fast storage中。另一方面，为了在载入边列表和更新列表时最大化对Slow storage的顺序访问速速，分区的数量应该尽可能的少。因此，我们这样来确定分区的大小，通过使用缓冲区和其它的辅助数据结构，使得每个刘分区的顶点集可以填满Fast storage。
2.5 API的限制和扩展
不同于vertex-centric 图处理模型的API ，在我们的edge-centric 模型中不存在函数对一个顶点的边列表和更新列表进行迭代。因此，为了允许用户指定对边的发散和收集函数，X-Stream 同样对顶点的迭代，只是简单的迭代所有的顶点并将用户指定的函数应用于每个顶点。这对于初始化和多种组合操作来说是有用的。 除了edge-centric 的发散与收集外，X-Stream 还支持其它的接口。例如，X-Stream 支持在W-Stream 上建立的用于图和图算法的半流式传输模型。虽然这些模型可以表达更多的图算法，在这篇文章中我们更专注于熟悉的发散与收集模型。
3 核外流引擎
核外流引擎的输入是包含图的无序边列表的文件，另外每个流分区还有三个磁盘文件：分别为顶点集，边集和更新集的文件。
正如第2节所述，在edge-centric 的发散与收集模型下，在发散与收集阶段实现顺序访问是容易的，困难的部分是在shuffle 阶段。为了在流外核引擎中解决这个问题，我们对示例4所描绘的计算模型进行轻微的修正。我们将shuffle 阶段合并到发散阶段用于取代严格区分的发散，shuffle ，收集阶段。另外，在进行发散阶段时，将产生的更新附加到一个内存中的缓冲区中。一旦该缓冲区满了，就执行一个内存shuffle ，将位于内存缓冲区中的更新列表根据其顶点集所在的流分区而进行划分，然后将它们添加到各自分区的更新列表中。
3.1 内存中的数据结构
除了用于存储流分区顶点集的数组外，我们还需要一个位于内存中的数据结构用于存放来自磁盘的输入（发散阶段的边集和收集阶段的更
全文共18177字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[12720]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
