一個基于Redis架構的分布式圖計算系統設計

劉慶典，王昂,2，李川

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

一個基于Redis架構的分布式圖計算系統設計

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

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

圖數據模型；分布式系統架構；存儲系統

0　引言

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

1　定義

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

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

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

2　圖訪問模型

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

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

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

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

3　系統架構

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

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

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

圖1　系統架構

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

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

4　存儲系統

本文使用基于內存的鍵值數據庫Redis來存儲圖基礎數據、分配信息和其他系統信息。數據會定期從內存備份到硬盤，以避免數據丟失。之所以選擇Redis作為基礎數據存儲因為以下原因：

（1）訪問速度快

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

（2）支持豐富的數據類型

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

（3）操作具有原子性

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

（4）豐富的工具

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

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

5　可視化模塊

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

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

圖2　可視化模塊顯示結果

表1　數據集

6　結語

本文提出了基于圖數據模型的分布式大圖系統架構、存儲系統及系統原型，介紹該系統的設計架構、關鍵實現技術、基本搭建方法，為相關研究和實踐構建一個基礎性的平臺。

[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-），男，山東臨沂人，碩士，研究方向為數據挖掘、分布式計算

2015-12-31

2016-01-20

提出且設計基于大圖數據分割的分布式圖處理系統。該系統解決大圖數據的實時讀取、分割，實現大圖數據的分布式存儲，且實現圖的可視化模塊與算法。探討該系統的設計架構、關鍵實現技術、基本搭建方法。為以后的學術研究和實踐構建一個基礎的平臺。

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

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.