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-consolegremlin-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() {
@Override
public 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 里读取出来,并进行 namejack 的过滤,返回结果;
  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内部数据存储结构
---(完)---
Yves wechat
扫一扫互相关注吧~
  • 本文作者: Yves
  • 本文标题: Gremlin 图查询概述
  • 发布时间: 2018年11月22日 - 17:11
  • 更新时间: 2020年07月22日 - 00:07
  • 本文链接: /2018/11/22/gremlin_traversal_process/
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!

扫一扫关注公众号