分布式Out-of-core图计算系统Chaos初体验

Chaos简介

Chaos[1]是由洛桑联邦理工学院EPFL实验室和Intel发表于SOSP’2015的分布式Out-of-core图计算系统。旨在用商业集群处理超大规模（边数量为trillion级别）图计算问题。分布式Out-of-core图计算系统的两种设计思路是集群拓展（单机Out-of-core拓展到分布式Out-of-core）和存储拓展（分布式In-memory拓展到分布式Out-of-core）。Chaos是基于X-Stream[2]做的集群扩展和改进，如果要充分发挥Chaos的性能优势，它对集群环境有一个苛刻的基本假设：A fundamental assumption underlying the design of Chaos is that machine-to-machine network bandwidth exceeds the bandwidth of a storage device and that network switch bandwidth exceeds the aggregate bandwidth of all storage devices in the cluster。即Chaos要求计算节点之间的网络带宽要大于本机存储带宽，并且集群的网络交换机聚合带宽要大于集群中所有存储设备的总带宽。

由于最近在写硕士毕业论文，系统测试方面关于A22D Graph和Chaos做对比的实验由孙建强同学帮忙完成，本文主要由他提供简述Chaos的体验使用，而关于Chaos更详细的系统原理介绍将在后期娓娓道来。

测试环境

测试环境是一个机架内的四台服务器和一个万兆交换机，通过10 Gbps SFP+光纤直连线组成的超小型集群。具体的，4个计算节点是配置完全相同的二手DELL R510服务器，每个计算节点包含一颗16核CPU，8*4GB内存，1TB的SATA磁盘和一张PCI-Express万兆的网卡，并装有64位的CentOS 7.3.1611操作系统，内核版本是3.10.0-514。

网络交换机是HP Quanta LB6M，它有24个10GbE的SFP+端口，其背板聚合带宽480 Gbps。每个计算节点上都有一个张Mellanox品牌的ConnectX-3 PCI-Express单口网卡，通过安装MLNX_OFED驱动可支持RoCE（RDMA over Converged Ethernet）。计算节点和网络交换机之间通过4根3米长的10 Gbps SFP+光纤直连线连通，组成计算集群。

当前集群计算节点之间的网络带宽114.3MB/s大于磁盘最大顺序读写带宽109.2MB/s，并且交换机的聚合带宽也远大于集群所有磁盘的聚合带宽，完全满足Chaos运行环境的要求。

Chaos安装部署（每个计算节点都执行）

环境要求：boost库

获取系统源码：git clone https://github.com/epfl-labos/chaos.git

编译：cd chaos 然后 make

安装过程中可能遇到的一些问题：

【1】No such file or directory zlib.h

主要问题是缺少文件zlib-devel，安装即可：yum install zlib-devel

【2】Fatal error can't create object_files/core.o no such file or directory

缺少object_files文件夹，需自己手动创建，mkdir object_files

【3】缺少boost/numeric/bindings/lapack/gesv.hpp

这个问题是chaos使用了一个非boost标准库文件，可能安装boost中没有该库，需要自己手动安装。首先看下Makefile的第23行确定该路径确实是你系统中boost的位置，否则手动修正。执行ls /usr/include/boost/numeric/ 看该目录下是否有bindings文件夹，如果没有则需要手动安装。boost.numeric.bindings源码下载wget https://mathema.tician.de/dl/software/boost-numeric-bindings/boost-numeric-bindings-20081116.tar.gz。解压后移动到boost相应目录下

tar zxvf boost-numeric-bindings-20081116.tar.gz

mv boost-numeric-bindings/boost/numeric/bindings/ /usr/include/boost/numberic/

【4】cannot open output file bin/benchmark_driver: No such file or directory

同问题2手动创建一下文件夹即可：mkdir bin

【5】 /usr/bin/ld: cannot find –llapack

这里是缺少一个链接库文件，首选解决方案是使用yum安装：sudo yum install liblapack-dev。若显示没有这个文件的安装包，则选用源码安装：wget http://www.netlib.org/lapack/lapack-3.8.0.tar.gz，然后解压tar zxvf lapack-3.8.0.tar.gz。把配置文件make.inc.example改为make.inc，执行make (这里编译花的时间稍长)，会生成一个liblapack.a的静态链接库，将该文件移动到/usr/lib下，mv liblapack.a /usr/lib 即可。

至此应该已经编译成功了。

为Chaos准备图数据

Chaos的输入数据是二进制的边集，有两种方法：

（1）使用Chaos系统提供的工具自动生成一个测试图：

cd ~/chaos/generators/

./rmat --name test --scale 20 --edges 166777216 --xscale_interval 1 --xscale_node 0

生成一个名字为test的无向带权图，该图有2^20个顶点，一共有166777216条边，仅使用一台机器（单机运行），此处生成机器编号为0。

如果要生成一个多机运行的图，比如四台机器，生成第三台机器的输入图数据

./rmat --name test --scale 20 --edges 166777216--xscale_interval 4 --xscale_node2

使用--xscale_interval指定了机器数量，使用--xscale_node指定是第几台机器的数据，机器编号从0开始计数。

