分散式Out-of-core圖計算系統Chaos初體驗

最新 04-16

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掉即可重新運行。

測試用例