技术与标准丨图数据库技术发展趋势研究

  • A+
所属分类:云安全

摘要大数据时代,数据间的关联蕴藏着重要的商业价值,如何在海量数据中挖掘关联信息是企业的一大挑战,图数据库应运而生并飞速发展。围绕图数据库,介绍了基础定义、技术架构、图数据库计算特点等概念,梳理了国内外图数据库产业侧的发展现状,最后总结了图数据库技术未来发展趋势。

关键词:图数据库;数据价值;关联分析


引言

当前,互联网、物联网、金融等领域中积累了海量的数据,数据间的关联可以产生重要的价值。随着大数据技术的不断发展,如何汇集各个领域数据、通过数据间的关联与分析挖掘海量数据的价值成为了各行业关注的重点。在技术的探索中,图处理技术为数据赋能提供了新的方式,可驱动行业更好地发展。图数据通过将实体与关系点变化的方式将知识结构化保存,是一种基于事务关联关系的模型表达,具有数据天然可解释性,备受学术界和工业界推崇。在数据的关联分析中,传统的关系型数据库需要进行大量的关联操作,在小规模数据的情况下这样的操作还可以接受,但是当数据规模逐渐增大,关联操作会造成性能呈指数级下降。图数据库相较于传统关系型数据库和NoSQL数据库,其丰富完整的关系表达提供了高效的关联查询和完备的实体信息。

大型互联网公司很早便开始创建自己专有的图处理技术及图数据库系统,用于社交关系挖掘、网页检索与排序、推荐系统等,并获得了巨大的商业成功。目前,通信、互联网、电子商务、社交网络和物联网等领域中积累了大量的图数据,其规模巨大并且不断增长:Facebook的社交网络规模在2011年已超过8 亿顶点;而腾讯QQ的社交网络目前在10 亿个顶点的规模;在电信行业中,广州市仅一个月内由电话呼叫方和被呼叫方组成的图的规模就超过4.5 千万个顶点、1.5 亿条边;而ClueWeb[1]数据包含海量的网页,其于2012年公布的数据集已经达到10 亿个顶点、425 亿条边的规模,仅是存储边的列表文件就超过400 GB。但是,相比其他的数据库技术,目前图数据库还处于起步阶段,各方面的技术概念还未统一,应用场景仍在探索,选型实施资料较少。本文将首先围绕图数据库技术给出图数据库相关定义,从技术路线和性能进行图数据库与传统关系型数据库的对比研究;然后,介绍国内外图数据库产业发展现状与应用场景;最后,根据产业现状给出图数据库的一些未来发展趋势研判。


图数据库概述

图数据库以图论为理论基础,使用图模型,将关联数据的实体作为顶点存储,关系作为边存储,解决了数据复杂关联带来的严重随机访问问题。在分类上,图数据库可归类为NoSQL数据库。

2.1图模型

图是一组对象的集合,由顶点和边构成,顶点表示实体或实例,如人、账号、组织、业务等,它们可以类比于关系型数据库里的记录或行,或文档数据库里的文档;边是连接顶点的线,表示顶点之间的关联关系。边是图数据库中的关键概念,在关系型数据库或文档存储数据库中,没有对边的抽象概念进行直接实现。图模型主要包含属性图、资源描述框架(Resource Description Framework,RDF)图两种(见图1)。
技术与标准丨图数据库技术发展趋势研究

图1  图模型示意图

2.2图数据库定义

图数据库基于图模型,对图数据进行存储、操作和访问,与关系型数据库中的联机事务处理(Online Transactional Processing,OLTP)数据库是类似的,支持事务、可持久化等特性。图数据库根据底层存储实现的不同,可分为原生图数据库和非原生图数据库两种。

  1. 原生图数据库:使用图模型进行数据存储,可以针对图数据做优化,从而带来更好的性能,例如 Neo4j。

  2. 非原生图数据库:底层存储使用非图模型进行存储,在存储之上封装图的语义,进行图处理,其优点是易于开发,适合产品众多的大型公司,形成相互配合的产品栈,例如Titan、JanusGraph底层采用KV存储非图模型。

