图数据库-架构与算法

《图数据库-架构与算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、14图数据库：架构与算法董小姐我也是个复杂的动物嘴上一句带过心里却一直重复董小姐鼓楼的夜晚时间匆匆陌生的人请给我一支兰州——宋冬野《董小姐》图计算是一类在实际应用中非常常见的计算类别，当数据规模大到一定程度时，如何对其进行高效计算即成为迫切需要解决的问题。最常见的大规模图数据的例子就是互联网网页数据，网页之间通过链接指向形成规模超过500亿节点的巨型网页图。再如，Facebook社交网络也是规模巨大的图，仅好友关系已经形成超过10亿节点、千亿边的巨型图，考虑到Facebook正在将所有的实体数据节点都

2、构建成网状结构，其最终形成的巨型网络数据规模可以想见其规模。要处理如此规模的图数据，传统的单机处理方式显然已经无能为力，必须采用由大规模机器集群构成的并行图数据库。在处理图数据时，其内部存储结构往往采用邻接矩阵或邻接表的方式，图14-1是这两种存储方式的简单例子示意图。在大规模并行图数据库场景下，邻接表的方式更加常用，大部分图数据库和处理框架都采用了这一存储结构。图数据与大数据处理中常见的KV数据相比，有自身独有的特点，这也决定了其处理机制与其他类型的海量数据处理系统有很大的差异。具体而言，图数据的数

3、据局部性很差，相互之间有很密切的关联，具体体现就是图节点所展现出的边，其表征着数据之间的关联。很多自然图的结构遵循PowerLaw规则，满足PowerLaw规则的图数据分布极度不均匀，极少的节点通过大量的边和其他众多的节点发生关联。这给分布式存储和计算带来很大的困难，因为数据局部性差意味着数据分布大数据日知录：算法与架构到集群中的机器时存在潜在的数据分布不均匀或者计算中需要极高的网络通信量等问题。°Adjacency邻接矩阵matrixBCABCDE1∞∞A105B1210AC4D392023946E

4、7657°Adjacency邻接表ListA:(B,10),(D,5)∞∞2B:(C,1),(D,2)DEC:(E,4)D:(B,3),(C,9),(E,2)E:(A,7),(C,6)图14-1图的表示方式由于与图相关的应用形式多种多样，为了能够方便地对现有技术进行系统性的介绍，我们将图数据库分为两类：一类是在线查询类，另一类是离线挖掘类。在线查询类图数据库更关注用户查询低延时响应和系统高可用性，比如，Facebook用户登录时需要将好友列表以及实时变化的信息快速体现到用户交互界面上。离线挖掘类图数据

5、库则更强调数据挖掘等后台处理任务的数据吞吐量及任务完成效率。两者在任务目标上相差很大，这也造成了相关系统设计思路的巨大差异。本章首先以Facebook的TAO为例介绍在线查询类图数据库的基本设计思路，之后将重点放在离线挖掘类图数据库上，分别介绍如何对百亿级别的图数据进行数据分片、图计算的计算范型与编程模型，以及若干具有代表性的图数据库系统。14.1在线查询类图数据库14.1.1三层结构在线查询类图数据库的主要目的往往是给具体应用提供在线数据读写服务，其中尤其关注数据查询类服务，所以更强调系统的高可用性

6、和读写的低延迟。其体系结构一般由底向上可以划分为三层：分布式存储引擎层、图数据管理层和最上端的图操作API层。为了能够处理海量数据，底层的存储引擎往往采用分布式架构，从理论上看，具体使用何种存储引擎没有限制，实际上，这一层采用MySQL数据库居多，主要是可以利用成熟数据库的很多特有功能，比如事务等，这一层只负责数据的存储，分布式管理功能并不在这一层实现。x272第14章图数据库：架构与算法位于中间层的图数据管理层主要起到以下三个作用。其一，对底层分布式存储引擎的管理功能，比如，数据的分片与分发、对查询

7、的路由、系统容错等。其二，图操作逻辑到底层物理存储层读写操作的逻辑转换。图操作逻辑与其他类型的数据操作有较大的差异，比如，经常需要查询图节点之间的关系，为了更好地支持应用，在图数据管理层一般会将数据模型封装成具有图语义的模式，而由于底层存储引擎并不能直接支持这种图语义，所以需要有一个映射和转换过程，比如，若底层存储引擎采用关系数据库，那么需要将图语义转换为对应的若干SQL语句，这样才可能实现底层真正存取数据。其三，在线查询类图数据库往往更注重系统的高可用性和低延迟，其中，读操作的效率更是重中之重。为了

8、达到实时存取的目标，图数据管理层往往会采用优化措施来达到这一目标。最上层的API层主要是封装符合图操作逻辑的对外调用接口函数，以方便应用系统使用在线查询类图数据库。工业界比较知名的在线查询类图数据库包括Twitter的FlockDB和Facebook的TAO，这两者的架构基本符合上述三层体系。FlockDB是Twitter用来存取用户关注关系的图数据库，底层采用MySQL作为存储引擎，中间层采用Gizzard和Gizzmo来进行分布式数据管理，Gizzr