单机核外图计算系统之X-Stream(三)SOSP-2013

和二中介绍了单机图计算系统X-Stream“以边为中心”的scatter-gather图计算模型的实现原理和相应的Stream划分方法。本文详细介绍其在Out-of-core情形下的Streaming Engine。

Out-of-core Streaming Engine

X-Stream的Out-of-core图计算引擎的输入是一个包含图的无序边list,除此之外还为每个streaming partition准备了三个磁盘文件,分别存储vertices, edges和updates。X-Stream“以边为中心”的scatter-gather模型,容易在Scatter和Gather阶段实现顺序接入,唯一困难是在Shuffle阶段实现顺序接入。因此为Out-of-core情形修改了计算结构,将严格的Scatter,Shuffle和Gather三个顺序的阶段中,把Shuffle阶段合并到Scatter阶段。特别地,运行Scatter阶段时,把需要append的更新放到In-memory中的buffer,当buffer满时运行一个In-memory Shuffle,用来将buffer中的更新对应到不同顶点partition的更新list中,然后append这些list到每个partition对应的更新list磁盘文件。

In-memory Data Structures

除了顶点数组被用来存储每个streaming partition的顶点集之外,我们还需要一个In-memory数据结构来容纳从磁盘读进来的输入数据(即Scatter阶段的edges和Gather阶段的updates),In-memory Shuffle阶段的输入和输出数据,以及输出到磁盘的数据(即每一个In-memory Shuffle阶段之后的更新)。

为了避免动态的分配内存,我们设计了一个静态大小和静态分配的数据结构,即Stream buffer,用来存储可变长度的数据items。一个stream buffer由一个(大)byte数组(叫做Chunk Arrary)和含有K个(对应于K个streaming partitions)实体的索引数组组成。索引数据中第i个实体描述了Chunk Array中的一个chunk(即第i个partition的相关数据)。

使用两个streaming buffer,则In-memory Shuffle过程将会变得简单直接。一个streaming buffer用于存储Scatter阶段的结果(即更新集),另一个streaming buffer用来存储In-memory Shuffle的结果。我们对输入缓冲区进行一次遍历,计算发往每个分区的更新。然后填充第二个streaming buffer的索引数组。最后拷贝第一个buffer中的updates到第二个buffer对应位置的Chunk Array中。

Operation

磁盘引擎首先将输入边列表划分为不同的流分区,有趣的是,这个步骤可以通过In-memory Shuffle高效的实现。输入边list被连续的从磁盘中读取并放入一个streaming buffer中,shuffle到另一个streaming buffer,然后写入到对应streaming partitions的磁盘文件中。

预处理结束后,图处理引擎进入如下图所示的主处理循环(Disk Streaming Loop):

最后实现了两个优化,第一,如果全部的顶点集都能放入内存,则顶点数组不再需要在每次Gather阶段结束后被写到磁盘上了。第二,如果Scatter阶段的所有更新集可以被放入streaming buffer中,则更新集也不必在每次In-memory shuffle之后写入磁盘上了。换句话说,就是Gather节点能简单的重用Shuffle阶段在内存的输出。

Disk I/O

X-Stream执行与流缓冲区之间的异步直接I / O,绕过操作系统的页面缓存。无论流缓冲区中的块的起点如何,我们每个流分区使用额外的4K页面来保持I / O对齐。

我们利用访问的顺序性,实现从流中预取(prefetch)。一旦读入一个输入流缓冲区,我们就开始读入下一个输入流缓冲区。类似地,在一个输出缓冲器中对块的磁盘写入与将Scatter阶段的更新计算到另一个输出缓冲器中重叠。这需要为输入和输出分配额外的流缓冲区。我们发现输入和输出上的预取(prefetch)足以使磁盘处于100%忙碌状态。如果需要,可以使用更大的chunk array有效地实现更深的预取。

X-Stream显著的利用RAID结构带来的好处。顺序的写stripe文件分布在多个磁盘上,顺序的读这些stripe可以实现多倍的带宽(相比于单个磁盘)。我们也能探索输入和输出的并行,可以发生在不同的磁盘上。X-Stream对每个磁盘使用专用I/O线程执行异步I/O。因此,可以将边和更新放在不同的磁盘上,并行地对它们进行I/O操作。

X-Stream的I/O设计也适用于SSD盘。所有的X-Stream写操作都是顺序的,这可以避免“写放大”问题,以类似于日志结构文件系统和专门为闪存设备构建的内存分配器的方式。现代的flash传输层实际是在固件上实现一个日志结构的文件系统,X-Stream的顺序写可以更好的考虑到这种固件。此外,我们总是在文件被破坏时截断文件。在大多数操作系统上,截断自动转换为发送到SSD的TRIM命令,释放块,从而减轻SSD垃圾收集器的压力。

Number of Partitions

给定固定数量的内存,正确地对流缓冲区进行大小调整的需求会产生对流分区数量的额外要求,而不仅仅是需要将流分区的顶点集合在内存中。我们需要考虑足够大的I/O单元来接收流式带宽到磁盘。假设跨流分区的更新均匀分布,并假设我们需要发出S字节的I/O请求以实现最大I/O带宽,我们需要将块数组的大小调整为K个流分区的至少S * K字节。我们的设计需要两个流缓冲区,每个缓冲区用于输入和输出流,以支持预取。此外,我们需要一个用于shuffle的流缓冲区:总共5个。如果我们假设N是顶点占用的总空间,而M是可用的主内存总量,那么我们的要求转换为:

N/K + 5*S*K

对于非常大的图,也存在对这种不等式的可行解决方案是,让等式左边取最小值(a+b≥2√ab),即K=N/(5*S)1/2,表示需要最小的内存空间是2* [(5*N*S)1/2]。I/O单元S=16MB ,图所有顶点的大小N=1TB,所以当K=120个streaming partitions时,M=17GB。这忽略了索引数据的开销,这在我们的设计中会增加5KB。

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180728G1NVMZ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券