网易杭研 分享 图数据库基础



转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com

AIQ 机器学习大数据 知乎专栏 点击关注

文章作者:温正湖 网易杭研 资深数据库内核专家

内容来源:数据库内核 @知乎专栏

出品社区:DataFun

注:欢迎投稿「行知」,投递方式见文末。

本文尝试以提问回答的方式来介绍笔者所理解的图数据库。包括图数据库的基本定义,图数据库如何表达数据,图数据相比关系型数据库的优势,图数据库使用场景等。

Q:什么是图数据库?

A:图数据库是图数据库管理系统的简称,使用图形化的模型进行查询的数据库,通过节点、边和属性等方式来表示和存储数据,支持增删改查(CRUD)等操作。图数据库一般用于 OLTP 系统中,提供在线事务处理能力。与图数据库对应的是图计算引擎,一般用于 OLAP 系统中,提供基于图的大数据分析能力。

Q:图数据库如何表达数据?或者其建模方式

A:图数据库使用图模型来操作数据。目前使用的图模型有 3 种,分别是属性图(Property Graph)、资源描述框架(RDF)三元组和超图(HyperGraph)。现在较为知名的图数据库主要是基于属性图,更确切得说是带标签的属性图(Labeled-Property Graph),当然标签不是必须的。下面是使用带标签的属性图的 Twitter 用户关系。

属性图由顶点(圆圈)、边(箭头)、属性(key:value)和标签组成,顶点和边可以有标签,比如顶点的标签是 User,边的标签是 FOLLOWS。图中标签为 User 的顶点有 name 属性,属性值为 Johan 或 Peter 或 Emil。边表示了他们的关注关系。图中标签为 FOLLOWS 的边是单向边,如果是相互关注了,那么需要 2 条边表示。

如果不算上标签,属性图自身的关系可以用下图表示:

Q:为什么需要图数据库,相比关系型数据库等有什么优势?

A:因为关系型数据库不擅长处理数据之间的关系。

上图是一个使用关系数据库模型实现的商品交易的例子。如果要做商品推荐相关的查询时,可以发现其中一些查询是低效的(例如,“客户购买了什么产品?”),而有些查询可能是无法完成的(例如,“哪些客户购买了该产品?”)。

Q:能举个更详细的对比例子吗?

A:假设我们要查找某个公司的员工 Alice 属于哪个部门。

在关系型数据库中,一般需要建立员工信息表,员工和部门对应关系表(假设一个员工可以属于多个部门),部门信息表。查找时需分为 3 步:

A,先要通过员工信息表找到 Alice 对应的工号;

B,再使用工号去关系表中找到其对应的部门 ID;

C,最后使用部门 ID 在部门信息表中找到部门名称等信息。

A 需要一次索引查找过程,B 也需要一次索引查找,C 可能需要 3 次索引查找。如果是个大型公司,员工数万甚至十多万,那么员工和部门对应关系表的记录会非常多,B 的查找效率会远低于 A 和 C。

但如果在图数据库中,就不需要那么复杂的查询。这正是因为图数据库与关系型数据库的建模方式不同,或者说数据的存储方式不同。在图数据库中,员工和部门都在同一张图中,通过边直接建立关系。在查找时也是分为 3 步:

a,先通过在员工标签 Person 上建立的全局索引(可稀疏)来找到 Alice 对应的节点 Na;

b,再通过 Na 节点保存的标签为 BELONGS_TO 的边来找到对应的部门;

c,最后读取部门信息。

虽然也可以分为 3 步,但效率却大不相同。a 的效率基本等价于 A;b 无需进行索引查找,直接可以通过 Na 节点获取,虽然 Na 节点可能存在非常多不同标签的边,但跟员工和部门关系表的记录数肯定不是一个数量级的,而且通过 Na 查找边时还可以走 Na 节点的局部索引来加速查找;c 的效率不同的图数据库会有所不同,对于支持免索引邻接的 Neo4J 等图数据库,Na 直接指向 3 个部门节点的物理地址,对于其他非原生图存储的数据库,比如 JanusGraph,需要查找在部门标签 Department 上建立的全局索引。