相较关系型数据库,图数据库基于图模型存储和处理的方式主要有以下优势。

  1. 万物互联,图数据可以更直观地表达数据之间的关联关系。

  2. 图数据有强兼容性,可以更容易地存储、扩展多种类型的数据。

  3. 对关系数据的处理效率是关系型数据库的2~3个数量级。

Ian Robinson等曾经在5000 万点和边的数据规模下,对比了Neo4j与关系型数据库在关联查询的时间消耗(见表1),随着关联查询深度的增加,关系型数据库性能消耗呈指数倍增长甚至无法执行。

表1  Neo4j与某关系型数据库在关联查询的性能对比

技术与标准丨图数据库技术发展趋势研究

2.3图数据库技术架构

当前,市场上主流的图数据库主体架构如图2所示,分为存储层、计算层和接口层。

技术与标准丨图数据库技术发展趋势研究

图2  图数据库系统架

( 1 ) 存储层:图数据库有原生和非原生两种存储方式,这些数据通过图存储引擎进行图数据结构、索引逻辑上的管理。例如,原生图数据库中常使用链表或者B+树、LSM树(Log-Structured Merge-Tree,日志结构合并树)等树状结构存储图数据;而非原生图数据库一般复用外部NoSQL数据库进行数据存储,然后通过存储引擎将实际的数据以图数据的逻辑进行管理。

( 2 ) 计算层:提供对操作的处理和计算,主要工作是基础图算法的实现,其次也包括数据库通用的语法解析、任务调度、事务管理、优化器等组件。目前,大多数图数据库只能提供基础图算法,复杂的全图分析可能需要图处理引擎对接进行。

( 3 ) 接口层:提供了查询语言接口、API、SDK、可视化组件等对外提供服务。当前,图数据库没有统一的查询语言,因此图数据库产品在提供其原有查询语言外,也可能会提供Cypher、Gremlin等主流查询语言接口便于用户使用。此外,图数据的天然可解释性使得大多数图数据库产品也会提供一定的可视化能力,在数据库层面直观地为用户展现数据间的关联情况。


图数据库的计算

图数据库的使用场景主要为实时查询,包括本地查询、邻居查询和局部遍历。用户通过图查询语言在图上进行遍历、过滤和统计等操作,以满足实时的需求。此外,用户常常会提出比实时查询更为复杂的分析需求以挖掘图数据中的潜在价值。在图算法的实现上,最理想化的选择是在图数据库上直接实现图算法,但由于图数据库更侧重于高并发和海量存储,全图算法更侧重于迭代计算,因此目前更为常见的选择是提供另外的图处理引擎与图数据库集成(见图3):从图数据库对接或导入数据到图处理引擎中进行离线分析,结合其更为强大的计算能力对全图进行迭代计算,寻找某种特定模式(社区发现或欺诈模式)或者路径,满足数据挖掘的应用需求。

技术与标准丨图数据库技术发展趋势研究

图3  图数据库实时查询与离线分析

3.1实时查询

数据库为实时查询提供了两类常用的图算法。

( 1 ) 图遍历:也被称为图搜索,是指访问图中每个顶点的过程,对图的访问和更新都以图遍历为基础。图遍历常见算法包括广度优先搜索和深度优先搜索。

( 2 ) 路径发现:用以识别最符合大型网络中两点之间某些条件下的最短路径。路径发现常见算法包括最短路径、最小权重生成树和两两最短路径。

3.2离线分析

