一個基于Redis架構(gòu)的分布式圖計算系統(tǒng)設(shè)計

劉慶典，王昂,2，李川

（1.四川大學計算機學院，成都　610065；2.阿里巴巴，杭州）

一個基于Redis架構(gòu)的分布式圖計算系統(tǒng)設(shè)計

劉慶典1，王昂1,2，李川1

（1.四川大學計算機學院，成都610065；2.阿里巴巴，杭州）

圖數(shù)據(jù)模型；分布式系統(tǒng)架構(gòu)；存儲系統(tǒng)

0　引言

圖的概念最早是在1736年瑞士數(shù)學家L.Euler為解決K?nigsberg Bridge Problem[1]的論文中提出，這也是當前圖論領(lǐng)域公認的第一篇論文[2]。二十世紀六十年代之后，由于計算機科學和其他科學的發(fā)展推動，圖論的發(fā)展更為迅速。圖和網(wǎng)絡(luò)的普適性，面對真實應(yīng)用場景能夠有效地進行建模，且推演出解決方案，已使圖論研究如火如荼。面對社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)等需求，對于超大規(guī)模圖的高效管理、查詢的需求也與日俱增[3-6]。傳統(tǒng)的如交通路線規(guī)劃、疾病傳波路徑的預測、論文合作網(wǎng)絡(luò)合作者間的關(guān)系預測等，在新興社交網(wǎng)絡(luò)語義、生物信息網(wǎng)絡(luò)分析等方向都有非常廣泛的應(yīng)用。面對大規(guī)模的圖數(shù)據(jù)，常規(guī)的處理方法是置之于分布式多機器節(jié)點上進行并行處理，則圖分割問題的解決是采取該方案的前提。早在1970年代，圖分割問題就已經(jīng)成為圖論研究領(lǐng)域的熱門話題。經(jīng)過40余年的發(fā)展，傳統(tǒng)圖分割算法已趨近于成熟。將整個圖進行分割，才能夠在分布式圖計算平臺進行分析。為了更好的在分布式圖系統(tǒng)上進行學術(shù)研究和實踐應(yīng)用，本文設(shè)計了分布式圖計算系統(tǒng)。

1　定義

定義1（圖）設(shè)V為包含nV個元素的集合，E為包含nE個V集合中的元素對，則一個圖可以表示為一個二元組（V,E）。其中，V中的元素為圖的頂點集合，集合E?[V]2是由兩個頂點對組成，表征圖中的邊。頂點的數(shù)目也可記為|V|，邊的數(shù)目可以記為|E|。

定義2（超圖）設(shè)V為一個非空有限集合，設(shè)E為V的非空子集的集合。超圖G表示為二元組（V,E），其中V為頂點結(jié)合，E被稱為超邊或鏈接。

定義3（無向圖）設(shè)G=（V，E）。對于任意一條邊（v1，v2）∈E，若同樣存在一條邊（v2，v1）∈E，則稱此圖為無向圖。因而，對于無向圖中的一條邊也可表示為（v1，v2）=（v2，v1）=e∈E，其中v1，v2∈V。

2　圖訪問模型

一個圖由二元組G=（V，E）表示，其中V為圖中所有頂點集合，E為圖中邊集合。避免歧義，本文圖中的點統(tǒng)一稱為“頂點”，而分布式集群中的主機統(tǒng)一稱為“機器節(jié)點”或簡稱“節(jié)點”。

在對圖進行分割時，若對圖進行頂點分割，圖中所有邊會被分配到分布式系統(tǒng)中指定分區(qū)。若對圖進行邊分割，圖中所有頂點會被分配到分布式系統(tǒng)中指定分區(qū)。對于圖中頂點的操作包括兩種行為：讀操作和寫操作。“讀操作”是讀取頂點信息，而“寫操作”是更新頂點信息。一種常見圖訪問模式是 “獲取某頂點x所有鄰居狀態(tài)”。這是現(xiàn)實網(wǎng)絡(luò)，尤其是社交網(wǎng)絡(luò)中最經(jīng)常用到的訪問模式。系統(tǒng)需要首先找到頂點x，并遍歷其所有鄰居頂點，獲取其鄰居最新的狀態(tài)信息。社交網(wǎng)絡(luò)中存在很多鄰居數(shù)目十分龐大的用戶，快速查找出這些用戶的所有鄰居，這種查詢對于系統(tǒng)的擴展性提出很高要求。由于圖分割致使其鄰居可能不在同一個機器節(jié)點。因此造成的跨分區(qū)訪問會加大網(wǎng)絡(luò)負載，增加查詢延時。

