[关闭]
@Rays 2018-03-23T17:17:50.000000Z 字数 4923 阅读 8154

RedisGraph重磅推出: 作为Redis模块的高性能内存图数据库

数据库

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

作者： RedisGraph团队

正文：

引言

当前，基于图结构的数据（以下简称为“图数据”）无处不在。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语句的格式如下，该语句实现将新的实体和关系添加到一个图中。

  1. graph.QUERY <graph_id> 'CREATE (:<label> {<attribute_name>:<attribute_value>,...})'
  1. graph.QUERY <graph_id> 'CREATE (<source_node_alias>)-[<relation> {<attribute_name>:<attribute_value>,...}]->(<dest_node_alias>)'

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

  1. graph.QUERY IMDB 'CREATE (aldis:actor {name: "Aldis Hodge", birth_year: 1986}),
  2.                          (oshea:actor {name: "OShea Jackson", birth_year: 1991}),
  3.                          (corey:actor {name: "Corey Hawkins", birth_year: 1988}),
  4.                          (neil:actor {name: "Neil Brown", birthyear: 1980}),
  5.                          (compton:movie {title: "Straight Outta Compton", genre: "Biography", votes: 127258, rating: 7.9, year: 2015}),
  6.                          (neveregoback:movie {title: "Never Go Back", genre: "Action", votes: 15821, rating: 6.4, year: 2016}),
  7.                          (aldis)-[act]->(neveregoback),
  8.                          (aldis)-[act]->(compton),
  9.                          (oshea)-[act]->(compton),
  10.                          (corey)-[act]->(compton),
  11.                          (neil)-[act]->(compton)'

图的查询

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

  1. GRAPH.QUERY <graph_id> <query>

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

第一个查询是给出“Straight Outta Compton”电影中演员的年龄总和、最大年龄、最小年龄和平均年龄：

  1. GRAPH.QUERY IMDB "MATCH (a:actor)-[act]->(m:movie {title:\"Straight Outta Compton\"})
  2. RETURN m.title, SUM(a.age), MAX(a.age), MIN(a.age), AVG(a.age)"

RedisGraph将返回：

  1. 1) "m.title, SUM(a.age), MAX(a.age), MIN(a.age), AVG(a.age)"
  2. 2) "Straight Outta Compton,123.000000,37.000000,26.000000,30.750000"

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

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

  1. GRAPH.QUERY IMDB "MATCH (actor)-[act]->(movie) RETURN actor.name, COUNT(movie.title) AS movies_count ORDER BY
  2. movies_count DESC"
  4. 1) "actor.name, movies_count"
  5. 2) "Aldis Hodge,2.000000"
  6. 3) "O'Shea Jackson,1.000000"
  7. 4) "Corey Hawkins,1.000000"
  8. 5) "Neil Brown,1.000000"

RedisGraph的支撑理念

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

Hexastore对图的表示

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

  1. 主语（Subject）；
  2. 谓词（Predicate）；
  3. 目标（Object）。

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

  1. (Aldis_Hodge)-[act]->(Straight_Outta_Compton)

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

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

  1. SPO:Aldis_Hodge:act:Straight_Outta_Compton
  2. SOP:Aldis_Hodge:Straight_Outta_Compton:act
  3. POS:act:Straight_Outta_Compton:Aldis_Hodge
  4. PSO:act:Aldis_Hodge:Straight_Outta_Compton
  5. OPS:Straight_Outta_Compton:act:Aldis_Hodge
  6. 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共同参演过影片的演员：

  1. MATCH (aldis::actor {name:"Aldis Hodge"})-[act]->(m:movie)<-[act]-(a:actor) WHERE a.age > 30 RETURN m.title, a.name

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

查询解析器

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

  1. MATCH
  2. CREATE
  3. DELETE
  4. WHERE
  5. RETURN
  6. 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。

查看英文原文： RedisGraph: A High Performance In-Memory Graph Database as a Redis Module

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注