离线分析需要较长的时间来完成,分析的算法也相对复杂,可根据解决问题的目的不同分为以下几类。

  1. 中心性:是社交网络分析中常用的一个概念,用以表达社交网络中一个点或者一个人在整个网络中所在中心的程度。通过知道一个顶点的中心性,可以用来了解和判断该顶点在网络中所占据的重要性。中心性常见算法包括佩奇排名、中介中心性、紧密度中心性和调和中心性。

  2. 社群发现:用以划分复杂网络的社群结构。在复杂网络的研究中,如果网络的顶点可以被容易地分组成顶点集,且使得每组顶点在内部密集连接,则称网络具有社群结构。这意味着社群内的点的连接更为紧密,社群间的连接较为稀疏。社群发现常见算法包括Louvain算法和标签传播算法。

  3. 图挖掘:是基于图的数据挖掘,用来发现数据的模式。通过分析图数据,发现有趣、意外、有用的模式是非常必要的,可以用来帮助理解数据或作出决策,在社交网络、医药化学、交通运输网络等诸多领域中有着重要意义。常用的图挖掘算法包括频繁子图和数三角形。

随着人工智能技术的发展,机器学习、深度学习、神经网络等算法也可通过图处理引擎分析图数据库中的数据价值。当前,国际主流的图处理引擎包括GraphX、GraphLab、Giraph等(见表2)。

表2  3类图处理引擎

技术与标准丨图数据库技术发展趋势研究


国内外图数据库产业发展现状

根据第三方机构db-engines.com[3]的统计数据,近年来各类别数据库中图数据库受欢迎程度可谓是水涨船高,在学术界和工业界均是讨论热点。在工业界,自2007年第一款图数据库Neo4j问世开始,图数据库技术便不断更新迭代并涌现了大批竞争者,到如今发展不过短短十余年,就已经历了底层存储、架构等技术方面的重大变革,由最初的单机图数据库向分布式大规模图数据库发展。

( 1 ) Graph 1.0:小规模原生图存储

Graph 1.0时代(2007—2010年),以Neo4j为代表,采用原生图的方式实现图存储,获得了比关系型数据库快得多的复杂关联数据查询性能。然而,当时在软件架构设计上只支持单机部署,图数据库产品性能和业务扩展能力有限。

( 2 ) Graph 2.0:分布式大规模图存储

Graph2.0时代(2010年至今),随着大数据和物联网的蓬勃发展,数据本身的丰富程度增加,数据之间的关联性增多,扩展性成为数据库行业共同的痛点,分布式架构的兴起催生了很多的分布式图数据库项目。在这一发展阶段,支持分布式大规模图存储是关注的重点,图存储是否以原生的方式实现,不再是那么重要的问题,例如OrientDB选择了支持原生图存储,自研了分布式图数据存储模块,而JanusGraph则是在其他数据库(Cassandra、HBase等)之上封装实现图的语义。通过支持在通用硬件上进行水平扩展,分布式图数据库具备了在海量关联关系数据的存储与实时深度查询上绝佳的性能,但是在全图分析等需要迭代计算的场景下仍需要结合图处理引擎进行离线计算与分析。

目前,国外图数据库市场上开源、商用图数据库并驾齐 驱,其中开源图数据库有Neo4j、JanusGraph、ArangoDB等,商用图数据库有Neptune(亚马逊)、Cosmos(微软)、TigerGraph等。而我国图数据库产业发展也随着时代的更替而蓬勃发展,产品形态丰富。总体来看,国内数据库产品在大数据时代起步发展,有向分布式发展的需求与趋势,强调对实时复杂图查询的性能要求,多使用自研的查询语言,部分产品支持Cypher或Gremlin等查询语言。经中国信息通信研究院的详细调研及初步估计,当前国内的图数据库已有20 余款产品,主要由4 类研发主体发起,其特点如下。

  1. 各大高校实验室、研究所在图数据库发展初期研究开发的数据库产品,主要聚焦于支持RDF图模型的图数据库。

  2. 大型互联网企业由于自身积累的海量数据以及业务需求,催生了相关的数据库产品。这些产品考虑到企业原有数据系统的情况,结合原有数据系统而开发的非原生图数据库不在少数,但绝大多数使用分布式架构以供企业内部使用,产品迭代较快,当前也有部分产品实现了商业化。

  3. 新兴创业公司的图数据库产品,其最大特点是完全自主研发,强调高性能与数据库的事务性,但是产品版本更新迭代相对较少,目前也在往分布式架构发展。

  4. 传统IT服务商在图数据库的发展浪潮下,也加快了图数据库产品的研发步伐,并且通常与企业已有的其它产品(例如知识图谱工具)一同对外输出。



