Gremlin 图查询概述

图数据库基本概念

图形数据库是 NoSQL 数据库的一种类型，它应用图形理论存储实体之间的关系信息。最常见的例子，就是社会网络中人与人之间的关系。关系型数据库用于存储关系型数据的效果并不好，其查询复杂、缓慢、超出预期，而图形数据库的独特设计恰恰弥补了这个缺陷。Google的图形计算系统名为 Pregel。

目前主流的图数据库有：Neo4j，FlockDB，GraphDB，InfiniteGraph，Titan，JanusGraph，Pregel等。

下面介绍几个图数据库中的几个基本概念：

• RDF：RDF(Resource Description Framework)，即资源描述框架，其本质是一个数据模型（Data Model）。它提供了一个统一的标准，用于描述实体/资源。简单来说，就是表示事物的一种方法和手段。RDF 形式上表示为 SPO 三元组，有时候也称为一条语句（statement），知识图谱中我们也称其为一条知识。RDF 由节点和边组成，节点表示实体/资源、属性，边则表示了实体和实体之间的关系以及实体和属性的关系。RDF 没有外键和主键，它使用的是 URI，万维网的标准引用格式。通过 URI，一个三元组库可以直接链接到任何三元组库的其他任何数据。

• 属性图：属性图是由 顶点（Vertex），边（Edge），标签（Lable），关系类型 还有 属性（Property）组成的有向图。顶点也称为 节点（Node），边也称为 关系（Relationship）。在图形中，节点和关系是最重要的实体；

• TinkerPop：TinkerPop是一种开源图计算框架，是 Apache 软件基金会旗下的一个顶级项目，该项目专注于为图数据库建立行业标准，包括一种名为Gremlin的标准语言（可跨语言）；

• Titan：Titan项目创建于2012年，于2016年停止维护，是一个方便拓展的图数据库，支持HBase、Cassandra 等作为后端，ES、Lucene 等做全文索引，以TinkerPop作为图的查询和计算框架；

• JanusGraph：JanusGraph 是 Titan 1.0.0版本的延续，JanusGraph继承了 Titan 的全部功能并做了进一步的改进，并支持 Hadoop 2和 Tinkerpop 3.2.3，采用 Gremlin 图查询语言；

• Neo4j：Neo4j 使用「图」这种最通用的数据结构来对数据进行建模，使得 Neo4j 的数据模型在表达能力上非常强。链表、树和散列表等数据结构都可以抽象成用图来表示。

图数据的发展趋势是什么？知乎上有一个回答我个人比较赞同（链接）。

图的本质难题是什么？是数据的高度关联带来的严重的随机访问。所以，传统的关系型数据库解决不了这个问题，因为他们仍然是面向磁盘优化，尽可能利用磁盘顺序读写的优势。neo4j这种数据结构在数据落到磁盘上的时候，随机访问比关系型数据库多更多，性能衰减想当厉害。那么分布式nosql的路子呢？网络是瓶颈。完美的最小割图分区算法是NP难题，而且在数据写入的情况下还要面临动态调整的难题。如果使用naive的分区算法，网络通讯的开销是想当大的。

所以，个人浅见，只有靠新硬件来解决问题。更廉价的大内存、NVRAM、RDMA高速网络、随机读写更强的SSD磁盘、有硬件事务支持的CPU等。

下面是常见的几种图查询语言：

1. SPARQL：SPARQL这个名字是一个递归缩写，代表“SPARQL Protocol and RDF Query Language（SPARQL协议与RDF查询语言），它是面向RDF(Resource Description Framework)的三元组数据，W3C标准，无schema，在研究中应用非常广泛。SPARQL的查询与RDF是一致的，RDF是图，SPARQL查询是子图匹配。

2. Gremlin：数据以属性图的形式存在，可以认为是上面两种的混合体，属性仍然在表中，但是联接关系是直接以链接（比如指针）的形式存在的。查询的本质是图遍历，擅长解决求图的直径、点到点之间的路径，比如刘德华连接奥巴马需要几度关系。

3. Cypher：Cypher是 Neo4j 专门用于图数据库的查询语言，类似于Oracle数据库的SQL语言，是一种声明式查询语言，只需要用户描述需要执行什么动作（match、insert等），而不需要描述具体怎么做，需要注意的是，只有在商业版中，Cypher的查询语句编译器才会生成高性能的查询动作。

例1：查询所有城市类型为「Capital」的城市列表/URL

Cypher：

1
2

match(n:Capital)
return n;

SPARQL:

1
2
3
4

PREFIX rdf：< http://www.w3.org/2018/11/22-rdf-syntax-ns#>
SELECT * WHERE { ？city rdf：type < http://abc.org/Capital >
}

Gremlin:

1

g.V().hasLabel("Capital").values()

TinkerPop & Gremlin

TinkerPop 是一个图计算框架，用来进行实时的事务型处理，和批量的图分析，包含了一系列以 Gremlin 引擎为核心的子项目和模块。下面是 TinkerPop 框架下属性图的一个例子：

Gremlin 是 ThinkPop3 框架下的图查询语言，支持非常多的开发语言，例如 Python、JavaScript、Groovy、Scala、Go。Gremlin是一种函数式数据流语言，可以使得用户使用简洁的方式表述复杂的属性图（property graph）的遍历或查询。每个Gremlin遍历由一系列步骤（可能存在嵌套）组成，每一步都在数据流（data stream）上执行一个原子操作。目前我们主要用的Gremlin 语言是是 Groovy，语句类似这样：

1
2
3
4
5

// 查询andy到jack四跳以内的最短路径
g.V("andy").repeat(both().simplePath()).until(hasId("target_v_id").and().loops().is(lte(4))).hasId("jack").path().limit(1)

每一条 Gremlin 语句会被转换成一个脚本对象，交给具体的脚本引擎去执行，如上面的 Gremlin-Groovy 查询，涉及到的模块有：

• gremlin-core：定义了Gremlin 语句下的查询规范，由具体的图数据库实现(eg. PathProcessorStrategy.java)；；

• gremlin-groovy：基于 jsr223 实现的 groovy 脚本引擎(eg. GremlinGroovyScriptEngine.java)；

• gremlin-server：提供了 RESTFul 和 WebSocket 两种 Gremlin 查询能力(eg. GremlinServer.java)；

Gremlin还有其他的一些模块，如 gremlin-console、gremlin-jsr223等，需要的可以研究一下。框架型代码和工程代码（如 mybatis、nginx 等）的风格还是不一样的，一些好的设计模式值得好好研究。

值得一提的是，Gremlin 的模块中，有非常多的 SPI 实现：

下面是 gremlin-server 启动过程的部分代码，可以看到，gremlin-server 是一个典型的 netty 服务，通过通过的 ChannelHandler，支持了不同的协议（HTTP、WebSocket）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public synchronized CompletableFuture<ServerGremlinExecutor> start() throws Exception {if (serverStarted != null) {return serverStarted;}serverStarted = new CompletableFuture<>();final CompletableFuture<ServerGremlinExecutor> serverReadyFuture = serverStarted;try {final ServerBootstrap b = new ServerBootstrap();final Channelizer channelizer = createChannelizer(settings);channelizer.init(serverGremlinExecutor);b.group(bossGroup, workerGroup).childHandler(channelizer);if(isEpollEnabled){b.channel(EpollServerSocketChannel.class);} else{b.channel(NioServerSocketChannel.class);}b.bind(settings.host, settings.port).addListener(new ChannelFutureListener() {@Overridepublic void operationComplete(final ChannelFuture channelFuture) throws Exception {if (channelFuture.isSuccess()) {ch = channelFuture.channel();serverReadyFuture.complete(serverGremlinExecutor);} else {serverReadyFuture.completeExceptionally(new IOException(String.format("Could not bind to %s and %s - perhaps something else is bound to that address.", settings.host, settings.port)));}}});} catch (Exception ex) {logger.error("Gremlin Server Error", ex);serverReadyFuture.completeExceptionally(ex);}return serverStarted;
}

属性图底层存储（Hbase）

属性图存储概述

Tinkerpop 下有较多的属性图实现：IBM Graph、Titan、JanusGraph、HugeGraph，均支持多后端存储，多模式也是目前图数据库发展的的一个大方向。多模式无疑可以满足更多的用户，降低了数据迁移和维护的成本。但从另一方面来看，多个后端存储也带来了一些弊端：

• 我们就需要在软件架构进行抽象，增加一个可以适配多个存储的数据格式（StaticBuffer），数据无论是写入还是读取，都需要先转化成中间格式，这里带来了序列化和反序列化的一些性能损耗；

• 抽象后的架构，对外是统一的，不利于我们发挥后端的存储查询优势（如 Hbase 的 Coprocessor，是可以加速查询的），为了使用这种能力，我们需要破坏这种统一的架构去适配后端存储。

下面主要以 JanusGraph + Hbase 这套组合为例，介绍其存储过程（不同的存储后端存储格式不一样）。

JanusGraph 采用的分片方式（也有按照点切割的图数据库）是按Edge切割，而且是对于每一条边，都会被切断。切断后，该边会在起始 Vertex 上和目的 Vertex 上各存储一次（多浪费了空间）。通过这种方式，JanusGraph 不管是通过起始 Vertex，还是从目的 Vertex，都能快速找到对端 Vertex。

从上图我们可以得到如下的结论：

1. Hbase 每一行存储一个顶点，RowKey 为 Vertex Id；

2. 一个 Vertex 的 Properties 信息，以及与该 Vertex 相关的 Edges，都以独立的列存储，而且被存成了一行数据；

3. 表示 Edge 的列中，包含了 Label 信息，Edge ID，相邻 Vertex 信息，属性等信息；

4. 表示 Vertex Property 的列中，包含了 Property 的 ID，以及 Property 的值；