其它还有很多参数读者可以自行查看并运行测试，如使用--symmetric指定生成一个无向图，默认是生成一个有向图的。

可以看到生成了两个文件：

test文件是要输入的二进制图数据，test.ini是图数据的说明文件，它有166777216条边，怎么样验证呢？我们知道一般一条边是由两个顶点或另加一个权值标识，因此一条二进制边的SIZE就是用两个顶点值的大小加上权值大小。顶点总数量是220完全可以用int类型表示全部的顶点编号即sizeof(int)，本环境为4字节。若更多的顶点则可能需要用long表示每个顶点的ID编号及sizeof(long)，本环境为8字节。对于有权图来说还要加权值，一般用float表示即sizeof(float)，本环境为4字节。因此test文件的每条边占12字节。

若是无权值图时，则每条边的大小为8个字节，那么如控制生成的图是否带权值呢？经过一番分析后，可以发现在/path/chaos/generators/Makefile 的第7行中有一项编译宏定义：

当这个标志存在时，ramt生成的即为有权图，否则为无权图，使用方法为：

$ make clean #清除原rmat文件

# 根据自己需求，修改Makefile第七行，需要则保留该标志，否则用#注释掉即可

$ make #重新生成ramt工具

我们继续讨论下test.ini，该文件标识了当前计算节点上test的部分数据情况，表明对应的图名称，是否有边权，顶点数，边数。

其中type标识了是否有权值，1表示有权值，2表示无权值，vertices表示该图顶点总数，edges表示当前部分的边数。注意这里不是全图的总边数，只是当前部分图数据的边数，Chaos会根据文件大小，类型，顶点总数和边数这些信息确定每条边的构成，运行时通过读取二进制文件转换为源顶点编号，目的顶点编号或权值等。

（2）使用自己采集或下载的数据

Chaos是个分布式图计算系统，为了并行化运行，所以我们需要将一个图尽可能均等的分割到多个计算节点上。以切分twitter-2010[3]社交图数据到本集群四个计算节点为例，压缩文本格式数据下载地址[4]，然后解压，并使用下面代码转换为二进制文件twitter_rv.bin。

使用split工具切分twitter-2010数据（每条边8字节，无权值）：

[root@graph-rdma05twitter-2010]# ll

[root@graph-rdma05 chaos]#python

# 一条边是8个字节，所以每一份含有367091295.5条边，需要向上取整367091296

进行分割：

[root@graph-rdma05twitter-2010]# split ./twitter_rv.bin -b 2936730368

[root@graph-rdma05twitter-2010]# ll

验证总大小：

然后将这四个文件scp到四个计算节点上，相同的目录下命名为twitter2010（建议放在/path/chaos/bin目录下），并配置对应的ini文件，注意边的数量要跟文件大小对应：

[root@graph-rdma05 bin]# cat twitter2010.ini

[graph]

name=twitter2010

type=2

若出现类似下面的错误，则要仔细检查ini文件的拼写了，特别是vertices，建议拷贝test.ini再修改。

运行Chaos

下面我们来讲讲如何运行程序，将输入数据及相应的配置文件移动到bin目录下，运行Chaos的指令是benchmark_driver。但还需用slipstore.ini文件配置集群环境，格式如下：

简单解释下就是：集群的规模多少台机器，当前计算节点的id（从0开始编号），ip地址，端口号，网卡名，参考：

[root@graph-rdma05 bin]# cat slipstore.ini

[machines]

count=4

me=0

name0=10.0.0.165

base_port0=5555

iface0=p3p1

name1=10.0.0.166

base_port1=5555

iface1=p3p1

name2=10.0.0.167

base_port2=5555

iface2=p3p1

name3=10.0.0.168

base_port3=5555

iface3=p3p1

运行示例，在test数据集上运行10次迭代的PageRank算法：

# ./benchmark_driver -g test -b pagerank --pagerank::niters10 -a -p 16 --physical_memory 268435456

参数解释下：-g后跟着图的名称，-b后面跟着要运行的算法，如pagerank要输入迭代次数，BFS要输入遍历起始顶点编号。-a参数意为自动调整分区计数，-p后跟要开启多少个进程，--physical_memory后跟内存大小，单位是字节。

当然benchmark_driver还有很多其它参数，可以运行./benchmark_driver –h 进行查看并测试。如果是多机运行，就需要每台机器都运行一遍这个命令，这里可以用clush工具运行。

这里提两个可能出现的问题，一个是在多机运行时可能在建立ZeroMQ的TCP连接时会阻塞，原因可能是防火墙给屏蔽掉了，这时简单的在所有计算节点上执行iptables-F即可。另一个可能出现的问题是，当一个计算节点上的程序意外终止后，下一次再运行显示端口被占用，可通过ps命令查找出该进程，并kill掉即可重新运行。

测试用例

[1]《Chaos:Scale-out Graph Processing from Secondary Storage》SOSP’15

[2]《X-Stream:Edge-centric Graph Processing using Streaming Partitions》SOSP’13

[3] http://an.kaist.ac.kr/traces/WWW2010.html

[4] http://an.kaist.ac.kr/~haewoon/release/twitter_social_graph/twitter_rv.zip

[5] https://github.com/epfl-labos/chaos