图数据库发展趋势

目前,图数据库正处于飞速发展的状态,随着概念的普及、需求的变化,图数据库正在向如下方向发展。

5.1查询语言统一化

目前,图数据库市场查询语言不一,有使用Gremlin、Cypher、SPARQL的,也有使用自己开发定义的查询语言。用户在业务中使用图数据库时学习成本高,对图数据库产品的推广带来一定的阻碍。同时,国际上ISO/IEC的GQL制定耗时4年,与当前图数据库市场的发展速度严重不匹配。如何解决这一问题已是厂商与用户共同关注的问题。

5.2图数据库与图处理引擎融合化

现今图数据库只能提供较简单的图算法进行实时查询,不能独立完成复杂的全图迭代计算,需要与图处理引擎结合,增加了额外的处理过程,加重了系统负担。当前,分布式图数据库支持了更大规模的数据,同时通过优化保证了查询的高性能,未来与图处理引擎深度融合从而为用户提供更简单、更复杂的计算能力是图数据库厂商的研发方向。此外,图神经网络理论与技术的飞速发展也值得关注。

4.3软硬件一体化

图数据库数据非规则访问的特性一直是性能提升的重要瓶颈,随着图切分、图算法的不断提升,图数据库对底层硬件的需求愈加迫切,将来可以通过软硬件协同设计的方式,比如采用NVM(非易失性存储器)减少持久化存储的开销,使用RDMA(远程直接数据存取)增强通信效率,或者将事务的部分要求交给硬件(例如HTM)来控制、简化软件设计等。


结束语

本文给出了图数据库的基本定义和通用架构,介绍了图数据库的数据处理方式和相关算法,通过调研对国内外图数据库产业发展进行了梳理和阐述,同时提出了产业侧未来的一些发展趋势。现在,图数据库产品还在起步初期,技术能力还在飞速变革,应用市场也在不断的探索扩展。当前,图数据库在知识图谱、社交网络、金融领域等均有不俗表现,随着5G时代的到来,万物互联的概念越发深入人心,图数据正是这种关联方式最直接的表达。但是,图数据库产业的发展仍需要标准化工作来找寻正确的方向,普及观点、规范产品能力依然是产业当前的重中之重。

参考文献:

1.The Lemur Project. The ClueWeb12 dataset: dataset details[EB/OL]. [2020-08-10]. http:// lemurproject.org/clueweb12/specs.php.

2.Ian Robinson, Jim Webber, Emil Eifrem. 图数据库[M]. 北京: 人民邮电出版社, 2015.

3.DB-Engines. DB-Engines ranking[EB/OL]. [2020-08-10]. https://db-engines.com/en/ranking.

Research on technology development trend of graph database

LI Junyi,WANG Zhuo, MA Pengwei

(Cloud Computing & Big Data Research Institute, China Academy of Information and Communications Technology, Beijing 100191, China)

Abstract: In the era of big data, the association between data contains important commercial value. How to mine the associated information from the massive data is a major challenge for enterprises, and the graph database emerged and developed rapidly. This paper focuses on graph database, introduces concepts such as basic definitions, technical architecture, and graph database calculation characteristics, expounds the development of the industry of graph database, and finally summarizes the future trends of graph database technology.

Keywords: graph database; data value; association and analysis



原文来源:信息通信技术与政策
技术与标准丨图数据库技术发展趋势研究

本文始发于微信公众号(关键基础设施安全应急响应中心):技术与标准丨图数据库技术发展趋势研究

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: