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

时间 2019-11-15 标签揭秘 redisgraph redis 内嵌高性能内存图数据库

做者 | RedisGraph 开发团队

译者 | 盖磊

编辑 | Emily

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

更多干货内容请关注微信公众号“AI 前线”，（ID：ai-front）

引言

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

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

本文将介绍 RedisGraph 的一些内部设计和特性，并展现其当前所具有的能力。bash

RedisGraph 概览

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

牛刀小试：操做 RedisGraph

为介绍 RedisGraph 的一些关键特性，下面咱们给出一个基于 redis-cli 工具运行的例子。数据结构

构建一个图

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

下面一条命令建立了一个图：性能

图的查询

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

GRAPH.QUERY <graph_id> <query>复制代码

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

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

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

RedisGraph 的支撑理念

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

Hexastore 对图的表示

Hexastore 的结构由一系列三元组组成。其中，每一个三元组包括以下三部分：

主语（Subject）；
谓词（Predicate）；
目标（Object）。

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

(Aldis_Hodge)-[act]->(Straight_Outta_Compton)复制代码

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

该关系的六种可能排列以下：

SPO:Aldis_Hodge:act:Straight_Outta_Compton
SOP:Aldis_Hodge:Straight_Outta_Compton:act
POS:act:Straight_Outta_Compton:Aldis_Hodge
PSO:act:Aldis_Hodge:Straight_Outta_Compton
OPS:Straight_Outta_Compton:act:Aldis_Hodge
OSP:Straight_Outta_Compton:Aldis_Hodge:act复制代码

一旦构建了 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 前线”，（ID：ai-front）