另外一種常見訪問模式是查詢頂點x所有符合某些條件的鄰居。例如，查詢頂點x所有出生在四川，并且已經(jīng)結(jié)婚的鄰居。對于這類查詢，首先訪問x所有鄰居，并根據(jù)條件對鄰居進行過濾。這與上一種模式類似，但在實際應(yīng)用中這種1跳（1-hop）查詢，可能會擴展到2跳（2-hops），甚至是更多，因而所造成的跨分區(qū)訪問次數(shù)更大。

此外，一些子圖匹配查詢也是較為常見的訪問模式，但也都是基于上述兩個模式的擴展。

3　系統(tǒng)架構(gòu)

圖1 所展示的是系統(tǒng)上層架構(gòu)圖，包含分配邏輯模塊（Allocate Logic Module）、路由邏輯模塊（Route Logic Module）、動態(tài)均衡模塊（Balance Logic Module）、存儲模塊（Storage Module）、可視化模塊（Visualization System）等部分。

本研究的分布式圖系統(tǒng)主要由1個Master主機和k個Slave主機組成，k的大小根據(jù)實際應(yīng)用需求指定。每個Slave機器可被看作圖分割后的一個區(qū)塊。外部請求首先會被發(fā)送到Master節(jié)點，然后根據(jù)請求需要將信息分發(fā)到相應(yīng)的Slave主機。本文僅考慮一個Master節(jié)點情形，可通過簡單改進設(shè)計成多個并行Master節(jié)點模式。

Master節(jié)點主要工作包括三部分：頂點分配、路由和全局信息存儲。頂點分配意指在有新頂點或邊請求分配時，分配邏輯模塊會根據(jù)設(shè)計好的分配算法對新頂點或邊進行分配，將其存儲于某個Slave機器節(jié)點。路由功能意指對于外部查詢訪問請求通過查詢?nèi)中畔⒈?，找到訪問請求中頂點或邊所在的Slave節(jié)點，并將信息返回。此外，Master主機會存儲路由所需要的全局查詢表，保存著圖的分配信息。具體存儲系統(tǒng)的詳細細節(jié)將在第4節(jié)進行闡述。

圖1　系統(tǒng)架構(gòu)

Slave節(jié)點保存被分割后相應(yīng)圖分區(qū)中實際頂點信息。系統(tǒng)在運行過程中Slave主機會記錄每個頂點被讀和寫的頻率，并作為動態(tài)均衡的依據(jù)。動態(tài)均衡模塊在本文系統(tǒng)中起著至關(guān)重要的作用，它負責決定圖中的頂點是否擁有多個拷貝，從而最大限度地降低網(wǎng)絡(luò)負載和通信延時。通過一定時間的歷史訪問記錄，每個頂點會形成一定的讀寫模式。這些數(shù)據(jù)經(jīng)過收集匯總，然后用以判定各頂點最適合被分配到哪個Slave節(jié)點，從而最大限度降低機器間通信。動態(tài)均衡的細節(jié)將在后文中詳細描述。此外，Slave節(jié)點還會對外提供一些圖訪問接口，通過對底層封裝為方便上層獲取圖的相關(guān)信息。

為能夠更直接表示圖分割結(jié)果，系統(tǒng)包含一套可視化系統(tǒng)模塊。在第5節(jié)將詳細講述可視化模塊具體信息。

4　存儲系統(tǒng)

本文使用基于內(nèi)存的鍵值數(shù)據(jù)庫Redis來存儲圖基礎(chǔ)數(shù)據(jù)、分配信息和其他系統(tǒng)信息。數(shù)據(jù)會定期從內(nèi)存?zhèn)浞莸接脖P，以避免數(shù)據(jù)丟失。之所以選擇Redis作為基礎(chǔ)數(shù)據(jù)存儲因為以下原因：

（1）訪問速度快

由于Redis是一種基于內(nèi)存的數(shù)據(jù)庫，因而訪問速度極快。在Intel Xeon CPU E5520@2.27GHz機器上，Redis每秒可完成 552028次 Set操作，每秒完成707463次Get操作[7]，性能極高。

（2）支持豐富的數(shù)據(jù)類型

雖然Redis是一種鍵值數(shù)據(jù)庫，但其數(shù)據(jù)類型不只是整形和字符串型兩種。Redis支持軟件開發(fā)過程中大部分常見數(shù)據(jù)類型，如List、Set、Sorted Set、Hash等。

（3）操作具有原子性

所有的Redis操作都具有原子性，這使得在多線程或多用戶訪問數(shù)據(jù)庫時不會出現(xiàn)異常。

（4）豐富的工具

Redis的命令十分豐富，對于常見操作都進行了實現(xiàn)。例如鍵操作、字符串操作、Hash操作、集合交并集等。此外，還提供大量數(shù)據(jù)庫管理工具，如caching，messaging-queues，publish，subscribe等。

