#####好好好#######图解JanusGraph内部数据存储结构

前面的几篇文章中已经介绍了不少图数据库的基础知识&＃xff1a;

从扩线查询能力分析图数据库Titan的设计改进点

一起学图数据库系列&＃xff1a;图数据库概述

一起学图数据库系列&＃xff1a;图数据库与传统数据库的对比分析

开源图数据库Titan项目已经停止更新&＃xff0c;JanusGraph可以说复活了Titan项目&＃xff0c;到目前为止&＃xff0c;JanusGraph与Titan在核心机制上相差不大。JanusGraph/Titan有如下关键设计&＃xff1a;

1. 支持大规模图数据存储&＃xff0c;Titan图数据库是建立在分布式集群上&＃xff0c;数据存储容量和集群节点数量成正比

2. 支持弹性和线性扩展&＃xff0c;高可用&＃xff0c;高容错

3. 支持Gremlin图查询语言

4. 支持利用Hadoop计算框架对图数据进行分析

5. 支持外部索引&＃xff1a;ElasticSearch、Solr、Lucene

6. 支持多储存引擎&＃xff1a;Cassandra、HBase、Berkeley DB和InMemory模式;

7. 基于Apache License 2.0

本文内容以HBase作为Storage Backend&＃xff0c;详细介绍JanusGraph的内部数据存储结构。

JanusGraph基本概念

在介绍关系数据的数据存储结构之前&＃xff0c;我们先来看一下JanusGraph的基本概念。

同大多数图数据库一样&＃xff0c;JanusGraph采用属性图进行建模。基于属性图的模型&＃xff0c;JanusGraph有如下基本概念&＃xff1a;

Vertex Label&＃xff1a;节点的类型&＃xff0c;用于表示现实世界中的实体类型&＃xff0c;比如"人”&＃xff0c;“车”。在JanusGraph中&＃xff0c;每一个节点有且只有一个Vertex Label。当不显式指定Vertex Label时&＃xff0c;采用默认的Vertex Label。

Vertex&＃xff1a;节点/顶点&＃xff0c;用于表示现实世界中的实体对象。

Edge Label&＃xff1a;边的类型&＃xff0c;用于表示现实世界中的关系类型&＃xff0c;比如“通话关系”&＃xff0c;“转账关系”&＃xff0c;“微博关注关系”等&＃xff1b;

Edge: 边&＃xff0c;用于表示一个个具体的联系。JanusGraph的边都是单向边。如果需要双向边&＃xff0c;则通过两条相反方向的单向边组成。JanusGraph不存在无向边。

Property Key&＃xff1a;属性的类型&＃xff0c;比如“姓名”&＃xff0c;“年龄”&＃xff0c;“时间”等。Property Key有Cardinality的概念。Cardinality有SINGLE、LIST和SET三种选项。这三种选项分别用于表示一个Property中&＃xff0c;对于同一个Property Key是只允许有一个值、允许多个可重复的值&＃xff0c;还是多个不可重复的值。

Property&＃xff1a;属性&＃xff0c;用于表示一个个具体的附加信息&＃xff0c;采用Key-Value结构。Key就是Property Key&＃xff0c;Value就是具体的值。

属性图举例

张三与李四是同事关系&＃xff0c;他们从2017年开始成为同事&＃xff0c;用属性图表达&＃xff1a;

图切割

作为一种分布式图数据库&＃xff0c;JanusGraph需要将数据切分存储到多台机器上。

典型的图切割方法有两种: 一种是按点切割&＃xff0c;另一种是按边切割。

按点切割(Vertex-Cut)

按Vertex切割时&＃xff0c;切割线通过图的Vertex&＃xff0c;而不是Edge。每一条Edge边只保存一次&＃xff0c;并且每一条Edge只出现在一台机器上&＃xff0c;邻居多的Vertex会被分发到不同的机器上。

按边切割(Edge-Cut)

按Edge切割时&＃xff0c;切割线只穿过连接vertex的edge&＃xff0c;此时&＃xff0c;每一个vertex只保存一次。切断的Edge会保存到多台机器上。

JanusGraph采用的分片方式是按Edge切割&＃xff0c;而且是对于每一条边&＃xff0c;都会被切断。切断后&＃xff0c;该边会在起始Vertex上和目的Vertex上各存储一次。通过这种方式&＃xff0c;JanusGraph不管是通过起始Vertex&＃xff0c;还是从目的Vertex&＃xff0c;都能快速找到对端Vertex。

备注

1. 对于Super Node的存储模式不同&＃xff0c;这里暂不展开讨论。

2. JanusGraph允许将Edge Label定义为单向感知的edge. 对于单向感知的edge&＃xff0c;只会从起始vertex查询此edge&＃xff0c;不会从目的vertex反向查询。因此&＃xff0c;这种情况下&＃xff0c;目的节点不存储该vertex&＃xff0c;仅在起始节点存储。

存储方式

还是以上面的例子为例&＃xff0c;按边切割后&＃xff0c;变成如下结果&＃xff1a;

在JanusGraph中&＃xff0c;是点为中心&＃xff0c;按切边的方式存储数据的。节点的ID作为HBase的Rowkey&＃xff0c;节点上的每一个属性和每一条边&＃xff0c;作为该Rowkey的一个个独立的Cell。即每一个属性、每一条边&＃xff0c;都是一个个独立的KCV结构(Key-Column-Value)。

