一个基于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所有邻居，并根据条件对邻居进行过滤。这与上一种模式类似，但在实际应用中这种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.