Q:有具体的性能测试数据不?

A:我们举最经典的社交网络中查询的性能作为对比。

上图为一个社交网络,图中包括了朋友、同事、夫妻和恋人等多种关系。有人曾做过一个测试:在一个包含 100w 人,每人约有 50 个朋友的社交网络中找到最大深度为 5 的朋友的朋友。下图为图数据库 Neo4J 和关系型数据库在寻找扩展朋友时的性能对比。

从图中可以发现,深度为 2 时(即朋友的朋友),两种数据库性能相差不是很明显;深度为 3 时,很明显,关系型数据库的响应时间 30s,已经变得不可接受了;深度到 4 时,关系数据库需要近半个小时才能返回结果,已经妄称在线数据处理系统了;深度到 5 时,关系型数据库已经掉入深渊。而对于图数据库 Neo4J,深度从 3 到 5,其响应时间均在 3 秒以内。

可以看出,对于图数据库来说,数据量越大,越复杂的关联查询,约有利于体现其优势。从深度为 4/5 的查询结果我们可以看出,图数据库返回了整个社交网络一半以上的人数。

Q:除了性能好,图数据库还有其他优势吗?

A:除了很显而易见的性能优势外,灵活性和敏捷性也是图数据库相比关系型数据库的重要优势。图天生就是灵活可扩展的,可以对已存在的图结构增加新的边、节点、标签和子图,但却不会破坏现有的查询和应用程序的功能。这就使我们无需在项目之初,对数据的真实模样和复杂度缺乏了解的情况下被迫设计成最终而完整的数据模型,往往这样的模型并不是最终和完整的。

另一方面,有些业务本身就是灵活多变的,或者说敏捷的。使用图数据库(或其他 NoSQL 数据库,比如 MongoDB)可以快速跟上业务的变化而不需要进行 Schema 变更等代价不菲的管理操作。

Q:图数据库怎么使用,用 SQL 做增删改查吗?

A:图数据库不使用最传统的 SQL 作为 CRUD 语言,原因是 SQL 作为关系型数据库的查询语言,其也不擅长表达 Join 等关系查询和操作,在需要做多层的关系 Join 查询时,SQL 往往冗长而难以直观得理解。这是为什么不采用大家最为熟知的 SQL 却要引入新的图查询语言的主要原因。举个对比的例子:

在英文中“I love my younger sister as well as my grandmother on my father’s side”,与中文的“我爱我的妹妹和奶奶” 是一样的意思,但是在简洁程度上中文远远好于英文。(6 个词,9 个字) vs (14 个词, 70 个字)

也就是说,在图数据库中使用专门的图查询语言比使用 SQL 更加高效。目前主流的图查询语言是 Cypher 和 Gremlin。

Q:目前有哪些比较知名的图数据库?

A:图数据库跟其他数据库一样,有很多种分类方法,本文以是否“完全”开发源代码为标准来分为 2 类,并举 2 个最有代表性的例子,分别是 Neo4J 和 JanusGraph。

Neo4J 最主流的图数据库,相比其他数据库更加成熟,Neo4J 使用 Java 开发,支持 ACID,最新版本是 3.3.5。每个版本均有社区版和企业版,其中社区版是免费版,基于 GPLv3 协议开源,但局限于单机部署,功能受限。企业版包括了 Neo4J 所有功能,包括主从复制用于高可用和读写分离,可视化管理工具等,但增加了商业协议,需付费使用。Neo4J 不是分布式数据库,扩展性不是其优势。但它是一种原生的图数据库,同时也具备了图分析引擎的能力。应该说 Neo4J 是目前使用最为广泛的图数据库,大量介绍图数据库的书籍都是以 Neo4J 为基础来介绍的。

