The architecture of RedisGraph

本文关注RedisGraph的整体架构，分别从图存储模型、索引、并发控制、和执行计划四个方面简要阐述。下图为RedisGraph的整体架构图。

1 图存储模型

了解一个图数据库的架构，最重要的就是其图存储模型，即其中的图数据是怎么组织和存储的。

首先，在一个图数据库中，必不可少的数据是：节点的属性（node attribute）以及节点之间的关系（edge）。比如说，图数据库中有两个节点node1{name: 小明}、node1{name: 小红}，两者存在朋友关系，那么，就需要存储node1和node2的name属性，以及node1和node2之间的朋友关系。除此之外，RedisGraph还支持存储节点之间的关系的属性（edge attribute），比如，存储node1和node2朋友关系的建立时间。

在RedisGraph中，node attribute和edge attribute存储在Block数组中，而节点之间的关系使用邻接矩阵进行存储。值得注意的是，node的数量与邻接矩阵的维数是一致的。每一个节点都有一个node_id（≥ 0），节点属性存储在Block数组node_id偏移地址（nodes[node_id]）处，节点的下一跳信息存储在邻接矩阵（adjacency）的第node_id行。显而易见，这样做的目的是，快速索引节点属性和下一跳信息。

对于节点间关系的存储，RedisGraph不仅仅使用了邻接矩阵。为了方便快速查询，还是用了label矩阵（labels）和relation矩阵（relations）。为了适应类型化节点，每个标签分配一个额外的矩阵，即label矩阵。每个类型的关系都有自己的专用矩阵，即relation矩阵。

2 索引

RedisGraph中并没有索引的代码实现，其使用RediSearch搜索引擎来构造索引，并且，RedisGraph仅仅支持哈希索引。RedisGraph中的索引分为两种：exact match index和full-text index。本文只关注exact match index。

  • 为什么要建立索引？

    我们来看一个cypher查询：

    GRAPH.QUERY DEMO_GRAPH "MATCH (n:作品)-[]-(m:角色) where m.name='郭靖' return n.name"

    这个查询仅仅涉及name=‘郭靖’，如果没有在角色: name上建立索引，RedisGraph只能是扫描一遍Block数组，进行字符串匹配，来找出name=’郭靖’的节点。显然，这效率低下。

  • 索引的key和value是什么？

    以一个在节点属性上建立索引的cypher为例进行分析：

    GRAPH.QUERY DEMO_GRAPH "CREATE INDEX ON :角色(name)"

    RedisGraph在执行这个请求后，就会在角色的name属性上建立索引。

    索引的key是name属性；value是node_id。通过node_id，就可以在Block数组中查询节点属性，在矩阵中查询下一跳信息。

    同样，如果在关系的属性上建立索引，那么，索引的key是属性；value是edge_id。

3 并发控制

RedisGraph内创建有两个线程池，分别是读线程池(_readers_thpool)和写线程池(_writers_thpool)，分别用于处理读写请求。当接收到query时，redisgraph会为其分配读写线程，若线程池满，则放入等待队列中。

RedisGraph内创建有两个线程池，分别是读线程池和写线程池，分别用于处理读写请求。当接收到query时，RedisGraph会为其分配读写线程，若线程池满，则放入等待队列中。需要注意的是，写线程池中的线程数为1，即，RedisGraph中不会出现write-write冲突。

在并发控制过程中，Redisgraph的封锁粒度为Graph。

4 执行计划

RedisGraph使用Cypher查询语言，并为其构建了解析器。与一般的关系数据库类似，RedisGraph也需要进行词法分析、语法分析、语义分析等流程，从而生成执行计划。

RedisGraph会将查询操作转换为相应的矩阵操作，获取查询结果。当一个搜索模式 (N0)-[A]->(N1)-[B]->(N2)<-[A]-(N3) 被用作查询的一部分时，RedisGraph将其转换为一组矩阵乘法。对于给定的示例，一种可能的表达式是：A * B * Transpose(A)。