注意，Vertex/Edge/Property 在创建时，都会分配一个 ID，主要的逻辑在 Janusgraph-core 包中的 org.janusgraph.graphdb.idmanagement.IDManger 类中，下面是给顶点增加 ID 的过程。

1
2
3
4
5
6
7
8
9
10

public long getVertexID(long count, long partition, VertexIDType vertexType) {Preconditions.checkArgument(VertexIDType.UserVertex.is(vertexType.suffix()),"Not a user vertex type: %s",vertexType);Preconditions.checkArgument(count>0 && count<vertexCountBound,"Invalid count for bound: %s", vertexCountBound);if (vertexType==VertexIDType.PartitionedVertex) {Preconditions.checkArgument(partition==PARTITIONED_VERTEX_PARTITION);return getCanonicalVertexIdFromCount(count);} else {return constructId(count, partition, vertexType);}
}

这一篇文章结合 JanusGraph 的源码，对存储的细节分析的更为透彻，感兴趣的同学可以看一下：http://www.nosqlnotes.com/technotes/graphdb/janusgraph-dataformat/。

JanusGraph 查询示例

以下面的查询语句为例，具体的查询过程如下所示：

1

g.v("vid").out.out.has(name, "jack")

1. v("vid")：把 id 为 “vid” 的节点找出来，返回该节点，这里可能会用到索引；

2. out ：从上一步结果集合中，拉出一个，即 “vid” 的 id，并把该点对应的那行数据从hbase里读取出来（即该点的属性、相邻点、相邻边），返回出度节点，返回结果 edgeList1；

3. out ：从上一步结果 edgeList1 中，拉出一个，即把第一个出度点拉出来，并把该点对应的那行数据从 hbase 里读取出来（即该点的属性、相邻点、相邻边），找出出度节点，返回结果 edgeList2；

4. has：把 edgeList2 中的第一个节点拉出来，把该点对应的属性字段从 hbase 里读取出来，并进行 name 为 jack 的过滤，返回结果；

5. 迭代执行第4步，直至 edgeList2 遍历完毕；

6. 返回第3步，直至 edgeList1 遍历完毕；

7. 返回结果。

JanusGraph 索引

JanusGraph 支持两种类型的索引：graph index 和 vertex-centric index。graph index 常用于根据属性查询 Vertex 或 Edge 的场景；vertex index 在图遍历场景非常高效，尤其是当 Vertex 有很多 Edge 的情况下。

Graph Index

Composite index：Composite index通过一个或多个固定的key（schema）组合来获取 Vertex Key 或 Edge，也即查询条件是在Index中固定的，Composite index 只支持精确匹配，不支持范围查询。Composite index 依赖存储后端，不需要索引后端。

Mixed Index：支持通过其中的任意 key 的组合查询 Vertex 或者 Edge，使用上更加灵活，而且支持范围查询等，但 Mixed index 效率要比 Composite Index 低。与 Composite key 不同，Mixed Index 需要配置索引后端，JanusGraph 可以在一次安装中支持多个索引后端。

举例：

Composite Index:

1
2

// 顶点中含有name属性且值为jack的所有顶点
g.V().has('name', 'jack')

Mixed Index:

1
2

// 顶点中含有age属性且小于50的所有顶点
g.V().has('age', lt(50))

Vertex-Centric Index

Vertex-centric index（顶点中心索引）是为每个 vertex 建立的本地索引结构，在大型 graph 中，每个 vertex 有数千条Edge，在这些 vertex 中遍历效率将会非常低（需要在内存中过滤符合要求的 Edge）。Vertex-centric index 可以通过使用本地索引结构加速遍历效率。

举例：

下面的查询中，如果对 'battled' 类型的边属性 'rating' 建立了属性，则是可以利用上索引的。

1
2

h = g.V().has('name','hercules').next()
g.V(h).outE('battled').has('rating', gt(3.0)).inV()

注意：JanusGraph 自动为每个 edge label 的每个 property key 建立了 vertex-centric label，因此即使有数千个边也能高效查询。

JanusGraph 的缺陷

由上面的存储和查询也可以看到，基于 Hbase的属性图有下面几个明显的缺陷：

1. 顶点属性和边存储在一行中，当点的出入度越大时，属性查询耗时将会越大；

2. 更新边某一个属性时，需要先获取整个边的数据，修改完成后再写回，效率较低；

3. 对边的属性过滤，将数据取回客户端，在客户端进行过滤，增加了网络传输的消耗；

一言以蔽之，目前基于 NoSQL的图数据库，都可以视为只是在分布式 NoSQL 上封装了一层逻辑的图，存储和查询严重分离，性能提升的空间是十分巨大的。

Gremlin 查询示例

关于 Gremlin的语法和例子，请参考我之前写的 Gremlin 图查询概述 这一篇文章。

参考资料

1. https://github.com/tinkerpop/gremlin

2. 通过使用JanusGraph索引提高性能

3. PRACTICAL GREMLIN: An Apache TinkerPop Tutorial

4. 图解JanusGraph内部数据存储结构