图形数据库是 NoSQL 数据库的一种类型,它应用图形理论存储实体之间的关系信息。最常见的例子,就是社会网络中人与人之间的关系。关系型数据库用于存储关系型数据的效果并不好,其查询复杂、缓慢、超出预期,而图形数据库的独特设计恰恰弥补了这个缺陷。Google的图形计算系统名为 Pregel。
目前主流的图数据库有:Neo4j,FlockDB,GraphDB,InfiniteGraph,Titan,JanusGraph,Pregel等。
下面介绍几个图数据库中的几个基本概念:
图数据的发展趋势是什么?知乎上有一个回答我个人比较赞同(链接)。
图的本质难题是什么?是数据的高度关联带来的严重的随机访问。所以,传统的关系型数据库解决不了这个问题,因为他们仍然是面向磁盘优化,尽可能利用磁盘顺序读写的优势。neo4j这种数据结构在数据落到磁盘上的时候,随机访问比关系型数据库多更多,性能衰减想当厉害。那么分布式nosql的路子呢?网络是瓶颈。完美的最小割图分区算法是NP难题,而且在数据写入的情况下还要面临动态调整的难题。如果使用naive的分区算法,网络通讯的开销是想当大的。
所以,个人浅见,只有靠新硬件来解决问题。更廉价的大内存、NVRAM、RDMA高速网络、随机读写更强的SSD磁盘、有硬件事务支持的CPU等。
下面是常见的几种图查询语言:
例1:查询所有城市类型为「Capital」的城市列表/URL
Cypher:
match(n:Capital)
return n;
SPARQL:
PREFIX rdf:< http://www.w3.org/2018/11/22-rdf-syntax-ns#>
SELECT * WHERE {
?city rdf:type < http://abc.org/Capital >
}
Gremlin:
g.V().hasLabel("Capital").values()
TinkerPop 是一个图计算框架,用来进行实时的事务型处理,和批量的图分析,包含了一系列以 Gremlin 引擎为核心的子项目和模块。下面是 TinkerPop 框架下属性图的一个例子:
Gremlin 是 ThinkPop3 框架下的图查询语言,支持非常多的开发语言,例如 Python、JavaScript、Groovy、Scala、Go。Gremlin是一种函数式数据流语言,可以使得用户使用简洁的方式表述复杂的属性图(property graph)的遍历或查询。每个Gremlin遍历由一系列步骤(可能存在嵌套)组成,每一步都在数据流(data stream)上执行一个原子操作。目前我们主要用的Gremlin 语言是是 Groovy,语句类似这样:
// 查询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
查询,涉及到的模块有:
PathProcessorStrategy.java
);;GremlinGroovyScriptEngine.java
);GremlinServer.java
);Gremlin还有其他的一些模块,如 gremlin-console
、gremlin-jsr223
等,需要的可以研究一下。框架型代码和工程代码(如 mybatis、nginx 等)的风格还是不一样的,一些好的设计模式值得好好研究。
值得一提的是,Gremlin 的模块中,有非常多的 SPI
实现:
下面是 gremlin-server
启动过程的部分代码,可以看到,gremlin-server
是一个典型的 netty 服务,通过通过的 ChannelHandler
,支持了不同的协议(HTTP、WebSocket)。
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;
}
Tinkerpop 下有较多的属性图实现:IBM Graph、Titan、JanusGraph、HugeGraph,均支持多后端存储,多模式也是目前图数据库发展的的一个大方向。多模式无疑可以满足更多的用户,降低了数据迁移和维护的成本。但从另一方面来看,多个后端存储也带来了一些弊端:
下面主要以 JanusGraph + Hbase 这套组合为例,介绍其存储过程(不同的存储后端存储格式不一样)。
JanusGraph 采用的分片方式(也有按照点切割的图数据库)是按Edge切割,而且是对于每一条边,都会被切断。切断后,该边会在起始 Vertex 上和目的 Vertex 上各存储一次(多浪费了空间)。通过这种方式,JanusGraph 不管是通过起始 Vertex,还是从目的 Vertex,都能快速找到对端 Vertex。
从上图我们可以得到如下的结论:
注意,Vertex/Edge/Property 在创建时,都会分配一个 ID,主要的逻辑在 Janusgraph-core 包中的 org.janusgraph.graphdb.idmanagement.IDManger
类中,下面是给顶点增加 ID 的过程。
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/。
以下面的查询语句为例,具体的查询过程如下所示:
g.v("vid").out.out.has(name, "jack")
v("vid")
:把 id 为 “vid” 的节点找出来,返回该节点,这里可能会用到索引;out
:从上一步结果集合中,拉出一个,即 “vid” 的 id,并把该点对应的那行数据从hbase里读取出来(即该点的属性、相邻点、相邻边),返回出度节点,返回结果 edgeList1
;out
:从上一步结果 edgeList1
中,拉出一个,即把第一个出度点拉出来,并把该点对应的那行数据从 hbase 里读取出来(即该点的属性、相邻点、相邻边),找出出度节点,返回结果 edgeList2
;has
:把 edgeList2
中的第一个节点拉出来,把该点对应的属性字段从 hbase 里读取出来,并进行 name
为 jack
的过滤,返回结果;edgeList2
遍历完毕;edgeList1
遍历完毕;JanusGraph 支持两种类型的索引:graph index 和 vertex-centric index。graph index 常用于根据属性查询 Vertex 或 Edge 的场景;vertex index 在图遍历场景非常高效,尤其是当 Vertex 有很多 Edge 的情况下。
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:
// 顶点中含有name属性且值为jack的所有顶点
g.V().has('name', 'jack')
Mixed Index:
// 顶点中含有age属性且小于50的所有顶点
g.V().has('age', lt(50))
Vertex-centric index(顶点中心索引)是为每个 vertex 建立的本地索引结构,在大型 graph 中,每个 vertex 有数千条Edge,在这些 vertex 中遍历效率将会非常低(需要在内存中过滤符合要求的 Edge)。Vertex-centric index 可以通过使用本地索引结构加速遍历效率。
举例:
下面的查询中,如果对 'battled'
类型的边属性 'rating'
建立了属性,则是可以利用上索引的。
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,因此即使有数千个边也能高效查询。
由上面的存储和查询也可以看到,基于 Hbase的属性图有下面几个明显的缺陷:
一言以蔽之,目前基于 NoSQL的图数据库,都可以视为只是在分布式 NoSQL 上封装了一层逻辑的图,存储和查询严重分离,性能提升的空间是十分巨大的。
关于 Gremlin的语法和例子,请参考我之前写的 Gremlin 图查询概述 这一篇文章。