Neo4J 使用 Cypher 作为图数据库查询语言,由于 Neo4J 的成功,Cypher 目前被大多数图数据库所支持。Cypher 语言例子如下(找出所有 Johan 所关注的人所关注的人,该人也是 Johan 关注的人):

MATCH (a:Person {name:‘Johan’})-[:FOLLOWS]->(b)-[:FOLLOWS]->(c),

             (a)-[:FOLLOWS]->(c)  

RETURN b, c

JanusGraph 源于 Titan,最新版本 0.3.1 于 2018 年 10 月发布,基于 Apache 2 开源协议,是最有前景的开源图数据库,可支持数十亿级别的顶点和边规模,与 Neo4J 一样也使用 Java 开发,由 IBM 主导并提供云服务。

JanusGraph 可以为不断增大的数据和用户量提供了弹性和线性的扩展能力,通过数据多点分布和复制来提高性能和容错能力;支持 ACID 特性和最终一致性。与 Neo4J 不同,JanusGraph 不是原生的图数据库,相反的,其将数据存储到通用的存储系统上,支持的后端存储包括:Apache Cassandra、Apache HBase、Google Cloud Bigtable 和 Oracle BerkeleyDB。其中 BerkeleyDB 一般只做例子演示用。

JanusGraph 依托于 Apache 社区构建了完整的图数据库和图计算能力,通过跟 Apache 中其他组件相配合,提供了一整套完整的图计算生态系统。其中就包括了 Apache TinkerPop 所提供的图查询语言 Gremlin。Cypher 例子对应的查询在 Gremlin 中的表示方式如下:

g.V().has(‘User’,‘name’,‘Johan’).out(‘FOLLOWS’).as(‘b’).out(‘FOLLOWS’).as(‘c’).in(‘FOLLOWS’).has(‘User’,‘name’,‘Johan’).select(‘b’,‘c’).valueMap()

Q:上面提到了原生图数据库,这是什么意思?

A:上面说的原生又可细分为原生图存储和原生图处理,其中原生图存储指的是图数据库,比如 Neo4J 所使用的后端存储是专门为 Neo4J 这种图数据库定制和优化的,理论上说能更有利于发挥图数据库的性能。而非原生图存储指的是图数据库,比如 JanusGraph 使用通用的 NoSQL 数据库比如 HBase 来保存序列化后的图数据。

而原生图处理指的是利用了免索引邻接的图数据库。免索引邻接是指通过边关联的 2 个节点,其彼此指向是物理的,也就是通过边访问一个节点时,该边保存的就是目标节点在磁盘上的物理地址,这样就需要通过索引去找到目标节点,如果边很多的时候,对性能提升很有帮助。

Q:那么目前有哪些公司使用了图数据库呢?

A:使用图数据库的公司比比皆是,分布式各个行业。举例如下:

根据 Neo4J 官方描述,上述公司都使用了其产品,更多公司可点击链接:https://neo4j.com/customers/?ref=home

根据 JanusGraph 官网描述,上述公司用了 JanusGraph,附上链接:http://janusgraph.org/  

Q:看起来使用图数据库的公司确实不少啊,能归个类不?

A:图数据库确实有很广泛的适用场景,因为连接存在于自然和社会中的各个角落。每个事物都不是孤立的,而是跟其他事物或紧或松得联系着。随着人类社会的进步,各种关系的处理变得越来越重要,不仅是人,物与物之间的连接关系也越来越被我们所重视,万物互联的时代已经到来。下面举六个图数据库最常使用的场景。

一、社交网络应用

社交是人与人之间的连接,以图数据模型为内在的图数据库天生适用于明显的以联系为中心的领域。在社交网络中使用图数据库可以方便得识别人 / 群组和他们交流的事物之间的直接或间接的联系,使用户能够高效地对其他人或事物进行打分、评论、发现彼此存在的关系和共同关系的事情。可以更加直观得了解社交网络中人与人之间如何互动、如何关联、如何以群组的形式来做事情或选择。

