揭秘RedisGraph:Redis内嵌高性能内存图数据库

作者 | RedisGraph 开发团队

译者 | 盖磊

编辑 | Emily

AI 前线导读:RedisGraph 在 Redis 上实现了一种高性能内存图数据库。该项目作为 Redis 模块开源提供,支持 openCyper 查询语言,可完成图的创建、查询、条件匹配等操作。为支持高效的图搜索操作,RedisGraph 底层实现了一种称为 Hexastore 的三元组存储结构。本文介绍了 RedisGraph 的一些内部设计和特性,并展示其当前所具备的能力。

更多干货内容请关注微信公众号“AI 前线”,(ID:ai-front)

引言

当前,基于图结构的数据(以下简称为“图数据”)无处不在。Facebook、Twitter 和 Pinterest 等企业已经看到并最大化地利用了这些相互关联数据的强大之处。这直接导致了对图数据解决方案关注度的提升,各种解决方案也与日俱增。

Redis 可加载模块系统的推出,使我们意识到在 Redis 工具集中引入图数据结构的巨大潜力。Redis 采用原生 C 语言实现,侧重于提供高性能特性。现在我们通过开发 Redis,为其新引入了图数据库能力。RedisGraph 以开源项目提供在 GitHub 上。

本文将介绍 RedisGraph 的一些内部设计和特性,并展示其当前所具备的能力。

RedisGraph 概览

RedisGraph 是一种基于 Redis 全新设计实现的图数据库。它使用了新的 Redis Modules API,扩展 Redis 并提供了一些新的命令和功能。其主要特性包括:简单且快速的索引和查询、在内存中存储数据、使用了定制的内存高效数据结构、基于磁盘的数据持久化、以数据表形式给出的结果集、支持简单并广为使用的图查询语言 Cypher,以及数据的过滤、聚合和排序等。

牛刀小试:操作 RedisGraph

为介绍 RedisGraph 的一些关键特性,下面我们给出一个基于 redis-cli 工具运行的例子。

构建一个图

实体通常表示为图中的节点。本例创建了一个小规模的图,图中的实体为演员和电影,以“参演”关系连接参演电影的演员和电影。使用 GRAPH.QUERY 命令发布 CREATE 语句的格式如下,该语句实现将新的实体和关系添加到一个图中。

下面一条命令创建了一个图:

图的查询

RedisGraph 实现了 openCypher 图查询语言的一个子集。尽管其中仅支持该语言的数个功能,但是对于从图中抽取有用的信息而言,这些功能是完全够用的。使用 GRAPH.QUERY 命令执行查询的命令格式为:

下面我们在所创建的电影图数据上执行一系列查询。

其中,第一行是结果集的头部信息,按 RETURN 语句命名各个列。第二行中包含了查询的结果。

第二个查询是找出每位演员参演了多少部电影。

RedisGraph 的支撑理念

不同的图数据库,可能采用了不同的结构表示图。有的使用了邻接列表,也有的使用了邻接矩阵。每种表示结构都有其自身的优劣之处。对于 RedisGraph 而言,关键在于给出一种支持对图做快速搜索的数据结构。我们使用了一种称为“Hexastore”的结构保存图中的所有关系。

Hexastore 对图的表示

Hexastore 的结构由一系列三元组组成。其中,每个三元组包括如下三部分:

主语(Subject);

谓词(Predicate);

目标(Object)。

主语表示源节点,谓词表示关系,目标表示目的节点。对于图中的每条关系,Hexastore 将保存源节点、关系边和目的节点间所有可能存在的六种排列。以下面这条关系为例:

其中, Aldis_Hodge 是源节点,act 是关系,Straight_Outta_Compton 是目标节点。

该关系的六种可能排列如下:

一旦构建了 Hexastore,我们可以轻易地实现图搜索。例如,如果要查找“Straight Outta Compton”电影中的演员,那么可以实现为搜索 Hexastore 中所有包含前缀 OPS:Straight_Outta_Compton:act:* 的字符串。

如果要查找 Aldis Hodge 参演的所有电影,那么可以实现为查找所有包含前缀 SPO:Aldis_Hodge:act:* 的字符串。