如下图所示&＃xff1a;

备注

简化起见&＃xff0c;此处暂不考虑节点中如何记录其所属的Vertex Label。

详细存储格式

Vertex存储格式

1. Vertex ID以Rowkey的形式存储在HBase中&＃xff0c;Vertex ID共包含64个bit。

2. Vertex ID由partition id、count、ID padding三部分组成。

3. 最高位5个bit是partition id. partition是JanusGraph抽象出的一个概念。当Storage Backend是HBase时&＃xff0c;JanusGraph会根据partition数量&＃xff0c;自动计算并配置各个HBase Region的split key&＃xff0c;从而将各个partition均匀映射到HBase的多个Region中。然后通过均匀分配partition id最终实现数据均匀打散到Storage Backend的多台机器中。

4. 中间的count部分是流水号&＃xff0c;其中最高位比特固定为0.

5. 最后几个bit是ID padding, 表示Vertex的类型。具体的位数长度根据不同的Vertex类型而不同。最常用的普通Vertex&＃xff0c;其值为&＃39;000&＃39;。

各个Vertex类型后缀划分如下&＃xff08;拷贝自源码&＃xff09;&＃xff1a;

Property存储格式

一个Property Key所关联的属性值有可能有一个&＃xff0c;也有可能有多个&＃xff0c;因此&＃xff0c;JanusGraph使用Cardinality来描述Property Key的这种特点。Cardinality有SINGLE,LIST和SET三种类型&＃xff1a;

• SINGLE表示一个Property Key只对应一个Value&＃xff0c;这是最常用的场景。

• LIST表示一个Property Key可以对应多个Value&＃xff0c;多个Value可以有重复值。

• SET表示一个Property Key可以对应多个Value&＃xff0c;多个Value不可以有重复值。

JanusGraph的Property&＃xff0c;在不同的Cardinality下&＃xff0c;数据存储结构略有不同。整体原则是&＃xff1a;根据Cardinality的不同&＃xff0c;列名本身能够确定唯一的一个属性。

Cardinality为SINGLE时的存储结构

HBase的列名只存储Property Key的ID及方向。具体的Property Value值以及Property ID(JanusGraph为每一个Property分配的唯一ID)&＃xff0c;都存放在Cell的Value中。另外&＃xff0c;如果该Property还有额外的Remaining properties&＃xff0c;也会放在Value中。Remaining properties一般不使用&＃xff0c;仅在一些特殊场景下&＃xff0c;用于为该Property记录更多的附加信息(比如存储元数据Edge Labe的定义等)。

PropertyKeyID及方向整个结构的详细结构在后文中描述&＃xff1b;属性的值占用一个或多个字段&＃xff0c;具体格式在后文描述;属性的ID及Remaining属性采用相同的格式&＃xff0c;具体格式在后文描述。

Candinality为LIST时的存储结构

各个部分与Cardinality为SINGLE时的结构相似&＃xff0c;区别在于属性的ID被放在了列名中&＃xff0c;而不是放在Value中。

Candinality为SET存储结构

各个部分与Cardinality为SINGLE时的结构相似&＃xff0c;区别在于属性的值被放在了列名中&＃xff0c;而不是放在Value中。

属性的Property Key ID和方向存储结构

每一个Property Key本身也有一个唯一的ID。为标识各个属性是属于哪一种Property Key&＃xff0c;JanusGraph记录了各个属性对应的Property Key的ID。JanusGraph在存储时&＃xff0c;会将Property Key ID以及DirectionID(分系统类型/隐藏/常规不隐藏三种属性)组装在一起&＃xff0c;使用多个字节来表示。

属性的ID和属性值存储结构

属性的值根据Property Key中定义的数据类型不同&＃xff0c;有不同的序列化器。比如&＃xff0c;String有StringSerializer, integer有IntegerSerializer. 其中IntegerSerializer与属性ID的格式化方式相同。

属性的ID作为一种无符号整数&＃xff0c;JanusGraph将其格式化为多个字节。每一个字节的最高位比特用于表示是最后一个字节。0表示不是最后一个字节&＃xff0c;1表示是最后一个字节。

边存储格式

JanusGraph的Edge Label也有一个MULTIPLICITY概念。MULTIPLICITY有MULTI等不同的取值&＃xff0c;其中以MULTI取值最为常用。

MULTIPLICITY为MULTI时的存储结构

边的存储格式与属性类似&＃xff0c;Property Key和Edge Label被抽象成了Relation Type&＃xff0c;并采用相同的数据结构。SortKey是一种特殊的属性&＃xff0c;JanusGraph允许在定义Edge Label时指定其中的一个或多个属性为Sort Key。对于边的Sort Key属性&＃xff0c;JanusGraph在存储时会将其存储在Relation Type ID的后面,其他所有字段的前面。通过这种方式&＃xff0c;可以保证一个节点的多条同一个类型的边&＃xff0c;会按Sort Key属性排序存储。这对于一个节点有大量边时&＃xff0c;对查询性能提升有帮助。

MULTIPLICITY非MULTI且此方向存在多条边时的存储结构

MULTIPLICITY非MULTI且此方向仅有一条边时的存储结构