社交网络是最基础的图模型,在此基础上可以叠加更多的内容,比如个人的喜好、购买过的物品、日常的生活方式等,从而演化出更高级的图数据库应用模式,比如实时推荐系统。

二、实时推荐

在零售、招聘、情绪分析、搜索和知识管理领域,社交网络和推荐引擎可以提供关键的差异化能力,有很多种办法可以实现推荐,但使用图数据库在实时性和效率上有其特有的优势。推荐算法在人和事物之间建立联系,而联系建立的基础是用户的行为,比如购买、生产、消费、打分或评论有关资源等行为。推荐引擎可以识别出某些资源会吸引特定个人或群体,或者某些个人或群体可能对特定资源感兴趣。

一个有效的推荐依赖于对事物之间关联的理解,同时也依赖于这些关联的质量和强度,而属性图是所有这些关系密切、关联紧密的数据结构的最佳表达方式。用图数据库存储和查询这些数据使得应用程序可以为最终用户呈现实时结果,反映数据最新的变化,而不是返回给用户那些预计算的状态结果。

三、地理空间管理

地理空间类的应用程序包括公路网、铁路网等,地理空间操作依赖于特定的数据结构,简单的加权带方向的联系,复杂到空间索引如 R 树。和索引一样,这些数据结构天生就以图的形式呈现,尤其是层级结构,非常适合图数据库。

总的来说,通信、物流、旅游已经路由计算相关领域的地理空间应用经常会使用图数据库。

四、主数据管理(Master Data Managerment)

在企业或组织中,主数据管理 (MDM) 包括的数据涉及用户、客户、产品、供应商、部门、区域、站点、成本中心和业务单元等。这些数据来源可能是多种多样的,MDM 用来识别、清洗、存储和管理这些数据。其关键问题包括谁组织结构的变化、企业合并和业务规则的变化来管理这些变化;融合新的数据源,用外部源数据补充已有的数据;解决报告需求、鉴定需求和商业智能客户的需求;当数据的值和模式变化时对数据进行版本管理。图数据库的数据模型高效匹配 MDM 的快速演变和不断变化的业务需求。

五、网络和数据中心管理

图数据库已经成功地使用在了电信、网络管理和分析、云平台管理、数据中心和 IT 资产管理以及网络影响分析等领域。在这些领域里,他们将影响分析和问题解决的时间时间从数天数小时减少到了分钟级甚至秒级。面对不断变化的网络模式,图数据库的性能和灵活性都是它适合这些领域应用的重要因素。

六、授权和访问控制

图数据库可以存储那些复杂的、高度关联的、跨越数十亿参与者和资源的访问控制结构。尤其适用于内容管理、联合授权服务、社交网络偏好已经软件服务化提供。将这些系统从关系型数据库切换到图数据库后,性能从分钟级提升到毫秒级。

上面仅列举了部分例子,除此之外,图数据库产品还广泛用在金融和保险行业反欺诈、风控,电商和社交类产品防机器人作弊等领域。

总结

图数据库是一种越来越受关注的新型 NoSQL 数据库,图数据库研究和实践相关的论文占据了数据库领域顶尖会议和期刊中很重要的部分。目前国内有些企业也已推出了自己的图数据库系统,有自主研发的,也有基于开源图数据进行优化的。作为数据库从业人员,有必要对图数据库有最基本的了解。本文以问题驱动的方式简单介绍图数据库,希望对大家了解图数据库有所帮助。

作者介绍:

温正湖,网易杭研资深数据库内核专家。《MySQL 内核:InnoDB 存储引擎 卷 1》作者之一,申请技术专利 10+,已授权 5+。曾主导了网易公有云 RDS、MongoDB 等数据库云服务建设,现负责网易 MySQL 分支 InnoSQL 开发和维护,专注于数据库内核技术和分布式系统架构。


更多高质资源 尽在AIQ 机器学习大数据 知乎专栏 点击关注

转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com