尽管 Hexastore 会占用大量的内存,因为每条关系表示为六个三元组,但是这样的三元组数据结构不仅支持快速搜索,而且可以高效地使用内存,因为它并不会重复地生成已有的字符串前缀。

openCypher 查询语言

目前已经存在着一些图查询语言,我们并不想重新造轮子,实现我们自己的语言。因此,我们决定实现最广为使用的图查询语言 openCyper 的一个子集。尽管 Open-Cypher 项目提供的语言解析器创建方法易于使用,但我们还是决定创建我们自己的解析器。该解析器使用 Lex 作为分词器,并使用 Lemon 生成 C 目标解析器。

正如上面所提及的,我们目前只支持该语言的一个子集。我们将会继续添加一些新能力,并扩展语言。

运行时的查询执行

下面,我们介绍 RedisGraph 中的模块在执行查询中的操作步骤。以下面的查询为例,该查询找出所有 30 岁以上并与 Aldis Hodge 共同参演过影片的演员:

RedisGraph 将解析查询、构建抽象语法树、构建执行计划(由标签扫描操作、Filter 操作、Expand 操作、Expand into 操作等组成的)、执行计划、将匹配的实体属性添加到结果集中。

查询解析器

对于一个给定的有效查询,解析器将会生成抽象语法树。下列六类语句,会在抽象语法树中分别生成对应的主节点:

MATCH

CREATE

DELETE

WHERE

RETURN

ORDER

生成抽象语法树,是一种描述和结构化语言的通用方法。

过滤树

查询通过创建谓词过滤出实体。以上面的查询为例,其中需要过滤掉小于 30 岁的演员。在查询中,可以使用 OR、AND 等关键字组合谓词构造粒度条件。在运行时会根据 WHERE 语句构建过滤树。过滤树中的每个节点可以表示一个条件(例如 A>B),也可以表示一个操作(AND 或 OR)。候选实体将通过过滤树进行求值。

查询处理

MATCH 语句描述了被查询实体(即节点)间的关系。节点可以具有别名,以支持执行查询生命周期后期的引用(WHERE、RETURN 语句)。但是,最终还必须为所有的节点指定一个 ID。对节点指定 ID 过程称为搜索阶段。

搜索阶段根据 MATCH 语句查询 Hexastore,找出所有的 ID。以上面的查询为例,搜索阶段以查找 Aldis Hodge 参演的电影为开始。对于所搜索到的每部电影扩展搜索,找到当前电影的参演演员。

这样的搜索过程可以看成是一个遍历图的迭代过程。该迭代过程在每一步发现一个新 ID。一旦节点指定了 ID,就可以确认当前的实体符合过滤语句的条件。这时可以抽取 RETURN 语句中指定的请求属性,并将新纪录添加到最终结果集中。

基准测试

插入一条新关系的复杂度是 O(1),RedisGraph 可以在 1 秒内创建 10 万条新关系。在不同的底层硬件上,测试结果可能会存在差异。

检索数据的性能完全取决于图的规模,以及所执行的查询类型。对于一个小规模图,例如约 1000 个实体、2500 条边,RedisGraph 每秒可执行约 6.5 万次的“朋友的朋友”(FOAF)查询。

需要指出的是,除了 Hexastore 之外,我们并未对实体做索引。未来我们将实现实体索引,这将会极大地降低查询执行时间。

许可情况

Redis-Graph 以 AGPL-3.0 许可发布。

结束语

RedisGraph 项目尽管推出不久,但它已经可以作为图数据库的一个替代选项。RedisGraph 支持的操作子集可以分析并探索图数据。作为一个 Redis 模块,所有 Redis 客户无需做出任何调整就可以使用该模块功能。我们考虑继续改进,并在开源社区的帮助下进一步扩展 RedisGraph。

查看英文原文:

http://redisgraph.io/design/

AI前线

紧跟前沿的AI技术社群

一些粉丝朋友还没有养成阅读后点赞的习惯,希望大家在阅读后顺便点赞,以示鼓励!原创是一种信仰,专注是一种态度!

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180326G1GA4Q00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券