RedisGraph的整体架构

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)。