本文在實驗過程中，在確定存儲模型和結(jié)構(gòu)之后對Redis進行封裝，編寫專門用于分布式圖的庫形成圖的訪問接口，如圖1 中Graph Interface模塊所示。這使得底層圖存儲的細節(jié)透明，用戶可直接通過調(diào)用接口函數(shù)訪問已存儲的圖數(shù)據(jù)。

5　可視化模塊

常見圖分割系統(tǒng)將結(jié)果通過數(shù)字指標來表征分割好壞，這讓用戶難以區(qū)分。頂點被分割到哪個分區(qū)也并不容易被查看。本模塊通過可視化技術(shù)顯示分割后的結(jié)果。如圖2 所示，這是圖分割后的可視化圖。通過可視化，本研究提供人眼一樣直覺的、交互的可視化環(huán)境。

本文借助d3.js引擎對分割結(jié)果可視化。d3.js是一個可視化相關(guān)的JavaScript庫，通過操作數(shù)據(jù)來進行可視化展示。圖2 是對表1中Jazz數(shù)據(jù)集進行分割后的結(jié)果，其中藍色的為主頂點，橙色的為影子頂點（主頂點和影子頂點的概念將在后文中詳細介紹）?？梢暬K通過不同顏色來表征不同的頂點特征，頂點名稱信息也可通過設(shè)置來確定顯示與否。圖2 是將Jazz數(shù)據(jù)分割到4個分區(qū)中，每張圖代表一個分區(qū)保存的結(jié)果。通過可視化之后，可對分割好壞一目了然。此外，可視化模塊通過每個頂點的度來決定頂點圓圈大小。度越大圓圈半徑也越大，否則越小。這使得頂點重要性也可通過可視化表現(xiàn)出來。可視化模塊會自動根據(jù)力學原理確定整個圖布局，用戶也可通過拖拽頂點來重新調(diào)整頂點位置。

圖2　可視化模塊顯示結(jié)果

表1　數(shù)據(jù)集

6　結(jié)語

本文提出了基于圖數(shù)據(jù)模型的分布式大圖系統(tǒng)架構(gòu)、存儲系統(tǒng)及系統(tǒng)原型，介紹該系統(tǒng)的設(shè)計架構(gòu)、關(guān)鍵實現(xiàn)技術(shù)、基本搭建方法，為相關(guān)研究和實踐構(gòu)建一個基礎(chǔ)性的平臺。

[1]Solutio Problematis Ad Geometriam Situs Pertinentis,Commentarii Academiae Scientiarum Impe-Rialis Petropolitanae 8(1736)：128-140.

[2]Euler L.,Solutio Problematis Ad Geometriam Situs Pertinentis,Comm.Acad.Sci.Imp.Petropal,8(1736),138-140 or Opera Ommia Ser.I.,7(1760)：1-10.

[3]Girvan M.Newman M E J.Community Structure in Social and Biological Networks[J].Proc.Natl.Acad.Sci.USA.2002,99(12):7821.

[4]Newman M E J.Fast Algorithm for Detecting Community Structure in Networks[J].Phys.Rev.E.2004,69(6):66133.

[5]Clauset A,Newman M E J,Moore C.Finding Community Structure in Very Large Networks[J].Phys.Rev E.2004,70(6):66111.

[6]Newman M E J.The Structure of Scientific Collaboration Networks[J].Proc.Natl.Acad.Sci.USA.2001,98(2):404.

[7]How fast is Redis.http://redis.io/topics/benchmarks.2015-03-12.

Graph Data Model;Distributed System Architecture;Storage System

Design of a Distributed Graph Computing System Based on Redis

LIU Qing-dian1，WANG Ang1，2，LI Chuan1
（1.College of Computer Science,Sichuan University，Chengdu 610065；2.Alibaba，Hangzhou）

劉慶典（1989-），男，山東臨沂人，碩士，研究方向為數(shù)據(jù)挖掘、分布式計算

2015-12-31

2016-01-20

提出且設(shè)計基于大圖數(shù)據(jù)分割的分布式圖處理系統(tǒng)。該系統(tǒng)解決大圖數(shù)據(jù)的實時讀取、分割，實現(xiàn)大圖數(shù)據(jù)的分布式存儲，且實現(xiàn)圖的可視化模塊與算法。探討該系統(tǒng)的設(shè)計架構(gòu)、關(guān)鍵實現(xiàn)技術(shù)、基本搭建方法。為以后的學術(shù)研究和實踐構(gòu)建一個基礎(chǔ)的平臺。

李川（1977-），男，河南鄭州人，博士，副教授，研究方向為數(shù)據(jù)庫、數(shù)據(jù)挖掘

Presents and designs a distributed processing system based on large graph partitioning.The system solves the problem of large graph data reading and partitioning in real time,and realizes a distributed storage of large graph data,also solves the visualization module and algorithm of graph.Studies the design of the system architecture,key technology and platform structures in order to build a fundamental platform for future academic research and practice.